资源描述：
《最短路径问题的求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第12卷增刊郑州纺织工学院学报Vol.12Supplement2001年6月JOURNALOFZHENGZHOUTEXTILEINSTITUTEJune,2001文章编号:10074945(2001)增刊011903最短路径问题的求解王军,王连圭(广东省中山市中山学院信息与电子工程系,广东中山528402)*摘要:文中就最短路径问题进行了研究,针对具体的引例提出了六种算法:宽度优先搜索法、A算法、等代价搜索法、Warshall算法、动态规划法、标号法等,详尽分析了每种算法的内容、适用性及优缺点.关键词:最短路径;解题方法
2、;算法分析中图分类号:O245文献标识码:A最短路径问题是一种最优解问题,是近年来全国在学生((0,7,3,10,15),(7,0,5,13,12),(3,5,0,6,5),(10,13,6,挑战杯、数学建模等竞赛中常见的一类中等程度的难题,也0,11),(15,12,5,11,0));是一个在交通运输、城市规划以及计算机网络规划等工程实际以下是几种解法:中具有重要指导意义的问题,甚至有时一些看似跟最短路径问1宽度优先搜索题无关的问题也可以归结为最短路径问题.下面就以具体引例来简要分析一下此类问题的算法.宽度优先搜索并不是
3、一种很优秀的算法,这里只是简单介引例1:假设A、B、C、D、E各个城市之间旅费如图1所绍一下它的算法.具体方法是:从A点开始依次展开得到示.某人想从城市A出发游览各城市一遍,而所用费用最少.试AB、AC、AD、AE四个新结点(第二层结点),当然每个新结点要编程序输出结果.记录下其距离;再次以AB展开得到ABC、ABD、ABE三个新结点(第三层结点),而由AC结点可展开得到ACB、ACD、ACE三个新结点,自然AD可以展开得到ADB、ADC、ADE,AE可以展开得到AEB、AEC、AED等新结点,对于每个结点也须记录下其距离;再把第三层结点全
4、部展开,得到所有的第四层结点:ABCD、ABCE、ABDC、ABDE、ABEC、ABEDAEDB、AEDC,每个结点也需记录下其距离;再把第四层结点全部展开,得到所有的第五层结点:ABCDE、ABCED、、AEDBC、AEDCB,每个结点也需记录下其距离;到此,所有可能的结点均已展开,而第五层结点中最小的那个就是题目的解了.由上可见,这种算法也是把所有的可能路径都列出来再找最短的那条,图1游览点分布示意图显而易见这也是一种很费时的算法.解这类题时很多人往往不得要领,不少人采用穷举法把所有可能的情况全部列出,再找出其中最短的那条路径;
5、或是采用2A*算法递归或深度搜索,找出所有路径,再找出最短的那条.这两种方A*算法是在宽度优先搜索算法的基础上,每次都是利用法可见都是费时非常多的解法,如果城市数目多的话则要花大一个自己确定的估价函数对所有没展开的结点进行估价,从而量的运行时间.实际上,递归、深度搜索等算法一般用于求所有找出最应该被展开的结点(也就是说要找的答案最有可能是从解问题(例如求从A出发每个城市走一遍一共有哪几种走法),[1]该结点展开),把该结点展开,直到找到目标结点为止.而这几种算法对于求最短路径这类最优解问题显然是不合适的,以下介绍的几种算法就要优越很多.3等代
6、价搜索法首先,应该先建立一个邻接矩阵来存放任意两点间的距离等代价搜索法也是基于宽度优先搜索上进行优化的一种算数据,以便在程序中方便调用,如下:法,它与A*算法有点相似,只不过它不需要去另找估价函数,constdis:array[1..5,1..5]ofinteger=而是以该结点到A点的距离作为估价值,每次展开估价值最小收稿日期:20010308作者简介:王军(1971),男,硕士,中山学院助教.王连圭为中山学院副教授,主要研究方向为非线性控制和鲁棒控制.120郑州纺织工学院学报
7、2001年第12卷的结点.具体方法是:从A点开始依次展开得到AB(7)、AC看,可用一个数轴简单地表示这种算法:(3)、AD(10)、AE(15)四个新结点,把第一层结点A标记为己(1)以A点为0点,展开与其相邻的点,并在数轴中标出.展开,并且每个新结点要记录下其距离(括号中的数字);把未展开过的AB、AC、AD、AE四个结点中距离最小的一个展开,即展开AC(3)结点,得到ACB(8)、ACD(16)、ACE(13)三个结点,并把结点AC标记为己展开;再从未展开的所有结点中找(2)因为C点离起点A最近,因此可以断
8、定C点一定是由出距离最小的一个展开,即展开AB(7)结点,得到ABC(12)、A直接到C点这条路径是最短的(因为A、C两点间没有其它AB
