旅游售货员问题的近似算法
- 1. 旅行售货员问题的近似算法 问题描述： 教材中解旅行售货员问题的近似算法pproxTSP 可以进一步得到改进。由近似算法η=2 的证明过程容易看出，如果将G 的最小生成树T 的边看作是G的双重边，则回路W就是T的一个欧拉回路。而近似最优哈密顿回路是在这条欧拉回路中删除第2 次经过的顶点得到的。如果基于T找出一条更短的欧拉回路，则可以得到一条更短的哈密顿回路。
- 2. 编程任务： 设计并实现上述近似算法，且其性能比达到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
- 3. 算法思路： 本题是利用蒙特卡罗算法 ，将节点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秒）取最小值作为最优长度。
- 4. 介绍完毕！
