如何在动态规划+位掩码求解的旅行商问题中追踪最优路径

你的问题核心是DP表只记录了最小成本，没保存决策路径，直接传path参数会因为递归中的局部覆盖导致失效。解决思路是额外维护一个prev（前驱）表，记录每个状态（mask, current）下选择的下一个最优节点，最后通过回溯这个表还原完整路径。

具体实现步骤 #

1. 新增前驱记录表 #

创建一个和dp结构完全一致的二维数组prev，类型为std::vector<std::vector<int>>，用来存储每个状态对应的最优决策节点。

2. 修改递归函数记录决策 #

在递归计算最小成本的过程中，当找到更优的子问题解时，将对应的节点记录到prev[mask][current]中。

3. 回溯前驱表生成路径 #

计算完最小成本后，从初始状态（mask=1，current=0）开始，根据prev表依次找到每个步骤的下一个节点，直到回到起点。

修改后的完整代码 #

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

static int tsp(const std::vector<std::vector<int>>& dist, size_t current, uint64_t mask, 
               std::vector<std::vector<int>>& dp, std::vector<std::vector<int>>& prev) {
    int n = dist.size();
    if (mask == ((uint64_t)1 << n) - 1) {
        // 所有节点访问完毕，回到起点，无后续节点设为-1
        prev[mask][current] = -1;
        return dist[current][0];
    }

    if (dp[mask][current] != -1)
        return dp[mask][current];

    int result = INT_MAX;
    int best_next = -1;
    for (uint64_t i = 0; i < n; ++i) {
        uint64_t val = (uint64_t)1 << i;
        if (mask & val)
            continue;

        int sub_cost = dist[current][i] + tsp(dist, i, mask | val, dp, prev);
        if (sub_cost < result) {
            result = sub_cost;
            best_next = i; // 记录当前状态下的最优下一个节点
        }
    }

    dp[mask][current] = result;
    prev[mask][current] = best_next;
    return result;
}

std::vector<int> get_optimal_path(const std::vector<std::vector<int>>& prev, int start, int n) {
    std::vector<int> path;
    uint64_t mask = 1 << start;
    int current = start;

    path.push_back(current);
    while (true) {
        int next_node = prev[mask][current];
        if (next_node == -1) {
            // 回到起点，结束回溯
            path.push_back(start);
            break;
        }
        path.push_back(next_node);
        mask |= (1 << next_node);
        current = next_node;
    }
    return path;
}

int main() {
    std::vector<std::vector<int>> dist{
        {0, 10, 41, 31},
        {10, 0, 30, 19},
        {41, 30, 0, 20},
        {31, 19, 20, 0}
    };
    int n = dist.size();

    std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, -1));
    std::vector<std::vector<int>> prev(1 << n, std::vector<int>(n, -1));

    int min_cost = tsp(dist, 0, 1, dp, prev);
    std::cout << "最小成本: " << min_cost << std::endl;

    std::vector<int> path = get_optimal_path(prev, 0, n);
    std::cout << "最优路径: ";
    for (size_t i = 0; i < path.size(); ++i) {
        if (i > 0) std::cout << "-";
        std::cout << path[i];
    }
    std::cout << std::endl;

    return 0;
}

代码说明 #

• prev[mask][current]存储的是：当处于mask状态（已访问节点集合）、当前在current节点时，下一步应该前往的最优节点。
• get_optimal_path函数从起点开始，依据prev表逐步跳转，直到回到起点，生成完整的最优路径。
• 运行后会输出最小成本: 90和最优路径: 0-1-3-2-0，与预期一致。

内容的提问来源于stack exchange，提问作者Szyszka947