tsp问题动态规划c++

TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，然后回到出发城市，并要求所走路程最短。动态规划是解决TSP问题的一种方法。下面是一个使用C++实现TSP问题动态规划的例子：

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

const int MAXN = 20;
const int INF = 0x3f3f3f3f;

int c[MAXN][MAXN]; // 城市间距
int d[1 << MAXN][MAXN]; // TSP最终结果
int col; // TSP最终结果表的列数
int sub[1 << MAXN]; // 子集

void setDistance(int num) { // 创建城市间间距矩阵C
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            cin >> c[i][j];
        }
    }
}

int subContain(int n) { // 判断元素是否存在于子集
    int i = 0;
    while (sub[i] != -1) {
        if (sub[i] == n) {
            return 1;
        }
        i++;
    }
    return 0;
}

int subGather(int n, int num) { // 将数字n转化为子集形式存放在集合sub[]中
    int i = 0;
    int length = 0;
    memset(sub, -1, sizeof(sub));
    while (n > 0) {
        if (n & 1) {
            sub[i] = num - 1;
            length++;
        }
        n >>= 1;
        i++;
    }
    return length;
}

int deSub(int k, int j) { // 求集合{1,3}剔除元素3后的子集
    int t = 1 << j;
    return (k & (~t));
}

int doTSP(int num) {
    memset(d, INF, sizeof(d));
    d[1][0] = 0;
    for (int i = 1; i < (1 << num); i++) {
        int length = subGather(i, num);
        for (int j = 0; j < num; j++) {
            if (subContain(j)) {
                for (int k = 0; k < num; k++) {
                    if (subContain(k) && k != j) {
                        int t = deSub(i, j);
                        d[i][j] = min(d[i][j], d[t][k] + c[k][j]);
                    }
                }
            }
        }
    }
    return d[(1 << num) - 1][0];
}

void showResult(int num) { // 输出结果
    int i = (1 << num) - 1;
    int j = 0;
    col = 0;
    int result[20];
    memset(result, -1, sizeof(result));
    while (i > 0) {
        result[col++] = j;
        int t = i;
        i = deSub(i, j);
        j = 0;
        while (t > i) {
            t >>= 1;
            j++;
        }
    }
    cout << "最短路径为：" << endl;
    for (int i = col - 1; i >= 0; i--) {
        cout << result[i] << " ";
    }
    cout << endl;
}

int main() {
    int num;
    cout << "请输入城市数量：" << endl;
    cin >> num;
    cout << "请输入城市间距矩阵C：" << endl;
    setDistance(num);
    int shortestPath = doTSP(num);
    cout << "最短路径长度为：" << shortestPath << endl;
    showResult(num);
    return 0;
}