Найти кратчайший путь в DLV

Question

Я пытаюсь найти все пути в графе с минимальным расстоянием, используя DLV. Скажем, у меня есть следующий график:

Я ожидаю получить предикаты (я надеюсь, что я не пропустить какой-нибудь):

• путь (а, б, 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), я получаю пути, которых не должно быть, например, путь (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.     

Solution без списков (с помощью 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() предполагает, что край графика двунаправлен.