Prolog not finding all solutions

user_7473854 0
Viewed 232

Modelling the stops of an underground tube line like so:

stop(line1, 1, station1).
stop(line1, 2, station2).
stop(line1, 3, station3).
stop(line1, 4, station4).
stop(line1, 5, station5).
stop(line2, 1, station2).
stop(line2, 2, station4).

where stop(L, N, S) means S is the N'th stop on line L, I'm trying to define path(S1, S2, P) that calculates possible paths between S1 and S2.

Here a path is a list of "segments", a segment being a journey along the same line, i.e. segment(L,S1,S2) represents the continuous journey from S1 to S2 along line L. So a possible solution to path(a,d,P) is P=[segment(line1, a, b), segment(line2, b, d)], i.e. go from a to b on line1, then go from b to d on line2.

An additional constraint is that a path should not include the same line more than once.

I've got the following:

segment(L, S1, S2) :- stop(L, N1, S1), stop(L, N2, S2), N2>N1.
line_present_in_path(_, []) :- false.
line_present_in_path(L, [H|_]) :- segment(L, _, _) = H.
line_present_in_path(L, [_|T]) :- line_present_in_path(L, T).
path(S1, S2, [H]) :- segment(_, S1, S2) = H, H.
path(S1, S2, [H|T]) :- segment(L, S1, X) = H, H, \+line_present_in_path(L, T), path(X, S2, T).

but something peculiar happens. If I explicitly specify all the parameters myself, it recognises it as a correct path:

?- path(station1, station4, [segment(line1, station1, station2),segment(line2, station2, station4)]).
true ;
false.

However, if I ask it to calculate all paths, it only finds one path, different to the path it just verified as correct:

?- path(station1, station4, P).
P = [segment(line1, station1, station4)] ;
false.

I must admit I'm new to Prolog so I might be missing something basic. But, I really can't understand why it can verify a given path as correct, but it doesn't find that path when trying to find all paths.

prolog
1 Answers

The bug is in the second clause for the path/3 predicate. Rewriting it for clarity:

path(S1, S2, [segment(L, S1, X)|T]) :-
    \+ line_present_in_path(L, T),
    path(X, S2, T).

With a goal such as path(station1, station4, P), you call the line_present_in_path/2 predicate with a variable in the second argument. That call always succeeds and thus its negation always fails. In general, you should be cautious of only using \+/1 with a sufficiently instantiated argument.

Hint: to solve the bug, use an additional argument to the path predicate to hold the stations found so far. E.g.

path(S1, S2, Path) :-
    path(S1, S2, Path, []).

path(S1, S2, Path, Visited) :-
    ...

You can use the de facto standard member/2 predicate to check if a station is already in the path and add it to the visited list otherwise. Path finding is a common question and you will find several related answers here in StackOverflow. But try first to solve it on your own.

user_6346290
Related