c++贪心法求tsp

在旅行商问题（Traveling Salesman Problem, TSP）中，贪心算法是一种常用的近似解决方案策略。TSP的目标是最短路径，使得一位“旅行商”访问所有城市一次然后返回起点。然而，由于它是NP完全问题，找到最优解的时间复杂度很高。

在一些简单的贪心算法（如克鲁斯卡尔法或哈夫曼编码）中，并不是直接应用到TSP上，但对于一些变种如"近邻贪心"（Nearest Neighbor, NN），可以尝试以下步骤：

1. **初始路线**：从任意一个城市开始，每次选择当前未访问过的最近的城市加入路线，直到所有城市都被访问过。

#include <vector>
using namespace std;

vector<int> nearest_neighbor(vector<vector<int>>& cities) {
    vector<int> visited(cities.size(), 0);
    int current_city = 0;
    vector<int> route;

    route.push_back(current_city);
    
    while (visited.size() != cities.size()) {
        visited[current_city] = 1;
        int next_city_index = min_element(cities[current_city].begin(), cities[current_city].end(),
                                        [&](int a, int b){ return cities[a][current_city] < cities[b][current_city]; }) - cities[current_city].begin();
        route.push_back(next_city_index);
        current_city = next_city_index;
    }

    // 添加回起点完成闭合环
    route.push_back(current_city);
    return route;
}

这个算法得到的结果通常不会是最优解，但它能提供一种快速的启发式解。实际上，对于TSP，更复杂且精确的贪心算法有 Held-Karp 算法等，它们试图通过动态规划改进初始路线。