旅游售货员问题的近似算法.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.txt781454282636515333727191510output.txt311426537

?算法思路：本题是利用蒙特卡罗算法，将节点1..n随机排序，计算此排列的哈密顿回路的长度并保存路径。（如1324序列，则此排列长度为c(1,3)+c(3,2)+c(2,4)+c(4,1)）然后for(inti=2;i=n;i++)for(intj=2;j=n;j++){判断交换节点i，j后哈密顿回路的长度有没有变短，有的话进行交换并更新最优值，否则不交换。}//计算此随机排列哈密顿回路长度的最小值多次执行（执行1秒）取最小值作为最优长度。

介绍完毕！