2. Приклади і/Або-подання задач

2.1. І/Або-подання задачі пошуку маршруту

Для задачі пошуку найкоротшого маршруту І/Або-Граф разом з функцією вартості можна визначити в такий спосіб:

• Або-вузли мають форму X-Z, що означає пошук найкоротшого шляху з X в Z.

• І-вузли мають форму

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.