CODEWITHSUNDEEP
listrecursionprologtransitive-closure
user2928132
user2928132

Reputation: 25

Trouble getting a list of trip paths in Prolog

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.

Upvotes: 0

Views: 867

Answers (2)

false
false

Reputation: 10142

More generally,

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

See the definition of closure0/3

Upvotes: 1

Paulo Moura
Paulo Moura

Reputation: 18683

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, []).

Upvotes: 0

Related Questions