Рассмотрим пример, приведенный на рис. 11.1. Задача состоит в том, что необходимо найти план переупорядочения кубиков, поставленных друг на друга, как показано на этом рисунке. Разрешается передвигать одновременно только один кубик. Кубик можно передвигать, только если на нем не стоит другой кубик. Такой кубик можно поставить на стол или на другой кубик (кубики, поставленные друг на друга, образуют столбик). Чтобы определить требуемый план, нужно найти последовательность действий, позволяющих осуществить указанную перестановку кубиков.
Эту задачу можно рассматривать как задачу изучения возможных вариантов. В первоначальной проблемной ситуации имеется только один вариант: поставить кубик С на стол. А после того как кубик С поставлен на стол, появляются три следующих варианта:
• поставить А на стол;
• поставить А на С;
• поставить С на А.
Безусловно, что в процессе поиска альтернативных решений не следует уделять большого внимания предыдущему шагу, в котором кубик С был поставлен на стол, поскольку в данной ситуации он представлял собой единственно возможное действие.
D::
Рис. 11.1. Задача перестановки кубиков
Как показывает данный пример, при анализе подобной проблемы приходится сталкиваться с двумя основными понятиями.
1. Проблемные ситуации.
2. Допустимые шаги, или действия, которые преобразуют одни проблемные ситуации в другие.
Проблемные ситуации и допустимые действия образуют ориентированный граф, называемый пространством состояний. Пространство состояний для задачи, рассматриваемой в данном примере, показано на рис, 11.2. Узлы этого графа соответствуют проблемным ситуациям, а дуги — допустимым переходам между состояниями. Задача поиска плана решения эквивалентна поиску пути между заданной начальной ситуацией (начальным узло.м) и некоторой указанной конечной ситуацией, называемой также целевым узлом.
|
Рис, 11.2. Представление задачи, перестановки кубиков в виде пространства состояний; полужирными стрелками обозначен путь решения задачи, представленной на рис. 11.1
Глава 11. Основные стратегии решения проблем
На рис. 11.3 приведен еще один пример задачи. Здесь рассматриваются головоломка "игра в восемь" и ее представление в виде проблемы поиска пути. Головоломка состоит из восьми скользящих фишек, пронумерованных цифрами от 1 до 8 и размещенных в коробке с размерами 3x3, с девятью ячейками. Одна из ячеек всегда пуста, и в эту пустую ячейку может быть передвинута по горизонтали или по вертикали любая соседняя фишка. Это правило можно выразить иначе: пустую ячейку можно перемещать по коробке, меняя ее местами с любой из соседних фишек. Конечной ситуацией является некоторое особое расположение фишек, как показано, например, на рис. 11.3.
| г | А | |
| ■.'■ | s |
| L | ||
| ; | б |
 |  |
| г | ||
| К | ||
| (. |
| I | \ | |
| * | г | |
| ь |
1 3 4
I i
7 6 5
13 4 13 4
S 2 5 8 2
7 6 7 6 5
Рис. 11,3, Головоломка "игра в восемь" и соответствующее ей представление в виде пространства состояний
Подытожим понятия, представленные в этих примерах. Пространство состояний указанной задачи определяет "правила игры", согласно которым узлы в пространстве состояний соответствуют ситуациям, а дуги •— допустимым шагам, или действиям, или этапам решения. Любая конкретная задача определяется следующими составляющими,
• Пространство состояний.
• Начальный узел.
• Целевое состояние (состояние, которое должно быть достигнуто); целевыми узлами называются такие узлы, которые соответствуют этому состоянию.
Допустимым шагам (или действиям) могут быть поставлены в соответствие СТОИМОСТИ. Например, стоимости, назначенные действиям по перестановке кубиков в аа-
Часть II. Применение языка Prolog в области искусственного интеллекта
даче по их переупорядочению, могут указывать, что одни кубики сложнее переставлять, чем другие. В задаче с коммивояжером шаги соответствуют прямым поездкам из города в город. Естественно, что стоимости этих шагов представляют расстояния между городами.
В тех случаях, если шагам назначаются стоимости, обычно требуется осуществить оптимизацию - найти решение с минимальной стоимостью. Стоимостью решения является сумма стоимостей всех дуг на пути решения. Но даже если стоимость дуг не указана, может рассматриваться задача оптимизации, в которой необходимо найти кратчайшие решения.
Прежде чем перейти к рассмотрению некоторых программ, в которых реализованы классические алгоритмы поиска в пространство состояний, рассмотрим, как пространство состояний может быть представлено в программе Prolog.
Пространство состояний представляется отношением
si X, Y)
которое принимает истинное значение, если в данном пространстве состояний имеется допустимый переход из узла X в узел Y. В таком случае узел Y принято называть преемником узла X. Если с допустимыми шагами связаны стоимости, то вводится третий параметр — стоимость шага:
Е(X, Y, Cost}
Это отношение может быть представлено в программе явно, в виде множества фактов. Но такой вариант при наличии типичного пространства состояний с какой-либо значительной сложностью может оказаться практически неприемлемым или невозможным. Поэтому, как правило, отношение определения преемника, s, задается неявно путем указания правил вычисления узлов, которые являются преемниками указанного узла.
Обычно возникает еще один важный вопрос — как представлять проблемные ситуации, иными словами, сами узлы. Это представление должно быть компактным, но должно также обеспечивать эффективное выполнение необходимых операций, в частности, вычисление отношения, определяющего преемника, и, возможно, соответствующие стоимости.
В качестве примера рассмотрим задачу перестановки кубиков, показанную на рис. 11.1. Проанализируем более общий случай, при котором" разрешается применять любое количество кубиков, расположенных в виде одного или нескольких столбиков. Количество столбиков может быть ограничено некоторым заданным максимумом для того, чтобы задача стала более интересной. К тому же это ограничение может оказаться вполне реальным, поскольку робот, который манипулирует кубиками, может иметь в своем распоряжении только ограниченное рабочее пространство.
Проблемную ситуацию можно представить как список столбиков. Каждый столбик, в свою очередь, представляется в виде списка кубиков в этом столбике, упорядоченного таким образом, чтобы верхний кубик в столбике представлял собой голову списка. Пустые столбики представлены пустыми списками. Поэтому первоначальную ситуацию задачи (см. рис. 11.1) можно определить следующим образом::[с,а,Ы, [J,t]]
Целевой ситуацией является любое расположение кубиков, при котором в одном из столбиков находятся все кубики, расположенные по порядку. Возможны три таких ситуации:
[[а,Ь,с], [],[]] [ [), [а,Ь,с], []] [[I ЛЬ [а,Ь,с]]
Отношение определения преемника можно запрограммировать в соответствии со следующим правилом: ситуация 2 является преемником ситуации 1, если в ситуации 1 имеются два столбика, Stackl и Stack2, и верхний кубик можно перенести со столбика Stackl на столбик Stack2. Поскольку все ситуации представляются как
Глава 11. Основные стратегии решения проблем
списки кубиков в столбиках, такую формулировку задачи можно перевести на язык Prolog следующим образом:
S{ Stacks, [Staefel, [Topi [ Stack2] i otherstacks]):- % Перенести верхний
% кубик Toрвi на столбик stack2
Si! ЕЩ Й32; Stacks,иЗГ1'-! ЙЙ S3 SSS
den x, [x | L], ы.
dell X, (Y1 L],(I I Ll] j:-
del(X, L, Ll).
Целевое состояние для данного примера задачи является следующим: goall Situation}:-
member([a,b,C;, Situation}.
Алгоритмы поиска реализуются в программе в виде отношения solve (Start, Solution)
где Start - начальный узел в пространстве состояний, a Solution - путь от узла Start до любого целевого узла. Для рассматриваемой задачи перестановки кубиков соответствующий вызов может иметь вид?- solve! [ [с,а,Ы, П ,П 1, Solution).
В результате успешного поиска переменная Solution конкретизируется списком перестановок кубиков. Этот список представляет собой план преобразования начального состояния в такое состояние, что все три кубика находятся в одном столбике и расположены как [ а, b, с ].
