In today's practice of dynamic programming, I met a problem called "Shortest Hamilton Path". In fact, the thought of state compression DP is not difficult to catch, but there are details hidden in the problem.

The Problem( Shortest Hamilton Path )

Given a weighted undirected graph with n vertices, which are numbered from 0 to n - 1. Please answer the shortest hamilton path from 0 to *n - 1.

Hamilton Path: A path that visits each vertex from 1 to n - 1 onece and only once.

The range: 1 <= n <= 20, 0 <= w <= 10^7. w indicates the weight.

Solution

Firstly, let's see what if we use brute force to solve it.

Since we have to enumerate all the possible paths between 1 and n - 1, the time complexity will come to O(n!). that's too complex becausen``` is up to 20.

Well, the thought of DP comes to me because the problem could be divided into child problems. The shortest hamilton path from 0 to k(k < n - 1) is a child problem.

The key is that how to build the state transition equation. You will find it impossible to directly build it because there are total n! conditions, which is too large for us to save them on the heap.

Then how to satisfy the requirement of time and space simultaneously?

The answer is state compression DP. Noticed that n <= 20 and as is known to all, Int32 have 1 bit to indicate the symbol and 31 bit to indicate the number. Then we could compress the state of a condition into an integer.

For example, as is shown in the figure below, we use binary to express the condition of each vertex, "chosen" or "not chosen".

Now let's build the state transition equation.

We use f[i][j] to indicate the available path to condition "i" which has vertex j as the latest added vertex.

Well, it may be a little difficult to understand. The "i" is the integer shown in the figure above, which express a kind of condition. You can just think it as a kind of combination of the vertices.

The transition equation is shown below. We use w to indicate the weight of vertices.

$$ f\left[ i \right] \left[ j \right] \,\,=\,\,\underset{k\,\,=\,\,1}{\overset{n\,\,-\,\,1}{Min}}\left( \min \left( f\left[ i \right] \left[ j \right] , f\left[ i\,\,-\,\,\left( 1 <<\,\,j \right) \right] \left[ k \right] \,\,+\,\,w\left[ k \right] \left[ j \right] \right) \right) $$

Vertex j is the vertext we want to add this time. Obviously, in the last time, there is not vertex j in the path. So we use f[i - (1 << j)][k] to suggest this point, which means the current state is transfered from a path without vertex j and with vertex "k" as the end. The minimum value between f[i][j] and f[i - (1 << j)][k] + w[k] is choosed to be the length of the path to "i". Certainly, the value of k could be in the range between 1 and n - 1, so we loop with k to get the final value.

Code

An instance of the code of the solution is given here.

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20, M = 1 << N;

int n;
int w[N][N];
int f[M][N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            cin >> w[i][j];

    memset(f, 0x3f, sizeof f); // Init the array with a number large enough
    f[1][0] = 0;

    for (int i = 0; i < 1 << n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1)
                for (int k = 0; k < n; k ++ )
                    if (i >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);

    cout << f[(1 << n) - 1][n - 1];

    return 0;
}

It's a clean job, isn't it?

However, there is a fatal detail in the code, which is hidden in the block below.

for (int i = 0; i < 1 << n; i ++ ) // line 1
        for (int j = 0; j < n; j ++ )  // line 2
            if (i >> j & 1) // line 3
                for (int k = 0; k < n; k ++ )
                    if (i >> k & 1)  // line 5
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);

What if we exchange line 1 and line 2?

If you tried yourself, you will find you get the wrong answer. Why?

The key is that you can not use a state that haven't been calculated to transfer from one state to another.

1. If we exchanged the order: state f[i - (1 << j)][k] may have not been calculated because the k have not been visited since the loop of k is outermost.

2. If we kept the order: state f[i - (1 << j)][k] must have been calculated because every time when we enter the "next i", a loop of k has been completed.

You may be confused about the item 2 above because it seems that some state of f[i - (1 << j)][k] haven't been visited. For example, we began at "00001". After the first step, we got "00011". And now we want to calculate f["10011"][3]. Then we enumerate the k from 1 to 4. When k = 4, it seems that a contradiction happens...

And that's why we write down line 3 and line 5! These two sentence ensure that invalid state will be excluded before the state transition. Line 3 ensures that the current "i" has vertex j and line 5 ensures the last state(and the current state) as vertex k.

Now all things have been well done!

Complexity Analysis

1. Time Complexity: $$ O(n^22^n) $$

2. Space Complexity: $$ O(n2^n) $$