Prolog

Неизвестно

Эту задачу можно рассматривать как задачу достижения следующих трех целей:

(1) Диск а– на колышек 3.

(2) Диск b– на колышек 3.

(3) Диск с– на колышек 3.

Беда в том, что эти цели не независимы. Например, можно сразу переложить диск а на колышек 3, и первая цель будет достигнута. Но тогда две другие цели станут недостижимыми (если только мы не отменим первое наше действие). К счастью, существует такой удобный порядок достижения этих целей, из которого можно легко вывести искомое решение.

Рис. 13. 6.

Задача о ханойской башне

Порядок этот можно установить при помощи следующего рассуждения: самая трудная цель - это цель 3 (диск с– на колышек 3), потому что на диск с наложено больше всего ограничений. В подобных ситуациях часто срабатывает хорошая идея: пытаться достичь первой самую трудную цель. Этот принцип основан на следующей логике: поскольку другие цели достигнуть легче (на них меньше ограничений), можно надеяться на то, что их достижение возможно без отмены действий на достижение самой трудной цели.

Применительно к нашей задаче это означает, что необходимо придерживаться следующей стратегии:

Первой достигнуть цель "диск с– на колышек 3",

а затем - все остальные.

Но первая цель не может быть достигнута сразу, так как в начальной ситуации диск с двигать нельзя. Следовательно, сначала мы должны подготовить этот ход, и наша стратегия принимает такой вид

(1) Обеспечить возможность перемещения диска с с 1 на 3.

(2) Переложить с с 1 на 3.

(3) Достигнуть остальные цели (а на 3 и b на 3).

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

Для того, чтобы переложить a, b и с с 1 на 3, необходимо

(1) переложить а и b с 1 на 2, и

(2) переложить с с 1 на 3, и

(1) переложить а и b с 2 на 3.

Задача 2 тривиальна (она решается за один шаг). Остальные две подзадачи можно решать независимо от задачи 2, так как диски а и b можно двигать, не обращая внимание на положение диска с. Для решения задач 1 и 3 можно применить тот же самый принцип разбиения (на этот раз диск b будет самым "трудным"). В соответствии с этим принципом задача 1 сводится к трем тривиальным подзадачам:

Для того, чтобы переложить а и b с 1 на 2, необходимо:

(1) переложить а с 1 на 3, и

(2) переложить b с 1 на 2, и

(1) переложить а с 3 на 2.

13. 2. 3. Формулировка игровых задач в терминах И / ИЛИ-графов

Такие игры, как шахматы или шашки, естественно рассматривать как задачи, представленные И / ИЛИ-графами. Игры такого рода называются играми двух лиц с полной информацией. Будем считать, что существует только два возможных исхода игры: ВЫИГРЫШ и ПРОИГРЫШ. (Об играх с тремя возможными исходами -ВЫИГРЫШ, ПРОИГРЫШ и НИЧЬЯ, можно также говорить, что они имеют только два исхода: ВЫИГРЫШ и НЕВЫИГРЫШ). Так как участники игры ходят по очереди, мы имеем два вида позиций, в зависимости от того, чей ход. Давайте условимся называть участников игры "игрок" и "противник", тогда мы будем иметь следующие два вида позиций: позиция с ходом игрока ("позиция игрока") и позиция с ходом противника ("позиция противника"). Допустим также, что начальная позиция Р– это позиция игрока. Каждый вариант хода игрока в этой позиции приводит к одной из позиций противника Q₁, Q₂, Q₃, ... (см.

рис. 13.7). Далее каждый вариант хода противника в позиции Q₁ приводит к одной из позиций игрока R₁₁, R₁₂, ... . В И / ИЛИ-дереве, показанном на рис. 13.7, вершины соответствуют позициям, а дуги - возможным ходам. Уровни позиций игрока чередуются в дереве с уровнями позиций противника. Для того, чтобы выиграть в позиции Р, нужно найти ход, переводящий Р в выигранную позицию Q_i. (при некотором i). Таким образом, игрок выигрывает в позиции Р, если он выигрывает в Q₁, или Q₂, или Q₃, или ... . Следовательно, Р– это ИЛИ-вершина. Для любого i позиция Q_i– это позиция противника, поэтому если в этой позиции выигрывает игрок, то он выигрывает и после каждого вариан-

Рис. 13. 7. Формулировка игровой задачи для игры двух лиц в

форме И / ИЛИ-дерева; участники игры: "игрок" и "противник".

та хода противника. Другими словами, игрок выигрывает в Q_i, если он выигрывает во всех позициях R_i1 и R_i2 и ... . Таким образом, все позиции противника - это И-вершины. Целевые вершины - это позиции, выигранные согласно правилам игры, например позиции, в которых король противника получает мат. Позициям проигранным соответствуют задачи, не имеющие решения. Для того, чтобы решить игровую задачу, мы должны построить решающее дерево, гарантирующее победу игрока независимо от ответов противника. Такое дерево задает полную стратегию достижения выигрыша: для каждого возможного продолжения, выбранного противником, в дереве стратегии есть ответный ход, приводящий к победе.

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

13. 3. Базовые процедуры поиска в И / ИЛИ-графах

В этом разделе нас будет интересовать какое-нибудь решение задачи независимо от его стоимости, поэтому проигнорируем пока стоимости связей или вершин И / ИЛИ-графа. Простейший способ организовать поиск в И / ИЛИ-графах средствами Пролога - это использовать переборный механизм, заложенный в самой пролог-системе. Оказывается, что это очень просто сделать, потому что процедурный смысл Пролога это и есть не что иное, как поиск в И / ИЛИ-графе. Например, И / ИЛИ-граф рис. 13.4 (без учета стоимостей дуг) можно описать при помощи следующих предложений:

а :- b. % а - ИЛИ-вершина с двумя преемниками

а :- с. % b и с

b :- d, е. % b - И-вершина с двумя преемниками d и е

с :- h.

с :- f, g.

f :- h, i.

d. g. h. % d, g и h - целевые вершины

Для того, чтобы узнать, имеет ли эта задача решение, нужно просто спросить:

?- а.

Получив этот вопрос, пролог-система произведет поиск в глубину в дереве рис. 13.4 и после того, как пройдет через все вершины подграфа, соответствующего решающему дереву рис. 13.4(b), ответит "да".

Преимущество такого метода программирования И / ИЛИ-поиска состоит в его простоте. Но есть и недостатки:

Мы получаем ответ "да" или "нет", но не получаем решающее дерево. Можно было бы восстановить решающее дерево при помощи трассировки программы, но такой способ неудобен, да его и недостаточно, если мы хотим иметь возможность явно обратиться к решающему дереву как к объекту программы.