资源描述：
《最短路径问题的几个算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、个人收集整理勿做商业用途 最短路径问题)r+g ｖ%［５p） W）J 最短路径问题是一个非常能联系实际的问题,某人想从城市Ａ出发游览各城市一遍，而所用费用最少。试编程序输出结果。ﻫ/c+ｒ2ｘ8 S7j!N４z 解这类题时同学们往往不得要领,不少同学采用穷举法把所有可能的情况全部列出，再找出其中最短的那条路径；或是采用递归或深度搜索,找出所有路径，再找出最短的那条。这两种方法可见都是费时非常多的解法，如果城市数目多的话则很可能要超时了。ﻫ/ N%M0K＊[&X2 A&Ｕ4ｌ.}/f实际上我们知道,递归、深度搜索
2、等算法一般用于求所有解问题(例如求A出发每个城市走一遍一共有哪几种走法),而这几种算法对于求最短路径这类最优解问题显然是不合适的，以下介绍的几种算法就要优越很多。:V７ @）ｖ"g3＼ 首先,对于这类图我们都应该先建立一个邻接矩阵来存放任意两点间的距离数据，以便在程序中方便调用,如下：ﻫ( Ｎ8ｂ．x＋V／e3Z％Ｙ;ｙconstdis:array[1..５,1．.5]ofintegｅr=（（ ０，７, 3,10,15），0 ｕ; Y０Oi２Ｌ/i" ﻫ ( ７, 0,5,１３,1２)，ﻫ％ U５D#
3、I&L/ F（[）y（ ｊ9ｘ6 o (3,5, 0， 5，10），８I－ f" E:D1 Jﻫ (１０,1３,５, 0,１1）,$W"P1｝8T,}+ px． S- Z!a (15,１2，１0,11, ０)）;#p！L４
4、＋ b;c)V 以下是几种解法:３G３ ｃ#u'e－I７ｙﻫ一、宽度优先搜索%O9Ｏ４ G３W,L９ ｌ3Ｑ９Oﻫ 宽度优先搜索并不是一种很优秀的算法,只里只是简单介绍一下它的算法。$Q＂ｓ５d，b＄N／c３V，？+Z具体方法是:2 c d6
5、Y)/ t9ｈ3ｃ/i１、从Ａ点开始依次展开得到AB、AC、AD、AE四个新结点（第二层结点）,当然每个新结点要记录下其距离；ﻫ1?1ｇ,G.
6、'ｎ＃D＊O） ^8 A 2、个人收集整理勿做商业用途再次以AＢ展开得到ABC、ABD、AＢE三个新结点(第三层结点),而由ＡC结点可展开得到ＡCB、ACＤ、ACE三个新结点,自然AD可以展开得到ADB、AＤＣ、ADE，AE可以展开得到AEB、AEC、AＥＤ等新结点，对于每个结点也须记录下其距离;５ｎ． ｄ+ ^"Ｂ5`7A；v 3、 再把第三层结点全部展开,得到所有的第四层结点
7、：ABCＤ、ＡBCＥ、ABDC、AＢＤＥ、BEＣ、ABED……ＡＥDB、AEDＣ，每个结点也需记录下其距离；ﻫ$u) ］%ｉ；V8m０ ～0m6p 4、再把第四层结点全部展开,得到所有的第五层结点:ABＣDE、ＡＢCED、……、AE １＼5 {2`0 ｒ: ＩＶ*hﻫDBC、ＡＥDCB，每个结点也需记录下其距离;"@;v2Y/ T.[（]1r9Ｙ 5、到此，所有可能的结点均已展开，而第五层结点中最小的那个就是题目的解了。ﻫ２w３R4 O＂Ｑ. c+q;Ｒ＋R７q3] 由上可见,这种算法也是把所有的可能路径都列出来再找最
8、短的那条，显而易见这也是一种很费时的算法。)p.？+X5 c: Ｂ＊｀5 ｕ4 j7O 二、A＊算法#K4e４
9、-I$ｘ+Ｏ１y#@８ }Ａ＊算法是在宽度优先搜索算法的基础上，每次并不是把所有可展的结点展开，而是对所有没有展开的结点,利用一个自己确定的估价函数对所有没展开的结点进行估价,从而找出最应该被展开的结点(也就是说我们要找的答案最有可能是从该结点展开），而把该结点展开,直到找到目标结点为止。2_0Z．d；G* A( Ｅ+ [&W9Ｖ* [ﻫ这种算法最关键的问题就是如何确定估价函数，估价函数越准则越快找到答案。A*算法
10、实现起来并不难,只不过难在找准估价函数，大家可以自已找资料看看。/ D1T7 [1u+ E8ｂ 三、等代价搜索法 0Ｊ3Ｊ$W（z%c/ｍ5?：lk） ？'K个人收集整理勿做商业用途 等代价搜索法也是基于宽度优先搜索上进行了部分优化的一种算法，它与A＊算法的相似之处都是每次只展开某一个结点（不是展开所有结点），不同之处在于:它不需要去另找专门的估价函数，而是以该结点到A点的距离作为估价值，也就是说，等代价搜索法是Ａ＊算法的一种简化版本。它的大体思路是:ﻫ:}E! kO p 1、从A点开始依次展开得到AB（7）、AＣ（3）
11、、AD(１0)、AE（1５）四个新结点,把第一层结点A标记为已展开，并且每个新结点要记录下其距离(括号中的数字)；0 z G０p3V（K"Ｘﻫ 2、把未展开过的AＢ、AC、AD、AE四个结点中距离最小的一个展开,即展开ＡC（3）结点,得到AＣＢ(8）、ACD（16)、ＡCE(13）三个结点
