基于航班成本的计划计划

Question

假设有一张飞机清单，定义如下：

plane(rome,berlin).
plane(berlin,london).
plane(london,lisboa).
plane(london,dublin).
plane(dublin,paris).
plane(rome,paris).
plane(berlin,paris).

我会解决这个问题，找出两个城市之间的所有路线，方法如下：

route(Dep, Arr, [Dep, Arr]) :- plane(Dep, Arr).
route(Dep, Arr, [Dep|C]) :- plane(Dep, Z), route(Z, Arr, C).

例如，用

?- route(rome,paris,P).

我获得：

P = [rome, paris] 

P = [rome, berlin, paris] 

P = [rome, berlin, london, dublin, paris] 

假。

如果我加上价格的话，问题就来了。

plane(rome,berlin,20).
plane(berlin,london,14).
plane(london,lisboa,44).
plane(london,dublin,99).
plane(dublin,paris,44).
plane(rome,paris,4).
plane(berlin,paris,6).

我有两个问题：

• 最后一个错误代表什么？
• 我怎样才能得到所有路线的总价格和便宜的清单？

Answer 1

正如评论中指出的那样，false意味着找不到更多的解决方案。

要获得成本，首先要将成本作为累加器参数添加到谓词中：

route(Dep, Arr, Route, Cost) :-
    route(Dep, Arr, Route, 0, Cost).
route(Dep, Arr, [Dep, Arr], AccCost, FinalCost) :-
    plane(Dep, Arr, Cost),
    FinalCost is AccCost + Cost.
route(Dep, Arr, [Dep|C], AccCost, FinalCost) :-
    plane(Dep, Z, Cost),
    NewCost is AccCost + Cost,
    route(Z, Arr, C, NewCost, FinalCost).

然后，route(Dep, Arr, Route, Cost)将依次生成每个路由。如果你想把它们列在列表中，你可以用setof/3来完成

list_of_routes(Dep, Arr, Routes) :-
    setof(C-R, route(Dep, Arr, R, C), Routes).

这将产生一个类似于Cost-Route的元素列表，这些元素由升序Cost排序。

要获得最便宜的路线，请从列表中的第一个元素开始：

cheapest_route(Dep, Arr, Route, Cost) :-
    setof(C-R, route(Dep, Arr, R, C), [Cost-Route|_]).