CODEWITHSUNDEEP
c++algorithmbit-manipulationsubsettraveling-salesman
tman
tman

Reputation: 89

Dynamic programming: iteration order of subsets in TSP

Question: How does one go about the correct iteration order of all city subsets {1,2,...,n} in the traveling salesman problem?

In my solution, subsets are represented by a bitmask (simply an integer for now). All results are stored in 2-dimensional array C, where the 1st dimension S, resembles the city subset (i.e., the bitmask). The 2nd dimension j, holds the cost of traveling between all cities in S, with j being the ending city.

Every subset includes city 0 (starting city), and the algorithm starts of by setting the shortest route:

C[{0}][0] = 0;

For this algorithm to work, however, all subsets should by iterated in order of subset size.

Here's a straightforward code snippet, that prints all subsets in increasing value:

#include <cstdio>

const int n = 5; // number of cities
const int s = 1 << n; // number of subsets

void printb(int x)
{
    for (int i = n-1; i >= 0; i--) {
        printf("%d", (x >> i) & 1);
    }
}

int main()
{
    for (int i = 0; i < s; i++) {
        printb(i); printf("\n");
    }

    return 0;
}

My goal is to enumerate the subsets in order of subset size (bit count).

Algorithm description I'm using: Algorithms, S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (p188)

Upvotes: 1

Views: 1744

Answers (1)

Rob Neuhaus
Rob Neuhaus

Reputation: 9290

In order to solve TSP correctly, you don't actually need to traverse all size 1 subsets before you traverse a size 2 subset. You just need to traverse all subsets of a given set X before you traverse set X. Doing the iteration in numeric order with the standard encoding of sets satisfies this property.

Upvotes: 2

Related Questions