The Travelling PokeMan

This problem is admittedly an instance of the Travelling Salesman Problem .

The naive solution is to check out all possible tours. This is O(n!) and obviously takes too long. We'll use Held-Karp's Algorithm to provide a $O(n^2 2^n)$ dynamic programming solution.

Because we know that PiHan starts from the first stop, we could say that the tour begins and ends there. Consider subsets S ⊆ {2, . . . , N} of stops and, for c ∈ S, let D(S, c) be the minimum distance, starting at city 1, visiting all stops in S and finishing at city c. The recursive step is as follows:

$D(S,c) = \left\{\begin{matrix} dist_{1,c} & \text{if } S = \left \{ c \right \} \\ \min \left \{ D((S \setminus c), j) + dist_{j,i} \right \} & otherwise \end{matrix}\right.$

We can now code this up

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <iostream>
#include <fstream>
#include <limits>
#include <cstring>
#include <algorithm>

int main(){
    const int N = 16;
    std::ifstream fIn("pokedata.in");

    int distance[N][N];

    for (int i=0; i < N; i++)
        for (int j=0; j < N; j++)
            fIn >> distance[i][j];

    //representing the set in the form of an integer - the i-th bit set iff the i-th stop is selected.      
    int dp[1 << N][16];
    std::memset(dp,-1,sizeof(dp));

    dp[1][0] = 0;
    for (int i=1; i < (1 << N); i++){
        for (int j=0; j < N; j++){
            if (dp[i][j] == -1)
                continue;
            for (int k=1; k < N; k++){
                if ((i & (1 << k)) != 0)
                    continue;
                int p = (i | (1 << k));
                if (dp[p][k] == -1)
                    dp[p][k] = dp[i][j] + distance[j][k];
                dp[p][k] = std::min(dp[p][k],dp[i][j]+distance[j][k]);
            }

        }
    }

    int ans = std::numeric_limits<int>::max();
    for (int i=1; i < N; i++)
        if (dp[(1 << N)-1][i] > 0)
            ans = std::min(ans, dp[(1 << N)-1][i] + distance[i][0]);

    std::cout << ans << std::endl;  

}

This solution is based on the naive solution checking out all possible tours but with a modified approach that make it not take too long.

The exploration start from the first stop and explore the possible solution like a tree, when a branch is likely to exceed the previously found minimum, this branch is abounded.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

costs = [[0, 3696, 1790, 1136, 279, 824, 2609, 481, 4051, 2835, 97, 3069, 460, 2940, 3985, 2575],
[3696, 0, 2549, 1395, 2253, 1292, 1834, 2319, 2118, 2836, 1007, 69, 2723, 1694, 974, 1171],
[1790, 2549, 0, 2891, 3359, 2807, 3925, 248, 3762, 2103, 245, 2774, 289, 3147, 3326, 2836],
[1136, 1395, 2891, 0, 2261, 3993, 1771, 4047, 3197, 3289, 2762, 3556, 288, 992, 700, 3129],
[279, 2253, 3359, 2261, 0, 2484, 1258, 2687, 2358, 3941, 361, 178, 2895, 2401, 525, 3788],
[824, 1292, 2807, 3993, 2484, 0, 2606, 3987, 2415, 1042, 690, 369, 2526, 3910, 1253, 2550],
[2609, 1834, 3925, 1771, 1258, 2606, 0, 1224, 2246, 4072, 1227, 3917, 3859, 2390, 1285, 67],
[481, 2319, 248, 4047, 2687, 3987, 1224, 0, 3317, 1401, 2679, 1207, 1042, 1806, 3397, 1197],
[4051, 2118, 3762, 3197, 2358, 2415, 2246, 3317, 0, 3444, 82, 2531, 3453, 2081, 2562, 1507],
[2835, 2836, 2103, 3289, 3941, 1042, 4072, 1401, 3444, 0, 3956, 3049, 295, 208, 1230, 1597],
[97, 1007, 245, 2762, 361, 690, 1227, 2679, 82, 3956, 0, 3966, 2779, 3554, 1960, 2710],
[3069, 69, 2774, 3556, 178, 369, 3917, 1207, 2531, 3049, 3966, 0, 1369, 262, 3230, 2204],
[460, 2723, 289, 288, 2895, 2526, 3859, 1042, 3453, 295, 2779, 1369, 0, 1245, 1580, 3499],
[2940, 1694, 3147, 992, 2401, 3910, 2390, 1806, 2081, 208, 3554, 262, 1245, 0, 365, 1220],
[3985, 974, 3326, 700, 525, 1253, 1285, 3397, 2562, 1230, 1960, 3230, 1580, 365, 0, 582],
[2575, 1171, 2836, 3129, 3788, 2550, 67, 1197, 1507, 1597, 2710, 2204, 3499, 1220, 582, 0]]

reste = []
ariane = [0]
minpath = float("inf")

def initreste():
    global reste
    sortedcosts = sorted([costs[i][j] for i in range(16) for j in range(16) if i < j])
    cost = 0
    for i in range(16):
        cost += sortedcosts[i]
        reste = [cost] + reste


def godeep( sofar, level):
    global minpath, water

    if sofar + reste[level]  > minpath:        
        return 
    elif level == 15:
        minpath = min(minpath, sofar + costs[0][ariane[-1]])
        return 
    else:
        for p in range(1,16):
            if p not in ariane:
                ariane.append(p)
                godeep(sofar + costs[ariane[-2]][ariane[-1]], level + 1)
                ariane.pop()

def solve():
    "The Travelling PokeMan"
    global minpath
    initreste()
    godeep( 0, 0)
    return minpath

print(solve())

# Output
# 7935