使用Prolog中的广度优先搜索(BFS)解决食人族/传教士问题？

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的搜索,有一种非常简单的方法可以将深度优先搜索程序转换为广度优先搜索程序.这种技术称为迭代加深.

只需添加一个额外的参数,以确保搜索只会走N步.所以一个dfs版本:

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

通过为深度添加参数将其转换为bfs.例如,使用后继算术:

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相比.