在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).

如果 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).

为什么会是false呢？难道我们不应该通过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的解决方案。

- user1889797

Answer 1

欢迎来到Prolog！本质上，问题在于当您到达R1中的not(member(Z, P))时，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中意味着添加一个“开放集”参数来包含尚未尝试的解决方案，并在每个节点中首先尝试open set中的某些内容，然后将该节点的可能性添加到open set的末尾。当open set被消耗尽时，您已经尝试了所有可以到达的节点。对于某些路径查找问题，这比深度优先搜索更好。您还可以尝试将路径分成访问过的和未来的组件，并仅检查访问过的组件。只要当前步骤中未生成循环，您就可以确保根本不会生成循环，无需担心未来的步骤。

你提出问题的方式使我相信你不想要完整的解决方案，只是提示，所以我认为这就是你需要的全部。如果这不对，请告诉我。

- Daniel Lyons