行业知识
关于旅行商问题的多种算法求解
一、问题���述
旅行商问题是指旅行家要旅行n个城市,要求每个城市经历一次且仅经历一次然后回到出发城市,并要求所走路程最短。
首先通过所给出的一个无向图,即n个顶点,m个无向边,每条边有一个权值代表两个点之间的距离,要求把每一个点都走一遍并回到原点,求路径的最短值。
二、问题分析
(1)分析:从初始点出发的周游路线一共有(n-1)!条,即等于除初始结点外的n-1个结点的排列数,因此旅行商问题是一个排列问题。通过枚举(n-1)!条周游路线,从中找出一条具有最小成本的周游路线的算法,其计算时间为O(n!)。
(2)完成方案:可以通过将问题给出的无向图,如:图1,即城市点和到其他城市的所需路程集合成一个二维数组,且保证到自身的路程设置为无穷大避免方案中出现到原本所在城市的方案,如:图2。再通过动态规划、贪心法、分支限界等算法进行相应算法的求解。
(3)预期结果:在程序运行后显示最佳方案的结果。
图1 无向图
图2 无向图对应的矩阵
三、算法设计与分析
1、算法输入和输出
(1)算法输入:城市数量,到其他城市的距离(到自身距离设置为无穷大);
(2)算法输出:路过所有城市所需总路径的最小值
2、算法说明
(1)贪心法:贪心算法总是作出在当前看来最好的选择。贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。例如单源最短路经问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。
(2)动态规划法:动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题;但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
(3)分支限界法:分支限界法:采用广度优先产生状态空间树的结点,并使用剪枝函数的方法。“分支”采用广度优先策略,依次生成扩展结点的所有分支(即,儿子结点)。
“限界”在结点的扩展过程中,计算结点的上界(或下界),边搜索边剪枝,以提高搜索效率。
3、算法描述
(1)贪心法:采用最近邻点策略,从任意一点出发,每次到没经过的点中最近的一个,直到经过所有的点,最后回到出发点。即如果当前在顶点u,则取与顶点u距离最近的点p。
(2)动态规划法:某一个点i不经过任意点回到起始点的最短路径和为mp[i][0](默认初始点为0),dp[i][0]= mp[i][0];(1
上一篇:服务器怎么关联安全组?
下一篇:知网服务器崩溃怎么解决?