DLVの最短経路を見つける

Question

DLVを使用して、最小距離のグラフ内のすべてのパスを検索しようとしています。私は（私はいずれもスキップしないことを望む）述語を得るために期待してい

：

• パス（A、B、1）、パス、私は次のグラフを持っていると言います（b、a、1）、パス（b、c、1）、パス（d、a、1）、パス（a、 （c、e、1）、パス（c、e、1）、パス（c、d、2）、パス（b、e、2） ）
• path（d、a、 1）、パス（d、b、2）、パス（d、e、2）、パス（d、c、3）
• パス（e、a、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) 

3番目のルールのアイデアは、彼らが戻って（X = Z！）を予定されていない場合は2つの、既存のパスを追加したと同じエッジを結ぶ経路が既に存在ではありませんより短い距離（経路（X、Z、V）ではなく、V <L、#int（V））である。 #int（V）を追加する必要がありました。それ以外の場合、ルールは安全ではなかったからです。この安全性の問題を整数値で解決するより良い方法があるかどうかはわかりません。

このコードを実行すると（フラグN = 5で＃maxint = 5に設定すると）、そこには存在しないパス、たとえばpath（d、a、5）が得られます。 #int（V）などの問題があるかどうかは分かりませんが、すでにパス（d、a、1）があるのでこれらのパスが表示されるとは思われません。おそらくそれは#int（V）のせいだが、これをどうやって行うのか分からない。

誰も私がこれを解決するのを手助けできますか？前もって感謝します。

Answer 1

例/ spaths.dl DESからの配布。 ...以下のコメントコードを参照してください - パスを追跡するためにリストを使用して問題に

% 
% 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. 

Answer 2

ソリューション：

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. 

注述語 arc（）は、グラフのエッジが双方向であることを前提としています。