TSP问题贪心法代码实现C++

旅行商问题（Travelling Salesman Problem, TSP）是一个经典的组合优化问题，目标是找到一条从给定城市列表出发，经过所有城市恰好一次并返回原点的最短路径。贪心算法是一种近似解决TSP问题的方法，但不是最优解，通常用于求得启发式解。

下面是一个简单的C++代码示例，使用贪心策略（优先选择最近的城市）作为初始解：

#include <iostream>
#include <vector>
#include <algorithm>

// 定义城市结构体
struct City {
    int id;
    double x, y; // 坐标
};

// 计算两个城市之间的距离
double distance(City& a, City& b) {
    return std::sqrt(std::pow(a.x - b.x, 2) + std::pow(a.y - b.y, 2));
}

// 使用贪心算法生成初步路线
std::vector<int> greedy_TSP(const std::vector<City>& cities) {
    std::sort(cities.begin(), cities.end(), [](const City& a, const City& b) { return distance(a, cities[0]) < distance(b, cities[0]); });
    std::vector<int> route = {cities[0].id};
    
    for (size_t i = 1; i < cities.size(); ++i) {
        route.push_back(cities[i].id);
    }
    route.back() = cities[0].id; // 返回起点
    return route;
}

int main() {
    std::vector<City> cities = {{1, 1}, {2, 5}, {3, 3}, {4, 6}}; // 示例城市坐标
    std::vector<int> initial_route = greedy_TSP(cities);

    std::cout << "Greedy TSP Route: ";
    for (int city : initial_route)
        std::cout << city << " -> ";

    return 0;
}

这个代码首先对城市按到起点的距离排序，然后按照顺序依次添加到路线中，最后连接回起点。但请注意，这种方法得到的结果并不是最佳解决方案，因为贪心策略无法保证全局最小化。