0

Suppose to have a list of air planes defined as follow:

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

I will solve the problem to find all routes between two cities in the following way:

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

For example with

?- route(rome,paris,P).

I obtain:

P = [rome, paris] 

P = [rome, berlin, paris] 

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

false.

The problem comes if I add prices, e.g.,

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).

I have two questions:

  • What does the last false represent?
  • How can I get the list of all the routes with the total price and the cheaper one?
lurker
  • 56,987
  • 9
  • 69
  • 103
abc
  • 11,579
  • 2
  • 26
  • 51
  • 2
    For `false`, look at [this answer](http://stackoverflow.com/a/27256298/772868) – false Dec 10 '14 at 15:20
  • Don't you get a `;` after `P = [rome, paris]` ? I really expect this to be there ... – false Dec 10 '14 at 15:28
  • I'm using swi-prolog, I get one solution at a time, and I press "space" to see all – abc Dec 10 '14 at 15:36
  • 1
    In the versions of SWI I have, I see a `;` after each answer, even if I press SPACE to get the next answer. – false Dec 10 '14 at 15:50

1 Answers1

1

As pointed out in the comments, false means no more solutions were found.

To get the costs, you'll want to add the cost as an accumulator argument to your predicate to start with:

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).

Then, route(Dep, Arr, Route, Cost) will generate each route in turn. If you want them in a list, you can do it with setof/3:

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

This will yield a list of elements that look like Cost-Route, ordered by ascending Cost.

To get the cheapest route, pull off the first element of that list:

cheapest_route(Dep, Arr, Route, Cost) :-
    setof(C-R, route(Dep, Arr, R, C), [Cost-Route|_]).
lurker
  • 56,987
  • 9
  • 69
  • 103
  • What does C-R in setof stand for? I've seen setof with just 1 variable as first argument. I've tried to remove "-R" and I have the list of all the paths. – abc Dec 10 '14 at 18:23
  • 1
    @newbie, All that does is create a Prolog *term*, `C-R` where `C` and `R` are variables. I could have used something like `foo(C,R)` or a little list, `[C,R]`. But I chose `C-R` since it is useful method of representing a pair of values. It's equivalent to the term, `'-'(C,R)`. So the `setof` collects all pairs of values of `C` and `R` and puts them in the form, `C-R` (note that you aren't limited to one variable in what you collect with `setof`). In Prolog, if you sort like terms, they go in order of the first argument, then the second, etc. – lurker Dec 10 '14 at 18:33
  • Thank you, how can that predicate be written in more comprensible way for prolog beginners like me? – abc Dec 10 '14 at 18:51
  • 1
    You mean `list_of_routes`? It's not going to get much simpler since you're trying to collect, in a list, routes and associated cost. The cost is a number and the route is a list. You'd need to choose a way to represent those together (I chose `C-R`, but, as I mentioned, you can use `[C,R]` or `cost_route(C,R)` or just `(C,R)`...) and that will have to be part of the `setof` call. For example, using `cost_route(C,R)` would look like, `list_of_routes(Dep, Arr, Routes) :- setof(cost_route(C,R), route(Dep, Arr, R, C), Routes).` – lurker Dec 10 '14 at 18:58