Поиск в глубину

Для того чтобы алг не уходил в беск цикл и находил результат эффективным нужно исп спец методы поиска решения.

Мы в этом курсе рассмотрим один из самых простых методов – поиск в глубину. Он гарантирует отсутствие цикла. Этот метод мы рассмотрим на примере задачи о волке, козле и капусте.

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

Нам нужно определить эти маршруты. Для того чтобы преступить к решению нужно сформ состояния. Задать структуу для представления состояния.

Состояние wgc(лодка,левый,правый).

initial_state(wgc(left,[wolf,goat,cabbage],[])).

final_state(wgc(right,[],[wolf,goat,cabbage])).

У состояния 3 компонента. 1 где находится лодка. 2 что на левом берегу. 3 что на правом берегу. Сразу мы модем задать начальное состояние. Лодка на лево берегу, вол, коза, капуста, все они на левом берегу, на правом берегу пусто.

Финальное состояние – лодка на правом, слева ничего нет, волк коза и капуста справа.

Возможные действия.

Будем описывать их предикатом move.

move(wgc(left,L,_),Cargo) :- member(Cargo,L).

move(wgc(right,_,R),Cargo) :- member(Cargo,R).

move(wgc(_,_,_),alone).

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

Движение на левый береге аналогично. Это когда лодка распологается… есть груз…он будет…

3 возможность – когда лодка плывет на другой берег без груза. Атом alone - без груза.

Эти действия приводят к изменению состояния задачи. Исходное (в начале шага) состояние, груз, новое состояние. Обычно когда меняется состояние задачи, то желательно представить в виде нескольких независимых изменений. В нашем случае изм состояния имеет 2 аспекта – изм положения лодки, изм состояния берегов(переменные переставить на берегах).

Изменение сост лодки – слева на право, справа налево.

Изм состояния берегов – если лодки без грукза то положение объектов без изменения. Если берег был левым,…, то груз удаляется с левого берега и добавл на правый берег.

Если лодка справа – груз удал с правого берега и добавл в левый берег.

update(wgc(B,L,R),Cargo,wgc(B1,L1,R1)) :-

update_boat(B,B1), update_banks(Cargo,B,L,R,L1,R1).

update_boat(left,right).

update_boat(right,left).

update_banks(alone,_,L,R,L,R).

update_banks(Cargo,left,L,R,L1,R1) :-

delete(Cargo,L,L1), insert(Cargo,R,R1).

update_banks(Cargo,right,L,R,L1,R1) :-

delete(Cargo,R,R1), insert(Cargo,L,L1).

Мы будем сравнивать множества, для удобства сравнения сделаем их упорядоченными. Правило precedes указывает отношение предшественник. Волк сильнее всех, капуста слабее всех.

Вставка элемента в список не нарушая порядок.

insert(X,[Y|Ys],[X,Y|Ys]) :-

precedes(X,Y).

insert(X,[Y|Ys],[Y|Zs]) :-

precedes(Y,X), insert(X,Ys,Zs).

insert(X,[],[X]).

precedes(wolf,_).

precedes(_,cabbage).

Далее…

Legal – определяет допустимость данного состояния.

Если лодка слева…то не должно быть нелегальным…

Illegal – берег явл не легальным если на нем волк и козел, и козел и капуста.

delete(X,[X|Xs],Xs).

delete(X,[Y|Ys],[Y|Zs]) :-

delete(X,Ys,Zs).

legal(wgc(left,_,R)) :- not illegal(R).

legal(wgc(right,L,_)) :- not illegal(L).

illegal(Bank) :- member(wolf,Bank), member(goat,Bank). illegal(Bank) :- member(goat,Bank), member(cabbage,Bank).

Теперь мы можем рассмотреть сам алг поиска в глубину. Он будет польз теми предикатами, которые рассмотрели. Его параметры – состояние задачи, предыстория(список пройденных состояний), действие которого нужно выполнить.

Если состояние задачи яв финальным, то ничего не надо делать. Уже имеем решение. Общий случай – найти move и moves, т.е. действия. Нужно по сост найти действие, по сост и действию найти новое состояние (сделать update), должны проверить явл ли оно допустимым. Если не допустимо то другой ход… State1 не должно быть в истории. Состояние должно быть новым. То можно продолжить поиск из state1 , стейт1 занести в историю, получим moves.

solve_dfs(State,History,[]) :-

final_state(State).

solve_dfs(State,History,[Move|Moves]) :-

move(State,Move),

update(State,Move,State1),

legal(State1),

not member(State1,History),

solve_dfs(State1,[State1|History],Moves).

test_dfs(Moves) :-

initial_state(State), solve_dfs(State,[State],Moves).

Лаба 4

Изменить

tst_dfs(moves):-

Initial_state(State),

Solve_dfs(State,[State],Moves).

Решить задачу о миссионерах и каннибалах.

Условие.

На берегу реки стоят 3 миссионера и 3 каннибала. Им надо переправиться на другой берег.

Ограничения. Лодка вмещает 2 человека. И нельзя оставлять на берегу не миссионеров ни каннибалов в меньшинстве. Лодка сама плавать не может. В лодке руководитель.