CS 312, section 003

« Which edge to include/exclude? (updated, due 3/28 or 3/30) | Main | Putting the TSP Algorithm Together »

March 25, 2005

Avoiding premature cycles (due 3/30)

1. What is a premature cycle?
2. Are premature cycles possible in the include/exclude formulation of the problem? That's the algorithm that picks an edge to include and exclude resulting in two new nodes.
3. Sketch an algorithm and accompnying datastractures for detecting premature cycles as they are formed.
4. Make sure you can detect premature cycles and that you can detect completed cycles too.

array to of int[n]. // an array that lives in each nod.e 

is edge (x,y) ok to add? 
int here;
here = y;  // note that I didn't modify the "to" array. 
for (i = 1 ; i < n; i++)   // since I started at y (rather than x) I only go up to n-1 in a solution. 
    here = to[here]; 
    if (here == x) then return false // not ok to add x,y. 
return true // it is ok to add x,y. 

Posted by jones at March 25, 2005 03:45 PM

Comments

Post a comment