2

我对 Prolog 完全陌生，并且正在研究图表。我在网上发现了一个问题，要求我指定一个节点，然后列出从该节点可到达的所有简单路径。没有目标节点，只需尝试所有可能性并返回所有这些路径。

我将图表示为路径（X，Y），表示从 X 到 Y 的有向边。

我建立了这个简单的周期性知识库：

path(a, b).
path(b, c).
path(c, d).
path(d, a).
path(d, e).
path(d, f).
path(f, g).

如果我查询 all_paths(a, P)，那么 P 应该是（假设 ; 是垃圾邮件，直到所有选项用尽）。

P = [a].
P = [a, b].
P = [a, b, c].
P = [a, b, c, d].
P = [a, b, c, d, e].
P = [a, b, c, d, f].
P = [a, b, c, d, f, g].

作为初学者，我写了类似的东西：

all_paths(Source, P) :- all_paths(Source, P, []).
all_paths(_, [], _).
all_paths(Source, [Source | P], Visited) :-
    path(Source, Node),
    \+ memberchk(Node, Visited),
    all_paths(Node, P, [Node | Visited]).

好的，稍微改了一下，现在我回来了：

X = [] ? ;
X = [a] ? ;
X = [a,b] ? ;
X = [a,b,c] ? ;
X = [a,b,c,d] ? ; <- Here it does not pick up e
X = [a,b,c,d] ? ;
X = [a,b,c,d] ? ;
X = [a,b,c,d,f] ? ;

有人可以帮助弄清楚如何正确获取所有路径吗？

4

2 回答 2

3

无需重新发明轮子！

首先，我们将您的谓词重命名path/2为edge/2：

edge(a, b).
edge(b, c).
edge(c, d).
edge(d, a).
edge(d, e).
edge(d, f).
edge(f, g).

然后，我们结合使用 ：path/4edge/2

?- path(edge,Path,From,To).
  Path = [To],          From = To
; Path = [a,b],         From = a, To = b
; Path = [a,b,c],       From = a, To = c
; Path = [a,b,c,d],     From = a, To = d
; Path = [a,b,c,d,e],   From = a, To = e
; Path = [a,b,c,d,f],   From = a, To = f
; Path = [a,b,c,d,f,g], From = a, To = g
; Path = [b,c],         From = b, To = c
; Path = [b,c,d],       From = b, To = d
; Path = [b,c,d,a],     From = b, To = a
; Path = [b,c,d,e],     From = b, To = e
; Path = [b,c,d,f],     From = b, To = f
; Path = [b,c,d,f,g],   From = b, To = g
; Path = [c,d],         From = c, To = d
; Path = [c,d,a],       From = c, To = a
; Path = [c,d,a,b],     From = c, To = b
; Path = [c,d,e],       From = c, To = e
; Path = [c,d,f],       From = c, To = f
; Path = [c,d,f,g],     From = c, To = g
; Path = [d,a],         From = d, To = a
; Path = [d,a,b],       From = d, To = b
; Path = [d,a,b,c],     From = d, To = c
; Path = [d,e],         From = d, To = e
; Path = [d,f],         From = d, To = f
; Path = [d,f,g],       From = d, To = g
; Path = [f,g],         From = f, To = g
; false.

编辑

如果我们只对从 开始的路径感兴趣a，我们只需编写：

?- path(edge,Path,a,To).
  Path = [a],                To = a
; Path = [a, b],             To = b
; Path = [a, b, c],          To = c
; Path = [a, b, c, d],       To = d
; Path = [a, b, c, d, e],    To = e
; Path = [a, b, c, d, f],    To = f
; Path = [a, b, c, d, f, g], To = g
; false.
于 2015-10-16T18:41:40.440 回答
1

“交换”节点和源

all_paths(_, [], _).
all_paths(Source, [Node | P], Visited) :-
    path(Source, Node),
    \+ memberchk(Node, Visited),
    all_paths(Node, P, [Source | Visited]).

产量

?- all_paths(a, P).
P = [] ;
P = [b] ;
P = [b, c] ;
P = [b, c, d] ;
P = [b, c, d, e] ;
P = [b, c, d, f] ;
P = [b, c, d, f, g] ;
false.

它缺少起始节点，我只需在“驱动程序”谓词中添加：

all_paths(Source, [Source|P]) :- all_paths(Source, P, []).

产量

?- all_paths(a, P).
P = [a] ;
P = [a, b] ;
P = [a, b, c] ;
P = [a, b, c, d] ;
P = [a, b, c, d, e] ;
P = [a, b, c, d, f] ;
P = [a, b, c, d, f, g] ;
false.

风格说明：如果我们遵循一些关于 IO 参数的规则，则代码更具可读性。输出参数应该在输入参数之后。好吧，这并不总是适用...

于 2015-10-16T19:16:28.863 回答