回溯法求解TSP问题

Question

假设当前旅行售货员的住地为1号城市，边上的权为城市之间的交通费用，要求从1号城市出发，到其它城市各去一次推销商品，然后再回到住地所花费的总交通费用最少的路线。（要求：做好搜索前的准备，然后用搜索树展示搜索过程）

Answer 1

好的，下面是C++代码实现：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 20;

int n, m[N][N], f[1 << N][N];

int dp(int S, int u) //S表示状态集合，u表示当前所在的节点
{
    if (S == (1 << n) - 1 && u == 0) return 0; //若所有节点都遍历过，且到达了起始节点，则找到了答案，返回0。
    if (~f[S][u]) return f[S][u];  //若该状态已经记忆化，直接返回
    int res = 1e9;
    for (int i = 0; i < n; i++) 
    {
        if (S & (1 << i)) continue;  //节点已经遍历过
        res = min(res, dp(S | (1 << i), i) + m[u][i]); //更新答案
    }
    return f[S][u] = res;  //记忆化
}

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

    memset(f, -1, sizeof f);
    cout << dp(1, 0); //起点为1，状态为{1}
    return 0;  
}

该算法使用状态压缩和记忆化搜索实现，其中 $f[S][u]$ 表示走过状态集合 $S$，目前所在节点为 $u$ 的最小代价。