旅行商问题

此题实际上是一个动态规划的问题
B站讲解
将整个路径排成一个圈，这一圈总的路程最小
因此从哪个点出发已经无所谓了，指定为0
先递推一个开环问题，也就是从某个固定点出发遍历地图上所有的点，最短的总路径是什么
- 任意一个长度为n，结尾点为i的问题都依赖于一个长度为n-1，而且不包括i点的路径的总路程
递推数组中记录[按位表示的经历过的点][末尾位置][路线的总长度]
递推
n从2开始
对于所有长度为n-1的路径，搜索其中所有到达过的点不同的路径
对于到达过的点相同的路径，按末尾点不同搜索路径
用地图上除了开始点之外的所有点尝试作为新的到达点
- 如果这个点该路径已经到达过了，跳过
- 如果没有，则将其添加到路径中，将路径的总长度增加一个原来的末尾点到这个点的距离
将路径的末尾点修改为当前点
查找长度为n的路径表中是否已经存在了<到达点与其相同><末尾点与其相同>的路径
- 如果存在，将其长度和刚求出的长度取最小值，更新为新的<到达点与其相同><末尾点与其相同>的所有路径的最小长度（不关心中间点的顺序，只在意结束位置）
最开始的时候，向dp图长度为1的路径添加所有起始点以外的点，长度为从起始点到任意点的距离，表示从开始点到任意其他点的路径
结束的时候，长度为n的路径应该具有相同的到达点（也就是除了开始点之外的点全部到达过），这是末尾点不同，根据不同的末尾点，寻找末尾点返回起始点的距离，将其加到路径的长度上计算出每条长度为n的路径的闭环长度

最短的一条就是结果

#include <cmath>
#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
#include <climits>
using namespace std;

vector<vector<int>> to;
vector<unordered_map<int, unordered_map<int, int>>> dp;
int main() {
    int n;
    cin>>n;
    to = vector<vector<int>>(n, vector<int>(n));
    for(int i = 0; i<n; ++i)
    {
        for(int j = 0;j<n; ++j)
        {
            cin>>to[i][j];
        }
    }
    dp = vector<unordered_map<int, unordered_map<int, int>>>(n+1);
    // 默认从0开始
    // dp的第一个下标是路径长度，第二个是当前到达过的点标志（从低到高按位），第三个是当前路径的最后一个点
    for(int i = 1; i<n; ++i)
    {
        dp[1][1<<i][i] = to[0][i];

    }
    for(int len = 2; len<n; ++len)
    {
        for(auto p : dp[len-1])
        {
            for(auto q : p.second)
            {
                for(int s = 1; s<n; ++s)
                {
                    if((1<<s)&p.first)continue;
                    if(dp[len].count(p.first|1<<s))
                    {
                        if(dp[len][p.first|1<<s].count(s))
                        {
                            dp[len][p.first|1<<s][s] = min(dp[len][p.first|1<<s][s], q.second+to[q.first][s]);
                        }
                        else 
                        {
                            dp[len][p.first|1<<s][s] = q.second+to[q.first][s];
                        }
                    }
                    else 
                    {
                        dp[len][p.first|1<<s][s] = q.second+to[q.first][s];
                    }
                }
            }
        }

    }
    int minDist = INT_MAX;
    for(auto p : dp[n-1])
    {
        for(auto q:p.second)
        {
            minDist = min(minDist, q.second+to[q.first][0]);
        }
    }
    cout<<minDist<<endl;
}
// 64 位输出请用 printf("%lld")

旅行商问题

递推