2

我正在尝试使用 DLV 在图中以最小距离查找所有路径。假设我有以下图表：

图形

我期待获得谓词（我希望我不要跳过任何谓词）：

  • 路径（a，b，1），路径（a，d，1），路径（a，e，1），路径（a，c，2）
  • 路径（b，a，1），路径（b，c，1），路径（d，d，2），路径（b，e，2）
  • 路径（c，b，1），路径（c，e，1），路径（c，a，2），路径（c，d，3）
  • 路径（d，a，1），路径（d，b，2），路径（d，e，2），路径（d，c，3）
  • 路径（e，a，1），路径（e，c，1），路径（e，d，2），路径（e，b，2）

我假设您可以向左或向右移动拱门。所以，我尝试了以下方法：

path(X, Y, 1) :- arc(X, Y).
path(Y, X, 1) :- arc(X, Y).
path(X, Z, L) :- path(X, Y, M), path(Y, Z, N), 
                 X!=Z, 
                 L = M + N,
                 not path(X, Z, V), V < L, #int(V)

第三条规则的想法是添加 2 条现有路径，如果它们不返回 (X!=Z) 并且还没有一条路径以更短的距离连接相同的边（不是路径（X，Z，V）， V < L，#int(V))。我必须添加#int(V)，否则规则不安全。我不知道是否有更好的方法可以用整数值解决这个安全问题。

当我运行此代码时（使用标志 -N=5 设置 #maxint=5），我得到不应该存在的路径，例如 path(d,a,5)。我不知道问题出在#int(V) 还是其他问题上，但我不希望这些路径出现，因为我已经有了路径(d,a,1)。可能是因为#int(V) 但我不知道如何正确地做到这一点。

谁能帮我解决这个问题？提前致谢。

4

2 回答 2

1

使用列表跟踪路径问题的解决方案：

path(X, Y, [X, Y], 1) :- arc(X, Y).
path(Y, X, [Y, X], 1) :- arc(X, Y).
path(X, Z, P, D) :- path(X, Y, P1, D1),
                    path(Y, Z, P2, 1),
                    #insLast(P1, Z, P), 
                    D = D1 + 1,
                    not #member(Z, P1).
shortest_path(X, Y, D) :-   node(X), node(Y), 
                            #min{L: path(X, Y, P, L)} = D.

不需要列表的解决方案（在CapelliC的帮助下）

path(X, Y, 1)   :-  arc(X,Y).
path(Y, X, 1)   :-  arc(X,Y).
path(X, Y, D)   :-  path(X,Z,D0), arc(Z,Y),
                    #count{A: node(A)} = Max,
                    D0<Max, X != Y,
                    D = D0+1.

shorter_paths(X, Y, D) :- node(X), node(Y), 
                          #min{L: path(X, Y, L)} = D.

请注意，我们需要使用谓词node()定义所有节点，并且谓词arc()假定图的边是双向的。

于 2016-09-16T06:27:31.013 回答
0

来自DES发行版的示例/spaths.dl 。请参阅下面的注释代码... -

%
% Shortest Paths in a Graph
%
% Datalog Formulation
%
% Program: Shortest paths in a graph
% Author : Fernando Sáenz-Pérez
% Date   : September, 2009

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

path(X,Y,1) :- 
  edge(X,Y).
path(X,Y,L) :-
  path(X,Z,L0),
  edge(Z,Y),
  count(edge(A,B),Max),
  L0<Max,
  L is L0+1.

spaths(X,Y,L) :-
   min(path(X,Y,Z),Z,L).


% Note that the following is not stratifiable in DES

%sp(X,Y,1) :- 
%  edge(X,Y).
%sp(X,Y,L) :-
%  sp(X,Z,L0),
%  not(shorter(X,Z,L0)), 
%  edge(Z,Y),
%  L is L0+1.

%shorter(X,Y,L) :-
%  sp(X,Y,L0),
%  L0<L.
于 2016-09-15T11:19:29.053 回答