CODEWITHSUNDEEP
prologpath-finding
Matheus208
Matheus208

Reputation: 1429

Prolog Pathfinding with Prioritisation

I have an assignment to write a Prolog program that lists paths between two Underground (subway) stations, but it should favour the paths with less line changes (it should stay as long as possible in the same line before switching lines).

I've come up with a mock scenario and this code, while it correctly lists some paths (I know I still have to code the cycle detection), does not prioritise same-line segments as it should.

My router is:

route(X,Y,[drive(X,Y,L)],_) :- road(X,Y,L).

%route(From, To, Directions, Lines_Visited).
route(X,Y,[drive(X,Z,L)|R],Ls) :-
    take(Ls,L,_),     %prioritise same-line paths
    road(X,Z,L),  
    route(Z,Y,R,Ls), !.

route(X,Y,[drive(X,Z,L)|R],Ls) :-
    road(X,Z,L),       %if no same-line pathes exist, try different line
    route(Z,Y,R,[Ls|L]).

Where take/3 is

take([H|T], H, T).

One test scenario would be:

road(a,b,x).
road(b,c,x).
road(c,d,x).
road(d,e,x).
road(e,f,x).
road(b,f,y).
road(f,g,x).

%a - b - c - d - e - f - g
%    |_______________|

If I try route(a,f,X). I'd get the path a -> b -> f , which changes lines once, and THEN the one-line path a->b->c->d->e->f.

Apparently my prioritisation is not working and I can't come up with a different way of doing it. Can someone please shed some light and point me to a direction to solve this more efficiently?

Upvotes: 1

Views: 348

Answers (1)

CapelliC
CapelliC

Reputation: 60014

Your code need much restructuring. Basically, you're not using at all the info about which line is used in current path (take/3 is useless, since it doesn't bind the third argument). Here is my take on this. Add the loop detection, now that you have the 'seen so far' nodes...

%route(From, To, Directions, Lines_Visited).
route(X,X,RPath,Path) :- reverse(RPath,Path).
route(X,Y,[Last|R],Ls) :-
    Last = [drive(X,Z,L)|_], %prioritise same-line paths
    road(X,Z,L),  
    route(Z,Y,R,Ls).
route(X,Y,PathSoFar,Ls) :-
    road(X,Z,L),       %if no same-line pathes exist, try different line
    route(Z,Y,[road(X,Z,L)|PathSoFar],Ls).

test:

?- route(a,f,[],X).
X = [road(a, b, x), road(b, c, x), road(c, d, x), road(d, e, x), road(e, f, x)] ;
X = [road(a, b, x), road(b, f, y)] ;
false.

Upvotes: 1

Related Questions