许志伟课题组官方中文主页：https://JaywayXu.github.io/zh-cn/\[\min \left\{\sum_{i=1}^{n-1} d\left(c_{k_i}, c_{k_{i+1}}\right)+d\left(c_{k_n}, c_{k_1}\right)\right\} \]
搜索空间：
排列树结构，每个结点 \(\langle i_1, i_2, \dots, i_k \rangle\) 表示前 \(k\) 步的路线已确定。
约束条件：
界 (Bound)： 当前已找到的最短巡回路线的长度。
代价函数：
假设顶点 \(c_i\) 出发的最短边为 \(l_i\)，\(d_j\) 为已选定的巡回路线中第 \(j\) 段的长度，则代价函数为：
\[\boldsymbol{L}=\sum_{j=1}^k \boldsymbol{d}_j+\boldsymbol{l}_{i_k}+\sum_{i_i \notin B} \boldsymbol{l}_{i_j} \]
我们通过一个具体路径的代价函数计算示例，来更好理解分支限界算法中如何评估路径的代价和下界。
如图所示，我们假设货郎从 1号城市 出发，依次访问了 3号城市 和 2号城市，形成了部分路径 \(\langle 1, 3, 2 \rangle\)。现在我们已经走到 2号城市，接下来需要计算该路径的代价函数，来评估当前路径的花费以及剩余部分的下界。
代价函数 \(L\) 的通用表达式如下：
\[L = \text{已走过的路径长度} + \text{剩余部分的估计长度下界} \]
已走过的路径长度：
将已访问的城市之间的路径距离累加，例如在路径 \(\langle 1, 3, 2 \rangle\) 中，
\[1 \to 3：9 \,\, (单位) \]
\[3 \to 2：13 \,\, (单位) \]
已走过的路径总长度为：
\[9 + 13 = 22 \,\, (单位) \]
剩余部分的估计长度下界：
因此，剩余部分的估计长度下界为：
\[2 + 2 = 4 \,\, (单位) \]
将已走过的路径长度和剩余部分的下界相加，得到代价函数的值：
\[L = 22 + 4 = 26 \,\, (单位) \]
这个代价函数的结果表明，无论之后如何规划剩余的路径，完整路径的总长度不会小于 26。这个下界帮助算法在搜索时进行剪枝，即当其他路径的代价超过该下界时，就不再继续深入搜索该分支。
初始结点： 从城市 1 出发。
可选路径：
深度优先遍历：
第一条路径：\(\langle 1, 2, 3, 4, 1 \rangle\)，长度 \(29\)。
更新界：
找到路径 \(\langle 1, 2, 4, 3, 1 \rangle\)，长度 \(23\)。更新界 \(B = 23\)。
剪枝：
当搜索路径 \(\langle 1, 3, 2 \rangle\) 的代价函数值为 \(26\)，大于当前界 \(B = 23\)，停止搜索该分支。
初始路径：
更新路径：
剪枝：
最优解：
搜索树的规模：
时间复杂度：
实际性能：
通过剪枝操作，大大减少了实际搜索空间，因此平均运行时间优于蛮力算法。
货郎问题的分支限界算法：
时间复杂度： \(O(n!)\)，在最坏情况下与蛮力算法相同，但通过剪枝可显著提升平均性能。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。