Prolog - Help fixing a rule

Question

I have a database full of facts such as:

overground(newcrossgate,brockley,2).
overground(brockley,honoroakpark,3).
overground(honoroakpark,foresthill,3).
overground(foresthill,sydenham,2).
overground(sydenham,pengewest,3).
overground(pengewest,anerley,2).
overground(anerley,norwoodjunction,3).
overground(norwoodjunction,westcroydon,8).
overground(sydenham,crystalpalace,5).
overground(highburyandislington,canonbury,2).
overground(canonbury,dalstonjunction,3).
overground(dalstonjunction,haggerston,1).
overground(haggerston,hoxton,2).
overground(hoxton,shoreditchhighstreet,3).

example: newcrossgate to brockley takes 2 minutes.

I then created a rule so that if I enter the query istime(newcrossgate,honoroakpark,Z). then prolog should give me the time it takes to travel between those two stations. (The rule I made is designed to calculate the distance between any two stations at all, not just adjacent ones).

istime(X,Y,Z):- istime(X,Y,0,Z); istime(Y,X,0,Z).
istime(X,Y,T,Z):- overground(X,Y,Z), T1 is T + Z.
istime(X,Y,Z):- overground(X,A,T), istime(A,Y,T1), Z is T + T1.
istime(X,Y,Z):- overground(X,B,T), istime(B,X,T1), Z is T + T1.

it seems to work perfectly for newcrossgate to the first couple stations, e.g newcrossgate to foresthill or sydenham. However, after testing newcrossgate to westcroydon which takes 26mins, I tried newcrossgate to crystalpalace and prolog said it should take 15 mins...despite the fact its the next station after westcroydon. Clearly somethings wrong here, however it works for most of the stations while coming up with a occasional error in time every now and again, can anyone tell me whats wrong? :S

Answer 1

To make it work you need to do the reverse of both journeys stated in your last clause. Keep the predicate as it is, istime(X,Y,Z) and just make another clause containing the reverse journeys. This way it works with all the stations. (Tried and Tested)

Answer 2

Have you tried to cycle through answers with ;? 26mins is not the shortest time between newcrossgate and westcroydon...

Edit: my bad! Apparently the shorter results were due to a bug in your code (see my comment about the 4th clause). However, your code is correct, 15mins is the shortest route between newcrossgate and crystalpalace. Only because there is a route that goes from newcrossgate to westcroydon, then crystalpalace, that doesn't mean it's the shortest route, or the route your program will yield first.

Update: if you're running into problems to find answers to some routes, I'd suggest changing the 3rd clause to:

istime(X,Y,_,Z):- overground(X,A,T), istime(A,Y,T1), Z is T + T1.

The reason is simple: your first clause swaps X with Y, which is good, since with that you're saying the routes are symmetrical. However, the 3rd clause does not benefit from that, because it's never called by the swapped one. Ignoring the 3rd argument (which you're not using anyway) and thus letting the 1st clause call the 3rd might fix your issue, since some valid routes that were not used previously will be now.

(also: I agree with Nicholas Carey's answer, it would be better to use the third argument as an accumulator; but as I said, ignoring it for now might just work)

Answer 3

This is essentially the same problem as your previous question, the only difference is that you need to accumulate the time as you go.

One thing I see is that your "public" predicate, istime/3 tries to do too much. All it should do is seed the accumulator and invoke the worker predicate istime/4. Since you're looking for route/time in both directions, the public predicate should be just

istime( X , Y , Z ) :- istime( X , Y , 0 , Z ) .
istime( X , Y , Z ) :- istime( Y , X , 0 , Z ) .

The above is essentially the first clause of your istime/3 predicate

istime(X,Y,Z):- istime(X,Y,0,Z); istime(Y,X,0,Z).

The remaining clauses of istime/3, the recursive ones:

istime(X,Y,Z):- overground(X,A,T), istime(A,Y,T1), Z is T + T1.
istime(X,Y,Z):- overground(X,B,T), istime(B,X,T1), Z is T + T1.

should properly be part of istime/4 and have the accumulator present. That's where your problem is.

Give it another shot and edit your question to show the next iteration. If you still can't figure it out, I'll show you some different ways to do it.

Some Hints

1. Your "worker" predicate will likely look a lot like your earlier "find a route between two stations" exercise, but it will have an extra argument, the accumulator for elapsed time.

2. There are two special cases. If you use the approach you used in your "find a route between two stations" solution, the special cases are

   • A and B are directly adjacent.
   • A and B are connected via at least one intermediate stop.

There's another approach as well, that might be described as using lookahead, in which case the special cases are

• A and B are the same, in which case you're arrived.
• A and B are not and are connected by zero or more intermediate stops.

FWIW, You shouldn't necessarily expect the route with the shortest elapsed time or the minimal number of hops to be the first solution found. Backtracking will produce all the routes, but the order in which they are found has to do with the order in which the facts are stored in the database. A minimal cost search of the graph is another kettle of fish entirely.