问题描述
我正在解决经典的传教士(M)和食人族(C)问题，左岸的开始状态是3 M和3 C，右岸的目标状态是3M和3C.我已经完成了程序中的基本功能，并且需要实现BFS和DFS之类的搜索策略.
I am working on solving the classic Missionaries(M) and Cannibals(C) problem, the start state is 3 M and 3 C on the left bank and the goal state is 3M, 3C on the right bank. I have complete the basic function in my program and I need to implemet the search-strategy such as BFS and DFS.
基本上，我的代码是从Internet学习的.到目前为止，我可以使用DFS方法成功运行该程序，但是我尝试使用BFS运行，它始终返回false.这是我的第一个SWI-Prolog程序，找不到我的代码的问题所在.
Basically my code is learn from the Internet. So far I can successfuly run the program with DFS method, but I try to run with BFS it always return false. This is my very first SWI-Prolog program, I can not find where is the problem of my code.
这是我的代码的一部分，希望您能帮助我找到它的问题
Here is part of my code, hope you can help me find the problem of it
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代码进行更改，但它不起作用.
I use findall to find all possible path before go to next level. Only the one pass the safe() will be consider as possible next state. The state will not use if it already exist. Since my program can run with DFS so I think there is nothing wrong with move() and safe() predicate. My BFS predicate is changing base on my DFS code, but its not work.
推荐答案
如果将深度优先的搜索直接映射到Prolog的搜索，则有一种非常简单的方法可以将深度优先的搜索程序转换为宽度优先的程序. .这种技术称为迭代加深.
There is a very simple way to turn a depth-first search program into a breadth-first one, provided the depth-first search is directly mapped to Prolog's search. This technique is called iterative deepening.
只需添加一个附加参数即可确保搜索仅进行N步.所以是dfs版本:
Simply add an additional argument to ensure that the search will only go N steps deep.So a dfs-version:
dfs(State) :-
final(State).
dfs(State1) :-
state_transition(State1, State2),
dfs(State2).
通过添加深度参数将
转换为bfs.例如.通过使用 successor-arithmetics :
Is transformed into a bfs by adding an argument for the depth. E.g. by using 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).
A goal bfs(State,s(s(s(0)))) will now find all derivations requiring 3 or less steps. You still can perform dfs! Simply use bfs(State,X).
要查找所有派生，请使用natural_number(X), bfs(State,X).
To find all derivations use natural_number(X), bfs(State,X).
通常使用列表而不是s(X)号很有用.此列表可能包含所有中间状态或执行的特定转换.
Often it is useful to use a list instead of the s(X)-number. This list might contain all intermediary states or the particular transitions performed.
您可能会犹豫使用此技术，因为它似乎会重新计算许多中间状态(重复扩展状态").毕竟，它首先用一个步骤搜索所有路径，然后最多两个步骤，然后最多三个步骤...但是，如果您的问题是搜索问题，则隐藏在state_transition/2中的分支因子将缓解该问题.高架.要看到这一点，请考虑一个2的分支因子:我们的开销只有2倍！通常，有很容易的方法来恢复该系数2:例如，通过加快state_transition/2或final/1来加快速度.
You might hesitate to use this technique, because it seems to recompute a lot of intermediary states ("repeatedly expanded states"). After all, first it searches all paths with one step, then, at most two steps, then, at most three steps... However, if your problem is a search problem, the branching factor here hidden within state_transition/2 will mitigate that overhead. To see this, consider a branching factor of 2: We only will have an overhead of a factor of two! Often, there are easy ways to regain that factor of two: E.g., by speeding up state_transition/2 or final/1.
但是最大的优点是，与天真dfs相比，它不占用很多空间.
But the biggest advantage is that it does not consume a lot of space - in contrast to naive dfs.
这篇关于在Prolog中使用广度优先搜索(BFS)解决食人族/传教士?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！