2

我得到了一个弧列表：

arc(a,b).
arc(b,c).
arc(c,d).
arc(d,b).
arc(d,e).
arc(e,e).
arc(e,f).

我写了一组子句，它们会告诉我是否有从 nodeX到 node的路径Y。可能会出现循环，我已经解释过了。

path(X,Y) :-
    arc(X,Y).
path(X,Y) :-
    arc(X,Z),
    path(Z,Y,[X]).

path(X,Y,P) :-
    arc(X,Y).
path(X,Y,P) :-
    \+ member(X,P),
    arc(X,Z),
    append([X],P,L),
    path(Z,Y,L).

我需要修改它以在成功时返回已遍历的节点列表。我不清楚我将如何做到这一点。

我假设我的基本情况类似于path2(X,Y,[X,Y]) :- arc(X,Y).但不适用于我的程序。我对上一部分的解决方案有问题，还是我只是缺少一个小修改？任何帮助，将不胜感激。谢谢！

4

3 回答 3

2

关闭...但考虑：

path(Start, End, Path) :-
    path(Start, End, [], Path).

使用起点和终点节点调用path/3将构建它们之间的路径（如果存在），并回溯以为您提供备用路线。没有节点被访问两次。这[]是一个节点累加器列表，因此我们可以在构建路径时检查我们没有绕圈子。

path(Now, End, Acc, Path) :-
    arc(Now, Mid),
    Mid == End, !,
    append(Acc, [Now, End], Path).

path(Now, End, Acc, Path) :-
    arc(Now, Mid),
    \+ member(Mid, Acc),
    path(Mid, End, [Now|Acc], Path).

这些谓词做实际的工作。第一个是基本情况，通过另一个调用到达结束节点arc/2；在这种情况下，已经建立了一条路径。第二个遍历（有向）图，但仅遍历尚未访问的节点。

所有路径都可以通过以下方式一次定位findall/3：

findall(Path, path(Start,End,Path), Paths).

对于Start和End到节点原子的绑定值。

于 2010-10-10T22:23:24.073 回答
1

移动到更高的层次并使用1作为基本习语！

%        你的二元谓词 arc/2 在这里使用
% |
% v
?-路径（弧，路径，从，到）。
   从 = 到 , 路径 = [到]
; 从 = a，到 = b，路径 = [a，b]
; 从 = a，到 = c，路径 = [a,b,c]
; 从 = a，到 = d，路径 = [a,b,c,d]
; 从 = a，到 = e，路径 = [a,b,c,d,e]
; 从 = a，到 = f，路径 = [a,b,c,d,e,f]
; 从 = b，到 = c，路径 = [b，c]
; 从 = b，到 = d，路径 = [b,c,d]
; 从 = b，到 = e，路径 = [b,c,d,e]
; 从 = b，到 = f，路径 = [b,c,d,e,f]
; 从 = c，到 = d，路径 = [c,d]
; 从 = c，到 = b，路径 = [c,d,b]
; 从 = c，到 = e，路径 = [c,d,e]
; 从 = c，到 = f，路径 = [c,d,e,f]
; 从 = d，到 = b，路径 = [d，b]
; 从 = d，到 = c，路径 = [d,b,c]
; 从 = d，到 = e，路径 = [d，e]
; 从 = d，到 = f，路径 = [d,e,f]
; 从 = e，到 = f，路径 = [e，f]
; 错误的。

脚注 1：由通用 path/4实现。

于 2015-12-21T14:12:25.297 回答
0

Sharky 给出的答案似乎对我不起作用，但下面的 mod 对我来说确实并且感觉更直接。：

path(Now, End, Acc, [Now,End]) :-
    arc(Now, End),
    \+ member(Now, Acc),
    \+ member(End, Acc).

path(Now, End, Acc, Path) :-
    arc(Now, Mid),
    \+ member(Mid, Acc),
    path(Mid, End, [Now|Acc], Path).

如果我遗漏了什么，请告诉我。

于 2015-11-17T19:04:24.540 回答