- 此为课题组所指导本科生和低年级硕士生学习组合优化问题汇报
- 所用教材:北京大学屈婉玲教授《算法设计与分析》
- 课程资料:https://www.icourse163.org/course/PKU-1002525003 承诺不用于任何商业用途,仅用于学术交流和分享
- 更多内容请关注
许志伟
课题组官方中文主页:https://JaywayXu.github.io/zh-cn/
1. 货郎问题的分支限界算法求解 (10.4)
1.1. 货郎问题的定义
- 给定一个城市集合 \(C = \{c_1, c_2, \dots, c_n\}\),任何两个城市之间都有距离 \(d\left(c_i, c_j\right)=d\left(c_j, c_i\right) \in \mathbf{Z}^{+}, 1 \leq i<j \leq n\)。
- 目标: 找到一个城市的排列,使得从一个城市出发,访问每个城市恰好一次,并返回出发城市,总路径长度最短。
1.2. 算法设计
- 解向量:
解: \(1,2, \ldots, n\) 的排列 \(k_1, k_2, \ldots, k_n\) 使得:
-
搜索空间:
排列树结构,每个结点 \(\langle i_1, i_2, \dots, i_k \rangle\) 表示前 \(k\) 步的路线已确定。 -
约束条件:
- 已走过的城市标号放入集合 \(B = \{i_1, i_2, \dots, i_k\}\)。
- 下一步只能选择未访问过的城市:\(i_{k+1} \in \{2, \dots, n\} \setminus B\)。
- 即每个节点只能访问一次
1.3. 代价函数与界的定义
-
界 (Bound): 当前已找到的最短巡回路线的长度。
-
代价函数:
假设顶点 \(c_i\) 出发的最短边为 \(l_i\),\(d_j\) 为已选定的巡回路线中第 \(j\) 段的长度,则代价函数为:
- 前半部分:已走过的路径长度。
- 后半部分:剩余未访问的城市,从每个城市出发的最短边构成的下界。
1.4. 代价函数示例
1.4. 代价函数示例
我们通过一个具体路径的代价函数计算示例,来更好理解分支限界算法中如何评估路径的代价和下界。
示例路径及红色路径描述
如图所示,我们假设货郎从 1号城市 出发,依次访问了 3号城市 和 2号城市,形成了部分路径 \(\langle 1, 3, 2 \rangle\)。现在我们已经走到 2号城市,接下来需要计算该路径的代价函数,来评估当前路径的花费以及剩余部分的下界。
代价函数的计算公式
代价函数 \(L\) 的通用表达式如下:
\[L = \text{已走过的路径长度} + \text{剩余部分的估计长度下界} \]-
已走过的路径长度:
\[1 \to 3:9 \,\, (单位) \]\[3 \to 2:13 \,\, (单位) \]
将已访问的城市之间的路径距离累加,例如在路径 \(\langle 1, 3, 2 \rangle\) 中,已走过的路径总长度为:
\[9 + 13 = 22 \,\, (单位) \] -
剩余部分的估计长度下界:
- 当前停留在 2号城市,我们需要从 2号城市出发选择一条最短边。
2号城市的最短边是 \(2 \to 4\),边长为 \(2\)。 - 在剩余的未访问城市中,还未访问的城市是 4号城市。从 4号城市出发的最短边也是 \(4 \to 2\),长度同样为 \(2\)。
- 当前停留在 2号城市,我们需要从 2号城市出发选择一条最短边。
因此,剩余部分的估计长度下界为:
\[2 + 2 = 4 \,\, (单位) \]完整代价函数值计算
将已走过的路径长度和剩余部分的下界相加,得到代价函数的值:
\[L = 22 + 4 = 26 \,\, (单位) \]下界解释
这个代价函数的结果表明,无论之后如何规划剩余的路径,完整路径的总长度不会小于 26。这个下界帮助算法在搜索时进行剪枝,即当其他路径的代价超过该下界时,就不再继续深入搜索该分支。
1.5. 搜索树结构
-
初始结点: 从城市 1 出发。
-
可选路径:
- 第一层:1 号城市之后可以去 2、3、4。
- 第二层:假设选择了 2 号城市,则下一步可选 3 或 4。
-
深度优先遍历:
-
第一条路径:\(\langle 1, 2, 3, 4, 1 \rangle\),长度 \(29\)。
- 这是第一个找到的巡回路线,界 \(B = 29\)。
-
更新界:
找到路径 \(\langle 1, 2, 4, 3, 1 \rangle\),长度 \(23\)。更新界 \(B = 23\)。 -
剪枝:
当搜索路径 \(\langle 1, 3, 2 \rangle\) 的代价函数值为 \(26\),大于当前界 \(B = 23\),停止搜索该分支。
-
1.6. 实例运行过程
-
初始路径:
- 路径 \(\langle 1, 2, 3, 4, 1 \rangle\),长度为 \(29\)。
-
更新路径:
- 找到更优路径 \(\langle 1, 2, 4, 3, 1 \rangle\),长度为 \(23\),更新界。
-
剪枝:
- 代价函数值 \(F = 26\),停止该分支的搜索。
-
最优解:
- 找到路径 \(\langle 1, 3, 4, 2, 1 \rangle\),长度 \(23\)。
- 该路径与之前的最优解长度相同。
- 找到路径 \(\langle 1, 3, 4, 2, 1 \rangle\),长度 \(23\)。
1.7. 算法分析
-
搜索树的规模:
- 树叶的个数为 \(O((n - 1)!)\)。
- 每个叶片对应一条路径,每条路径有 \(n\) 个结点。
-
时间复杂度:
- 单个路径计算时间: \(O(n)\)。
- 总时间复杂度: \(O(n!)\)。
- 在最坏情况下,与蛮力算法的时间复杂度相同。
-
实际性能:
通过剪枝操作,大大减少了实际搜索空间,因此平均运行时间优于蛮力算法。
1.8. 小结
-
货郎问题的分支限界算法:
- 约束条件: 只能选择未访问过的城市。
- 代价函数: 已走过的路径长度 + 未访问部分的长度下界。
-
时间复杂度: \(O(n!)\),在最坏情况下与蛮力算法相同,但通过剪枝可显著提升平均性能。