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

Question

我正在解决经典的传教士(M)与野人(C)问题，起始状态是左岸有3个传教士和3个野人，目标状态是右岸有3个传教士和3个野人。我的程序基本功能已经完成，现在需要实现搜索策略，如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代码进行更改，但它没有起作用。

- Shawn Lien

---

findall/3的元数为3，但是你的代码中只使用了一个参数。同时你使用了变量Visisted和Visited。它们应该是一样的吗？尝试缩进你的代码以使其更易读，并添加一些注释。否则，很难理解你使用findall/3调用和后续块所要实现的目标。 - twinterer

Answer 1

有一种非常简单的方法可以将深度优先搜索程序转换为广度优先搜索程序，前提是深度优先搜索直接映射到Prolog搜索。这个技巧被称为迭代加深。

只需添加一个额外的参数以确保搜索仅深入N步即可将其转换为广度优先搜索版本。

因此，dfs版本如下：

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

通过添加深度参数，将其转换为广度优先搜索。例如，可以使用successor-arithmetics：

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

一个目标 bfs(State,s(s(s(0)))) 现在将找到所有需要三步或更少的推导。你仍然可以执行 dfs！只需使用 bfs(State,X)。

要查找所有推导，请使用 natural_number(X), bfs(State,X)。

通常使用列表而不是 s(X) 数字很有用。该列表可能包含所有中间状态或执行的特定转换。

您可能会犹豫使用此技术，因为它似乎会重新计算许多中间状态（“重复扩展的状态”）。毕竟，它首先搜索所有一步路径，然后最多两步，然后最多三步...但是，如果您的问题是搜索问题，则隐藏在 state_transition/2 中的分支因子将减轻这种开销。为了看到这一点，考虑一个分支因子为 2：我们只会有两倍的开销！通常，有简单的方法来恢复这个两倍的因子：例如，通过加速 state_transition/2 或 final/1。

但最大的优势是它不会消耗太多空间 - 与天真的 dfs 相反。

- false

---

[对于深度优先搜索] 只需使用 bfs（State，X） 即可。这太棒了。 :) - Will Ness

Answer 2

Logtalk发行版包括一个名为“searching”的示例，它实现了一个状态空间搜索框架：

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

“经典”问题包括（农夫、传教士和食人族、8 迷宫、桥牌、水罐等）。一些搜索算法是根据 Ivan Bratko 的书籍《人工智能的 Prolog 编程》进行的改编（获得许可）。该示例还包括一个性能监视器，可以为您提供有关搜索方法性能的一些基本统计数据（例如分支因素和状态转换数）。该框架易于扩展，适用于新问题和新搜索方法。

- Paulo Moura

Answer 3

如果有人对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)

- Gihan Gamage

Answer 4

请参考此代码片段以查看一个可能的解决方案，或许对您的问题有所帮助。

代码片段: 在Prolog中解决传教士和野人问题

- Juanito Fatas

Answer 5

我已经用深度优先和广度优先解决了问题，试图清晰地将可重用部分与状态搜索算法分开：

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的谓词，清楚地说明何时停止搜索。

- CapelliC

---

一个状态空间搜索框架，例如我在上面引用的Logtalk“搜索”示例中实现的那样，允许您使用任何状态空间和搜索方法的组合。 - Paulo Moura

@Paulo Moura：这个框架是一个相当复杂的系统，如何帮助Shawn Lien？我发现breadth_first1包含了一个复杂的expand/expandall，它们互相递归（乍一看），我无法确定它是否实现了终止条件。这让我想到了我自己制作的solve_bfs，虽然很简单，但显然是通用的，可能是错误的。我刚刚测试了与dfs比较... - CapelliC

一些搜索算法，包括广度优先搜索，是在获得许可的情况下从Ivan Bratko的书《人工智能的Prolog编程》中改编而来。该书详细解释了这些算法。请注意，您可以轻松地将自己的广度优先算法版本添加到框架中，并使用提供的示例进行测试。 - Paulo Moura

Answer 6

如果您的Prolog系统具有前向链接器，您还可以通过前向链接规则对其进行建模来解决问题。以下是在Jekejeke Minlog中解决水壶问题的示例。状态由谓词state/2表示。

首先，您需要编写一个过滤重复项的规则。该规则指出，如果一个state/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..

这种方法可以告诉你是否有解决方案，但不能解释解决方案。使其可解释的一种方法是使用fact state/4而不是fact state/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

- user502187