answer-set-programming - 计算有向图中两个节点之间的距离

Question

我目前正在使用 clingo 学习答案集编程，并且我真的很难计算有向图中节点之间的距离。

我知道如何针对每个距离对其进行硬编码，但这并不是真正的方法。

我目前有这个:

node(X) :- edge(X,_).
node(Y) :- edge(_,Y).

edge(X,Y) :- edge(X,Z), edge(Z,Y).

distance(X,Y,1) :- edge(X,Y).
distance(X,Y,2) :- distance(X,Z,_), distance(Z,Y,_), X != Z, Y != Z.
%distance(X,Y,D) :- ?

我知道哪些节点从第三行到达其他节点，但如何计算有向图中它们之间的距离？

Answer 1

这是程序:

node(X) :- edge(X,_) .
node(Y) :- edge(_,Y) .
num(N) :- N = #count{ X : node(X) }. % compute the number of nodes (see below)

edge(Y,X) :- edge(X,Y) .
distance(X,Y,1) :- edge(X,Y) .
distance(X,Y,D) :- distance(X,Z,D1), distance(Z,Y,D2),
                   X!=Y,         % for not allowing self-reaching paths (that are always of length 2)
                   D=D1+D2,      % sum the edges' distances
                   D<N, num(N) . % the distance is less than the number of nodes (otherwise it would loop infinitely)
min_distance(X,Y,D) :- distance(X,Y,_), #min {DD : distance(X,Y,DD)} = D .

如果你想强加0作为节点到自身的距离，只需添加以下规则:

distance(X,X,0) :- node(X) .

现在采用以下 EDB 实例:

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

执行只为谓词 min_distance/3 生成这些基本原子:

min_distance(a,b,1) min_distance(b,c,1) min_distance(a,c,1) min_distance(a,d,1) min_distance(d,e,1) min_distance(e,d,1) min_distance(d,a,1) min_distance(c,a,1) min_distance(c,b,1) min_distance(b,a,1) min_distance(e,a,2) min_distance(a,e,2) min_distance(c,d,2) min_distance(b,d,2) min_distance(d,c,2) min_distance(d,b,2) min_distance(e,b,3) min_distance(e,c,3) min_distance(c,e,3) min_distance(b,e,3)

如果您想将结果限制为“单向”距离，您可以添加 X<=Y在最后一条规则的正文中，获取:

min_distance(a,b,1) min_distance(b,c,1) min_distance(a,c,1) min_distance(a,d,1) min_distance(d,e,1) min_distance(a,e,2) min_distance(c,d,2) min_distance(b,d,2) min_distance(c,e,3) min_distance(b,e,3)