3

我正在解决经典的 Missionaries(M) 和 Cannibals(C) 问题，起始状态是左岸的 3M 和 3C，目标状态是右岸的 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 代码进行更改，但它不起作用。

4

6 回答 6

6

有一种非常简单的方法可以将深度优先搜索程序转换为广度优先程序，前提是深度优先搜索直接映射到 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 的分支因子：我们只会有 2 倍的开销！通常，有一些简单的方法可以重新获得这两个因素：例如，通过加速state_transition/2或final/1。

但最大的优点是它不会消耗大量空间——与天真的 dfs 相比。

于 2012-03-30T15:58:01.633 回答
1

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

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

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

于 2012-03-30T23:17:10.253 回答
1

如果有人仍然对 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)
于 2020-04-29T05:37:28.363 回答
0

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

要点：在 Prolog 中解决传教士和食人者

于 2012-04-01T03:07:35.150 回答
0

我先解决了深度优先，然后解决了广度优先，试图清楚地将可重用部分与状态搜索算法分开：

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 的谓词来明确何时停止搜索。

于 2012-04-01T18:14:46.530 回答
-1

如果你的 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..

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

于 2014-01-14T15:53:55.637 回答