Поиск решения на графах пространства состояний

Тема:  Поиск решения на графах пространства состояний

Цель: Изучить различные стратегии для слепых методов поиска решений на графе пространства состояний.

Задание: Реализовать логическую головоломку: три рыцаря и три оруженосца подошли к берегу реки. Нужно переправить их на другой берег. Известно, что в лодке может поместиться только два объекта. Также нельзя оставлять оруженосца без своего рыцаря. Нужно решить как организовать пепеправу через реку.

Теоретическое описание

              Граф – множество вершин вместе с множеством ребер. Каждое ребро задается парой вершин. Если ребра направлены, то называются дугами. Дуги задаются упорядоченными парами. Такие графы называются направленными. Ребрам можно приписывать имена или метки, в зависимости от конкретного приложения.

Графы можно представлять:

1.      Каждое ребро – отдельное предложение:

link ( a, b ).

link ( b, c ).

2.      Весь граф – как один объект, состоящий из двух множеств: множество вершин и множество ребер ( дуг ). Каждое множество - список

          G = graf ( [ a, b, c, d, e ], [ p( a, b ), p( b, c ),…,p( d, e ) ] ).

Для направленного графа:

         G1= graf ( [ a | _ ], [ d( a, b, 1 ), d( b, c, 4 ) …] )

Пространство состояний – граф, вершины которого соответствуют ситуациям, встречаются в задаче, а решение сводится к поиску пути в этом графе. Дуги – разрешенные переходы из одного состояния в другое.

Конкретная задача определяется:

а) Пространством состояний

б) Стартовой вершиной

в) Целевым условием – условием, к достижению которого надо стремиться.

Пространство состояний – некоторое множество уникальных состояний системы, некоторые из которых связаны между собой. Если два состояния связаны, это значит, что возможен переход системы из одного состояния в другое. Пространство состояний может быть представлено в виде графа, в котором узлами являются состояния системы, а рёбра – возможными переходами. Рёбра могут быть направленными. Это значит, что возможен переход системы только от первого связанного состояния ко второму, но не наоборот. Поиск в пространстве состояний – это поиск пути в этом графе от начального состояния к конечному.

В головоломке (логической задачи) основной проблемой является выбор наилучшего условия для некоторого состояния.

Методы поиска относятся к методу планирования в пространстве состояний.

Задача о рыцарях и оруженосцах – классическая задача поиска в пространстве состояний методом «образовать-проверить». Она состоит из двух частей: первая часть находит решение на графе пространства состояний, а вторая – проверяет это найденное решение. Начальное состояние системы – все объекты расположены на левом берегу, конечное – на правом (см. рис. 1). Каждое найденное решение проверяется на опасность (см. рис. 2).

Существует много различных подходов к проблеме поиска решающего пути для задач, сформулированных в терминах пространства состояний. Основные две стратегии поиска – это поиск в глубину и поиск в ширину.

Стратегия поиска в глубину:

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

Стратегия поиска в ширину:

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

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

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

Рис. 1 . Начальное и конечное состояние системы

Рис. 2 . Условие на опасность состояние системы

Граф пространства состояний

Рис. 3 . Метод поиска «образовать-проверить»

Рис. 4 . Стратегия поиска в ширину

Рис. 5 . Стратегия поиска в глубину

Описание программы

1. Алгоритм работы программы.

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

              Программа работает следующим образом. Предикат start инициализирует поиск с помощью предиката findpath и записывает найденное решение в базу данных с помощью предиката outpath. Предикат findpath переводит систему в следующее состояние по правилам, описанным в предикате move, если такое состояние не опасно (проверяется с помощью предиката danger) и если такое состояние ещё не было посещено (проверяется с помощью предиката member). Если текущее и конечное состояние системы совпадают, то он прекращает свою работу.

2. Описание программы.

Введены следующие обозначения типов данных:

LOCATION = l;r;b – описывает положение объекта – левый или правый берег или лодка

STATE = state(LOCLIST, LOCLIST, LOCATION) – описывает состояние системы, то есть положение всех её объектов – рыцарей, оруженосцев и лодки

PATH = STATE*– описывает список состояний системы, то есть путь в пространстве состояний

OBJECT = r1; r2; r3; r4; r5 o1; o2; o3; o4; o5 – описывает тип объекта (первый рыцарь, второй рыцарь, третий рыцарь, первый оруженосец, второй оруженосец или третий оруженосец)

LOCLIST=LOCATION* - описывает список объектов

              В программе определены следующие предикаты:

opposite(LOCATION, LOCATION) – определяет, находятся ли передаваемые ему объекты на противоположных берегах

danger(STATE) – определяет, опасно ли переданное ему состояние

move(STATE, STATE) – определяет, возможен ли переход системы между переданными ему состояниями

member(STATE, PATH) – определяет, не содержится ли передаваемое ему состояние в списке состояний

findpath(STATE, STATE, PATH, PATH) – ищет путь от первого состояния ко второму и сохраняет его во втором списке

outpath(PATH) - сохраняет путь в базе данных как последовательность состояний

start(STATE, STATE) – инициализирует алгоритм программы

inboat(LOCLIST, LOCLIST, integer) – описывает состояние в лодке

length(LOCLIST, integer, integer) – описывает количество объектов в лодке

outbackground(WINDOW) – выводит фоновую картинку в указанное окно

outitem(LOCATION, OBJECT, WINDOW) – выводит изображение указанного объекта в указанной позиции на указанное окно

Текст программы

*****************************************************************************

Студент: Середнев А.А.

Группа: 8ВС-1

Дисциплина: РЛП

Задание на ГРЗ: Решить проблему о перевозе на другой берег пяти рыцарей и пяти оруженосцев

******************************************************************************

DOMAINS

              OBJECT = r1;r2;r3;r4;r5; o1;o2;o3;o4;o5 %с каким объектом мы работаем….рыцарем или оруженосцем.

              LOCATION = l;r;b %местоположение объекта(левый или правый берег или лодка)

              LOCLIST=LOCATION* %список объектов

              STATE = state(LOCLIST, LOCLIST, LOCATION) %состояния объектов - рыцарей, оруженосцев, лодки

              PATH = STATE* %список состояний

DATABASE - db

              st(STATE)%объекты системы

              path_db(STATE)%состояние системы

predicates

  task_win_eh : EHANDLER

  nondeterm start(STATE,STATE) %инициализирует поиск пути из первого передаваемого ему состояния во второе (запуск поиска решений)

  nondeterm findpath(STATE,STATE,PATH,PATH) %ищет путь из первого передаваемого ему состояния во второе(первый передаваемый ему путь служит для проверки - было ли уже посещено данное состояние системы при поисках, а во второй сохраняется найденное решение (пути поиска)

  nondeterm move(STATE,STATE)  %определяет возможен ли немедленный переход системы из первого передаваемого ему состояния в другое (возможные ходы)

  nondeterm  danger(STATE)  %проверяет опасно ли передаваемое ему состояние системы

  nondeterm opposite(LOCLIST,LOCATION) %определяет противоположны ли два передаваемых ему местонахождения

  nondeterm member(STATE,PATH) %было ли посещяно системой это состояние

  inboat(LOCLIST,LOCLIST,integer)

  length(LOCLIST,integer,integer)

  outpath(PATH) %сохраняет переданный ему путь в базе данных как последовательный набор состояний

%вывод картинок

  outitem(LOCATION,OBJECT,WINDOW)%выводит на указанное окно указанный объект в указанном месте

  outbackground(WINDOW)%выводит фоновый рисунок

clauses

%ищем решение

start(S,G):-

              findpath(S,G,[S],L), %производится поиск

              outpath(L). %найденый результат записывается в базу данных

findpath(G,G,T,T):-!. %нахождение искомого решения определяется как совпадение текущего и конечного состояния

findpath(S,G,L,L1):-

              move(S,S1), %возмжен ли переход в какое-то состояние

              retractall(st(_)),

              assertz(st(S1)),%голова заносится в базу данных, т.о. состояния записываются в обратном порядке в базу данных

              danger(S1), %не опасно ли это состояние

              not(member(S1,L)),%не было ли уже посещено данное состояние

              findpath( S1,G,[S1|L],L1). %если все эти условия выполняются - система переходит в это состояние

member(state(X,Y,_),[state(X,Y,_)|_]). %проверяет: является ли состояние Х головой списка

member(X,[_|L]):-member(X,L). %если нет, то рекурсивно проверяется содержится ли оно в хвосте списка

danger(state([],[],_)).  %если передан пустой список, то работа предиката завершается

danger(state([R1|R],[O1|O],B)):-

              R1=O1,%равно ли местонахождение оруженосца и рыцаря

              danger(state(R,O,B)).%если да, то идем дальше; нет-выходим

danger(state([R1|R],[O1|O],B)):-

              not(R1=O1), %равно ли местонахождение оруженосца и рыцаря

              st(state(X,_,_)),

              opposite(X,O1),

              danger(state(R,O,B)).

%проверка

opposite([],_).  %если передан пустой список, то работа предиката завершается

opposite([R1|R],O1):-

              not(O1=R1), %равно ли местонахождение оруженосца и рыцаря

              opposite(R,O1).%если нет, то идем дальше; да-выходим

%Рыцарь высаживается из лодки на правый берег

move(state([b,R2,R3,R4,R5],[O1,O2,O3,O4,O5],_),state([r,R2,R3,R4,R5],[O1,O2,O3,O4,O5],r)).

move(state([R1,b,R3,R4,R5],[O1,O2,O3,O4,O5],_),state([R1,r,R3,R4,R5],[O1,O2,O3,O4,O5],r)).

move(state([R1,R2,b,R4,R5],[O1,O2,O3,O4,O5],_),state([R1,R2,r,R4,R5],[O1,O2,O3,O4,O5],r)).