TSP问题的近似算法求解（如基于PRIM等主体算法） c++代码

以下是基于PRIM算法的TSP问题近似解的C++代码。

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <iomanip>
using namespace std;

const int INF = 0x3f3f3f3f;

struct Point {
    double x, y;
};

struct Edge {
    int to, cost;
};

vector<Point> points; // 存储所有点
vector<vector<Edge>> graph; // 存储图
vector<bool> used; // 存储是否已访问
vector<int> d; // 存储最短距离
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que; // 用于优先队列

// 计算两点间距离
double calcDist(Point a, Point b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

// 建图
void buildGraph() {
    graph.resize(points.size());
    for (int i = 0; i < points.size(); i++) {
        for (int j = 0; j < points.size(); j++) {
            if (i == j) continue;
            double dist = calcDist(points[i], points[j]);
            graph[i].push_back(Edge{j, (int)(dist + 0.5)});
        }
    }
}

// 基于prim算法的最小生成树
int prim(int start) {
    used.assign(points.size(), false);
    d.assign(points.size(), INF);
    d[start] = 0;
    que.push(make_pair(0, start));

    int res = 0;
    while (!que.empty()) {
        pair<int, int> p = que.top();
        que.pop();
        int v = p.second;
        if (used[v]) continue;
        used[v] = true;
        res += d[v];
        for (int i = 0; i < graph[v].size(); i++) {
            Edge e = graph[v][i];
            if (d[e.to] > e.cost && !used[e.to]) {
                d[e.to] = e.cost;
                que.push(make_pair(d[e.to], e.to));
            }
        }
    }
    return res;
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        Point p;
        cin >> p.x >> p.y;
        points.push_back(p);
    }

    // 建图
    buildGraph();

    // 计算最小生成树
    int minCost = prim(0);

    // 计算近似解
    double ans = minCost * 2.0;
    cout << fixed << setprecision(10) << ans << endl;

    return 0;
}

代码中先定义了一个`Point`结构体用于存储二维平面上的点，然后定义了一个`Edge`结构体用于存储图中的边。接着定义了全局变量`points`存储所有的点，`graph`存储图，`used`存储是否已访问，`d`存储最短距离，`que`是一个优先队列，用于实现Prim算法。

在`buildGraph`函数中，我们遍历所有的点，计算两点间的距离，然后将其作为边加入到图中。

在`prim`函数中，我们先将所有顶点的距离初始化为无穷大，然后将起点的距离设置为0，并将其加入到优先队列中。接着，我们不断从优先队列中取出距离最小的顶点，并将其标记为已访问。然后遍历这个顶点的所有邻居，如果发现某个邻居的距离比之前记录的距离小，就更新距离并将其加入到优先队列中。

最后，在主函数中，我们先计算最小生成树的权值和，然后将其乘以2作为近似解输出即可。