48小时限时可重复遍历节点的最优回路算法设计求助

问题建模 #

这本质是带时间约束、允许重复访问节点但节点收益仅计一次的旅行商问题（TSP）变种，核心约束：

• 总旅行时长 < 48小时（建议统一转换为分钟：2880分钟，避免浮点误差）
• 必须返回出发城市
• 目标是最大化已访问城市的评分总和（重复访问同一城市不重复累加评分）

核心优化思路 #

暴力DFS枚举所有路径的时间复杂度为指数级且无状态复用，完全不可行。我们需要用动态规划（DP）结合状态剪枝，核心是把状态定义为「已访问城市集合+当前所在城市+已用时间」，通过记录每个状态的最高评分，避免重复计算相同访问逻辑的路径。

具体实现步骤 #

1. 预处理：计算任意城市间的最短旅行时间 #

由于并非所有城市间有直达路径，先通过Floyd-Warshall或Dijkstra算法预处理出任意两个城市u和v之间的最短旅行时间dist[u][v]。如果u和v之间无法到达，标记为无穷大。

2. 状态定义 #

用DP[mask][u][t]表示：

• mask：二进制掩码，第i位为1表示已访问城市i并获得其评分（重复访问不改变mask）
• u：当前所在的城市编号
• t：已消耗的旅行时间（分钟）
• 存储值：该状态下能获得的最高评分总和

初始化时，设出发城市为s，则DP[1 << s][s][0] = score[s]，其余状态初始化为-∞（表示不可达）。

3. 状态转移 #

遍历所有有效状态(mask, u, t)，对每个状态执行以下操作：

• 遍历所有可到达的城市v（即dist[u][v]不为无穷大）
• 计算新的旅行时间：t_new = t + dist[u][v]，若t_new >= 2880则跳过（超过总时长限制）
• 计算新的掩码和评分：
  • 若v未被访问过（mask的第v位为0）：
    • mask_new = mask | (1 << v)
    • score_new = DP[mask][u][t] + score[v]
  • 若v已被访问过：
    • mask_new = mask
    • score_new = DP[mask][u][t]
• 若score_new > DP[mask_new][v][t_new]，则更新DP[mask_new][v][t_new] = score_new

4. 剪枝优化（关键） #

为了减少状态数量，对每个(mask, u)组合，只保留Pareto最优状态：

• 对于同一(mask, u)下的两个状态t1 < t2，若DP[mask][u][t1] >= DP[mask][u][t2]，则直接丢弃t2对应的状态——因为用更短的时间拿到了不低的评分，后续所有从t2出发的路径都不可能比t1的更优。

5. 计算最终结果 #

遍历所有有效状态(mask, u, t)，筛选出满足t + dist[u][s] < 2880的状态（即从当前城市返回出发城市后总时长仍符合要求），取这些状态的评分最大值即为答案。

复杂度分析 #

• 最坏情况状态数：O(2^n * n * T)，其中n为城市数量，T=2880为总分钟数
• 实际通过剪枝后，状态数会大幅减少：对于n<=12的场景完全可行；若n达到15，结合Pareto剪枝也能在合理时间内计算完成

注意事项 #

• 时间单位必须统一（建议用分钟），避免因浮点运算产生的误差
• 若出发城市返回自身的时间不为0（比如绕路），需在最终判断时计入该时间
• 预处理最短路径时，要处理无法到达的城市对（标记为无穷大，转移时跳过）

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