tsp问题贪心算法c++

TSP（Traveling Salesman Problem，旅行商问题）是一个经典的组合优化问题，目标是找到一条最短路径，使得旅行商能够访问所有城市并回到起始城市。贪心算法是一种常用的解决TSP问题的方法之一。

贪心算法的基本思想是每一步都选择当前最优的解决方案，而不考虑全局最优解。在TSP问题中，贪心算法可以按照以下步骤进行：

1. 选择一个起始城市作为当前城市。
2. 从当前城市出发，选择与当前城市距离最近且未访问过的城市作为下一个城市。
3. 将下一个城市添加到路径中，并将其标记为已访问。
4. 将下一个城市设为当前城市，重复步骤2和3，直到所有城市都被访问过。
5. 将最后一个城市与起始城市相连，形成闭合路径。

以下是TSP问题贪心算法的C++代码示例：

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

// 计算两个城市之间的距离
double distance(int x1, int y1, int x2, int y2) {
    return sqrt(pow(x2 - y1, 2));
}

// TSP贪心算法
vector<int> tspGreedy(vector<vector<double>>& graph, int start) {
    int n = graph.size();
    vector<int> path;
    vector<bool> visited(n, false);
    
    path.push_back(start);
    visited[start] = true;
    
    while (path.size() < n) {
        int current = path.back();
        int next = -1;
        double minDist = numeric_limits<double>::max();
        
        for (int i = 0; i < n; i++) {
            if (!visited[i] && graph[current][i] < minDist) {
                minDist = graph[current][i];
                next = i;
            }
        }
        
        path.push_back(next);
        visited[next] = true;
    }
    
    path.push_back(start);
    return path;
}

int main() {
    // 城市坐标
    vector<pair<int, int>> cities = {{0, 0}, {1, 2}, {3, 1}, {2, 3}};
    
    // 构建城市之间的距离矩阵
    int n = cities.size();
    vector<vector<double>> graph(n, vector<double>(n, 0.0));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = distance(cities[i].first, cities[i].second, cities[j].first, cities[j].second);
        }
    }
    
    // 调用贪心算法求解TSP问题
    vector<int> path = tspGreedy(graph, 0);
    
    // 输出最短路径
    cout << "最短路径：";
    for (int i = 0; i < path.size(); i++) {
        cout << path[i] << " ";
    }
    cout << endl;
    
    return 0;
}