单向TSP算法代码c++

以下是基于动态规划的单向TSP算法的C++代码实现，其中包括了压缩状态和剪枝的优化：

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

const int N = 20;

int n;
int w[N][N];
int dp[1 << N][N];

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

    memset(dp, 0x3f, sizeof dp);
    dp[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) && j != k) // 判断终点是否在集合中且不等于起点
                    {
                        dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + w[k][j]);
                    } 
                }
            }
        }
    }

    int res = 0x3f3f3f3f;
    for (int i = 0; i < n; i++)
        res = min(res, dp[(1 << n) - 1][i] + w[i][0]);

    cout << res << endl;

    return 0;
}

其中，dp[i][j]表示从节点j出发，经过集合i中的所有节点，最终回到起点的最短路径长度。在枚举集合i时，可以使用二进制数来表示集合，即第i位为1表示节点i在集合中，为0表示节点i不在集合中。同时，可以使用状态压缩的方法，将集合i压缩为一个长度为k的二进制数。在状态转移时，需要进行剪枝，即如果当前状态的最短路径长度已经超过了当前最优解，就可以直接跳过。最终的答案为dp[(1 << n) - 1][i] + w[i][0]，其中i表示起点为节点i，w[i][0]表示起点i到终点0的距离。