固定节点数带多约束的加权图两点最短路径求解优化问题

核心问题定位 #

你当前实现的受限DFS性能差的核心原因是没有利用position属性的强约束，无差别遍历邻接节点导致搜索空间被不必要放大，同时递归调用、列表成员判断等操作也带来了大量额外开销。

最优解决方案：基于排列的分层动态规划 #

该方案完全不损失精度，常规场景下Python运行耗时可控制在1秒内，远低于10秒要求。

核心逻辑 #

因为路径必须恰好包含5个position全唯一的节点，刚好对应5个枚举值的全排列，总共只有5! = 120种可能的position序列，可基于该特性极大压缩搜索空间：

1. 预处理所有节点按position分组，得到5组节点集合G[p]，p为position枚举值
2. 生成所有合法的position排列：
   • 无必选节点时直接生成5个枚举的全排列，共120种
   • 有1-2个必选节点时，过滤出包含所有必选节点对应position的排列，剩余排列数量最多为2*4! = 48（1个必选节点）或2*3! = 12（2个必选节点）
3. 对每个排列p0→p1→p2→p3→p4做分层动态规划：
   • 定义dp[k][node]为走到排列第k位的node节点时的最小成本，以及对应的路径
   • 初始化：若排列第0位对应必选节点则直接初始化该节点成本为0，否则初始化起始节点成本为0
   • 逐层转移：dp[k][v] = min(dp[k][v], dp[k-1][u] + weight(u, v))，其中u属于G[p_{k-1}]，v属于G[p_k]且u和v存在连边
   • 转移到第4位后，检查节点是否为目标节点、路径包含所有必选节点，记录最小成本的路径
4. 遍历完所有排列后返回全局最优路径即可

现有代码局部优化方案（无需重构核心逻辑） #

如果你不想大改现有DFS实现，可通过以下修改将性能提升5-10倍：

• 增加上界剪枝：每次递归前判断当前路径累计成本 + 当前节点到目标节点的最小权重下界（可预计算所有节点到终点的最短路径）如果大于当前最优成本，直接终止该分支搜索
• 把路径中的节点、已用position存为集合，将成员判断的时间复杂度从O(n)降到O(1)
• 预计算所有边的权重并缓存，避免每次调用graph.weight重复计算
• 把递归实现改为迭代实现，消除Python递归调用的额外开销
• 过滤邻接节点时优先遍历必选节点相关的边，更快找到基准最优解用于后续剪枝

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