用贪心法求解tsp的两种c++代码

贪心算法通常不是解决旅行商问题（Traveling Salesman Problem, TSP）的理想方法，因为TSP属于NP完全问题，最优解需要搜索所有可能性，而贪心策略只能得到局部最优而非全局最优。然而，有一些近似算法可以基于贪心思想，如" nearest neighbor"（最近邻）或 "closest pair first"（最短路径优先）等启发式方法。

以下是使用贪心策略（最近邻）的一种简单C++代码示例：

#include <vector>
#include <algorithm>

double distance(const std::vector<std::pair<int, int>>& cities) {
    // 计算两点之间的曼哈顿距离或其他合适的距离度量
}

std::vector<int> nearest_neighbor_tsp(std::vector<std::pair<int, int>>& cities) {
    std::sort(cities.begin(), cities.end(), [](const auto& a, const auto& b) { return a.first + a.second < b.first + b.second; });
    
    int n = cities.size();
    std::vector<int> tour(n);
    tour[0] = 0;
    for (int i = 1; i < n; ++i) {
        tour[i] = std::distance(tour.begin(), std::min_element(tour.begin() + i, tour.end(), [cities](int a, int b) { return distance({cities[a], cities[b]}) < distance({cities[b], cities[a]}); }));
    }
    
    // 添加回起点以完成环形路径
    tour.back() = 0;

    return tour;
}

另一种基于“最短路径优先”的思路，虽然更接近于Dijkstra或A*搜索这样的图算法，但由于TSP是加权无向图，且要求是最小生成树，通常不直接称为“贪心”而是“贪婪”，但这仍然是一个简化版本：

#include <queue>
using namespace std;

struct Edge {
    int to, weight;
};

bool compareEdges(const Edge& e1, const Edge& e2) {
    return e1.weight < e2.weight;
}

vector<int> closest_pair_first_tsp(vector<Edge>& edges, vector<int>& start) {
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
    unordered_set<int> visited;
    visited.insert(start);

    vector<int> tour(start);
    tour.push_back(start);

    for (auto edge : edges) {
        if (visited.find(edge.to) == visited.end()) {
            pq.push(edge);
        }

        while (!pq.empty() && visited.find(pq.top().to) != visited.end()) {
            visited.erase(pq.top().to);
            pq.pop();
        }

        if (!pq.empty()) {
            tour.push_back(pq.top().to);
            visited.insert(pq.top().to);
            pq.pop();
        }
    }

    // Add the last node back to the start to close the cycle
    tour.push_back(start);
    return tour;
}