Databases
StackOverflow2013
Postsdbo
POMinimal Distance Hamiltonian Path Javascript
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POMinimal Distance Hamiltonian Path Javascript
    text
    copied!<p>I know this is a fairly frequent question (tsp in general), but I've been stumped by it for awhile now. I'm looking to find the minimal distance hamiltonian path given a set of x,y coordinates. The start and end point are completely arbitrary but it must NOT cycle, so standard tsp is out (although supposedly adding a dummy point at 0 distance to all other nodes and then removing it later works, i have no idea how I'd do that).</p> <p>There are plenty of links to math papers and the like discussing algorithms to solve similar problems, but I'd much rather work with code than complex equations and i'd really rather not reinvent the wheel.</p> <p>Surely there is a fairly straightforward implementation in a major language java,c#,c++,ruby,javascript,php,etc that can solve a ~20 node version of my problem.</p> <p><strong>Edit:</strong> I'm also looking for as accurate as possible, obviously it can't be completely accurate as 20! is a lot of permutations, but equal to or better than what a human could do in a couple minutes would be perfect.</p> <p><strong>Edit2:</strong> Also to clarify, I'm working with standard 2d coordinates on an unweighted graph. The distance A->B == B->A</p> <p><strong>Edit3:</strong> To eliminate confusion, here's a visual example with just a few points to show how tsp can be suboptimal (this case is an easy fix but with more nodes it can be more extreme).</p> <p>TSP Minus Longest Segment (red line)</p> <p><img src="https://i.stack.imgur.com/eImjg.png" alt="TSP Minus Longest Segment (red line)"></p> <p>Desired Output</p> <p><img src="https://i.stack.imgur.com/9LEDf.png" alt="Desired Output"></p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload