22-TSP近似算法.ppt

第24讲 TSP问题近似算法
杨明
指挥信息系统学院软件工程教研中心
******@
算法设计与分析
8/17/2017
8/17/2017
1
计算机算法设计与分析
内容
TSP问题
满足三角不等式的TSP问题近似算法
TSP问题的启发式算法
8/17/2017
2
计算机算法设计与分析
最优解
旅行售货员问题—TSP
问题描述
给定一个完全无向图G=(V,E),其每一边(u,v)∈E有一非负整数费用c(u,v),要找出G的最小费用哈密顿回路。
TSP问题是NP完全问题。
完全图
8/17/2017
3
计算机算法设计与分析
旅行商问题
TSP问题的近似算法
悲观的结论
不存在具有常数性能比的解TSP问题的多项式时间近似算法,除非P=NP。
换句话说,若P≠NP,则对任意常数ρ>1,不存在性能比为ρ的解TSP问题的多项式时间近似算法。
证明方法
opt=|V|
opt>ρ|V|
f
f
G中存在哈密顿圈
G中不存在哈密顿圈
哈密顿圈问题
C(H)>ρ|V|
8/17/2017
4
计算机算法设计与分析
用算法A解哈密顿回路问题
反证法
假设若有一个解TSP问题的近似算法A,其性能比为a。
不失一般性,可a设为一整数,在这个假设下,可利用算法A设计一个解哈密顿回路问题的多项式时间算法。
8/17/2017
5
计算机算法设计与分析
用算法A解哈密顿回路问题
G中存在哈密顿圈
G中不存在哈密顿圈
opt=|V|
opt>c|V|
f
f
哈密顿圈问题
旅行商问题
不可近似性
8/17/2017
6
计算机算法设计与分析
特殊的TSP问题
费用满足三角不等式的TSP
费用函数c具有三角不等式性质
对任意的3个顶点u,v,w∈V,有:c(u,w)≤c(u,v)+c(v,w)。
例
欧氏距离
最短路径
即使费用函数具有三角不等式性质,TSP问题仍为NP完全问题。
8/17/2017
7
计算机算法设计与分析
对于给定的无向图G,可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法。
void approxTSP (Graph G)
{
(1)选择G的任一顶点r;
(2)用Prim算法找出带权图g的一棵以r为根的最小生成树T;
(3)前序遍历树T得到的顶点表L;
(4)将r加到表L的末尾,按表L中顶点次序组成回路H;
(5)return L;
}
TSP问题近似算法
8/17/2017
8
计算机算法设计与分析
TSP问题近似算法
最小生成树
MST先序遍历
取捷径形成解
最优解
完全图
8/17/2017
9
计算机算法设计与分析
approxTSP的性能比
approxTSP是求解费用满足三角不等式TSP问题的2-近似算法
证明
设T是算法approxTSP计算出的图G的最小生成树,H*为图的最小费用旅行售货员回路。
从H*中任意删去一条边后,可得图G的一颗生成树。由于T是最小生成树,故有c(T)<=c(H*)。
设W是对T依前序所做的完全遍历,而W对T所做的遍历经过T中的每条边恰好两次,所以有c(W)=2c(T)<=2c(H*)
8/17/2017
10
计算机算法设计与分析