[最短路径问题的几个算法.docVIP

最短路径问题) r+ g v% [5 p) W) J 最短路径问题是一个非常能联系实际的问题，某人想从城市A出发游览各 城市一遍，而所用费用最少。试编程序输出结果。/ c+ r2 x8 S7 j! N4 z　　解这类题时同学们往往不得要领，不少同学采用穷举法把所有可能的情况全部列出，再找出其中最短的那条路径；或是采用递归或深度搜索，找出所有路径，再找出最短的那条。这两种方法可见都是费时非常多的解法，如果城市数目多的话则很可能要超时了。/ N% M0 K* [ X2 A U4 l. }/ f　　实际上我们知道，递归、深度搜索等算法一般用于求所有解问题（例如求A出发每个城市走一遍一共有哪几种走法），而这几种算法对于求最短路径这类最优解问题显然是不合适的，以下介绍的几种算法就要优越很多。 : V7 @) v g3 \　　首先，对于这类图我们都应该先建立一个邻接矩阵来存放任意两点间的距离数据，以便在程序中方便调用，如下：( N8 b. x+ V/ e3 Z% Y; yconst dis:array[1..5,1..5] of integer =( ( 0, 7, 3,10,15), 0 u; Y0 O i2 L/ i \　　　　　　　　　　　　　　　　　　　　　　( 7, 0, 5,13,12),% U5 D# I L/ F( [) y( j9 x6 o　　　　　　　　　　　　　　　　　　　　　　( 3, 5, 0, 5,10), 8 I- f E: D1 J　　　　　　　　　　　　　　　　　　　　　　(10,13, 5, 0,11),$ W P1 }8 T, }+ p x. S- Z! a　　　　　　　　　　　　　　　　　　　　　　(15,12,10,11, 0));# p! L4 |+ b; c) V　　以下是几种解法： 3 G3 c# u e- I7 y　　一、 宽度优先搜索 % O9 O4 G3 W, L9 l3 Q9 O　　宽度优先搜索并不是一种很优秀的算法，只里只是简单介绍一下它的算法。$ Q s5 d, b$ N/ c3 V, ?+ Z　　具体方法是： 2 c d6 Y) \/ t9 h3 c/ i　　1、 从A点开始依次展开得到AB、AC、AD、AE四个新结点（第二层结点），当然每个新结点要记录下其距离；1 ?1 g, G. | n# D* O) ^8 A　　2、 再次以AB展开得到ABC、ABD、ABE三个新结点（第三层结点），而由AC结点可展开得到ACB、ACD、ACE三个新结点，自然AD可以展开得到ADB、ADC、ADE，AE可以展开得到AEB、AEC、AED等新结点，对于每个结点也须记录下其距离； 5 n. d+ ^ B5 `7 A; v　　3、 再把第三层结点全部展开，得到所有的第四层结点：ABCD、ABCE、ABDC、ABDE、BEC、ABED……AEDB、AEDC，每个结点也需记录下其距离；$ u) ]% i; V8 m0 ~0 m6 p　　4、 再把第四层结点全部展开，得到所有的第五层结点：ABCDE、ABCED、……、AE 1 \5 {2 `0 r: I V* hDBC、AEDCB，每个结点也需记录下其距离； @; v2 Y/ T. [( ]1 r9 Y　　5、 到此，所有可能的结点均已展开，而第五层结点中最小的那个就是题目的解了。2 w3 R4 O Q. c+ q; R+ R7 q3 ]　　由上可见，这种算法也是把所有的可能路径都列出来再找最短的那条，显而易见这也是一种很费时的算法。 ) p. ?+ X5 c: B* `5 u4 j7 O　　二、 A＊算法# K4 e4 |- I$ x+ O1 y# @8 }　　A＊算法是在宽度优先搜索算法的基础上，每次并不是把所有可展的结点展开，而是对所有没有展开的结点，利用一个自己确定的估价函数对所有没展开的结点进行估价，从而找出最应该被展开的结点（也就是说我们要找的答案最有可能是从该结点展开），而把该结点展开，直到找到目标结点为止。 2 _0 Z. d; G* A( E+ [ W9 V* [　　这种算法最关键的问题就是如何确定估价函数，估价函数越准则越快找到答案。A＊算法实现起来并不难，只不过难在找准估价函数，大家可以自已找资料看看。/ D1 T7 [1 u+ E8 b　　三、等代价搜索法 　　 0 J3 J$ W( z% c/ m5 ?: l k) ? K　　等代价搜索法也是基于宽度优先搜索上进行了部分优化的一种算法，它与A＊算法的相似之处都是每次只展开某一个结点（不是展开所有结点），不同之处在于：它不需要去另找专门的估价函数，而是以该结点到A点的距离