Prolog中的DAG遍历+ Cost

Question

我正在尝试实现一个DAG遍历算法，该算法也可以获得边之间的成本。我想我已经很接近了，但是查询总是返回无效的路径。有没有人能看一眼，看看我这里漏掉了什么？

edge(b, a, 5).
edge(a, u, 10).
edge(u, o, 140).
edge(u, r, 130).
edge(r, o, 20).
edge(r, v, 50).
edge(o, v, 45).
edge(b, v, 20).

path(Start, Start, [], 0).
path(Start, Finish, [Start, Finish], C) :-
    edge(Start, Finish, Cost),
    C is Cost.
path(Start, Finish, [Start|Path], C) :-
    edge(Start, X, Cost),
    path(X, Finish, Path, RCost),
    C is Cost + RCost.

我在试着运行path(b, v, S, C).。它会生成所有有效路径，但也会生成一些无效路径。

C = 20,
S = [b, v]
C = 200,
S = [b, a, u, o, v]
C = 200,
S = [b, a, u, o]
C = 195,
S = [b, a, u, r, v]
C = 210,
S = [b, a, u, r, o, v]
C = 210,
S = [b, a, u, r, o]
C = 195,
S = [b, a, u, r]
C = 20,
S = [b]

谢谢。

Answer 1

我所见过的最好的图遍历代码是这个问题：Definition of a path/trail/walk

我们可以根据您的情况修改为：

edge(b, a, 5).
edge(a, u, 10).
edge(u, o, 140).
edge(u, r, 130).
edge(r, o, 20).
edge(r, v, 50).
edge(o, v, 45).
edge(b, v, 20).


:- meta_predicate path(3,?,?,?).

:- meta_predicate path(3,?,?,?,+).

path(R_3, [X0|Ys], X0,X) :-
   path(R_3, Ys, X0,X, [X0]).

path(_R_3, [], X-0,X-0, _).
path(R_3, [X1-Cost2|Ys], X0-Cost,X, Xs) :-
   call(R_3, X0,X1,Cost),
   non_member(X1, Xs),
   path(R_3, Ys, X1-Cost2,X, [X1-Cost2|Xs]).

non_member(_E, []).
non_member(E, [X-_Cost|Xs]) :-
   dif(E,X),
   non_member(E, Xs).

然后我们可以查询：

?- path(edge,Path,From,To).
Path = [_22918-0],
From = To, To = _22918-0 ;
Path = [b-5, a-0],
From = b-5,
To = a-0 ;
Path = [b-5, a-10, u-0],
From = b-5,
To = u-0 ;
Path = [b-5, a-10, u-140, o-0],
From = b-5,
To = o-0 ;
Path = [b-5, a-10, u-140, o-45, v-0],
From = b-5,
To = v-0 ;

等

因此，我们得到了一个节点列表，其中包含到达下一个节点的成本。然后，您可以简单地将它们求和如下：

?- path(edge,Path,From,To), pairs_values(Path,Values), sumlist(Values,Sum).
Path = [_24478-0],
From = To, To = _24478-0,
Values = [0],
Sum = 0 ;
Path = [b-5, a-0],
From = b-5,
To = a-0,
Values = [5, 0],
Sum = 5 ;
Path = [b-5, a-10, u-0],
From = b-5,
To = u-0,
Values = [5, 10, 0],
Sum = 15 ;
Path = [b-5, a-10, u-140, o-0],
From = b-5,
To = o-0,
Values = [5, 10, 140, 0],
Sum = 155 

等

或者，您可以修改代码，以便在保存sum计算时计算sum。

在这里，我认为我们假设从任何一个节点到另一个节点只有一条边。

Answer 2

您的代码中有一个错误。这一点：

path(Start, Start, [], 0).

应该是

path(Start, Start, [Start], 0).

否则Path in

path(Start, Finish, [Start|Path], C) :-
    edge(Start, X, Cost),
    path(X, Finish, Path, RCost),
    C is Cost + RCost.

从那个(第一个)子句返回为空，但是您在这里真正想要的是让它包含Finish作为最后一个元素。

实际上，这也是从您的谓词的逻辑读取中得出的。如果path(Start, Start, Path, Cost)要成功，这意味着有一个从Start到Start的Path，它是非空的[Start]。空路径根本不是路径。

现在，所有报告的路径都是有效的。其中一些被多次报告，但这是另一个问题。