4

Recently I asked a question on Stack Overflow asking for help to solve a problem. It is a travelling salesman problem where I have up to 40,000 cities but I only need to visit 15 of them.

I was pointed to use Dijkstra with a priority queue to make a connectivity matrix for the 15 cities I need to visit and then do TSP on that matrix with DP. I had previously only used Dijkstra with O(n^2). After trying to figure out how to implement Dijkstra, I finally did it (enough to optimize from 240 seconds to 0.6 for 40,000 cities). But now I am stuck at the TSP part.

Here are the materials I used for learning TSP :

I sort of understand the algorithm (but not completely), but I am having troubles implementing it. Before this I have done dynamic programming with arrays that would be dp[int] or dp[int][int]. But now when my dp matrix has to be dp[subset][int] I don't have any idea how should I do this.

My questions are :

  • How do I handle the subsets with dynamic programming? (an example in C++ would be appreciated)
  • Do the algorithms I linked to allow visiting cities more than once, and if they don't what should I change?
  • Should I perhaps use another TSP algorithm instead? (I noticed there are several ways to do it). Keep in mind that I must get the exact value, not approximate.

Edit:

After some more research I stumbled across some competitive programming contest lectures from Stanford and managed to find TSP here (slides 26-30). The key is to represent the subset as a bitmask. This still leaves my other questions unanswered though.

Can any changes be made to that algorithm to allow visiting a city more than once. If it can be done, what are those changes? Otherwise, what should I try?

Community
  • 1
  • 1
A. Andevski
  • 437
  • 1
  • 5
  • 17
  • 1
    I'm not positive, but I'm pretty sure you can't use Dijkstra's algorithm to get an exact solution to the traveling salesman problem (unless you want a greedy approximation). Keep in mind that Dijkstra's is polynomial and your answer is going to need to be exponential. – Patrick Collins Jun 16 '14 at 22:09
  • @PatrickCollins I am not using Dijkstra to get an exact solution for TSP. I just mentioned that I used Dijkstra to generate the connectivity matrix that I will use for TSP. I plan to do TSP with dynamic programming. Please read carefully – A. Andevski Jun 16 '14 at 22:14
  • Ah, okay, I misunderstood -- I thought you were looking to use Dijkstra's algorithm as a step in your TSP implementation. (Which would be the way to go if you were looking for the greedy approximation) – Patrick Collins Jun 16 '14 at 22:15
  • It sounds like you need to visit 15 *given* cities, but please make this clear. What you currently have could just as easily be interpreted to mean, "Find the subset of 15 cities that has the shortest TSP". – j_random_hacker Jun 17 '14 at 01:01

3 Answers3

2

I think you can use the dynamic solution and add to each pair of node a second edge with the shortest path. See also this question:Variation of TSP which visits multiple cities.

Community
  • 1
  • 1
Micromega
  • 12,486
  • 7
  • 35
  • 72
  • This actually worked for me with no adjustments. The first part of my algorithm (the Dijkstra I ran) actually serves as a Floyd-Warshall for me. A simple TSP run solved it. – A. Andevski Jun 17 '14 at 10:27
0

Here is a TSP implementation, you will find the link of the implemented problem in the post.

The algorithms you linked don't allow visiting cities more than once.

For your third question, I think Phpdna answer was good.

Omar Abdelrahman
  • 325
  • 4
  • 11
-1

Can cities be visited more than once? Yes and no. In your first step, you reduce the problem to the 15 relevant cities. This results in a complete graph, i.e. one where every node is connected to every other node. The connection between two such nodes might involve multiple cities on the original map, including some of the relevant ones, but that shouldn't be relevant to your algorithm in the second step.

Whether to use a different algorithm, I would perhaps do a depth-first search through the graph. Using a minimum spanning tree, you can give an upper and lower bound to the remaining cities, and use that to pick promising solutions and to discard hopeless ones (aka pruning). There was also a bunch of research done on this topic, just search the web. For example, in cases where the map is actually carthesian (i.e. the travelling costs are the distance between two points on a plane), you can exploit this info to improve the algorithms a bit.

Lastly, if you really intend to increase the number of visited cities, you will find that the time for computing it increases vastly, so you will have to abandon your requirement for an exact solution.

Ulrich Eckhardt
  • 16,572
  • 3
  • 28
  • 55