Prolog:找到一个不能满足目标的列表

Question

如果我有一个边缘列表，比如"告诉我从一个被认为危险的城市到一个被认为安全的城市的路线"，这样......

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] ;

任何建议将不胜感激！

Answer 1

问题描述模棱两可，也许这就是您怀疑的原因。据我了解，unsafe(X).显然是错误的，因为消除了每个过滤条件。您可以尝试以这种方式简化规则（我已经注释掉了低效的规则，您可以删除它）：

% unsafe(X) :- findall(Y,safe(Y),SafeList), member(X,SafeList), !, fail.
unsafe(X) :- + safe(X).

编辑你与威尔·尼斯交换的评论澄清了一点任务：当路径不能再延伸时，停止条件必须为真，任何安全的城市都被禁止路径。我简化了一些代码，删除了不必要的功能，因此您可以专注于逻辑：graph 是非循环的，因此不需要访问路径，而不是传递 Goal，只需使用 required 语句：

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].