Reply to thread

Message

[QUOTE="Joshua Cranmer, post: 3615095"]
So I decided to try to see how gullible this algorithm was. This is the 
JS version, as best as I can tell (copy+paste into editor):
function distance(a, b) {
   var dx = a.x - b.x; var dy = a.y - b.y;
   return Math.sqrt(dx * dx + dy * dy);
}

var left, leftHist = [], right, rightHist = [];
var nodes = {};
function TSP(args) {
   var start = args[0].id;
   left = right = args.shift();
   for each (var arg in args) {
     nodes[arg.id] = arg;
   }

num = args.length;
   while (num >= 2) {
      var bestLeft, bestRight, best = 10000*10000;
      for (var leftNext in nodes) {
          for (var rightNext in nodes) {
             if (leftNext == rightNext) continue;
             if (distance(nodes[leftNext], nodes[rightNext]) < best) {
               bestLeft = leftNext; bestRight = rightNext;
               best = distance(nodes[leftNext], nodes[rightNext]);
             }
          }
      }
      leftHist.push(bestLeft); rightHist.push(bestRight);
      delete nodes[bestLeft]; delete nodes[bestRight];
      num -= 2;
   }

var last = false;
   for (var arg in nodes) {
     last = arg;
   }
   var output = [start];
   for each (var onLeft in leftHist)
     output.push(onLeft);
   if (last) output.push(last);
   rightHist.reverse();
   for each (var onRight in rightHist)
     output.push(onRight);
   return output;
}

I drew a graph that looked roughly like a diamond, with two nearby nodes 
at each vertex.

Brute force produced something looking like a diamond, with a length of 
666.661.

JSH's current algorithm looks like an hour glass with a length of 
1375.509, or roughly twice the best path, which is what I predicted in 
an earlier post.

Besides, programming in JS isn't hard, especially when one has all the 
features of Java accessible from JS if you work hard enough. Having JS 
experience myself, I eschewed the Java features.
[/QUOTE]

Verification