UMCPC Traveling Salesman Problem 20160908

tsp.cpp

// Travelling Salesman problem
// Sample code @ UMCPC
// Time complexity: O(n + 2^n)


// memo: cached value
int tsp(int curr, int visited) { // visited = binary visited list
    if (memo[curr][visited] != -1) {
        // return cached value
        return memo[curr][visited];
    }

    if (visited == (1 << N) - 1) { // if everything is visited
        memo[curr][visited] = dist[curr][start];
        return memo[curr][visited];
    }

    int min_cost = MAX_INT;

    for (int i = 0; i < N; i++) {
        if (visited & (1 << i) == 0 && i != curr) {
            // if not visited and not checking curr item
            min_cost = min(min_cost, tsp(i, visited | 1 << curr) + dist[curr][i]);
        }
    }
    memo[curr][visited] = min_cost;
    return min_cost;
}

cout << tsp(starting_city, 1 << starting_city);

// Binary shift:
// 0b100100101001 = Visited: 0, 3, 5, 8, 11
// Check a point: visited & (1 << i) == 0
// Mod a point: visited |= (1 << i)
// Check all visited: visited == (1 << N) - 1