货郎担算法和代码c++

货郎担算法，又称为旅行商问题（Traveling Salesman Problem，TSP），是一个经典的组合优化问题，它的目标是找到一条最短路径，使得一名“货郎”能够访问每个城市恰好一次并返回起点。这是一个NP完全问题，意味着没有已知的有效多项式时间解法可以解决所有规模的问题。

在C++中，解决货郎担问题通常采用启发式算法，如遗传算法、模拟退火算法或蚁群算法等近似求解方法。以下是简单的模拟退火算法的一个示例：

#include <vector>
#include <cstdlib>
#include <ctime>

// 假设 cities 是一个二维向量，存储城市的坐标
std::vector<std::pair<int, int>> cities;

bool isSolutionBetter(std::vector<int>& tour, std::vector<int>& currentTour) {
    int distance = calculateDistance(tour);
    int current = calculateDistance(currentTour);
    return distance < current;
}

void swapCities(int& i, int& j, std::vector<int>& tour) {
    int temp = tour[i];
    tour[i] = tour[j];
    tour[j] = temp;
}

std::vector<int> simulatedAnnealing() {
    // 初始化随机路线
    std::vector<int> tour(cities.size());
    for (int i = 0; i < cities.size(); ++i) {
        tour[i] = i;
    }

    // 设置初始温度和冷却因子
    double temperature = 100.0;
    double coolingFactor = 0.95;
    double acceptanceProbability;

    while (temperature > 1e-6) {
        // 随机选择两个城市交换位置
        int i = rand() % cities.size();
        int j = rand() % cities.size();
        while (j == i) {
            j = rand() % cities.size();
        }
        
        std::vector<int> newTour = tour;
        swapCities(i, j, newTour);

        if (isSolutionBetter(newTour, tour)) {
            tour = newTour;
        } else {
            double costDifference = calculateDistance(tour) - calculateDistance(newTour);
            acceptanceProbability = std::exp(-costDifference / temperature);
            if (rand() / static_cast<double>(RAND_MAX) < acceptanceProbability) {
                tour = newTour;
            }
        }

        temperature *= coolingFactor;
    }

    return tour;
}

double calculateDistance(const std::vector<int>& tour) {
    double total = 0;
    for (size_t i = 0; i < tour.size() - 1; ++i) {
        total += cities[tour[i]].first + cities[tour[i+1]].first;
        total += cities[tour[i]].second + cities[tour[i+1]].second;
    }
    // 返回最后一个城市到第一个城市的距离
    total += cities[tour.back()].first + cities[0].first;
    total += cities[tour.back()].second + cities[0].second;
    return total;
}