Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
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
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.
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.

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 rifling through the Monastery: (14)
As of 2014-07-11 17:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When choosing user names for websites, I prefer to use:








    Results (232 votes), past polls