1

我正在 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 .

如您所见，在第三条路线之后，循环开始发生。我想避免它们，但我有点不确定如何去做。

4

1 回答 1

2

这里有一些“交易技巧”可以使程序工作，更高效：而不是附加，“cons”累加器中的节点，并累积成本。这需要另外两个变量，但结果过程是尾递归的，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).
于 2013-04-26T23:52:34.050 回答