贪心法求解TSP问题c++代码

贪心算法通常不是解决旅行商问题 (Traveling Salesman Problem, TSP) 的理想方法，因为TSP是一个已知的NP完全问题，而贪心策略并不保证一定能找到全局最优解。然而，有一些近似算法，如"nearest neighbor" 或 "closest pair first"，可以作为启发式解决方案。

下面是一个简单的基于贪心策略的近似C++代码示例，它使用了 nearest neighbor 算法：

#include <iostream>
#include <vector>
#include <limits.h>

struct City {
    int id;
    double x, y; // 假设城市是由二维坐标表示
};

double distance(City& a, City& b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

int nearestNeighbor(std::vector<City>& cities) {
    std::vector<int> tour(cities.size());
    tour[0] = 0;

    for (size_t i = 1; i < cities.size(); ++i) {
        int minDistance = INT_MAX;
        size_t nextCityIndex = 0;
        for (size_t j = 0; j < cities.size(); ++j) {
            if (j != tour[i - 1] && distance(cities[tour[i - 1]], cities[j]) < minDistance) {
                minDistance = distance(cities[tour[i - 1]], cities[j]);
                nextCityIndex = j;
            }
        }
        tour.push_back(nextCityIndex);
    }

    // Add back to the start for the loop closure
    tour.push_back(tour[0]);

    return tour;
}

int main() {
    std::vector<City> cities = {/* 城市数据 */};
    auto tour = nearestNeighbor(cities);

    for (size_t i = 0; i < tour.size(); ++i) {
        std::cout << "City " << tour[i] << " -> ";
    }
    std::cout << "City 0\n";

    return 0;
}

这个代码首先定义了一个City结构体，然后计算两点之间的欧氏距离。`nearestNeighbor` 函数按顺序选择最近的城市加入路径，直到所有城市都被访问过，并返回一个城市索引的序列。注意，这仅给出的是最短路径的一个近似解，而不是最优解。