laziness, impatience, and hubris | |
PerlMonks |
Re^3: Travelling problem (minimal hamilton path)by LanX (Saint) |
on Dec 21, 2013 at 23:04 UTC ( [id://1068067]=note: print w/replies, xml ) | Need Help?? |
The Christofides Algorithm mentioned by educated foo guaranties a solution better than 1.5 times the optimum. Nota bene: since you have a fixed start and end for an "open" hamiltonian path (i.e. not a circle like in the TSP) you'll need to adjust the algorithm accordingly. ¹
Cheers Rolf ( addicted to the Perl Programming Language)
update¹) after reading two SO discussions (search "minimal hamilton path") you just need to add a dummy point neighboring (only) the desired start- and end-point with distance 0 (!) Like this any TSP algorithm will chose start and end as neighbors for a hamilton circle with the same accumulated length like a optimized hamilton path, you just need to ignore the two dummy edges at the end.
In Section
Seekers of Perl Wisdom
|
|