Re: Travelling problem

Are you aware that

you areš describing the well known travelling salesman problem?
"perfect" solutions for non-trivial cases of NP-complete problems are unknown?
there are very good solutions for real world problems though?

Please check if you really need all criteria!

Pick at most 2 of 3 and we might be able to help:

Fast (i.e. polynomial˛) computation
Proven minimal path
unknown number of nodes > n (n ~ 20 ?)

If it's just a theoretical question and you can't limit the requirements, then I suppose a branch and bound algorithm might be the best approach, but it won't be faster than brute force in some edge cases.

HTH! =)

Cheers Rolf

( addicted to the Perl Programming Language)

update

had a short glance at the WP article and it describes much better what I wanted to tell.

footnotes

š) almost

˛) corrected, educated foo++

Comment on Re: Travelling problem

Replies are listed 'Best First'.
Re^2: Travelling problem by educated_foo (Vicar) on Dec 22, 2013 at 00:54 UTC
Fast (i.e. non-polynomial) computation You mean "i.e. polynomial," right? NP is exponential ;-). I heartily agree with your post, and defer to my favorite MJD talk for the details. EDIT: Nut graph: next time someone tells you to give up on your problem because it's NP-complete, ignore them.	[reply]
Re^3: Travelling problem by LanX (Saint) on Dec 22, 2013 at 01:00 UTC
> You mean "i.e. polynomial," yes, kind of "non-exponential" =) Was a short night! :) Cheers Rolf ( addicted to the Perl Programming Language) update > next time someone tells you to give up on your problem because it's NP-complete, ignore them. Unfortunately well described problems are rare here.	[reply]
Re^4: Travelling problem by educated_foo (Vicar) on Dec 22, 2013 at 01:35 UTC
Unfortunately well described problems are rare here. As are honestly thoughtful and helpful responses, and genuine discussion. As someone who has been here awhile (perhaps far too long), I know how to separate the wheat-y help from the karma-whoring chaff (I've contributed to both). New users, however, may not know how to filter out the mindless nostrums.	[reply]
Re^5: Travelling problem by LanX (Saint) on Dec 22, 2013 at 02:06 UTC
Re^6: Travelling problem by educated_foo (Vicar) on Dec 22, 2013 at 13:40 UTC
Re^2: Travelling problem by Dirk80 (Pilgrim) on Dec 21, 2013 at 21:12 UTC
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.	[reply]
Re^3: Travelling problem (minimal hamilton path) by LanX (Saint) 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.	[reply]
Re^3: Travelling problem by BrowserUk (Patriarch) 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.	[reply]
Re^4: Travelling problem by Dirk80 (Pilgrim) on Dec 21, 2013 at 21:31 UTC
Of course. Here is a link to my dataset: distances.dat	[reply]
Re^5: Travelling problem by BrowserUk (Patriarch) on Dec 21, 2013 at 22:01 UTC
Re^6: Travelling problem by Dirk80 (Pilgrim) on Dec 22, 2013 at 00:23 UTC


Do you know where your variables are?
	PerlMonks