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

Задача с ханойской башней (рис. 13.6) является еще одним классическим приме­ром эффективного применения схемы декомпозиции AND/OR. Для упрощения рас­смотрим описанную ниже простую версию этой задачи, содержащую только три диска.

Даны три оси, 1, 2 и 3, и три диска, а, Ь и с (из них а - самый маленький и с -самый большой). Первоначально все диски нанизаны на ось 1. Задача состоит в том, чтобы перенести их все на ось 3. Разрешено переносить одновременно только один диск и нельзя класть диск большего диаметра на диск меньшего диаметра.

Юшшм

1 2 3

Рис. 13.6. Задача с ханойской башней

Такую задачу можно рассматривать как задачу достижения следующего множест­ва целей.

Часть II.Применение языка Prolog в области искусственного интеллекта

1. Диск а на оси 3.

2. Диск Ь на оси 3.

3. Диск с на оси 3.

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

Таким образом, стратегия решения задачи, которая вытекает из этого принципа, состоит в следующем:

вначале достичь дели "диск с на оси 3"; затем достичь оставшихся целей.

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

1. Обеспечить перемещение с оси 1 на ось 3 диска с.

2. Перенести с оси 1 на ось 3 диск с.

3. Достичь оставшихся целей — диск а на оси 3 и диск Ь на оси 3.

Диск с можно перенести с оси 1 на ось 3, если оба оставшихся диска, а и Ь, на­низаны на ось 2. Поэтому наша первоначальная задача переноса с оси 1 на ось 3 дис­ков a, b и с сводится к трем перечисленным ниже подзадачам.

Чтобы переместить с оси 1 на ось 3 диски а, Ь и с, необходимо выполнить следующее.

1. Переместить с оси 1 на ось 2 диски а и Ь.

2. Переместить с оси 1 на ось 3 диск с.

3. Переместить с оси 2 на ось 3 диски а и Ь.

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

Чтобы переместить с оси 1 на ось 2 диски а и Ь, необходимо выполнить следующее.

1. Переместить с оси 1 на ось 3 диск а.

2. Переместить с оси 1 на ось 2 диск to.

3. Переместить с оси 3 на ось 2 диск а.

13.2.3. Формулировка процесса игры в виде графа AND/OR

Такие игры, как шахматы и шашки, могут естественным образом рассматривать­ся как задачи, представленные в виде графов AND/OR. Подобные игры называются играми с двумя участниками, с полной информацией, и здесь предполагается, что в

Глава 13. Декомпозиция задач играфы AND/OR

них могут быть только два возможных исхода — победа и поражение. (Игры с тремя исходами • — победа, поражение или ничья — также могут рассматриваться как имеющие только два исхода: победа и отсутствие победы.) По мере того как два иг­рока по очереди делают ходы, возникают позиции двух типов, в зависимости от того, кто должен ходить. Назовем двух игроков свой и чужой, поэтому два типа позиций состоят в следующем: позиция сййШ) хода и позиция чужого хода. Предположим, что игра начинается с позиции своего хода ?. Каждый вариант своего хода в этой пози­ции приводит к созданию одной из позиций чужого хода, Qi, Оз. ... (рис. 13.7). Кроме того, каждый из вариантов чужого хода в позиции Qi приводит к созданию одной из

позиций Rn, Ки............. В дереве AND/OR (рис. 13.7) узлы соответствуют позициям, а

дуги — возможным ходам. Уровни своего хода чередуются с уровнями чужого хода. Чтобы выиграть в начальной позиции, Р, необходимо найти ход, переводящий игру из позиции Р в позицию Qi, для некоторого i, таким образом, чтобы позиция Qi была выигрышной. Поэтому позиция Р является выигрышной, если выигрышной является позиция Qi, или Сь, или ... . Итак, позиция Р представляет собой узел OR. Для всех i позиция Q* является позицией чужого хода, поэтому, если она должна быть выиг­рышной для своего игрока, то необходимо добиться, чтобы ее можно было выиграть после любого чужого хода. Поэтому позиция Q] является выигрышной, если выиг­рышными являются все позиции, и J^i, и R;?, и .... В соответствии с этим все пози­ции чужого хода являются узлами AND. Целевые узлы представляют собой позиции, выигранные согласно правилам данной игры; например, в шахматах •— это позиция с чужим королем, получившим мат. Те позиции, которые проиграны согласно прави­лам данной игры, соответствуют неразрешимым задачам. Чтобы решить задачу дос­тижения выигрыша в игре, необходимо найти дерево решения, гарантирующее свою победу независимо от ответов противника. Таким образом, подобное дерево решения представляет собой полную стратегию победы в игре: на любое возможное продолже­ние, которое может быть выбрано противником, в этом дереве стратегии есть такой ход, который приводит к победе.

позиция своего хода позиция чужого хода

сеой лод

Рис. 13.7. Формулировка игры с двуня участниками о виде графа AND/OR; игроки обозначаются как свой и чужой

13.3. Основные процедуры поиска в графе AND/OR

В данном разделе рассматриваются только процедуры поиска хотя бы одного ре­шения задачи, независимо от его стоимости. Поэтому для целей этого раздела можно проигнорировать стоимости связей или узлов в графе AND/OR.

Часть II. Применение языка Prolog в области искусственного интеллекта

Простейший способ организации поиска в графах AND/OR с помощью программы Prolog состоит в использовании собственного механизма поиска Prolog. Как оказа­лось, эта задача является тривиальной, поскольку по своему процедурному значению программа Prolog представляет собой ни что иное, как процедуру для поиска в гра­фах AND/OR. Например, граф AND/OR, приведенный на рис. 13.4 (если не рассмат­ривать стоимости дуг) может быть представлен с помощью следующих предложений: а :- Ь. % Узел а - это узел OR с двумя преемниками, b и с а :- с. b :- d, e. % Узел b - это узел AN D с двумя преемниками, d и е

с :- 1, д. f :- h, i.

d. д. h, i d, д и h • целевые узлы

Чтобы узнать, можно ли решить задачу а, достаточно просто задать системе сле­дующий вопрос: ?- а.

После этого система Prolog фактически выполнит поиск в графе, приведенном на рис. 13.4,по методу поиска в глубину и ответит "yes", посетив ту часть графа поис­ка, которая соотаетствует дереву решения на рис. 13.4, б.

Преимуществом такого подхода к программированию поиска в графе AND/ORявляется его простота. Но этот подход имеет также перечисленные ниже недостатки.

• Он позволяет получить лишь ответ "yes" или "по", который не сопровождает­ся также деревом решения. Дерево решения можно восстановить из трасси­ровки программы, но такой подход становится громоздким и неэффективным, если необходимо, чтобы дерево решения было явно доступным в качестве од­ного из объектов в программе.

• Такую программу трудно дополнить, чтобы она позволяла также учитывать стоимости.

• Если граф AND/OR представляет собой граф общего типа, содержащий циклы, то система Prolog с ее стратегией поиска в глубину может войти в бесконеч­ный рекурсивный цикл.

Эти недостатки будем исправлять постепенно. Вначале определим собственную процедуру поиска в глубину для графов AND/OR.

Прежде всего необходимо изменить представление графов AND/OR в программе.
Для этого введем бинарное отношение, представленное в инфиксной системе обозна­
чений с помощью оператора "----- >". Например, информация о том, что узел а связан

с его двумя преемниками типа OR, будет представлена с помощью следующего пред­
ложения:
а----- > or:[b,c].

Оба символа, "------ >" и ":", являются инфиксными операторами, которые можно

определить следующим образом:

:- ор[ 600, :■-■■■,-------->) .

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

Поэтому полный граф AMD/OR, показанный на рис. 13.4, можно представить с помощью таких предложений:

а------ > or: [b,с] .

b> and: [d,e] .

с---- > and: !t, g] .

G---- > or:[h].

t —> or:[h,i].

goalt d). goal( g> . goal! h).

Процедуру поиска в глубину в графе AND/OR можно сформировать на основе приведенных ниже принципов.

Глава 13. Декомпозиция задач играфы AND/OR

Для поиска решения, представленного с помощью некоторого узла N, использу­ются следующие правила.

1. Если N— целевой узел,то решение является тривиальным.

2. Если К имеет преемников OR,то найти решение с помощью одного из них (попытаться использовать их одного за другим до тех пор, пока не будет найден тот, который приведет к решению).

3. Если узел N имеет преемников AND, то найти решение для всех них (попытаться найти решения, перебирая преемников одного за другим, таким образом, чтобы решение было найдено для всех этих преемников).

Если приведенные выше правила не позволяют найти решение, то следует пола­гать, что задача не может быть решена.

Соответствующая программа может быть представлена следующим образом:

solvet Mode) :-goal! Node) .

solvet Bode) :-

Node--- > or:Nodes, % Узел Node - узел OR

member( Nodel, Nodes) , % Выбрать преемника Model узла Node solve ( Nodel) .

Solvef Node) :-

Node------ ? and:Modes, % Узел Mode - узел AND

SOlvealK Nodes) . % Найти решения для всех преемников узла Node soivealKM ) .

SOlvealK [Node 1 Nodes]) :-

solvet Node) , solvealK Nodes) .

где member — обычное отношение проверки принадлежности к списку. Тем не менее эта программа все еще имеет следующие недостатки.

• Не формирует дерево решения;

• Восприимчива к бесконечным циклам, в зависимости от свойств графа
AND/OR (наличия в нем циклов).

Данную программу можно легко модифицировать таким образом, чтобы она фор­мировала дерево решения. Для этого необходимо откорректировать отношение solve, предусмотрев в нем следующие два параметра: solve(Node, Solutio.nTree)

Представим дерево решения следующим образом. Для этого могут рассматривать­ся три перечисленных ниже случая.

1. Если Mode — целевой узел, то соответствующим деревом решения является сам узел Node.

2. Если Node — узел OR, то дерево решения имеет следующую форму: Node>Subtree

где Subtree — дерево решения для одного из преемников узла Node.

3. Если Node — узел AND, то его дерево решения имеет форму
Node------ > and:Subtrees

где Subtrees — список деревьев решения всех преемников узла Node.
Например, в графе AND/OR (см. рис. 13.4) первое решение для верхнего узла а
может быть представлено таким образом:
а-----> b------> and:[d, е----> h]

286 Часть II. Применение языка Prolog в области искусственного интеллекта

Эти три формы дерева решения соответствуют первым трем предложениям, ка­сающимся рассматриваемого отношения solve. Поэтому первоначальную процедуру solve можно усовершенствовать, откорректировав каждое из трех предложений; это означает, что достаточно просто ввести в предложение solve дерево решения в каче­стве второго параметра. Результирующая программа показана в листинге 13.1. В этой программе имеется дополнительная процедура show для отображения деревь­ев решения. Например, дерево решения задачи (см. рис. 13.4) отображается процеду­рой show в следующей форме: а —> b — > d

е—>h

Программа в листинге 13.1 все еще способна переходить в бесконечные циклы. Один из простых способов предотвращения бесконечных циклов состоит в том, что необходимо следить за текущей глубиной поиска и запрещать программе поиск сверх некоторой указанной глубины. Это можно сделать, введя еще один параметр в отно­шение solve: solve! Node, SolutionTree, MaxDepth)

Здесь, как и прежде, узел Mode представляет задачу, которая должна быть реше­на, a SolutionTree— это решение, не превышающее по глубине MaxDepth. С дру­гой стороны, MaxDepth — это допустимая глубина поиска в графе. В том случае, ес­ли MaxDepth = 0, дальнейшее развертывание дерева не допускается; в противном случае, если MaxDepth > 0, то можно развернуть узел Kode и попытаться достичь решения с помощью его преемников, с меньшим пределом глубины MaxDepth - 1. Такое условие можно легко включить в программу, приведенную в листинге 13.1. Например, второе предложение, касающееся процедуры solve, принимает следую­щий вид.

solve: Mode, Node---- > Tree, MaxDepth! :-

HassDepth > 0,

Node------ > or:Modes, Ъ Узел Node - Это узел OR

raembec( Model, Nodes), % Выбрать преемника Model узла Node

Depthi is MaxDepth - 1, % Новый предел глубины

solver wodei, Tree, Depthl). i Найти решение для преемника,

<t установив меньший предел глубины

Эту процедуру поиска в глубину с ограничением по глубине можно также исполь­зовать в режиме итеративного углубления, моделируя тем самым поиск в ширину. Идея состоит в том, чтобы поиск в глубину выполнялся повторно, с увеличением каждый раз предела глубины до тех пор, пока не будет найдено решение. Это означа­ет, что нужно попытаться решить проблему с использованием предела глубины 0, за­тем 1, 2 и т.д. Такая программа имеет следующий вид.

Листинг 13.1, Программа поиска в глубину для графов AND/OR.Эта программа не предотвращает возникновения бесконечных циклов. Процедура solve находит дерево решения, а процедура show отображает такое дерево. При использовании процедуры show подразумевается, что для вывода имени каждого узла достаточно одного символа

'*..... Поиск в глубину длягзафсв AND/OR

% solve ( Node, SolutionTree):

% найти дерево решения для узла Hode з графе AND/OR

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

:- ор{ 600, xfx,-- > ! .

solve( Mode, Node) :- S Деревом решения для целевого узла является

i сам узел Node goal(Node) .

solve ( Mode, Node--------- > Tree) :-

Mode------ > or:Nodes, % Узел Node - это узел OR

Глава 13. Декомпозиция задам играфы AND/OR

member; Nodel, Nodes), solvet Nodel, Tree).

* Выбрать преемника Nodel узла Node

solve< Mode, Node- > and:Trees> :-

Node-- > and:Nodes, % Узел Node - это узел AMD

SOlvealM Nodes, Trees) . * Найти решения для всех преемников узла Node

% solveall{ (Model,Node2, . . . ] , [SolutionTreel,SolutionTree2, ...])

solvealK [] , [) ) .

SOlvealK [Node! Modes] , [Tree| Trees] ] :-

solve( Node, Tree),

solvealK Modes, Trees).

% Отображение дерева решения

show(Tree) :- % Отобразить дерево решения

show(Tree,0), !. % с отступом 0

% show( Tree, H): отобразить дерево решения с отступом 3

show! Node-- > Tree, H) :- !,

write(Mode), write('- > '),

HI Is H + 7, showf Tree, HI) . show( and: IT], B) :- ], % Отобразить одно дерево AMD show [T, К) .

show ( and:[TITS], H) :- !, % Отобразить список AND деревьев решения

show!T, В), tab(H) , show{ and;Ts, H! .

show( Node, H) :-write (Node) , jil.

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

Упражнения

13.1. Доработайте программу поиска в графе AND/OR по принципу поиска Б глуби­ну с ограничением по глубине в соответствии с процедурой, описанной в дан­ном разделе.

13.2. Определите на языке Prolog пространство состояний AND/OR для задачи с ха­нойской башней и используйте это определение с процедурами поиска, пред­ставленными в данном разделе.

13.3. Рассмотрите какую-либо простую игру с двумя участниками и с полной ин­формацией, в которой не применяется жребий, и определите ее представление а виде графа AND/OR Воспользуйтесь программой поиска в глубину в графах AND/OR чтобы найти стратегии выигрыша в форме деревьев AND/OR.

Часть II. Применение языка Prolog в области искусственного интеллекта

13.4. Поиск в графе AND/OR по заданному критерию