在Prolog中使用广度优先搜索（BFS）解决食人族/传教士？

Question

我正在研究经典的传教士（M）和食人族（C）问题，左岸的开始状态是3 M和3 C，右岸的目标状态是3M和3C。我已经完成了程序中的基本功能，并且需要实现搜索策略，例如BFS和DFS。

基本上，我的代码是从Internet学习。到目前为止，我可以使用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-version：

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：我们的开销仅为因子2！通常，有简单的方法来恢复该因子2：例如，通过加快state_transition/2或final/1的速度。

但是最大的好处是，它与原始dfs相比，不会占用很多空间。

Answer 2

Logtalk发行版包含一个示例“搜索”，该示例实现了用于状态空间搜索的框架：

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

包括“经典”问题（农民，传教士和食人族，难题8，桥梁，水壶等）。 Ivan Bratko的著作《人工智能的Prolog编程》改编了一些搜索算法（并得到了许可）。该示例还包括一个性能监视器，该监视器可以为您提供有关搜索方法性能的一些基本统计信息（例如，分支因子和状态转换数）。该框架易于扩展，适用于新问题和新搜索方法。

Answer 3

请参阅此要点以查看可能的解决方案，可能会对您的问题有所帮助。

要点：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..

该方法将告诉您是否有解决方案，但不会解释解决方案。一种可以解释的方法是使用事实状态/ 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

再见

源代码：水壶状态http://www.xlog.ch/jekejeke/forward/jugs3.p

源代码：水壶的状态和路径http://www.xlog.ch/jekejeke/forward/jugs3path.p

Answer 6

[如果仍然有人对python解决方案感兴趣，请查找以下内容。为了简化起见，只考虑了左侧的传教士和食人族。

这是解决方案树。

#M #missionaries in left
#C #cannibals in left
# B=1left
# B=0right

def is_valid(state):
    if(state[0]>3 or state[1]>3 or state[2]>1 or state[0]<0 or state[1]<0 or state[2]<0 or (0<state[0]<state[1]) or (0<(3-state[0])<(3-state[1]))):
        return False
    else:
        return True

def generate_next_states(M,C,B):
    moves = [[1, 0, 1], [0, 1, 1], [2, 0, 1], [0, 2, 1], [1, 1, 1]]
    valid_states = []
    for each in moves:
        if(B==1):next_state = [x1 - x2 for (x1, x2) in zip([M, C, B], each)]
        else:next_state = [x1 + x2 for (x1, x2) in zip([M, C, B], each)]
        if (is_valid(next_state)):
            # print(next_state)
            valid_states.append(next_state)
    return valid_states
solutions = []
def find_sol(M,C,B,visited):
    if([M,C,B]==[0,0,0]):#everyne crossed successfully
        # print("Solution reached, steps: ",visited+[[0,0,0]])
        solutions.append(visited+[[0,0,0]])
        return True
    elif([M,C,B] in visited):#prevent looping
        return False
    else:
        visited.append([M,C,B])
        if(B==1):#boat is in left
            for each_s in generate_next_states(M,C,B):
                find_sol(each_s[0],each_s[1],each_s[2],visited[:])
        else:#boat in in right
            for each_s in generate_next_states(M,C,B):
                find_sol(each_s[0],each_s[1],each_s[2],visited[:])


find_sol(3,3,1,[])

solutions.sort()
for each_sol in solutions:
    print(each_sol)