Prolog中的寻路

Question

我正在努力教自己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).

Iff 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的解决方案.

Answer 1

欢迎来到Prolog!问题本质上是当你进入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中意味着添加一个"开放集"参数来包含您尚未尝试的解决方案,并且在每个节点首先尝试在开放集中进行某些操作然后将该节点的可能性添加到打开集的末尾.当开放集熄灭时,你已经尝试了每个节点.对于一些路径发现问题,它无论如何都是比深度优先搜索更好的解决方案.您可以尝试的另一件事是将路径分离为已访问和未来的组件,并仅检查访问的组件.只要你没有在当前步骤中生成一个循环,你可以放心,你根本就没有生成循环,没有必要担心未来的步骤.

你说问题的方式让我相信你不想要一个完整的解决方案,只是一个提示,所以我认为这就是你所需要的.如果那不对,请告诉我.