旅行商问题c++

旅行商问题(TSP)是一个经典的组合优化问题，要求在给定的一些城市之间建立一条最短的回路，使得每个城市恰好被访问一次。这个问题是 NP 难问题，因此并没有一种高效的算法可以解决它。但是，我们可以使用一些近似算法来解决 TSP 问题。

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

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

using namespace std;

const int MAXN = 20;
const double INF = 1e9;

int n;
double dist[MAXN][MAXN];
bool vis[MAXN];

double tsp(int u, int cnt, double len) {
    if (cnt == n) {
        return len;
    }
    double res = INF;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            vis[i] = true;
            res = min(res, tsp(i, cnt + 1, len + dist[u][i]));
            vis[i] = false;
        }
    }
    return res;
}

int main() {
    cin >> n;
    vector<pair<double, double>> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].first >> points[i].second;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                double dx = points[i].first - points[j].first;
                double dy = points[i].second - points[j].second;
                dist[i][j] = sqrt(dx * dx + dy * dy);
            }
        }
    }
    fill(vis, vis + n, false);
    vis[0] = true;
    double ans = tsp(0, 1, 0);
    cout << ans << endl;
    return 0;
}

这个代码使用了一个简单的深度优先搜索的方式来枚举每个城市的访问顺序，并计算出回路的总长度。由于 TSP 问题是 NP 难问题，因此这个算法的时间复杂度是 O(n^n)，只适用于小规模的问题。