Избегание циклов в ориентированном графе

Question

Я пишу простую программу в SWI-Prolog для запуска через ориентированный граф от одного узла к другому. У меня есть проблемы с тем, чтобы избежать циклов, хотя мне нужна была бы помощь. У каждого ребра есть стоимость, связанная с ним, и каждый узел имеет «время пребывания».

edge(a, b, 10). 
edge(a, c, 20). 
edge(c, d, 50). 
edge(c, b, 40). 
edge(d, b, 30). 
edge(d, a, 40). 

stay(a, 10). 
stay(c, 30). 
stay(b, 15). 
stay(d, 20). 

route(Start, End, Route, Cost) :- 
    edge(Start, End, Cost), 
    append([Start], [End], Route). 

route(Start, End, Route, Cost) :- 
    edge(Start, Next, FirstCost), 
    stay(Next, StayTime), 
    route(Next, End, NewRoute, SecondCost), 
    Cost is FirstCost + SecondCost + StayTime, 
    append([Start], NewRoute, Route). 

я получаю следующий результат в swipl:

?- route(a,b,Routing,Cost). 
Routing = [a, b], 
Cost = 10 ; 
Routing = [a, c, b], 
Cost = 90 ; 
Routing = [a, c, d, b], 
Cost = 150 ; 
Routing = [a, c, d, a, b], 
Cost = 180 ; 
Routing = [a, c, d, a, c, b], 
Cost = 260 . 

Как вы можете видеть, после того, как 3-й маршрут, циклы начинают происходить. Я бы хотел их избежать, но я не уверен, как это сделать.

Answer 1

Вот некоторые «трюки торговли», чтобы сделать работу программы и более эффективной: вместо добавления «минусы» узлы в аккумуляторе , а также аккумулируют затраты. Для этого требуются еще две переменные, но в результате получается хвост рекурсивный, а Prolog может применять базовую оптимизацию, которая делает сложность программы линейной в пространстве.

route(Start, End, PathAcc, CostAcc, [End,Start|PathAcc], CostPath) :- 
    edge(Start, End, CostEdge), 
    CostPath is CostAcc + CostEdge. 

route(Start, End, PathAcc, CostAcc, Path, Cost) :- 
    edge(Start, Next, CostEdge), 
    \+ memberchk(Next, PathAcc), 
    stay(Next, StayTime), 
    CostNext is CostAcc + CostEdge + StayTime, 
    route(Next, End, [Start|PathAcc], CostNext, Path, Cost). 

Затем, чтобы восстановить оригинальный интерфейс, мы добавим точку входа:

route(Start, End, Route, Cost) :- 
    route(Start, End, [], 0, RevRoute, Cost), reverse(RevRoute, Route).