• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

Traveling Salesman

Authors Michael R. Garey / David S. Johnson

Computers and Intractability: A Guide to the Theory of NP-Completeness
 
Yo, the TSP is of class NP-Complete, meaning that there is no defined method to get a guaranteed optimal solution. Your best bet is to approximate using greedy graph algorithms such as Dijkstras or if the number of cities you need to visit allows it, you can possibly use brute force, that is, calculate all possible paths and then choose the shortest. Warning: this will take factorial time.
 
I believe the best solutions are currently based on heuristic approaches. You might also look at Genetic Algorithm & Simulated Annealing approaches.
Google will probably give you more leads then you can possibly follow.

Now, for a a really fun problem, have a look at a TSP where the cities are moving (this doubles the number of solutions), and you have multiple salesman 😀
 
Yes.. thanks.. I will be doing it three ways.. greedy, dynamic recursion, and divide and couquer.. I figured out the first two.. it's the divide one that's gonna be hardest
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top