我正在尝试自学 Prolog。下面,我写了一些我认为应该返回无向图中节点之间的所有路径的代码......但它没有。我试图理解为什么这个特定的代码不起作用(我认为这将这个问题与类似的 Prolog 寻路帖子区分开来)。我在 SWI-Prolog 中运行它。有什么线索吗?
% Define a directed graph (nodes may or may not be "room"s; edges are encoded by "leads_to" predicates).
room(kitchen).
room(living_room).
room(den).
room(stairs).
room(hall).
room(bathroom).
room(bedroom1).
room(bedroom2).
room(bedroom3).
room(studio).
leads_to(kitchen, living_room).
leads_to(living_room, stairs).
leads_to(living_room, den).
leads_to(stairs, hall).
leads_to(hall, bedroom1).
leads_to(hall, bedroom2).
leads_to(hall, bedroom3).
leads_to(hall, studio).
leads_to(living_room, outside). % Note "outside" is the only node that is not a "room"
leads_to(kitchen, outside).
% Define the indirection of the graph. This is what we'll work with.
neighbor(A,B) :- leads_to(A, B).
neighbor(A,B) :- leads_to(B, A).
如果 A --> B --> C --> D 是无环路径,则
path(A, D, [B, C])
应该是真的。即,第三个参数包含中间节点。
% Base Rule (R0)
path(X,Y,[]) :- neighbor(X,Y).
% Inductive Rule (R1)
path(X,Y,[Z|P]) :- not(X == Y), neighbor(X,Z), not(member(Z, P)), path(Z,Y,P).
然而,
?- path(bedroom1, stairs, P).
是假的。为什么?我们不应该与 R1 匹配吗
X = bedroom1
Y = stairs
Z = hall
P = []
自从,
?- neighbor(bedroom1, hall).
true.
?- not(member(hall, [])).
true.
?- path(hall, stairs, []).
true .
?
事实上,如果我评估
?- path(A, B, P).
我只得到长度为 1 的解决方案。
最佳答案
欢迎来到序言!本质上,问题在于当您到达 not(member(Z, P))
时在 R1,P
仍然是一个纯变量,因为评估还没有到 path(Z, Y, P)
定义它。关于 Prolog 的令人惊讶但鼓舞人心的事情之一是 member(Ground, Var)
将生成包含 Ground
的列表并用 Var
统一它们:
?- member(a, X).
X = [a|_G890] ;
X = [_G889, a|_G893] ;
X = [_G889, _G892, a|_G896] .
这具有令人困惑的副作用,即检查未实例化列表中的值总是会成功,这就是
not(member(Z, P))
的原因。将始终失败,导致 R1 始终失败。您获得所有 R0 解决方案而没有任何 R1 解决方案这一事实表明 R1 中的某些内容导致它始终失败。毕竟,我们知道 R0 有效。如果你交换这两个目标,你会得到你想要的第一个结果:
path(X,Y,[Z|P]) :- not(X == Y), neighbor(X,Z), path(Z,Y,P), not(member(Z, P)).
?- path(bedroom1, stairs, P).
P = [hall]
如果您要求其他解决方案,则会出现堆栈溢出。这是因为在更改之后,我们很高兴使用
path(Z,Y,P)
尽快生成带循环的解决方案。 , 只是在事后用 not(member(Z, P))
丢弃它们. (顺便说一句,为了稍微提高效率,我们可以切换到 memberchk/2
而不是 member/2
。当然,更快地做错误的事情并没有多大帮助。:)我倾向于将其转换为广度优先搜索,这在 Prolog 中意味着添加一个“开放集”参数来包含您尚未尝试过的解决方案,并且在每个节点首先尝试开放集中的某些内容,然后将该节点的可能性添加到开放集的末尾。当开放集熄灭时,您已经尝试了可以到达的每个节点。对于某些路径查找问题,无论如何它是比深度优先搜索更好的解决方案。您可以尝试的另一件事是将路径分成访问过的组件和 future 的组件,并且只检查访问过的组件。只要您在当前步骤中没有生成循环,您就可以放心,您根本不会生成循环,无需担心 future 的步骤。
你提出问题的方式让我相信你不想要一个完整的解决方案,只是一个提示,所以我认为这就是你所需要的。如果这不对,请告诉我。
关于Prolog中的寻路,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15468082/