旅行售货员问题的近似算法 ★问题描述: 教材中解旅行售货员问题的近似算法 pproxTSP 可以进一步得到改进。由近似算法η=2的证明过 程容易看出,如果将G的最小生成树T的边看作 是G的双重边,则回路W就是T的一个欧拉回路 而近似最优哈密顿回路是在这条欧拉回路中删除 第2次经过的顶点得到的。如果基于T找出一条 更短的欧拉回路,则可以得到一条更短的哈密顿 回路
旅行售货员问题的近似算法 问题描述： 教材中解旅行售货员问题的近似算法pproxTSP 可以进一步得到改进。由近似算法η=2 的证明过 程容易看出，如果将G 的最小生成树T 的边看作 是G的双重边，则回路W就是T的一个欧拉回路。 而近似最优哈密顿回路是在这条欧拉回路中删除 第2 次经过的顶点得到的。如果基于T找出一条 更短的欧拉回路，则可以得到一条更短的哈密顿 回路
★编程任务 设计并实现上述近似算法,且其性能比达到15。 ★数据输入: 由文件 Input. txt提供输入数据。文件第1行有2个正整数n和e,n表示 的顶点数;e是G的边数。接下来的e行中,每行有3个正整数ijc,表示边 j)的费用为c。 ★输入文件示例输出文件示例 Input. txt 78 145 428 263 651 533 372 719 1510 output. txt 31 1426537
编程任务： 设计并实现上述近似算法，且其性能比达到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随机排 序,计算此排列的哈密顿回路的长度并保存路径。 (如1324序列,则此排列长度为 c(13)+c(32)+c(24)+c(41)) 然后 for(int i=2;i<=n; i++) for(int j=2;j<=n:j++) 判断交换节点i,后哈密顿回路的长度有没有变短, 有的话进行交换并更新最优值,否则不交换。 }/计算此随机排列哈密顿回路长度的最小值 多次执行(执行1秒)取最小值作为最优长度
算法思路： 本题是利用蒙特卡罗算法 ，将节点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秒）取最小值作为最优长度
绍完!
介绍完毕！