-TSP近似算法

1、第第2424讲讲 TSPTSP问题近似算法问题近似算法杨杨 明明指挥信息系统学院软件工程教研中心指挥信息系统学院软件工程教研中心yangminglgdx.mtn算法设计与分析2021-11-11第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析2内容内容nTSP问题问题n满足三角不等式的满足三角不等式的TSP问题近似算法问题近似算法nTSP问题的启发式算法问题的启发式算法第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析3最优解最优解旅行售货员问题旅行售货员问题TSPn问题描述问题描述n给定一个完全无向图给定一个完全无

2、向图G=(V,E)G=(V,E)，其每一边，其每一边(u,v)E(u,v)E有一非负整数费用有一非负整数费用c(u,v)c(u,v)，要找出，要找出G G的最小费用哈的最小费用哈密顿回路。密顿回路。nTSPTSP问题是问题是NPNP完全问题。完全问题。完全图完全图第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析4旅行商问题旅行商问题TSP问题的近似算法问题的近似算法n悲观的结论悲观的结论n不存在具有常数性能比的解不存在具有常数性能比的解TSPTSP问题的多项式时间近似算法，除问题的多项式时间近似算法，除非非P=NP。n换句话说，若换句话说，若PNPPNP

3、，则对任意常数，则对任意常数11，不存在性能比为，不存在性能比为的的解解TSPTSP问题的多项式时间近似算法。问题的多项式时间近似算法。n证明方法证明方法opt=|V|opt|V|ffG中存在哈密顿圈G中不存在哈密顿圈哈密顿圈问题哈密顿圈问题C(H)|V|第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析5用算法用算法A解哈密顿回路问题解哈密顿回路问题 将 图),(EVG 变 换 为 TSP的 一 个 实 例cEVG, 1,1， 其 中,| ),(1vuVvuvuE，1E中边的费用),(vuc定义为： EEvuVEvuvuc1),(1|),(1),( 若原

4、图G有一哈密顿回路 H， 则费用函数 c赋予 H中每边的费用为1， 因此1G中含有费用为|V的TSP回路。 另一方面，若原图G没有一哈密顿回路，则1G的任一回路必用到不在 E中的边，因此1G的任一TSP回路的费用至少为|) 1|(|) 1|(VVV。 n反证法n假设若有一个解TSP问题的近似算法A，其性能比为a。n不失一般性，可a设为一整数，在这个假设下，可利用算法A设计一个解哈密顿回路问题的多项式时间算法。 第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析6用算法用算法A解哈密顿回路问题解哈密顿回路问题G中存在哈密顿圈G中不存在哈密顿圈opt=|V|o

5、ptc|V|ff哈密顿圈问题哈密顿圈问题旅行商问题旅行商问题不可近似性不可近似性第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析7特殊的特殊的TSP问题问题n费用满足三角不等式的费用满足三角不等式的TSP n费用函数费用函数c c具有三角不等式性质具有三角不等式性质n对任意的对任意的3 3个顶点个顶点u,v,wVu,v,wV，有：，有：c(u,w)c(u,v)+c(v,w)c(u,w)c(u,v)+c(v,w)。n例例n欧氏距离欧氏距离n最短路径最短路径n即使费用函数具有三角不等式性质，即使费用函数具有三角不等式性质，TSPTSP问题仍为问题仍为NPNP

6、完全问题。完全问题。 第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析8 对于给定的无向图G，可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法。 void approxTSPapproxTSP (Graph G) (1)选择G的任一顶点r； (2)用Prim算法找出带权图g的一棵以r为根的最小生成树T； (3)前序遍历树T得到的顶点表L； (4)将r加到表L的末尾，按表L中顶点次序组成回路H; (5)return L; TSP问题近似算法问题近似算法第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分

7、析9TSP问题近似算法问题近似算法最小生成树最小生成树MST先序遍历先序遍历取捷径形成解取捷径形成解最优解最优解完全图完全图第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析10approxTSP的性能比的性能比napproxTSP是求解费用满足三角不等式是求解费用满足三角不等式TSP问题问题的的2-近似算法近似算法n证明证明n设设T是算法是算法approxTSP计算出的图计算出的图G的最小生成树，的最小生成树，H*为图的最小费用旅行售货员回路。为图的最小费用旅行售货员回路。n从从H*中任意删去一条边后，可得图中任意删去一条边后，可得图G的一颗生成树。的一

8、颗生成树。由于由于T是最小生成树，故有是最小生成树，故有c(T)=c(H*)。n设设W是对是对T依前序所做的完全遍历，而依前序所做的完全遍历，而W对对T所做的遍所做的遍历经过历经过T中的每条边恰好两次，所以有中的每条边恰好两次，所以有c(W)=2c(T)=2c(H*) 第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析11approxTSP的性能比的性能比n证明（续）证明（续）n利用三角不等式将利用三角不等式将W改造成一条哈密顿回路改造成一条哈密顿回路H。n由于费用满足三角不等式，可以在由于费用满足三角不等式，可以在W的基础上，从的基础上，从中删去已访问过

9、的顶点而不会增加旅行费用。中删去已访问过的顶点而不会增加旅行费用。n若在中删去顶点若在中删去顶点u和和v间的一个顶点间的一个顶点w，就用边就用边(u,v)代代替原来从替原来从u到到v的一条路。的一条路。n反复利用这个办法删去反复利用这个办法删去W中的重复访问的顶点可得中的重复访问的顶点可得到一条旅行售货者回路。到一条旅行售货者回路。n由费用满足三角不等式，有由费用满足三角不等式，有c(H)=2c(T)=2c(H*) 第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析123/2-近似算法近似算法 Christofids (G=(V, E,W)用Prim算法找

10、出带权图(V, E)的最小生成树T1；找出T1中度为奇数的顶点集合S；找出由S导出图的最小费用完全匹配M；构造图T1+M的欧拉路径T2；利用费用三角不等式将T2调整为哈密顿回路T;第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析13Christofids 近似算法近似算法SM=MCPM(GS)T2=T1+MTT1=MST(G)完全图完全图G第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析14TSP问题的启发式算法问题的启发式算法n最近邻居策略最近邻居策略NearestTSP (G) Rs us while R!=V

11、 do在与u相连边中选择权值最小的边(u,v)，且u不在R中 CC+(u,v)uv end while CC+(v,s) return Cend第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析15TSP问题的启发式算法问题的启发式算法n最短链路策略最短链路策略ShortestLinkTSP (G) RE C while R!= do在R选择权值最小的边(u,v) RR-(u,v)If (边(u,v)不会在C中形成环且不会使C中顶点度大于2) then CC(u, v) end while 将 C中的路径中的首尾连接起来形成环路并返回该环路；end第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析16算法性能比较算法性能比较第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析17算法运行时间比较算法运行时间比较第第24讲讲 TSP问题的近似算法问题的近似算法2021-11-11计算机算法设计与分析18拓展研究拓展研究n局部优化局部优化n对构建的对