2 //import java.util.Random;
5 * A class that represents a node in a binary tree. Each node represents
6 * a city in the TSP benchmark.
11 * The number of nodes (cities) in this subtree
15 * The coordinates that this node represents
19 * Left child of the tree
21 private Tree_tsp left;
25 private Tree_tsp right;
27 * The next pointer in a linked list of nodes in the subtree. The list
28 * contains the order of the cities to visit.
30 private Tree_tsp next;
32 * The previous pointer in a linked list of nodes in the subtree. The list
33 * contains the order of the cities to visit.
35 private Tree_tsp prev;
37 // used by the random number generator
38 //private static final float M_E2; // = 7.3890560989306502274;
39 //private static final float M_E3; // = 20.08553692318766774179;
40 //private static final float M_E6; // = 403.42879349273512264299;
41 //private static final float M_E12; // = 162754.79141900392083592475;
44 * Construct a Tree node (a city) with the specified size
45 * @param size the number of nodes in the (sub)tree
46 * @param x the x coordinate of the city
47 * @param y the y coordinate of the city
48 * @param left the left subtree
49 * @param right the right subtree
51 Tree_tsp(int size, float x, float y, Tree_tsp l, Tree_tsp r)
53 /*M_E2 = 7.3890560989306502274f;
54 M_E3 = 20.08553692318766774179f;
55 M_E6 = 403.42879349273512264299f;
56 M_E12 = 162754.79141900392083592475f;*/
68 * Find Euclidean distance between this node and the specified node.
69 * @param b the specified node
70 * @return the Euclidean distance between two tree nodes.
72 float distance(Tree_tsp b)
74 return (Math.sqrtf((float)((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y))));
78 * Create a list of tree nodes. Requires root to be the tail of the list.
79 * Only fills in next field, not prev.
80 * @return the linked list of nodes
84 Tree_tsp myleft, myright;
85 Tree_tsp tleft,tright;
86 Tree_tsp retval = this;
90 myleft = left.makeList();
96 myright = right.makeList();
100 if (myright != null) {
105 if (myleft != null) {
118 * Reverse the linked list. Assumes that there is a dummy "prev"
119 * node at the beginning.
123 Tree_tsp prev = this.prev;
126 Tree_tsp back = this;
128 // reverse the list for the other nodes
130 for (Tree_tsp t = this.next; t != null; back = t, t = next) {
135 // reverse the list for this node
141 * Use closest-point heuristic from Cormen, Leiserson, and Rivest.
146 // create the list of nodes
147 Tree_tsp t = makeList();
149 // Create initial cycle
155 // Loop over remaining points
157 for (; t != null; t = donext) {
158 donext = t.next; /* value won't be around later */
159 Tree_tsp min = cycle;
160 float mindist = t.distance(cycle);
161 for (Tree_tsp tmp = cycle.next; tmp != cycle; tmp=tmp.next) {
162 float test = tmp.distance(t);
163 if (test < mindist) {
169 Tree_tsp next = min.next;
170 Tree_tsp prev = min.prev;
172 float mintonext = min.distance(next);
173 float mintoprev = min.distance(prev);
174 float ttonext = t.distance(next);
175 float ttoprev = t.distance(prev);
177 if ((float)(ttoprev - mintoprev) < (float)(ttonext - mintonext)) {
178 /* insert between min and prev */
195 * Merge two cycles as per Karp.
196 * @param a a subtree with one cycle
197 * @param b a subtree with the other cycle
199 Tree_tsp merge(Tree_tsp a, Tree_tsp b)
201 // Compute location for first cycle
203 float mindist = distance(a);
205 for (a = a.next; a != tmp; a = a.next) {
206 float test = distance(a);
207 if (test < mindist) {
213 Tree_tsp next = min.next;
214 Tree_tsp prev = min.prev;
215 float mintonext = min.distance(next);
216 float mintoprev = min.distance(prev);
217 float ttonext = distance(next);
218 float ttoprev = distance(prev);
222 if ((ttoprev - mintoprev) < (ttonext - mintonext)) {
223 // would insert between min and prev
229 // would insert between min and next
236 // Compute location for second cycle
238 mindist = distance(b);
240 for (b = b.next; b != tmp; b = b.next) {
241 float test = distance(b);
242 if (test < mindist) {
250 mintonext = min.distance(next);
251 mintoprev = min.distance(prev);
252 ttonext = this.distance(next);
253 ttoprev = this.distance(prev);
257 if ((ttoprev - mintoprev) < (ttonext - mintonext)) {
258 // would insert between min and prev
264 // would insert between min andn ext
271 // Now we have 4 choices to complete:
276 float n1ton2 = n1.distance(n2);
277 float n1top2 = n1.distance(p2);
278 float p1ton2 = p1.distance(n2);
279 float p1top2 = p1.distance(p2);
281 mindist = (float)(ttop1 + ttop2 + n1ton2);
284 float test = (float)(ttop1 + tton2 + n1top2);
285 if (test < mindist) {
290 test = tton1 + ttop2 + p1ton2;
291 if (test < mindist) {
296 test = tton1 + tton2 + p1top2;
302 // 1:p1,this this,p2 n2,n1 -- reverse 2!
311 } else if(choice == 2) {
313 // 2:p1,this this,n2 p2,n1 -- OK
321 } else if(choice == 3) {
323 // 3:p2,this this,n1 p1,n2 -- OK
331 } else if(choice == 4) {
333 // 4:n1,this this,n2 p2,p1 -- reverse 1!
347 * Compute TSP for the tree t. Use conquer for problems <= sz
348 * @param sz the cutoff point for using conquer vs. merge
352 if (this.sz <= sz) return conquer();
354 Tree_tsp leftval = left.tsp(sz);
355 Tree_tsp rightval = right.tsp(sz);
357 return merge(leftval, rightval);
361 * Print the list of cities to visit from the current node. The
362 * list is the result of computing the TSP problem.
363 * The list for the root node (city) should contain every other node
366 /*void printVisitOrder()
368 System.out.println("x = " + x + " y = " + y);
369 for (Tree_tsp tmp = next; tmp != this; tmp = tmp.next) {
370 System.out.println("x = " + tmp.x + " y = " + tmp.y);
379 * Return an estimate of median of n values distributed in [min,max)
380 * @param min the minimum value
381 * @param max the maximum value
383 * @return an estimate of median of n values distributed in [min,max)
385 private static float median(float min, float max, int n)
387 float M_E2 = 7.3890560989306502274f;
388 float M_E3 = 20.08553692318766774179f;
389 float M_E6 = 403.42879349273512264299f;
390 float M_E12 = 162754.79141900392083592475f;
392 // get random value in [0.0, 1.0)
393 float t = (new Random()).nextFloat();
397 retval = /*java.lang.*/(float)(Math.log(1.0-(2.0*(M_E12-1)*(t-0.5)/M_E12))/12.0f);
399 retval = (float)(-/*java.lang.*/Math.log(1.0-(2.0*(M_E12-1)*t/M_E12))/12.0f);
401 // We now have something distributed on (-1.0,1.0)
402 retval = (float)((retval+1.0f) * (max-min)/2.0f);
403 retval = retval + min;
408 * Get float uniformly distributed over [min,max)
409 * @return float uniformily distributed over [min,max)
411 private static float uniform(float min, float max)
413 // get random value between [0.0,1.0)
414 float retval = (new Random()).nextFloat();
415 retval = retval * (max-min);
420 * Builds a 2D tree of n nodes in specified range with dir as primary
421 * axis (false for x, true for y)
423 * @param n the size of the subtree to create
424 * @param dir the primary axis
425 * @param min_x the minimum x coordinate
426 * @param max_x the maximum x coordinate
427 * @param min_y the minimum y coordinate
428 * @param max_y the maximum y coordinate
429 * @return a reference to the root of the subtree
431 public static Tree_tsp buildTree(int n, boolean dir, float min_x,
432 float max_x, float min_y, float max_y)
434 if (n==0) return null;
436 Tree_tsp left, right;
440 float med = median(min_x,max_x,n);
441 left = buildTree(n/2, dir, min_x, med, min_y, max_y);
442 right = buildTree(n/2, dir, med, max_x, min_y, max_y);
444 y = uniform(min_y, max_y);
447 float med = median(min_y,max_y,n);
448 left = buildTree(n/2, dir, min_x, max_x, min_y, med);
449 right = buildTree(n/2, dir, min_x, max_x, med, max_y);
451 x = uniform(min_x, max_x);
453 return new Tree_tsp(n, x, y, left, right);