Beefy Boxes and Bandwidth Generously Provided by pair Networks
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??


in reply to Re^2: Travelling problem
in thread Travelling problem

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.

  • Comment on Re^3: Travelling problem (minimal hamilton path)

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1068067]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others wandering the Monastery: (4)
As of 2024-04-23 22:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found