用c++编程实现利用贪心法求解TSP问题（最近邻点策略）

TSP问题是指在给定的一些点中找到一条经过每个点恰好一次的最短路径。最近邻点策略是一种贪心法，它在每个节点选择最近的未访问节点作为下一个节点，直到所有节点都被访问。

下面是用C++实现最近邻点策略求解TSP问题的代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int INF = 1e9;

int n;
vector<vector<int>> graph; // 图的邻接矩阵
vector<int> path; // 存储路径的数组
vector<bool> visited; // 记录节点是否已访问

// 选择下一个节点
int selectNext(int cur) {
    int next = -1;
    int minDist = INF;
    for (int i = 0; i < n; i++) {
        if (!visited[i] && graph[cur][i] < minDist) {
            next = i;
            minDist = graph[cur][i];
        }
    }
    return next;
}

// 求解TSP问题
void tsp() {
    path.push_back(0);
    visited[0] = true;
    for (int i = 1; i < n; i++) {
        int next = selectNext(path.back());
        path.push_back(next);
        visited[next] = true;
    }
}

int main() {
    cin >> n;
    graph.resize(n, vector<int>(n));
    visited.resize(n);
    for (int i = 0; i < n; i++) {
        visited[i] = false;
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }
    tsp();
    cout << "Path: ";
    for (int i = 0; i < n; i++) {
        cout << path[i] << " ";
    }
    cout << endl;
    return 0;
}

以上代码中，我们首先读入图的邻接矩阵，然后调用`tsp()`函数求解TSP问题。在`tsp()`函数中，我们从起点开始，每次选择未访问的节点中距离当前节点最近的节点作为下一个节点，直到所有节点都被访问。

最后，我们输出得到的路径。