X-Z через Y

що означає: пошук найкоротшого шляху з X в Z, проходячи через Y.

· Вузол X-Z є цільовим вузлом (примітивною задачею), якщо на карті існує безпосередній зв'язок між X і Z.

· Вартість кожного цільового вузла X-Z дорівнює відстані по дорозі, що з'єднує X з Z.

· Вартість усіх інших (нетермінальних) вузлів рівна 0.

Вартість вирішуючого графа дорівнює сумі вартостей усіх його вузлів (у даному випадку це просто сума вартостей усіх термінальних вузлів). Для задачі рис. 1 стартова вершина - це а-z. На наступному малюнку показаний вирішуючий граф, що має вартість 9. Це дерево відповідає шляху [a,b,d,f,i,z], який можна побудувати, якщо пройти по всіх листах вирішуючого дерева зліва праворуч.

2.2. Задача про ханойську вежу - ще один класичний приклад ефективного застосування схеми декомпозиції І/Або. Розглянемо гранично спрощену версію цієї задачі – лише з трьома дисками.

Постановка задачі. Є три кілочки 1, 2 і 3 і три диски а, b і с (а - найменший, с - найбільший). Спочатку всі диски нанизані на кілочок 1, треба перенести їх на кілочок 3 такими переміщеннями по одному диску, що більший диск ніколи не розташовується на меншому.

Цю задачу можна розглядати як задачу досягнення наступних трьох цілей:

(1) Диск а - на кілочок 3.

(2) Диск b - на кілочок 3.

(3) Диск с - на кілочок 3.

Однак вони взаємозалежні – досягнення одної цілі може завадити досягненню іншої. Тому постає проблема пошуку порядка досягнення цих цілей, з якого можна було б вивести шуканий розв'язок.

У подібних ситуаціях часто спрацьовує гарна ідея: намагатися досягти першою найважчу ціль. У даному випадку: найважча ціль - це «Диск с - на кілочок 3», тому що на диск с накладене найбільше обмежень. В основі ідеї наступна логіка: оскільки інші цілі досягти легше (на них менше обмежень), можна сподіватись, що їхнє досягнення можливе без скасування дій на досягнення найважчої цілі.

Стосовно до нашої задачі це означає, що необхідно дотримуватись наступної стратегії:

Першою досягти ціль "диск с - на кілочок 3 ",
а потім - усі інші.

Але цю ціль не можна досягти відразу, бо є перепони - диск с рухати не можна. Тому стратегія набуває вид:

(1) Прибрати перепони переносу диска с з 1 на 3.

(2) Перекласти с з 1 на 3.

(3) Досягтися інші цілі (а на 3 та b на 3).

Перекласти c з 1 на 3 можна лише тоді, коли диски а та b обоє розташовані на кілочку 2. Тоді початкова задача переносу а, b і с з 1 на 3 зводиться до трьох підзадач:

Щоб перекласти а, b і с з 1 на 3, необхідно

(1) перекласти а та b з 1 на 2, і

(2) перекласти с з 1 на 3, і

(3) перекласти а та b з 2 на 3.

Задача 2 тривіальна (вирішується за один крок). Інші дві можна вирішити незалежно від задачі 2, оскільки положення диска с не заважає рухам дисків а та b. Для розв'язку задач 1 і 3 можна застосувати той же самий принцип декомпозиції (тепер найскладнішим буде перенос диску b). Згідно із цим попередня підзадача 1 зводиться до трьох тривіальних підзадач:

Щоб перекласти а та b з 1 на 2, необхідно:

(1) перекласти а з 1 на 3, і

(2) перекласти b з 1 на 2, і

(3) перекласти а з 3 на 2.

А попередня підзадача 3 зводиться до підзадач:

Щоб перекласти а та b з 2 на 3, необхідно:

(1) перекласти а з 2 на 1, і

(2) перекласти b з 2 на 3, і

(3) перекласти а з 1 на 3.

2.3. Формулювання ігрових задач у термінах І/Або-Графів.

Такі ігри, як шахи чи шашки, природно розглядати як задачі, подані І/Або-Графами. Їх називають іграми двох осіб з повною інформацією. Вважатимемо, що можливі лише два результати: виграш і програш. (Ігри з виграшем, програшем і нічиєю також можна вважати лише з двома результатами: виграшем і невиграшем). Тому що гравці ходять по черзі, маємо два види позицій залежно від того, чий хід. Назвемо гравців свій і чужий, тоді матимемо два види позицій: свого ходу і чужого ходу. Нехай початкова позиція Р - це позиція свого ходу, кожен варіант свого ходу в якій веде до деякої з позицій чужого ходу Q₁, Q₂, Q₃,... (див. малюнок). Далі кожен варіант чужого ходу в позиції Q₁ приводить до одній з своїх позицій R₁₁, R₁₂,....

В І/Або-дереві на малюнку вузли відповідають позиціям, а дуги - можливим ходам. Рівні свого ходу чергуються в дереві з рівнями чужого ходу.

Щоб виграти в початковій позиції Р, потрібно знайти хід, що переводить Р у виграшну позицію Q_i при деякому i. Тому, позиція Р є виграшною, якщо виграшною є позиція Q₁, або Q₂, або Q₃, або.... Отже, Р - це Або-вузол. Для всіх i позиція Q_i - це позиція чужого ходу, тому, якщо вона має бути виграшною для свого гравця, то необхідно домогтись, щоб її можна було виграти після довільного чужого ходу. Тому позиція Q_i є виграшною, якщо виграшними є всі з позицій R_i1, R_i2 і.... Згідно цьому, усі позиції чужого ходу є І-вузлами. Цільові вузли - це позиції, що виграні згідно правил даної гри; наприклад, у шахах - це матові позиції. Позиціям, програним згідно правил гри, відповідають задачі, що не мають рішення.

Щоб розв'язати ігрову задачу, треба побудувати вирішуюче дерево, що гарантує свою перемогу незалежно від чужих відповідей. Таке дерево задає повну стратегію перемоги в грі: для кожного чужого ходу у дереві стратегії є відповідний свій хід, що веде до перемоги.

3. Базові процедури пошуку в І/Або-Графах

Найпростіший спосіб пошуку в І/Або-Графах засобами Прологу - це використати переборний механізм, закладений у самій Пролог-системі. Виявляється, що це дуже просто зробити, тому що процедурний смисл Прологу і є не що інше, як пошук в І/Або-Графі. Наприклад, І/Або-Граф рис. 2 (без обліку вартостей дуг) можна описати наступними твердженнями:

а:- b. % а - Або-вузол із двома спадкоємцями b і с

а:- с.

b:- d, е. % b - І-вузол із двома спадкоємцями d і е

с:- h.

с:- f, g.

f:- h, i.

d. g. h. % d, g і h - цільові вершини

Щоб взнати, чи має ця задача розв'язок, потрібно просто запитати:

?- а.

Одержавши це питання, пролог-система зробить пошук у глибину в дереві рис. 2, і після того, як пройде через усі вершини підграфа, відповість "так".

Перевага такого методу програмування І/Або-пошуку полягає в його простоті. Але є й недоліки:

· Ми одержуємо лише відповідь "так" або "ні", але не одержуємо вирішуюче дерево. Можна було б відновити вирішуюче дерево за допомогою трасування програми, але це незручно і недостатньо, якщо вирішуюче дерево необхідне як об'єкт програми.

· У цю програму важко вносити доповнення для обробки вартостей.

· Якщо І/Або-Граф - це граф загального виду, що містить цикли, то пролог-система згідно до стратегії вглиб, може ввійти в нескінченний рекурсивний цикл.

П оступово виправимо ці недоліки. Спочатку визначимо власну процедуру пошуку вглиб для І/Або-Графів.

Насамперед треба змінити подання І/Або-Графів. Для цього введем бінарне відношення, зображуване інфіксним оператором '--->'. Наприклад, вершина а із двома Або-Спадкоємцями буде представлена твердженням

а ---> або: [b, с].

Обоє символи ' ---> ' та ': ' - інфіксні оператори, які визначимо як

:- ор(600, xfx, --->).

:- ор(500, xfx,:).

Увесь І/Або-Граф (рис. 2) тепер задається твердженнями

а ---> або: [b, с].

b ---> і: [d, e].

с ---> і: [f, g].

е ---> або: [h].

f ---> або: [h, i].

ціль(d). ціль(g). ціль(h).

Процедуру пошуку вглиб в І/Або-Графах можна побудувати, базуючись на наступних принципах:

Для пошуку рішення, представленого деяким вузлом В, необхідно дотримуватись наступних правил:

(1) Якщо В - цільовий вузол, то рішення є тривіальним.

(2) Якщо вузол В має Або-Спадкоємців, то знайти рішення за допомогою одного з них (пробуючи використати їх одного за другим, поки не буде знайдений той, що дасть розв'язок).

(3) Якщо вузол В має І-Спадкоємців, то потрібно розв'язати всі відповідні задачі (пробуючи вирішувати їх одну за одною, поки всі вони не будуть вирішені).

Якщо наведені правил не приводять до розв'язку, слід вважати, що задача не може бути вирішена.

Відповідна програма виглядає так:

розв'язати(Вузол):- ціль(Вузол).

розв'язати(Вузол):-

Вузол ---> або: Вузли, % Вузол - Або-Вузол

Дата добавления: 2014-01-04