中国邮递员问题
最优邮路
求赋权连通图中含有所有边且权和最小的闭途径
Euler图
- Euler迹：经过每条边恰好一次的迹
- Euler闭迹：经过每条边恰好一次的闭迹
- Euler图：有Euler闭迹的图
- Euler图的最优邮路：即Euler闭迹
非Euler图的最优邮路
- 必然要重复经过一些边
- 重复走过的边作为重边添加到图中
新图一定是Euler图 - 原图的最优邮路和新图的Euler闭迹一一对应
问题转换
- 添加重边成为Euler图（如果本身不是的话）
- 使添加的边权和最小
- 找Euler闭迹
添加重边成为Euler图
Euler图的充要条件
一个非空连通图是Euler图当且仅当它没有奇度顶点 #### 添加重边的方案 +
奇度顶点
使添加的边权和最小
定理
设
重边的添加方法
- 连接k对奇度顶点的k条无公共边的最短路
- 且边权和最小
旅行商问题
Hamilton图
- Hamilton路：经过每个顶点恰一次的路
- Hamilton圈：经过每个顶点恰一次的圈
- Hamilton图：有Hamilton圈的图
旅行商问题的难度
- 找Hamilton圈：NP-complete
- 找权和最小的Hamilton圈：NP-hard
旅行商问题的近似算法
- 邻近点法
- 最小生成树法
- 最小权匹配法
- Kernighan-Lin
邻近点法
基本思路
贪心的选择最近的未访问的邻点前行
算法性能
- 近似比
- 最终结果只和初始点的选取有关
- 时间复杂度：
最小生成树法
基本思路
- 找
的一颗最小生成树 - 为
中的每条边添加重边成为 - 找
的一条Euler闭迹 - 沿
前行，跳过已访问过的顶点，直至访问完所有顶点
算法性能
- 近似比
- 最终结果和最小生成树、闭迹、闭迹初始点有关
- 时间复杂度：找最小生成树
，添加重边 ，找Euler闭迹 ，沿Euler闭迹前行 - 本算法可以进一步优化
最小权匹配法
基本思路
- 找
的一颗最小生成树 - 找
中奇度顶点在 中异于导出子图 的最小权完美匹配 - 将
添加到 中成为 - 找
的一条Euler闭迹 - 沿
前行，跳过已访问过的顶点，直至访问完所有顶点
算法性能
- 近似比
- 最终结果和最小生成树、最小权完美匹配、闭迹、闭迹初始点有关
- 时间复杂度：找最小生成树
，找最小权完美匹配 添加边 ，找Euler闭迹 ，沿Euler闭迹前行 - 本算法可以进一步优化
Kernighan-Lin
理论近似比差，实际效果好的算法，详略。
