使用 Prolog 查找无向无环图中的所有路径

Question

`我想在加权无向无环图中打印从节点 a 到达节点 e 的所有方法。但是我的程序错过了一些很长的路线。

这是我的程序。

%Declare all the edges
edge(a,b,1). 
edge(a,c,6). 
edge(b,c,4). 
edge(b,d,3). 
edge(b,e,1). 
edge(c,d,1). 
edge(d,e,1).

% Two nodes are adjacent if there exists a edge between them
adj(X, Y, W) :- edge(X, Y, W).
adj(Y, X, W) :- edge(Y, X, W).

% return 0 weight and empty path because path is empty to reach the same node 
% from the node itself and therefor no wirght as well.
findpath(X, X, 0, []).

% if X and Y are adjacent then append Y to X into the Path Variable
findpath(X,Y,Weight,Path) :- adj(X,Y,Weight),
                             append([X],[Y],Path). 

% if X and Y are not adjacent, then consider nodes who are adjacent to Y with 
% weight W2 ,  recursively call path predicate replacing Y with A and W1 with W2
% add their weight - W as W1 + W2 and append to Path. 
findpath(X,Y,Weight,Path) :- not(adj(X,Y,Weight)), 
                             edge(A,Y,Weight1), 
                             findpath(X,A,Weight2,P1),
                             Weight is Weight1+Weight2, 
                             append(P1,[Y],Path).

Output

`2 ?- findpath(a, e, W, P).
W = 2,
P = [a, b, e] ;
W = 2,
P = [a, b, e] ;
W = 5,
P = [a, b, d, e] ;
W = 5,
P = [a, b, d, e] ;
W = 8,
P = [a, c, d, e] ;
W = 8,
P = [a, c, d, e] ;
false.

我的程序漏掉了 a, b, c, e 和 a, b, c, d,e。我不明白为什么？ 此外，它也会重复输出。`

Answer 1

（没有路径“abce”，因为

c

和

e

之间没有联系）

adj/3

描述了与

edge/3

所做的完全相同的解决方案。你们在头脑和目标中交换了论点。只交换一次。使用

path/4

给你所有的非循环路径。然后你需要增加重量。

:- set_prolog_flag(double_quotes, chars).

adj(X, Y, W) :- edge(X, Y, W).
adj(X, Y, W) :- edge(Y, X, W).

adj(X,Y) :-
   adj(X,Y,_).

?- path(adj, Path, a,e).
   Path = "abcde"
;  Path = "abde"
;  Path = "abe"
;  Path = "acde"
;  Path = "acdbe"
;  Path = "acbde"
;  Path = "acbe"
;  false.

?- setof(t,path(adj, Path, a,e),_).
   Path = "abcde"
;  Path = "abde"
;  Path = "abe"
;  Path = "acbde"
;  Path = "acbe"
;  Path = "acdbe"
;  Path = "acde".
?- path(adj, Path, a,Y).
   Path = "a", Y = a
;  Path = "ab", Y = b
;  Path = "abc", Y = c
;  Path = "abcd", Y = d
;  Path = "abcde", Y = e
;  Path = "abd", Y = d
;  Path = "abde", Y = e
;  Path = "abdc", Y = c
;  Path = "abe", Y = e
;  Path = "abed", Y = d
;  Path = "abedc", Y = c
;  Path = "ac", Y = c
;  Path = "acd", Y = d
;  Path = "acde", Y = e
;  Path = "acdeb", Y = b
;  Path = "acdb", Y = b
;  Path = "acdbe", Y = e
;  Path = "acb", Y = b
;  Path = "acbd", Y = d
;  Path = "acbde", Y = e
;  Path = "acbe", Y = e
;  Path = "acbed", Y = d
;  false.

Answer 2

如果你不想绕圈子，你需要保留一个“已访问”的边列表。你需要修复你的 adj/3 （这就是给你双重答案的原因！）

adj(X,Y,D) :-
    ( edge(X,Y,D)
    ; edge(Y,X,D)
    ).

path(X, Y, D, P) :-
    p(X, Y, [], D, P).

p(X, X, _, 0, [X]).
p(X, Y, V, D, [X|P]) :-
    adj(X, Z, W),
    \+ memberchk(Z, V),
    p(Z, Y, [X|V], D0, P),
    D is D0 + W.