CS 312, section 003

« An Access Database with more TSP Examples | Main | More about improvement presentations »

March 30, 2005

Notes about TSP Algorithms

What to put in each node? 
-	Reduced matrix
-	lower bound
-	included edges
-	excluded edges 
How to generate children? 
-	one child for from “here” to every destination 
o	probably not a good idea. Queue gets too big too fast. 
-	Pick “here” and generate a child for the n closest cities.  N children per node. 
-	Include or exclude an edge to generate 2 children 
How to traverse the graph? 
	- best first search using a pruning function. 
A bounding function
	- the matrix reduction algorithm from Wednesday.
Way to generate initial solutions 
-	pick the smallest edge from A to X then smallest from X to next city (other than A) and so forth.  Then return to A. 
-	pick a permutation of the city list and try that. 
-	Its probably worth doing more than 1 of these trials, but not worth doing all the permutations. You have to find the sweet spot.  Well, in your improvement you can find it if that’s what you want to do. 

The algorithm. 

class node 
   members 
matrix matrix, bound bound, vector solution, 
Boolean optimal
etc; 
methods
	reduce // reduce the matrix and increase the 
bound accordingly. 
		NextEdgeToIncludeAndExclude 
// pick an edge that maximizes exclude child’s bound or some other strategy. 
		excludeCityEdge (i,j) 
// excludes the edge from i to j, re-reduces the matrix and increases the bound as needed. 
Algorithm tsp-bb (matrix M)
: (vector v, int cost, bool optimal) 
priorityQueue of nodes pq; 

// set up my bssf. 
node bssf;  // best solution so far. 
(bssf.vector, bssf.bound) = 
min (several different solutions);
bssf.matrix = M; 
bssf.optimal = false; 

// build initial node. 
inode.matrix = M; 
inode.bound = 0; 
inode.reduce(); 
pq.push (inode);  

while (!pq.empty) {
	if (time has expired) 
then bssf.optimal = false; 
  break; 
 	curnode = pq.pop (); 
	(i,j) = curnode.NextCityEdgeToIncludeAndExclude(); 
	node include = new node(curnode); 
	node exclude = new node(curnode); 
	exclude.excludeCityEdge (i,j); 
	include.includeCityEdge (i,j); 
	if (include.isASolution() 
&& include.bound < bssf.bound)
		updateBSSF (include); // set optimal = true.  
		pq.prune();  
	// the order here matters, and you can use an else 
	// to simplify the code. 
if (include.bound < bssf.bound) 
pq.push (include); 
	if (exclude.bound < bssf.bound) 
	pq.push (exclude);  
}
// return the bssf. 
return bssf

Class node (int,int) NextCityEdgeToIncludeAndExclude () 
	// one strategy is to minimize bound on include-child.
	For each (i,j) such that M[i,j] = 0 
		M’ = copy of array M 
		Set row i = infinity and column j = infinity
		Set M’[j,i] = infinity 
		Difference = Reduce (M’) – bound 
		// another method… 
		If M[k,m] = 0 then
			Difference = min (row m) + min (column k) 
							Excluding M[k,m]. 
//Just a sketch.  Have fun and design your // own. 
Let i,j = M[i,j] so that we get the include and exlcude bounds we want.
// make sure there are no premature cycles. 
Use an array called “to” that tracks where you go “to” from city i. 
Write a for-loop to see if city i is connected to itself in less than n steps where n = # of cities. 
If i,j causes a premature them replace M[i,j} with infinity, reduce and try again. 

Posted by jones at March 30, 2005 11:50 AM

Comments

Post a comment