Основные стратегии решения задач. Поиск решения в пространстве состояний

Пространство состояний – это граф, вершины которого соотвествуют ситуациям, встречающимся в задаче («проблемные ситуации»), а решение задачи сводится к поиску путей на этом графе. На самом деле, задача поиска пути на графе и задача о N ферзях - это задачи, использующие одну из стратегий перебора альтернатив в пространстве состояний, а именно – стратегию поиска в глубину.

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

К таким задачам относятся следующие задачи:

переупорядочние кубиков, поставленных друг на друга в виде столбиков;

· задача о восьми ферзях;

· головоломка «игра в восемь»;

· головоломка о «ханойской башне»;

· задача о перевозке через реку волка, козы и капусты;

· задача о коммивояжере;

· другие оптимизационные задачи.

Со всеми задачами такого рода связано два типа понятий:

· проблемные ситуации;

· разрешенные ходы или действия, преобразующие одни проблемные ситуации в другие.

Проблемные ситуации вместе с возможными ходами образуют направленный граф, называемый пространством состояний.

На следующем рисунке представлена задача «игра в восемь» в виде задачи поиска пути в пространстве состояний. В головоломке используется восемь перемещаемых фишек, пронумерованных цифрами от 1 до 8. Фишки располагаются в девяти ячейках, образующих матрицу 3х3. Одна из ячеек всегда пуста, любая смежная с ней фишка может быть передвинута в эту ячейку. Конечная ситуация – это некоторая заранее заданная конфигурация фишек.

Пространство состояний некоторой задачи определяет «правила игры»: вершины пространства состояний соответствуют ситуациям, а дуги – разрешенным ходам или действиям, или шагам решения задачи. Конкретная задача определяется:

· пространством состояний;

· стартовой вершиной;

· целевым условием или целевой вершиной.

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

В тех случаях, когда ход имеет стоимость, программист заинтересован в отыскании решения минимальной стоимости. Стоимость решения – это сумма стоимостей дуг, из которых состоит «решающий путь» – путь из стартовой вершины в целевую. Даже если стоимости не заданы, все равно может возникнуть оптимизационная задача: требуется найти кратчайшее решение.

В представленной в примере 62 программе о N ферзях проблемная ситуация (вершина в пространстве состояний) описывается в виде списка из N X -координат ферзей, а переход из одной вершины в другую генерирует предикат queens, причем начальная ситуация генерируется предикатом range, а целевая ситуация определяется при помощи предиката attack.

Программа решения задачи о N ферзях реализует стратегию поиска в глубину. Под термином «в глубину» имеется в виду тот порядок, в котором рассматриваются альтернативы в пространстве состояний. Всегда, когда алгоритму поиска в глубину надлежит выбрать из нескольких вершин ту, в которую следует перейти для продолжения поиска, он предпочитает самую «глубокую» из них. Самая глубокая вершина – это вершина, расположенная дальше других от стартовой вершины. На следующем рисунке показан пример, который иллюстрирует работу алгоритма поиска в глубину. Этот порядок в точности соответствует результату трассировки процесса вычислений при поиске решения.

Порядок обхода вершин указан пунктирными стрелками, a – начальная вершина, j и f – целевые вершины.

Поиск в глубину наиболее адекватен рекурсивному стилю программирования, принятому в Прологе. Причина этого состоит в том, что обрабатывая цели, Пролог сам просматривает альтернативы именно в глубину.

На Прологе переход от одной проблемной ситуации к другой может быть представлен при помощи предиката after (X, Y, C), который истинен тогда, когда в пространстве состояний существует разрешенный ход из вершины X в вершину Y, стоимость которого равна C. Предикат after может быть задан в программе явным образом в виде фактов, однако такой принцип оказывается непрактичным, если пространство состояний является достаточно сложным. Поэтому отношение следования after обычно определяется неявно, при помощи правил вычисления вершин, следующих за некоторой заданной вершиной.

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

На каждом шаге разрешается переставлять только один кубик. Кубик можно взять только тогда, когда его верхняя поверхность свободна. Кубик можно поставить либо на стол, либо на другой кубик. Для того, чтобы получить требумое состояние, необходимо получить последовательность ходов, реализующую данную трансформацию. В качестве примера будет рассмотрен общий случай данной задачи, когда имеется произвольное число кубиков в столбиках. Число столбиков ограничено некоторым максимальным значением.

Проблемную ситуацию можно представить как список столбиков. Каждый столбик, в свою очередь, представляется списком кубиков, из которых он составлен. Кубики упорядочены в списке таким образом, что самый верхний кубик находится в голове списка. «Пустые» столбики изображаются как пустые списки. Таким образом, исходную ситуацию на рисунке можно записать как терм [[c, a, b], [], []].

Целевая ситуация- это любая конфигурация кубиков, содержащая столбик, составленный из имеющихся кубиков в указанном порядке. Таких ситуаций три:

[[a, b, c], [], []];

[[], [a, b, c], []];

[[], [], [a, b, c]].

Пример 63: решение задачи о перемещении кубиков.

trace

domains

list=symbol*

% описывает состояние одного столбика кубиков

sit=list*

% описывает состояние всех столбиков

sits=sit*

% описывает путь из начальной вершины в целевую вершину

predicates

after(sit,sit)

% определяет переход из одной вершины пространства состояния в другую, то есть описывает все возможные правила перекладывания кубиков

solve (sit, sit, sits, sits)

% определяет путь для решения задачи

member (list, sit)

% первый предикат ищет список в списке списков

member1(sit, sits)

% второй предикат ищет список списков в списке списко списков

writesp(sits)

% распечатывает путь

clauses

member(X, [X|_]):-!.

member(X,[_|T]):-member(X,T).

member1(X, [X|_]):-!.

member1(X,[_|T]):-member1(X,T).

after([St11,St12,St13],S):-St13=[H3|T3],S=[St11,[H3|St12],T3].

after([St11,St12,St13],S):-St13=[H3|T3],S=[[H3|St11],St12,T3].

after([St11,St12,St13],S):-St12=[H2|T2],S=[[H2|St11],T2,St13].

after([St11,St12,St13],S):-St12=[H2|T2],S=[St11,T2,[H2|St13]].

after([St11,St12,St13],S):-St11=[H1|T1],S=[T1,[H1|St12],St13].

after([St11,St12,St13],S):-St11=[H1|T1],S=[T1,St12,[H1|St13]].

solve(S,S1,Sp,[S1|Sp]):-after(S,S1), member([a,b,c],S1).

solve(S,S2,Sp,Sp2):-after(S,S1), not(member([a,b,c],S1)),

not(member1(S1,Sp)),solve(S1,S2,[S1|Sp],Sp2).

writesp([]).

writesp([H|T]):-writesp(T),write(H),nl.

goal

solve([[c,a,b],[],[]],S,[[c,a,b],[],[]],Sp),writesp(Sp).

В данном примере реализован усовершенствованный алгоритм поиска в глубину, в котором добавлен алгоритм обнаружения циклов. Предикат solve включает очередную вершину в решающий путь только в том случае, если она еще не встречалась раньше.

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

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

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

Еще одна проблема, возникающая при решении задачи поиска – это проблема комбинаторной сложности. Для сложных предметных областей число альтернатив столь велико, что проблема сложности часто принимает критический характер, так как длина решающего пути (тем более, если их множество, как при реализации поиска в ширину) может привести к экспоненциальному росту длины в зависимости от размерности задачи, что приводит к ситуации, называемой комбинаторным взрывом. Стратегии поиска в глубину и в ширину недостаточно «умны» для борьбы с такой ситуацией, так ка все пути рассматриваются как одинаково перспективные.

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

Сведение задачи к подзадачам. И/ИЛИ графы.

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

Вершинами a,b,c,d,f,g,h,z – представлены города. Расстояние между городами обозначено весом дуги из одной вершины графа в другую. На карте есть река. Допустим, что переправиться через реку можно только по двум мостам: один находится в городе f, а второй – в городе g. Очевидно, что искомый маршрут обязательно должен проходить через один из мостов, а значит должен проходить либо через f, либо через g. Таким образом, мы имеем две главные альтернативы:

· путь из a в z, проходящий через f;

· путь из a в z, проходящий через g.

Затем, каждую из этих двух альтернативных задач можно, в свою очередь, разбить следующим образом:

1. для того, чтобы найти путь из a в z через f, необходимо:

· найти путь из a в f и

· найти путь из f в z.

2. для того, чтобы найти путь из a в z через g, необходимо:

· найти путь из a в g и

· найти путь из g в z.

Таким образом, в двух альтернативах мы получили четыре подзадачи, которые можно решать независимо друг от друга. Полученное разбиение исходной задачи можно изобразить в форме И/ИЛИ – графа, представленного на рисунке.

Круглые дуги на графе указывают на отношение И между соответствующими подзадачами. Задачи более низкого уровня называются задачами-преемниками.

И/ИЛИ- граф- это направленный граф, вершины которого соответствуют задачам, а дуги – отношениям между задачами.

Между дугами также существуют свои отношения – это отношения И и ИЛИ, в зависимости от того, должны ли мы решить только одну из задач-преемников или же неколько из них. В принципе из верщины могут выходить дуги, находящиеся в отношении И вместе с дугами, находящимися в отношении ИЛИ. Тем не менее, будем предполагать, что каждая верщина имеет либо только И-преемников, либо только ИЛИ-преемников, так как в такую форму можно преобразовать любой И/ИЛИ- граф, вводя в него при необходимости вспомогательные ИЛИ-вершины. Вершину, из которой выходят только И- дуги называются И- вершиной; вершину, из которой выходят только ИЛИ- дуги,- ИЛИ- вершиной.

Решением задачи, представленной в виде И/ИЛИ- графа является решающее дерево, так как решение должно включать в себя все подзадачи И-вершин.

Решающее дерево T определяется следующим образом:

· исходная задача P – это корень дерева T;

· если P является ИЛИ-вершиной, то в T содержится только один из ее преемников (из И/ИЛИ-графа) вместе сос своим собственным решающим деревом;

· если P – это И-вершина, то все ее преемники (из И/ИЛИ-графа) вместе со своими решающими деревьями содержатся в T.

На представленном выше И/ИЛИ- графе представлены три решающих дерева, обозначенных штих-пунктирной, пунктирной и сплошной линиями. Соответственно, стоимости данных деревьев составляют 7, 12, 7. В данном случае стоимости определены как суммы стоимостей всех дуг дерева. Иногда стоимость решающего дерева определяется сумой стоимостей всех его вершин. В соответствии с заданным критерием, из всех решающих деревьев выбирается оптимальное.

Дата добавления: 2015-06-27