Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

ЗАГАЛЬНИЙ ПІДХІД ДО ВИРІШЕННЯ ЗАВДАННЯ

Завданню надається повний однозначний і безизбиточний вид в формі формалізованої постановки задачі. Оцінюється труднощі рішення задачі, виходячи з «обсягу» простору пошуку та складності обмежень.

6. Часткове (повернення до етапу 2) або спільне рішення задачі

Здійснюється пошук рішення задачі і, якщо необхідно, постановка завдання уточнюється або виконується заново (з етапу 2), щоб звузити простір пошуку.

7. Перевірка і узагальнення рішення.

Обговорюється рішення задачі, оцінюється адекватність знайденого рішення вихідним умовам завдання. З'ясовується істотність тих чи інших умов завдання. Визначається поведінка рішення в особливих точках. Оцінюється спільність використаного методу рішення.

СТРАТЕГІЇ ТА ПРОЦЕДУРИ ВИРІШЕННЯ ЗАВДАННЯ

Під стратегією вирішення завдання будемо мати на увазі загальне правило (метапроцедур) вирішення широкого кола завдань. При безпосередньому виконанні завдання будь-яка стратегія вирішення реалізується в формі виконання окремих кроків (етапів) рішення. По суті, стратегія рішення - це деяка метапроцедура, керуюча послідовністю виконання окремих процедур. Під процедурою вирішення завдання розуміється кожен окремий етап рішення, а точніше, сукупність дій, виконуваних на цьому етапі.

Якщо є деякий набір процедур вирішення конкретного завдання { , Л, ..., Р ", то власне рішення задачі являє собою виконання послідовності процедур Р, { , Р, 2 , ..., Р, до , де Р, { , Я ,,, .... Р, до е {/> ,, Л, Р ,,}. А які саме процедури і в якій послідовності вони повинні виконуватися, визначається вибраною стратегією рішення задачі.

Перерахуємо деякі стратегії вирішення завдань. Ряд стратегій вирішення завдань, спрямованих на побудову вирішального шляху на графі, ґрунтуються на так званій оціночної функції. Оціночна функція визначається на вершинах графа і, як правило, приймає в якості своїх значень речові числа. Для довільної вершини значення оціночної функції вказує на ступінь перевагу продовження пошуку вирішального шляху з цієї вершини. Чим краще вершина, тим більш перспективною є вона для застосування до неї пошукових процедур. Стратегія вирішення завдання, яку направляють оціночної функцією, є різновидом евристичного пошуку.

Іншим різновидом стратегії вирішення, яке б оціночної функцією, є пошук в глибину і пошук в ширину. При пошуку в глибину значення оціночної функції будь-якої вершини прямо пропорційно «відстані» від цієї вершини до початкової вершини. При пошуку в ширину ця залежність обернено пропорційна. В обох випадках відстань між вершинами можна вимірювати кількістю ребер графа в найкоротшому шляху, що пов'язують ці вершини.

Зауважимо, що оцінна функція не обов'язково повинна бути числовою функцією. Можна між вершинами встановити деякий якісне впорядкування. В іншому принципи роботи з якісною оціночної функцією ті ж, що і з кількісної.

Перерахуємо інші стратегії вирішення завдань. Для пошуку на графі, що відповідає простору станів (при першому способі формалізації), використовуються: метод гілок і меж, алгоритм найкоротших шляхів Мура, алгоритм Дейкстри, алгоритм Дорана і Мічі пошуку з низькою вартістю, алгоритм Харта, Нільсона і Рафаеля. Для пошуку на І- АБО дереві, відповідному простору подзадач (при другому способі формалізації), використовуються: алгоритм Ченга і Слейгла, метод ключових операторів, метод планування загального решателя завдань (G PS), дедуктивні методи на основі принципу резолюції, методи продукцій.

 
<<   ЗМІСТ   >>