如果我有一个问题的边列表，例如“显示从一个被认为是危险的城市到一个被认为是安全的城市的路线”，那么......
dangerous(oakland).
safe(portland).
move(rome,plane,portland).
move(portland,plane,rome).
move(halifax,train,gatwick).
move(gatwick,car,rome).
move(portland,plane,newyork).
move(oakland,plane,rome).
move(oakland,plane,gatwick).
move(halifax,train,gatwick).
move(gatwick,plane,rome).
move(oakland,train,newyork).
我可以通过使用以下深度优先搜索(在SO上找到)来获取通往安全城市的路径列表...
dfs_start(Start, Goal, Path) :- phrase(dfs(Start, [], Goal), Path).
dfs(Node, _, Goal) --> [Node], { call(Goal, Node) }.
dfs(Node0, Es, Goal) --> [Node0],
{ move(Node0,_,Node1), \+ member(Node1, Es) },
dfs(Node1, [Node0|Es], Goal).
然而，我试图解决的问题是找到所有从危险城市不会通向安全城市的路径(在这种情况下只有一个奥克兰 -> 纽约。) 如果我用...调用上面的函数
dfs_start(oakland,safe,Path).
...我明白了
Path = [oakland, rome, portland] ;
Path = [oakland, gatwick, rome, portland] ;
Path = [oakland, gatwick, rome, portland] ;
...但我想做的是调用类似...
dfs_start(oakland,unsafe,Path).
...并得到...
Path = [oakland, newyork] ;
如有任何建议，我们将不胜感激!
最佳答案
问题描述不明确，也许这就是你怀疑的原因。
据我了解， unsafe(X). 显然是错误的，因为消除了每个过滤条件。你可以尝试这样简化规则(效率低下的规则我已经注释掉了，你可以删除):
% unsafe(X) :- findall(Y,safe(Y),SafeList), member(X,SafeList), !, fail.
unsafe(X) :- \+ safe(X).
编辑您与 Will Ness 交换的评论澄清了一点任务:当路径无法进一步延伸时，停止条件必须为真，并且任何安全城市都被禁止进入路径。我简化了一些代码，删除了不必要的功能，这样您就可以专注于逻辑:图是非循环的，因此不需要访问路径，并且不需要传递目标，只需使用所需的语句:
unsafe_path([Start|Path]) :-
dangerous(Start),
phrase(dfs(Start), Path).
dfs(Node) --> [Node1],
{ move(Node, _, Node1),
\+ lead_to_safe(Node1)
} -> dfs(Node1) ; {true}.
lead_to_safe(Node) :- safe(Node).
lead_to_safe(Node) :-
move(Node, _, Node1),
lead_to_safe(Node1).
测试:
?- unsafe_path(P).
P = [oakland, newyork].
如果我们添加一个虚构的城市，路径就会延长:
?- assertz(move(newyork,train,turin)).
?- unsafe_path(P).
P = [oakland, newyork, turin].
如果我们让都灵成为通往安全城市的门户:
?- assertz(move(turin,train,portland)).
?- unsafe_path(P).
P = [oakland].
关于Prolog:查找不满足目标的列表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10964995/