Hamiltonian paths哈密尔顿路径

A Hamiltonian path is a path that visits each node of the graph exactly once. For example, the graph contains a Hamiltonian path from node 1 to node 3:

If a Hamiltonian path begins and ends at the same node, it is called a Hamiltonian circuit. The graph above also has an Hamiltonian circuit that begins and ends at node 1:

Construction

Since there is no efficient way to check if a Hamiltonian path exists, it is clear that there is also no method to efficiently construct the path, because otherwise we could just try to construct the path and see whether it exists.

A simple way to search for a Hamiltonian path is to use a backtracking algorithm that goes through all possible ways to construct the path. The time complexity of such an algorithm is at least , because there are different ways to choose the order of n nodes.(使用complete search + backtracking直接搜)

A more efficient solution is based on dynamic programming . The idea is to calculate values of a function possible (S, x), where S is a subset of nodes and x is one of the nodes. The function indicates whether there is a Hamiltonian path that visits the nodes of S and ends at node x. It is possible to implement this solution in .(使用状压dp)

例题，最短Hamilton路径

//求起点0到终点n-1的最短Hamilton路径
//使用了状压dp
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int dp[1 << N][N], a[N][N], n;
int main(){
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;  // 起点位置
    for (int mask = 1; mask < (1 << n); mask++)
        for (int end = 0; end < n; end++)    
            if (mask >> end & 1)    // 走过end
                for (int from = 0; from < n; from++){
                    // hamilton路径要求，到达from结点的状态中，不能经过end这个结点,
                    // 所以要把end这个点异或掉。从而，才能实现从from转移到end
                    if ((mask ^ (1 << end)) >> from & 1)  
                        dp[mask][end] = min(dp[mask][end],
                                            dp[mask ^ (1 << end)][from] + a[from][end]);
                }
    cout << dp[(1 << n) - 1][n - 1] << '\n';
    return 0;
}
/*
填表法 ：就是一般的动态规划，当前点的状态，可以直接用状态方程，根据之前点的状态推导出来。
刷表法：由当前点的状态，更新其他点的状态。需要注意：只用当每个状态所依赖的状态对它的影响相互独立。
上面那个是填表法
下面这个是刷表法
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int dp[1 << N][N], a[N][N], n;
int main(){
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;  // 起点位置
    for (int mask = 1; mask < (1 << n); mask++)
        for (int end = 0; end < n; end++)    
            if (mask >> end & 1)    // 走过end
                for (int nxt = 0; nxt < n; nxt++)
                    if (!(mask >> nxt & 1))
                        dp[mask | (1 << nxt)][nxt] = min(
                                dp[mask | (1 << nxt)][nxt],
                                dp[mask][end] + a[end][nxt]
                        );
    cout << dp[(1 << n) - 1][n - 1] << '\n';
    return 0;
}