CS 312, section 003

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) {
	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);
		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);
}