c++旅行商问题

旅行商问题（Traveling Salesman Problem，TSP）是计算机科学中的一类经典问题，它的目标是求解给定的一组城市和每对城市之间的距离，找到一条最短路径，使得每个城市恰好被访问一次，最后回到起点城市。这个问题属于NP难问题，因此不存在多项式时间算法可以完全解决该问题。常见的解决方法包括贪心算法、动态规划和遗传算法等。

下面是一个简单的用贪心算法解决TSP问题的C++代码示例：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int main() {
    int n; // 城市数
    cin >> n;
    vector<vector<int>> d(n, vector<int>(n)); // 距离矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> d[i][j];
        }
    }
    vector<int> path(n); // 存储路径
    for (int i = 0; i < n; ++i) {
        path[i] = i;
    }
    int ans = INF; // 最短路径长度
    do {
        int sum = 0; // 计算当前路径的长度
        for (int i = 1; i < n; ++i) {
            sum += d[path[i - 1]][path[i]];
        }
        sum += d[path[n - 1]][path[0]];
        ans = min(ans, sum); // 更新最短路径长度
    } while (next_permutation(path.begin() + 1, path.end())); // 生成全排列
    cout << ans << endl; // 输出最短路径长度
    return 0;
}

该代码使用了STL中的`vector`和`next_permutation`函数，具体实现过程是先读入距离矩阵，然后生成所有城市的全排列，对于每个排列计算路径长度并更新最短路径长度。这个算法的时间复杂度是O(n!)，因此只适用于小规模的问题。