%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%% TRAVELING SALESMAN PROBLEM %%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Last revision: December 2002 (G.Rossi) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % tsp(N,E,K): % determine whether there is a path in the graph N,E starting from a % source node S, passing exactly once for every other node and returning % in the initial node, of global cost less than a constant K % Data representation % % A weighted directed graph is represented as a pair N,E where % N is the set of nodes and % E is the set of edges, where each edge is represented by a triple % [s,c,t] where s is the source node, t is the target node and c is % an integer >= 0 representing the cost associated with the edge % The {log} library file 'setloglib.slog' is assumed to be stored % in the same directory where this file is: tsp(Nodes,Edges,Source,K) :- Source in Nodes & xdiff(Nodes,{Source},To_visit) & path(To_visit,Edges,Source,Target,Cost1) & [Target,Cost2,Source] in Edges & Cost1 + Cost2 < K. path({T},Edges,S,T,Cost) :- [S,Cost,T] in Edges. path({I/To_visit},Edges,S,T,Cost) :- [S,Cost1,I] in Edges & I nin To_visit & path(To_visit,Edges,I,T,Cost2) & Cost is Cost1 + Cost2. % For completely connected graphs the set of nodes can be computed from % the set of edges tsp(Edges,Source,K) :- Nodes = {X : exists([T,S,C], T = [S,C,X] & T in Edges)} & tsp(Nodes,Edges,Source,K). %%%%%%%%%%%%%%%%%%%%%%% SAMPLE GOALS %%%%%%%%%%%%%%%%%%%%%%%%%% % Auxiliary predicates sample_graph(graph1,{[a,5,b],[a,3,c],[c,1,b],[b,4,d],[c,3,d],[d,6,a]}). sample_tsp(GraphName,Source,TotalCost) :- sample_graph(GraphName,E) & tsp(E,Source,TotalCost). % Sample goals % % {log}=> sample_tsp(graph1,a,15). % yes % % {log}=> sample_tsp(graph1,a,14). % no %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%% A related problem %%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Given a graph N,E represented as above, find the subset of nodes SN of % the graph that is possible to visit starting from a node S % and coming back to S with a global cost less or equal to a constant K. tsp_subset(N,E,S,K,SN) :- S in SN & subset(SN,N) & tsp(SN,E,S,K). % For completely connected graphs tsp_subset(E,S,K,SN) :- N={X : exists([T,S,C], T = [S,C,X] & T in E)} & tsp_subset(N,E,S,K,SN). %%%%%%%%%%%%%%%%%%%%%%% SAMPLE GOALS %%%%%%%%%%%%%%%%%%%%%%%%%% % Auxiliary predicates sample_tsp_subset(GraphName,Source,TotalCost,NodeSet) :- sample_graph(GraphName,E) & tsp_subset(E,Source,TotalCost,NodeSet). sample_graph(graph2,{[a,5,b],[a,3,c],[c,1,b],[b,4,d],[c,3,d],[d,6,a],[b,1,a]}). % {log}=> sample_tsp_subset(graph1,a,13,NS). % NS = {a,c,d} % % {log}=> sample_tsp_subset(graph1,a,12,NS). % no % % {log}=> sample_tsp_subset(graph2,a,7,NS). % NS = {a,b} % Another solution? (y/n)y % NS = {a,b,c} % Another solution? (y/n)y % no % % {log}=> sample_tsp_subset(graph2,c,6,NS). % NS = {a,b,c} % Another solution? (y/n)y % no %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % start predicates %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% start :- consult_lib & nl & write('*********************************************************************') & nl & write('tsp(Edges,S,K):') & nl & write('determine whether there is a path in the given graph Edges starting ') & nl & write('from a source node S, passing exactly once for every other node and ') & nl& write('returning in the initial node, of global cost less than a constant K ') & nl & start2. start2 :- nl & write('Give the goal sample_graph(-GraphName,-Edges) to get a sample set of edges') & nl & write('named GraphName') & nl & nl & write('Give the goal sample_tsp(+GraphName,?SourceNode,?TotalCost) ') & nl & write('to solve the TSP problem for graph GraphName, ') & nl & write('with initial node SourceNode and global cost less than TotalCost.') & nl & start3. start3 :- nl & write(' Moreover ') & nl & nl & write('Give the goal sample_tsp_subset(+GraphName,?SourceNode,?TotalCost,?NodeSet) ') & nl & write('to find the subset NodeSet of nodes of GraphName containing SourceNode ') & nl & write('that is possible to visit starting from SourceNode and coming back to SourceNode') & nl & write('with a global cost less than TotalCost.') & nl & write('*********************************************************************') & nl & nl. %:-start.