时间戳

首页 > 解决方案 > Prolog 中的 DAG 遍历 + 成本

prolog - Prolog 中的 DAG 遍历 + 成本

问题描述

我正在尝试实现一个 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]

谢谢。

标签： prologswi-prologgraph-traversal

解决方案

我见过的最好的图遍历代码是在这个问题中： 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 ;

ETC

所以我们得到一个节点列表，其中包含到达下一个节点的成本。然后，您可以像这样简单地总结它们：

?- 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

ETC

或者您可以调整代码以在保存总和计算时计算总和。

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

推荐阅读