chrisaaker Posted April 30, 2011 Share Posted April 30, 2011 I am using a brute force approach to solve a version of the traveling salesman problem. I am looking into ways to optimize it but there are many. Basically I need help further defining the problem and how to solve it optimally. Given [path] [start city] [end city] [distance] P1 C1 C2 100 P2 C2 C1 400 P3 C1 C3 300 P4 C3 C1 200 P5 C2 C3 100 P6 C3 C2 400 Determine the shortest path which tours all the cites. Currently i check all possibilities using all combinations nCk where n = 6 and 3 <= k <= 6, filter these solutions to make sure all cities can be reached and finally choose the one with the lowest cost. Thanks Link to comment Share on other sites More sharing options...

imatfaal Posted May 1, 2011 Share Posted May 1, 2011 That's one hell of a one-way-system you have there - 4 times longer to return from C2->C1 than the outbound journey C1->C2. The travelling salesman problem does not canonically have different distances for outbound and inbound to a city (ie it forms a symmetric graph) , and also cities are only visited once; but I presume that these are new parts of the version you are looking at. the very point TSP is discussed is that it is prototypically np - that means that the solution time does not scale polynomially with the number of variables. I don't believe that removing the symmetry or the proviso tha cities are only visited once will stop the problem being NP-hard. The canonical version does have algorithms that can help - search on Nikos Christofides - his algorithm algorithm will get you within 50% of the actual best distance. The permutation method that you are looking at scales in the order of n! 30 cities would require over 10^34 operations. For your guidance a solution that solves TSP in polynomial time would get you, at least, a million bucks in prize money Link to comment Share on other sites More sharing options...

DrRocket Posted May 4, 2011 Share Posted May 4, 2011 That's one hell of a one-way-system you have there - 4 times longer to return from C2->C1 than the outbound journey C1->C2. The travelling salesman problem does not canonically have different distances for outbound and inbound to a city (ie it forms a symmetric graph) , and also cities are only visited once; but I presume that these are new parts of the version you are looking at. the very point TSP is discussed is that it is prototypically np - that means that the solution time does not scale polynomially with the number of variables. I don't believe that removing the symmetry or the proviso tha cities are only visited once will stop the problem being NP-hard. The canonical version does have algorithms that can help - search on Nikos Christofides - his algorithm algorithm will get you within 50% of the actual best distance. The permutation method that you are looking at scales in the order of n! 30 cities would require over 10^34 operations. For your guidance a solution that solves TSP in polynomial time would get you, at least, a million bucks in prize money The traveling salesman problem is in fact NP-complete, so finding a fast algorithm comes under the heading of "really hard'. (Add as many "really"s as you like). Link to comment Share on other sites More sharing options...

imatfaal Posted May 4, 2011 Share Posted May 4, 2011 (edited) DocRock - of course you're correct. As a corollary; has there been any further talk of Romanov's claim of solution to 3-SAT. I saw quite a lot about it at the beginning of this year in the popular science press, but very quickly it disappeared from view. I realise that it had to be very rigorously checked, do you happen to know if this process is still on going or that it was found to be lacking very quickly and died quietly? The mathematicians I read on the subject at the time were pretty certain it would be found to be incomplete and that the paper was poorly presented/on tenuous logical ground - but still felt that it merited proper research. I wonder if the academic maths press (which I do not read/ could not understand) have published any news. Vladimir Romanov has released source code for an algorithm which he claims can solve 3-SAT problems. The 3-SAT problem is NP-complete - and Romanov claims his algorithm will solve in polynomial time, this would prove that P==NP as all NP problems can be mapped within polynomial time to the satisfiability problem. With such a seemingly easily falsifiable claim Romanov might be proved wrong quite quickly - for any with the maths and compsci skill here is Romanov's announcement and links to the source code and article - and for those who need a bit more background here is a link to a long slashdot ramble that has some good stuff in it Edited May 4, 2011 by imatfaal Link to comment Share on other sites More sharing options...

DrRocket Posted May 7, 2011 Share Posted May 7, 2011 DocRock - of course you're correct. As a corollary; has there been any further talk of Romanov's claim of solution to 3-SAT. I saw quite a lot about it at the beginning of this year in the popular science press, but very quickly it disappeared from view. I realise that it had to be very rigorously checked, do you happen to know if this process is still on going or that it was found to be lacking very quickly and died quietly? The mathematicians I read on the subject at the time were pretty certain it would be found to be incomplete and that the paper was poorly presented/on tenuous logical ground - but still felt that it merited proper research. I wonder if the academic maths press (which I do not read/ could not understand) have published any news. Apparently there are some problems with Romanov's initial claim. http://www.computer.org/portal/web/news/home/-/blogs/3-sat-solution-flawed 1 Link to comment Share on other sites More sharing options...

imatfaal Posted May 9, 2011 Share Posted May 9, 2011 Apparently there are some problems with Romanov's initial claim. http://www.computer....solution-flawed Thanks. Link to comment Share on other sites More sharing options...

## Recommended Posts

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now