2

如果我有一个问题的边缘列表，例如“告诉我从一个被认为是危险的城市到一个被认为是安全的城市的路线”，那么......

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

任何建议将不胜感激！

4

1 回答 1

2

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

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

编辑您与 Will Ness 交换的评论澄清了一点任务：当路径无法进一步扩展时，停止条件必须为真，并且禁止任何安全城市进入路径。我简化了一点代码，去掉了不必要的特性，所以你可以专注于逻辑：图是非循环的，所以访问路径不是必需的，而不是传递一个 Goal，只需使用所需的语句：

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].
于 2012-06-10T06:05:18.373 回答