Held-Karp算法的C++代码

Held-Karp算法是动态规划的一种应用，用于解决旅行商问题 (TSP)。该算法通过记录部分路径的最小成本来避免重复计算，从而有效地降低计算复杂度。

Held-Karp算法使用一个状态压缩动态规划表dp，其中dp[mask][i]表示从起点出发，访问过所有由mask表示的集合中的节点，并以节点i结束的最小路径长度。

#include <iostream>
#include <vector>
#include <limits>

class HeldKarp {
private:
    int n; // 城市数量
    std::vector<std::vector<int>> distances; // 城市间距离矩阵
    std::vector<std::vector<int>> dp; // 动态规划表

public:
    // 构造函数，初始化距离矩阵和状态表
    HeldKarp(const std::vector<std::vector<int>>& dist) 
        : distances(dist), n(dist.size()) {
        int max_mask = 1 << n; // 最大的掩码数，即2^n
        dp.resize(max_mask, std::vector<int>(n, std::numeric_limits<int>::max())); // 初始化动态规划表，默认值为无穷大
        dp[1][0] = 0; // 起始城市的状态初始化为0
    }

    // 求解TSP问题的函数
    int solve() {
        for (int mask = 1; mask < (1 << n); mask++) { // 遍历所有可能的掩码
            for (int u = 0; u < n; u++) { // 遍历所有城市
                if (mask & (1 << u)) { // 如果城市u在掩码中
                    for (int v = 0; v < n; v++) { // 遍历所有城市
                        if (!(mask & (1 << v))) { // 如果城市v不在掩码中
                            int next_mask = mask | (1 << v); // 更新掩码，加入城市v
                            dp[next_mask][v] = std::min(dp[next_mask][v], dp[mask][u] + distances[u][v]); // 更新动态规划表
                        }
                    }
                }
            }
        }

        // 计算从最后一个城市回到起点的最短路径
        int ans = std::numeric_limits<int>::max(); // 初始化最小值为无穷大
        for (int u = 1; u < n; u++) { // 遍历所有城市
            ans = std::min(ans, dp[(1 << n) - 1][u] + distances[u][0]); // 计算最小值
        }
        return ans; // 返回最短路径长度
    }
};

int main() {
    // 定义城市间的距离矩阵
    std::vector<std::vector<int>> distances = {
        {0, 10, 15, 20}, // 城市0到其他城市的距离
        {10, 0, 35, 25}, // 城市1到其他城市的距离
        {15, 35, 0, 30}, // 城市2到其他城市的距离
        {20, 25, 30, 0} // 城市3到其他城市的距离
    };

    // 创建HeldKarp对象，并传入距离矩阵
    HeldKarp hk(distances);
    int minDistance = hk.solve(); // 求解最短路径长度
    std::cout << "最短路径长度: " << minDistance << std::endl; // 输出最短路径长度

    return 0; // 返回0，表示程序正常结束
}

原文地址：https://blog.csdn.net/m0_61862494/article/details/140557729

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！