DAG Traversal + Стоимость в Прологе

Question

Я пытаюсь реализовать алгоритм обхода 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]

Спасибо.

Answer 1

В вашем коде есть одна ошибка.Это:

path(Start, Start, [], 0).

должно было быть

path(Start, Start, [Start], 0).

в противном случае Path в

path(Start, Finish, [Start|Path], C) :-
    edge(Start, X, Cost),
    path(X, Finish, Path, RCost),
    C is Cost + RCost.

возвращается пустым из этого (первого) предложения, но то, что выздесь действительно предполагается, что он должен содержать Finish в качестве последнего элемента.

Действительно, это также следует из логического прочтения вашего предиката.Если path(Start, Start, Path, Cost) должен быть успешным, это означает, что есть Path от Start до Start, что равно непустому [Start].Пустой путь - это вообще не путь.

Теперь все указанные пути действительны.О некоторых сообщают несколько раз, но это другая проблема.

Answer 2

Лучший код прохождения графа, который я когда-либо видел, находится в этом вопросе: Определение пути / следа / прогулки

Мы можем адаптировать это для вашего случая так:

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 ;

и т. Д.

Таким образом, мы получаем список узлов со стоимостью, чтобы добраться до следующего узла.Затем вы можете просто суммировать их следующим образом:

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

и т. Д.

, или вы можете адаптировать код для подсчета суммы по мере сохранения вычисления суммы.

В этомЯ думаю, что мы предполагаем, что существует только одно ребро от любого одного узла к другому.