Вводные понятия и примеры

Рассмотрим пример, приведенный на рис. 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,иЗГ¹'- ! ЙЙ 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, с ].