Pathfinding

pathfinding.pl

adjacent(ems,phy).
adjacent(ems,soccer).
adjacent(soccer,cunn).
adjacent(ems,chem).
adjacent(chem,lap).
adjacent(lap,bridge).
adjacent(lap,arch).
adjacent(arch,engel).
adjacent(cunn,engel).
adjacent(bridge,union1).
adjacent(union1,lubar).
adjacent(union1,union2).
adjacent(union2,bolton).
adjacent(bolton,lubar).
adjacent(union2,union3).
adjacent(bolton,library).
adjacent(library,music).
adjacent(music,curtin).
adjacent(curtin,mitchell).
adjacent(mitchell,art).
adjacent(art,union3).
adjacent(mitchell,mellencamp).
adjacent(mellencamp,union3).

/*
 * dist(X,Y,1) is true if one of X,Y is adjacent to the other.
 */

dist(X,Y,1) :- adjacent(X,Y).
dist(X,Y,1) :- adjacent(Y,X).

/*
 * last(L,X) is true if X is the last element of the list L
 */

last([X],X).
last([_|Ls],X) :- last(Ls,X).

/*
 * pathdist(L,N) is true if the path in L has distance = N.
 * L should be fully instantiated or else this predicate may run forever.
 */

% don't assume all places are 1 apart
pathdist([_],0).
pathdist([X,Y|Zs],N) :- dist(X,Y,N2),
				pathdist([Y|Zs],N3),
				N is N2 + N3.

/*
 * pathbound(L,N) is true if the path in L has distance < N.
 * N must be fully instantiated.
 */

pathbound([_],   0).
pathbound([_,_] ,1).
pathbound([X|Xs],N) :- last(Xs,Y),
			     dist(X,Y,N2),
			     N2 < N.

/*
 * pathdecision(A,B,L,S) is true if L is a path from A to B with dist < S.
 * S must be fully instantiated.
 */

pathdecision(A,B,[A|T],S) :- last([A|T],B),
				     pathbound([A|T],S).

/*
 * better(P1,N2,P2,N2,P3,N3) is true if N3 is the smaller of N1 and N2
 *                                   and P3 is the corresponding path
 * N1 and N2 must be fully instantiated.
 */

better(P1,N1,P2,N2,P1,N1) :- pathdist(P1,N1),
				     pathdist(P2,N2),
		   		     N1 =< N2.
better(P1,N1,P2,N2,P2,N2) :- pathdist(P1,N1),
				     pathdist(P2,N2),
				     N1 > N2.

/*
 * choosebest(PS,P,N) is true if the shortest distance path in PS is P
 *                            with distance = N.
 * PS must be fully instantiated.
 */ 

choosebest([P],P,N) :- pathdist(P,N).

choosebest([H,K|T],P,N) :- pathdist(H,X),
				   pathdist(K,Y),
				   better(H,X,K,Y,P1,_),
				   choosebest([P1|T],P,N).

/*
 * minpath(A,B,N,L) is true if L is a minimum distance path from A to B
 *                          that has cost < N
 * A, B, and N must be fully instantiated.
 */

/*
minpath(A,B,N,L) :- findall(X, pathdecision(A,B,X,N),Z), 
			  choosebest(Z,L,N).
*/
minpath(A,B,N,L) :- pathdecision(A,B,M,N), 
			  choosebest(M,L,N).