Решать каннибалов/миссионеров, используя поиск по ширине (BFS) в Prolog?

Question

Я работаю над решением проблемы классических миссионеров (M) и каннибалов (C), начальное состояние - 3 M и 3 C на левом берегу, а состояние цели - 3M, 3C на правом берегу. У меня есть основная функция в моей программе, и мне нужно реализовать стратегию поиска, такую ​​как BFS и DFS.

В основном мой код учится в Интернете. Пока я могу успешно запустить программу с помощью метода DFS, но я пытаюсь запустить с BFS, он всегда возвращает false. Это моя первая программа SWI-Prolog, я не могу найти, где проблема с моим кодом.

Вот часть моего кода, надеюсь, что вы можете помочь мне найти проблему его

solve2 :- 
    bfs([[[3,3,left]]],[0,0,right],[[3,3,left]],Solution), 
    printSolution(Solution). 

bfs([[[A,B,C]]],[A,B,C],_,[]). 
bfs([[[A,B,C]|Visisted]|RestPaths],[D,E,F],Visisted,Moves) :- 
    findall([[I,J,K],[A,B,C]|Visited]), 
    (
     move([A,B,C],[I,J,K],Description), 
     safe([I,J,K]), 
     not(member([I,J,K],Visited) 
    ), 
    NewPaths 
    ), 
    append(RestPaths,NewPaths,CurrentPaths), 
    bfs(CurrentPaths,[D,E,F],[[I,J,K]|Visisted],MoreMoves), 
    Moves = [ [[A,B,C],[I,J,K],Description] | MoreMoves ]. 


move([A,B,left],[A1,B,right],'One missionary cross river') :- 
    A > 0, A1 is A - 1. 
    % Go this state if left M > 0. New left M is M-1 
. 
. 
. 
. 
. 
safe([A,B,_]) :- 
    (B =< A ; A = 0), 
    A1 is 3-A, B1 is 3-B, 
    (B1 =< A1; A1 =0). 

Я использую FindAll найти все возможные пути, прежде чем перейти к следующему уровню. Только один проход safe() будет рассматриваться как возможное следующее состояние. Государство не будет использовать, если оно уже существует. Поскольку моя программа может работать с DFS, я думаю, что нет ничего плохого в предикате move() и safe(). Мой предикат BFS меняет базу на мой код DFS, но он не работает.

Answer 1

Существует очень простой способ превратить программу поиска по глубине в ширину, при условии, что поиск по глубине непосредственно сопоставляется с поиском Prolog. Этот метод называется iterative deepening.

Просто добавьте дополнительный аргумент, чтобы гарантировать, что поиск будет идти только на N шагов. Так ДФС-версия:

dfs(State) :- 
    final(State). 
dfs(State1) :- 
    state_transition(State1, State2), 
    dfs(State2). 

превращается в BFS, добавив аргумент для глубины. Например. с помощью successor-arithmetics:

bfs(State, _) :- 
    final(State). 
bfs(State1, s(X)) :- 
    state_transition(State1, State2), 
    bfs(State2, X). 

А цель bfs(State,s(s(s(0)))) теперь найти все выкладки, требующие 3 или меньше шагов. Вы все еще можете выполнять dfs! Просто используйте bfs(State,X).

Чтобы найти все производные от natural_number(X), bfs(State,X).

Часто полезно использовать список вместо s (X) -номера. Этот список может содержать все промежуточные состояния или конкретные выполненные переходы.

Вы можете смутить эту технику, потому что она, похоже, перепродает много промежуточных состояний («неоднократно расширенные состояния»). В конце концов, сначала он ищет все пути одним шагом, затем не более чем на два шага, затем максимум на три шага ... Однако, если ваша проблема является проблемой поиска, коэффициент ветвления, скрытый в state_transition/2, уменьшит эти накладные расходы. Чтобы увидеть это, рассмотрим коэффициент ветвления 2: у нас будет только накладные расходы в два раза! Часто существуют простые способы восстановить этот коэффициент из двух: например, путем ускорения state_transition/2 или final/1.

Но самым большим преимуществом является то, что он не потребляет много места - в отличие от наивных dfs.

Answer 2

Распределение Logtalk включает в себя пример, «поиск», который реализует основу для государственного космического поиска:

https://github.com/LogtalkDotOrg/logtalk3/tree/master/examples/searching

«классические» проблемы включены (фермеров, миссионеров и людоедов, головоломка 8, мост, водяные кувшины и т. д.).Некоторые алгоритмы поиска адаптированы (с разрешения) из книги Ивана Братко «Пролог программирования для искусственного интеллекта». В этом примере также есть монитор производительности, который может дать вам некоторую базовую статистику по эффективности метода поиска (например, коэффициенты ветвления и количество переходов состояний). Рамку легко расширить, как для новых задач, так и для новых методов поиска.

Answer 3

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

Gist: solve Missionaries and cannibals in Prolog

Answer 4

Я решил с глубиной-первых, а затем в ширину, пытаясь четко отделить многоразовые часть от состояния алгоритма поиска:

miss_cann_dfs :- 
    initial(I), 
    solve_dfs(I, [I], Path), 
    maplist(writeln, Path), nl. 

solve_dfs(S, RPath, Path) :- 
    final(S), 
    reverse(RPath, Path). 
solve_dfs(S, SoFar, Path) :- 
    move(S, T), 
    \+ memberchk(T, SoFar), 
    solve_dfs(T, [T|SoFar], Path). 

miss_cann_bfs :- 
    initial(I), 
    solve_bfs([[I]], Path), 
    maplist(writeln, Path), nl. 

solve_bfs(Paths, Path) :- 
    extend(Paths, Extended), 
    ( member(RPath, Extended), 
     RPath = [H|_], 
     final(H), 
     reverse(RPath, Path) 
    ; solve_bfs(Extended, Path) 
    ). 

extend(Paths, Extended) :- 
    findall([Q,H|R], 
     ( member([H|R], Paths), 
      move(H, Q), 
      \+ member(Q, R) 
     ), Extended), 
    Extended \= []. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
% problem representation 
% independent from search method 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

initial((3,3, >, 0,0)). 
final((0,0, <, 3,3)). 

% apply a *valid* move 
move((M1i,C1i, Bi, M2i,C2i), (M1f,C1f, Bf, M2f,C2f)) :- 
    direction(Bi, F1, F2, Bf), 
    who_move(MM, CM), 
    M1f is M1i + MM * F1, M1f >= 0, 
    C1f is C1i + CM * F1, C1f >= 0, 
    (M1f >= C1f ; M1f == 0), 
    M2f is M2i + MM * F2, M2f >= 0, 
    C2f is C2i + CM * F2, C2f >= 0, 
    (M2f >= C2f ; M2f == 0). 

direction(>, -1, +1, <). 
direction(<, +1, -1, >). 

% valid placements on boat 
who_move(M, C) :- 
    M = 2, C = 0 ; 
    M = 1, C = 0 ; 
    M = 1, C = 1 ; 
    M = 0, C = 2 ; 
    M = 0, C = 1 . 

Я предлагаю вам структурируйте свой код аналогичным образом, с предикатом, похожим на extend/2, который будет ясно, когда остановить поиск.

Answer 5

Если ваша система Prolog имеет переадресацию, вы также можете решить проблему , моделируя ее с помощью правил прямой цепочки. Здесь является примером того, как решить проблему кувшина в Jekejeke Minlog. Состояние представлено предикатным состоянием/2.

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

% avoid duplicate state 
unit &:- &- state(X,Y) && state(X,Y), !. 

Тогда вы даете правила, утверждать, что поиск не должен быть продолжен , когда конечное состояние достиг. В настоящем примере мы проверяем , что один из сосудов содержит 1 литр воды:

% halt for final states 
unit &:- state(_,1), !. 
unit &:- state(1,_), !. 

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

% emptying a vessel 
state(0,X) &:- state(_,X). 
state(X,0) &:- state(X,_). 

% filling a vessel 
state(5,X) &:- state(_,X). 
state(X,7) &:- state(X,_). 

% pouring water from one vessel to the other vessel 
state(Z,T) &:- state(X,Y), Z is min(5,X+Y), T is max(0,X+Y-5). 
state(T,Z) &:- state(X,Y), Z is min(7,X+Y), T is max(0,X+Y-7). 

Теперь мы можем использовать вперед сцепления двигатель, чтобы сделать работу для нас. Это не будет делать итеративный углубление, и он также не сделает ширину в первую очередь. Это будет просто разрешение единицы по стратегии, которая жадна для , учитывая этот факт, и процесс завершается только тогда, когда пространство состояний является конечным. Вот результат:

?- post(state(0,0)), posted. 
state(0, 0). 
state(5, 0). 
state(5, 7). 
state(0, 7). 
Etc.. 

подход покажет вам, есть ли решение, но не объясняет решение. Один из подходов, чтобы объяснить это, заключается в использовании факта state/4 вместо состояния факта/2. Последние два аргумента используются для списка действий и длины списка.

Правило, которое позволяет избежать дубликатов, затем изменяется для правила, которое выбирает наименьшее решение.Она гласит:

% choose shorter path 
unit &:- &- state(X,Y,_,N) && state(X,Y,_,M), M<N, !. 
unit &:- state(X,Y,_,N) && &- state(X,Y,_,M), N<M. 

Тогда мы получим:

?- post(state(0,0,[],0)), posted. 
state(0, 0, [], 0). 
state(5, 0, [fl], 1). 
state(5, 7, [fr,fl], 2). 
state(0, 5, [plr,fl], 2). 
Etc.. 

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

?- post(state(0,0,[],0)), state(1,7,L,_), explain(L). 
0-0 
fill left vessel 
5-0 
pour left vessel into right vessel 
0-5 
fill left vessel 
5-5 
pour left vessel into right vessel 
3-7 
empty right vessel 
3-0 
pour left vessel into right vessel 
0-3 
fill left vessel 
5-3 
pour left vessel into right vessel 
1-7 

До свидания

Исходный код: Water Jug State
http://www.xlog.ch/jekejeke/forward/jugs3.p

Исходный код: Вода Кувшин Состояние и пути
http://www.xlog.ch/jekejeke/forward/jugs3path.p