pathfinding.pl

prolog 找路例子程序： === === === === === === Part 1-Adding connections Part 2-Simple Path example

% List of connected locations
% ----------------------------
% conncted(A,B,X). is proved if a courier can travel 
% from location A to location B in exactly X minutes.

connected(depot,a,30).
connected(depot,b,40).
connected(depot,c,20).
connected(a,depot,30).
connected(b,depot,40).
connected(c,depot,20).
connected(a,b,15).
connected(b,a,15).
connected(a,c,35).
connected(c,a,35).
connected(b,d,20).
connected(d,b,20).
connected(c,d,30).
connected(d,c,30).
connected(d,e,10).
connected(e,f,40).
connected(f,g,10).
connected(g,f,10).
connected(e,g,15).
connected(f,d,15).
connected(d,f,15).
connected(f,h,15).
connected(h,f,15).
connected(f,i,20).
connected(i,f,20).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Part 1 - Adding connections.				       %
%% Add a new clause at the end of the connected predicted      %
%% that will allows to proofs that location which directly     %
%% connected to itself and reachable in zero minutes.          %
%% The code to describe that proofs                            %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%!!! everything connected with itself just cost 0 mins%

connected(NODE,NODE,0).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Part 2 - Simple Path.				       %
%% perdicate:  path1 (a,b,P,T).     			       %
%% 'a' snd 'b' are the locations, 'P' is the path between      %
%% location 'a' and 'b'.  'a' is the first element for list    %
%% 'P' and 'b' is the last element. The variable 'T' will be   %
%% bound to the sum of the times it takes for path1            %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%!!! input query%
path1(SOURCE,DEST,PATH,TIME) :- routepath1(SOURCE,DEST,PATH,TIME).

%!!! base case, same node%
routepath1(X,Y,P,T) :- connected(X,Y,T), P=[X,Y].

%!!! recursice case.  X and Y is directed connecter  %
%!!! route path [X|P] need to start from 'X' and must%
%!!! end with 'Y' as show by 2nd line. program search% 
%!!! all the paths between 'X' and 'Y'               %
 
routepath1(X,Y,[X|P],T) :- connected(X,Z,T1), 
                routepath1(Z,Y,F,T2), P=F, 
                T is T1 + T2.    
%!!! Time be updated once a new node is addin%

  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% part 3 - Non-repeating path                                 %
%% predicate path2 finds a path between any two nodes          %
%% the result path shall not have any repeating nodes          %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%!!! base case, if path2 could be find from connected database.
path2(SOURCE,DEST,[SOURCE,DEST],TIME):-
	connected(SOURCE,DEST,TIME).

%!!! addin new 'list' argument to recode the path.
%!!! base for path2 with new argument.
path2(SOURCE,DEST,ROUTE,TIME):-
	path2([SOURCE],SOURCE,DEST,ROUTE,TIME).

%!!! recursice case
path2(INITPATH,DEST,DEST,[DEST],TIME):-
	connected(DEST,DEST,TIME).

%!!! full recursice case 	
path2(INITPATH,SOURCE,DEST,[SOURCE|ROUTEPATH],TIME):-
	connected(SOURCE,NEXTHOP,TIME1),
	legal(NEXTHOP,INITPATH),
	path2([NEXTHOP|INITPATH],NEXTHOP,DEST,ROUTEPATH,TIME2),
        TIME is TIME1 + TIME2.

%!!! legal is nothing more than a "non-membership" test.        
legal(X,[]).
legal(X,[H|F]):- \+ X =H , legal(X,F).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% part 4						       %	
%% starting at location: 'START'			       %
%% end result must containing all the locations in the "LIST"  %
%% end result takes less than "COST" minutes to complete.      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%!!! bandings between path_below_cost and path2.
path_below_cost(START, LIST, RS,COST) :- 
path2(START,DEST,ROUTE,TIME), 

%!!! DEST node could be everthing in the database.
my_member(DEST, [depot,a,b,c,d,e,f,g,h,i]), 

%!!! new path takes less than COST minutes 
TIME =< COST,

%!!! ROUTE must visits all of the locations in a given list. 
subset(LIST,ROUTE),

%!!! ROUTE banding with result list 'RS'
RS = ROUTE.

%!!! sebset is a group which all the elements can be find from another group  
subset([],Y).
subset([A|X],Y):-my_member(A,Y),subset(X,Y).

%!!! my_member is a "membership" test.
my_member(X,[X|_]).
my_member(X,[_|Y]):-member(X,Y).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% part 5
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%