0

I am having trouble with the following problem in Prolog, I have several facts in a knowledge base for example:

flight(rome,london,ba,1500,150,400).
flight(london,newyork,airfrance,600,60,200).
flight(rome,paris,airfrance,1200,120,500).  
flight(paris,newyork,airfrance,600,60,200).
flight(newyork,london,ba,1500,240,300).

I am only interested in getting a list of all possible routes from X to Y. I understand that I must use a recursive rule and that I have to add the places visited to a list to stop the cycle running over and over as the flight paths in the knowledge base have several cycles.

what I have so far is:

flight_route(X,Y):-
   flight(X,Y,A,B,C,D).

trip(X,X,[]).
trip(X,Z,T) :-
   flight_route(Y,Z),
   not(member(Y,T)),
   trip(X,Y,[Y|T]).

for some reason, when I look at the trace, the rule is failing when it tries to check that not(member(Y,T)) but I cant understand why this is the case.

user2928132
  • 25
  • 4

2 Answers2

1

More generally,

trip(X,Y) :-
   closure0(flight_route,X,Y).

See the definition of closure0/3

Community
  • 1
  • 1
false
  • 10,264
  • 13
  • 101
  • 209
0

The problem is in your definition of the trip/3 predicate. Try:

trip(X, X, _).
trip(X, Z, T) :-
   flight_route(X, Y),
   \+ member(Y, T),
   trip(Y, Z, [Y| T]).

In the first clause, when you're at your destination, it doesn't matter how you got there. Hence the (anonymous) variable in the third argument. Also, is likely more efficient to find a path starting from the origin point rather then the destination point. A possible issue might also be how you're calling the trip/3 predicate. Be sure to call it with an empty list passed on the third argument (if you don't ground T, the call \+ member(Y, T) will always fail). Or define a trip/2 argument to abstract that implementation detail:

trip(X, Y) :-
    trip(X, Y, []).
Paulo Moura
  • 18,373
  • 3
  • 23
  • 33
  • Thank you for your reply, I can see how your suggestion makes sense, but one thing that I am not sure of is how to write the list T. After making the changes you suggested I can query for example (rome,newyork). which returns True. However I am unsure how to return and write to the console all the possibilities of the list T. When I query (rome,newyork,T). I am getting a False result. Thanks again for your advice. – user2928132 Nov 02 '14 at 16:20
  • Hint: you could use an **additional** argument to return the path between two connected airports. The (current) list argument is just to avoid cycles. – Paulo Moura Nov 02 '14 at 16:28
  • Thank you for your answer Paulo. I think I got it now. – user2928132 Nov 11 '14 at 23:07