文档介绍：旅行售货员问题的近似算法
问题描述:
教材中解旅行售货员问题的近似算法pproxTSP 可以进一步得到改进。由近似算法η=2 的证明过程容易看出,如果将G 的最小生成树T 的边看作是G的双重边,则回路W就是T的一个欧拉回路。而近似最优哈密顿回路是在这条欧拉回路中删除第2 次经过的顶点得到的。如果基于T找出一条更短的欧拉回路,则可以得到一条更短的哈密顿回路。
编程任务:
设计并实现上述近似算法,。
数据输入:
。文件第1 行有2个正整数n 和e,n表示
的顶点数;e是G 的边数。接下来的e 行中,每行有3 个正整数i,j,c,表示边
(i,j)的费用为c。
输入文件示例输出文件示例

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

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秒)取最小值作为最优长度。
介绍完毕!