sw1ft's blog

Printing DP TSP path
By sw1ft, history, 8 years ago, In English

Hey everyone. I was looking at the code in CP3 book to solve the TSP using top-down DP in O(n^2*2^n) and was trying to print the path, but it seems impossible to me.

I thought about creating something like a "parent" array and then reconstruct, but couldn't.

This is the code:

static void tsp() {
// n = graph's number of vertices
memo = new double[n][1 << n];
for (int i = 0; i < n; ++i)
	for (int j = 0; j < 1 << n; ++j)
		memo[i][j] = Double.MIN_VALUE;
double distance = tsp(0, 1);
// Build ath - pending
System.out.println("Distance:" + distance);
}

static double dp(int pos, int bitmask) {
	if (bitmask == (1 << n) - 1)
		return graph[pos][0];
	if (Double.compare(memo[pos][bitmask], Double.MIN_VALUE) != 0)
		return memo[pos][bitmask];
	double ans = Double.MAX_VALUE;
	for (int nxt = 0; nxt < n; ++nxt)
		if (nxt != pos && (bitmask & (1 << nxt)) == 0)
			ans = Double.min(ans, graph[pos][nxt] + dp(nxt, bitmask | (1 << nxt)));
	memo[pos][bitmask] = ans;
	return ans;
}

Any help? Thanks!

Tags tsp, dp
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

You can use a parent matrix, as you said.

You have this line which updates the current ans of some give state:

ans = Double.min(ans, graph[pos][nxt] + dp(nxt, bitmask | (1 << nxt)));

Now, let's attribute the second parameter to some variable to make things easier, like:

double cur_value = graph[pos][nxt] + dp(nxt, bitmask | (1 << nxt));

If the value stored at ans is bigger than cur_value, than the state which you just calculated is better than the best you already have. With this in mind, you need to store this better state (the node to which you go) as the parent of the current node. So, you will have something like this:

double cur_value = graph[pos][nxt] + dp(nxt, bitmask | (1 << nxt));
if(ans > cur_value) {
   ans = cur_value;
   parent[pos][bitmask] = nxt;
}

After running the TSP as you do in your main function, you have all the parents calculated for each node. Now, it's easy to construct the solution: what you need to do is to start at the initial state which you pass as parameter for the TSP (0, 1) and keep getting the parent until you arrive at a node with a sentinel value (i.e. a node that doesn't exist, let's say -1 in this case). It will be something like this (I don't know Java syntax, so it will be some pseudocode):

int path = new int[n];
int path_counter = 0;
int cur_node = 0;
int cur_mask = 1;
do {
    path[path_counter] = cur_node;
    path_counter = path_counter + 1;
    cur_node = parent[cur_node][cur_mask];
    cur_mask = cur_mask | (1 << cur_node);
} while(cur_node != -1);

Hope it helps.

→ Reply