TSP（旅行商问题）C++完整代码

旅行商问题（Traveling Salesman Problem, TSP）是一个经典的组合优化问题，目标是最短路径，使得一位旅行者访问所有城市恰好一次然后返回起点。由于其复杂性，通常采用启发式算法如遗传算法、模拟退火或最近邻算法等求解近似最优解。

以下是使用C++的一个简化版最近邻算法的TSP解决思路，这只是一个基本框架，并非最高效的解决方案：

#include <vector>
#include <limits>

// 城市类，存储城市坐标
class City {
public:
    int x, y;
    City(int x, int y) : x(x), y(y) {}
};

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

// 近邻搜索，寻找当前路径中最远的城市并替换它
City nearest_city(std::vector<City>& path) {
    City farthest = path[0];
    int max_dist = 0;

    for (size_t i = 1; i < path.size(); ++i) {
        int dist = distance(path[i], farthest);
        if (dist > max_dist) {
            max_dist = dist;
            farthest = path[i];
        }
    }

    return farthest;
}

// 最近邻算法，用于求解TSP
std::vector<City> nearest_neighbor(const std::vector<City>& cities) {
    std::vector<City> path(cities.begin(), cities.begin());
    path.push_back(cities[0]); // 返回起点

    while (path.size() != cities.size()) {
        City next_city = nearest_city(path);
        path.erase(std::remove(path.begin(), path.end(), next_city), path.end());
        path.insert(path.end(), next_city);
    }

    return path;
}

int main() {
    // 添加实际城市的创建和数据
    std::vector<City> cities = { /* ... */ };
    
    std::vector<City> tour = nearest_neighbor(cities);
    for (const auto& city : tour) {
        std::cout << "City at (" << city.x << ", " << city.y << ")\n";
    }

    return 0;
}