Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Re^2: Travelling problem

by Dirk80 (Monk)
on Dec 21, 2013 at 21:12 UTC ( #1068055=note: print w/ replies, xml ) Need Help??


in reply to Re: Travelling problem
in thread Travelling problem

Yes, you are right. The "travelling salesman problem" exactly describes my problem. Thank you!!!

I have 24 places and I know the distance between these places in km. I have to visit the first place, then 22 places in any order and then the 24th place. I don't need a perfect solution. I just want to find a short way, not the shortest one. And the computation time should not be too long. An approximation is enough.


Comment on Re^2: Travelling problem
Replies are listed 'Best First'.
Re^3: Travelling problem (minimal hamilton path)
by LanX (Canon) on Dec 21, 2013 at 23:04 UTC
    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.

Re^3: Travelling problem
by BrowserUk (Pope) on Dec 21, 2013 at 21:21 UTC
    I have 24 places and I know the distance between these places in km. I have to visit the first place, then 22 places in any order and then the 24th place.

    Could you post a sample dataset?


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

        Start at 1 and end at 24?


        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (9)
As of 2015-07-29 22:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (269 votes), past polls