Обход DAG + стоимость в Прологе

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

Спасибо.


graph-traversal prolog swi-prolog
person Hello Ward    schedule 03.06.2018    source источник

Ответы (2)


arrow_upward
3
arrow_downward

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

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

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

так далее

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

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

person user27815    schedule 03.06.2018

arrow_upward
1
arrow_downward

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

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]. Пустой путь вообще не путь.

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

person Will Ness    schedule 03.06.2018