农民山羊狼和白菜在Prolog通过广度优先搜索

我想解决农民，山羊，狼，白菜谜语使用广度优先技术，我遇到了一些问题。当我尝试收集树的第二级的所有有效组合时，它会失败。这里是相关的代码，农民山羊狼和白菜在Prolog通过广度优先搜索

extend([Node|Path], NewPaths) :- 
    bagof([NewNode, Node|Path], 
     (s(Node, NewNode), not(member(NewNode, [Node|Path]))), 
     NewPaths), 
    !. 
extend(Path, []). 

s(state(X,X,W,C), state(Y,Y,W,C)) 
    :- opp(X,Y), not(unsafe(state(Y,Y,W,C))). 
s(state(X,G,X,C), state(Y,G,Y,C)) 
    :- opp(X,Y), not(unsafe(state(Y,G,Y,C))). 
s(state(X,G,W,X), state(Y,G,W,Y)) 
    :- opp(X,Y), not(unsafe(state(Y,G,W,Y))). 
s(state(X,G,W,C), state(Y,G,W,C)) 
    :- opp(X,Y), not(unsafe(state(Y,G,W,C))). 
s(state(F,G,W,C), state(F,G,W,C)) 
    :- fail. 

opp(e,w). 
opp(w,e). 

unsafe(state(X,Y,Y,C)) :- opp(X,Y). 
unsafe(state(X,Y,W,Y)) :- opp(X,Y). 

not(P) :- 
    P, !, fail 
    ; 
    true.

扩展谓词是我看到的问题。当我在第一个层次上运行它，它工作正常，

?- extend([state(e,e,e,e)],[X]). 
X = [state(w,w,e,e),state(e,e,e,e)]

当我运行第二个层次，它失败了，

?- extend([state(w,w,e,e)],[X]). 
no

应该返回类似以下，

X = [state(e,w,e,e),state(w,w,e,e),state(e,e,e,e)]

在此先感谢您的帮助，因为非常感谢。

问候，

达里安

来源

2014-03-06 sweet_bojangles

你看看[食人族/传教士（http://stackoverflow.com/questions/9937315/solve-cannibals-missionaries-using-breadth-first- search-bfs-in-prolog？rq = 1）问题？它非常相似。 –

@DanielLyons - 感谢您的链接，这对完成我的程序非常有帮助。 –

如果我询问你的代码，我得到

?- extend([state(w,w,e,e)],X). 
X = [[state(e, e, e, e), state(w, w, e, e)], [state(e, w, e, e), state(w, w, e, e)]]

X是列表的列表。然后，我简化伸展/ 2谓词，

extend([Node|Path], [Node|NewPaths]) :- 
    bagof(NewNode, 
     (s(Node, NewNode), not(member(NewNode, Path))), 
     NewPaths).

，我得到

?- extend([state(w,w,e,e)],X). 
X = [state(w, w, e, e), state(e, e, e, e), state(e, w, e, e)].

请注意，我用[X]查询扩展/ 2是不。

BTW这个条款是没用的

s(state(F,G,W,C), state(F,G,W,C)) 
    :- fail.

来源

2014-03-06 06:16:15 CapelliC

谢谢，这是让我通过我的路障的答案。 –

农民山羊狼和白菜在Prolog通过广度优先搜索

回答

相关问题