旅游售货员问题的近似算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,旅行售货员问题的近似算法,问题描述：,教材中解旅行售货员问题的近似算法,pproxTSP,可以进一步得到改进。由近似算法,=2,的证明过程容易看出，如果将,G,的最小生成树,T,的边看作是,G,的双重边，则回路,W,就是,T,的一个欧拉回路。而近似最优哈密顿回路是在这条欧拉回路中删除第,2,次经过的顶点得到的。如果基于,T,找出一条更短的欧拉回路，则可以得到一条更短的哈密顿回路。,编程任务：,设计并实现上述近似算法，且其性能比达到,1.5,。,数据输入：,由文件,input.txt,提供输入数据。文件第,1,行有,2,个正整数,n,和,e,，,n,表示,的顶点数；,e,是,G,的边数。接下来的,e,行中，每行有,3,个正整数,i,j,c,，表示边,(,i,j,),的费用为,c,。,输入文件示例 输出文件示例,input.txt,7 8,1 4 5,4 2 8,2 6 3,6 5 1,5 3 3,3 7 2,7 1 9,1 5 10,output.txt,31,1 4 2 6 5 3 7,算法思路：,本题是利用蒙特卡罗算法，将节点,1.n,随机排序，计算此排列的哈密顿回路的长度并保存路径。（如,1 3 2 4,序列，则此排列长度为,c(1,3)+c(3,2)+c(2,4)+c(4,1),）,然后,for(int,i=2;i=,n;i,+),for(int,j=2;j=,n;j,+),判断交换节点,i,，,j,后哈密顿回路的长度有没有变短，有的话进行交换并更新最优值，否则不交换。,/,计算此随机排列哈密顿回路长度的最小值,多次执行（执行,1,秒）取最小值作为最优长度。,介绍完毕！,