Recursion Problems in Prolog

Tag: recursion , prolog , backtracking Author: lcxxxxx Date: 2011-11-10

I'm having some difficulties in prolog, I'm trying to write a predicate that will return all paths between two cities, although at the moment it returns the first path it finds on an infinite loop. Not sure where I'm going wrong but I've been trying to figure this out all day and I'm getting nowhere.

Any help that could be offered would be appreciated.

go:-
    repeat,
    f([],0,lon,spa,OP,OD),
    write(OP),
    write(OD),
    fail.

city(lon).
city(ath).
city(spa).
city(kol).

path(lon,1,ath).
path(ath,3,spa).
path(spa,2,kol).
path(lon,1,kol).

joined(X,Y,D):-
    path(X,D,Y);path(Y,D,X).

f(Ci_Vi,Di,De,De,PaO,Di):-
    append([De],Ci_Vi,PaO),
    !.
f(Cities_Visited,Distance,Start,Destination,Output_Path,Output_Distance):-
    repeat,
    city(X),
    joined(Start,X,D),
    not_member(X,Cities_Visited),
    New_Distance is Distance + D,
    f([Start|Cities_Visited],New_Distance,X,Destination,Output_Path,Output_Distance).

not_member(X,List):-
    member(X,List),
    !,
    fail.
not_member(X,List).

The output I'm expecting here is [spa,ath,lon]4 [spa,kol,lon]3.

Once again, any help would be appreciated.

Many thanks in advance.

Best Answer

Your solution is essentially correct. Type f([],0,lon,spa,OP,OD), and you get the first path as expected. The only error I can see is that you're using repeat within your search predicate, which is why you keep computing the same solution. repeat is almost never necessary within business logic - backtracking for solutions is already built into the REP loop. Take it out, and you'll get the second path as expected, and then (correctly) failure.

comments:

I just tried taking out the repeat and I still get the infinite repeat of my first answer.
That's because you've got another repeat in your main loop (the go directive). Use the f([],0,lon,spa,OP,OD) goal directly, and press ; after the first solution, and it'll show you the second one. To enumerate solutions programmatically, you need to use findall/3, not repeat.
Ah, I see, thank you very much for the help, you are a good person.