最短路径

hyy012345

我们如何找到最短路径？又该杂么来运用于数模题中呢？

哎呦喂！！！

例1、假设A、B、C、D、E各个城市之间旅费如下图所示。某人想从城市A出发游览各城市一遍，而所用费用最少。试编程序输出结果。 11                           解这类题时同学们往往不得要领，不少同学采用穷举法把所有可能的情况全部列出，再找出其中最短的那条路径；或是采用递归或深度搜索，找出所有路径，再找出最短的那条。这两种方法可见都是费时非常多的解法，如果城市数目多的话则很可能要超时了。 实际上我们知道，递归、深度搜索等算法一般用于求所有解问题（例如求A出发每个城市走一遍一共有哪几种走法），而这几种算法对于求最短路径这类最优解问题显然是不合适的，以下介绍的几种算法就要优越很多。        首先，对于这类图我们都应该先建立一个邻接矩阵来存放任意两点间的距离数据，以便在程序中方便调用，如下： const dis:array[1..5,1..5] of integer =(( 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、  从A点开始依次展开得到AB、AC、AD、AE四个新结点（第二层结点），当然每个新结点要记录下其距离； 2、  再次以AB展开得到ABC、ABD、ABE三个新结点（第三层结点），而由AC结点可展开得到ACB、ACD、ACE三个新结点，自然AD可以展开得到ADB、ADC、ADE，AE可以展开得到AEB、AEC、AED等新结点，对于每个结点也须记录下其距离； 3、  再把第三层结点全部展开，得到所有的第四层结点：ABCD、ABCE、ABDC、ABDE、ABEC、ABED……AEDB、AEDC，每个结点也需记录下其距离； 4、  再把第四层结点全部展开，得到所有的第五层结点：ABCDE、ABCED、……、AEDBC、AEDCB，每个结点也需记录下其距离； 5、  到此，所有可能的结点均已展开，而第五层结点中最小的那个就是题目的解了。 由上可见，这种算法也是把所有的可能路径都列出来再找最短的那条，显而易见这也是一种很费时的算法。   二、            A＊算法 A＊算法是在宽度优先搜索算法的基础上，每次并不是把所有可展的结点展开，而是对所有没有展开的结点，利用一个自己确定的估价函数对所有没展开的结点进行估价，从而找出最应该被展开的结点（也就是说我们要找的答案最有可能是从该结点展开），而把该结点展开，直到找到目标结点为止。 这种算法最关键的问题就是如何确定估价函数，估价函数越准则越快找到答案。A＊算法实现起来并不难，只不过难在找准估价函数，大家可以自已找资料看看。   三、等代价搜索法        等代价搜索法也是基于宽度优先搜索上进行了部分优化的一种算法，它与A＊算法的相似之处都是每次只展开某一个结点（不是展开所有结点），不同之处在于：它不需要去另找专门的估价函数，而是以该结点到A点的距离作为估价值，也就是说，等代价搜索法是A＊算法的一种简化版本。它的大体思路是： 1、  从A点开始依次展开得到AB（7）、AC（3）、AD（10）、AE（15）四个新结点，把第一层结点A标记为已展开，并且每个新结点要记录下其距离（括号中的数字）； 2、  把未展开过的AB、AC、AD、AE四个结点中距离最小的一个展开，即展开AC（3）结点，得到ACB（8）、ACD（16）、ACE（13）三个结点，并把结点AC标记为已展开； 3、  再从未展开的所有结点中找出距离最小的一个展开，即展开AB（7）结点，得到ABC（12）、ABD（20）、ABE（19）三个结点，并把结点AB标记为已展开； 4、  再次从未展开的所有结点中找出距离最小的一个展开，即展开ACB（8）结点……； 5、  每次展开所有未展开的结点中距离最小的那个结点，直到展开的新结点中出现目标情况（结点含有5个字母）时，即得到了结果。 由上可见，A＊算法和等代价搜索法并没有象宽度优先搜索一样展开所有结点，只是根据某一原则（或某一估价函数值）每次展开距离A点最近的那个结点（或是估价函数计算出的最可能的那个结点），反复下去即可最终得到答案。虽然中途有时也展开了一些并不是答案的结点，但这种展开并不是大规模的，不是全部展开，因而耗时要比宽度优先搜索小得多。  

哎呦喂！！！

例1、假设A、B、C、D、E各个城市之间旅费如下图所示。某人想从城市A出发游览各城市一遍，而所用费用最少。试编程序输出结果。 11                           解这类题时同学们往往不得要领，不少同学采用穷举法把所有可能的情况全部列出，再找出其中最短的那条路径；或是采用递归或深度搜索，找出所有路径，再找出最短的那条。这两种方法可见都是费时非常多的解法，如果城市数目多的话则很可能要超时了。 实际上我们知道，递归、深度搜索等算法一般用于求所有解问题（例如求A出发每个城市走一遍一共有哪几种走法），而这几种算法对于求最短路径这类最优解问题显然是不合适的，以下介绍的几种算法就要优越很多。        首先，对于这类图我们都应该先建立一个邻接矩阵来存放任意两点间的距离数据，以便在程序中方便调用，如下： const dis:array[1..5,1..5] of integer =(( 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、  从A点开始依次展开得到AB、AC、AD、AE四个新结点（第二层结点），当然每个新结点要记录下其距离； 2、  再次以AB展开得到ABC、ABD、ABE三个新结点（第三层结点），而由AC结点可展开得到ACB、ACD、ACE三个新结点，自然AD可以展开得到ADB、ADC、ADE，AE可以展开得到AEB、AEC、AED等新结点，对于每个结点也须记录下其距离； 3、  再把第三层结点全部展开，得到所有的第四层结点：ABCD、ABCE、ABDC、ABDE、ABEC、ABED……AEDB、AEDC，每个结点也需记录下其距离； 4、  再把第四层结点全部展开，得到所有的第五层结点：ABCDE、ABCED、……、AEDBC、AEDCB，每个结点也需记录下其距离； 5、  到此，所有可能的结点均已展开，而第五层结点中最小的那个就是题目的解了。 由上可见，这种算法也是把所有的可能路径都列出来再找最短的那条，显而易见这也是一种很费时的算法。   二、            A＊算法 A＊算法是在宽度优先搜索算法的基础上，每次并不是把所有可展的结点展开，而是对所有没有展开的结点，利用一个自己确定的估价函数对所有没展开的结点进行估价，从而找出最应该被展开的结点（也就是说我们要找的答案最有可能是从该结点展开），而把该结点展开，直到找到目标结点为止。 这种算法最关键的问题就是如何确定估价函数，估价函数越准则越快找到答案。A＊算法实现起来并不难，只不过难在找准估价函数，大家可以自已找资料看看。   三、等代价搜索法        等代价搜索法也是基于宽度优先搜索上进行了部分优化的一种算法，它与A＊算法的相似之处都是每次只展开某一个结点（不是展开所有结点），不同之处在于：它不需要去另找专门的估价函数，而是以该结点到A点的距离作为估价值，也就是说，等代价搜索法是A＊算法的一种简化版本。它的大体思路是： 1、  从A点开始依次展开得到AB（7）、AC（3）、AD（10）、AE（15）四个新结点，把第一层结点A标记为已展开，并且每个新结点要记录下其距离（括号中的数字）； 2、  把未展开过的AB、AC、AD、AE四个结点中距离最小的一个展开，即展开AC（3）结点，得到ACB（8）、ACD（16）、ACE（13）三个结点，并把结点AC标记为已展开； 3、  再从未展开的所有结点中找出距离最小的一个展开，即展开AB（7）结点，得到ABC（12）、ABD（20）、ABE（19）三个结点，并把结点AB标记为已展开； 4、  再次从未展开的所有结点中找出距离最小的一个展开，即展开ACB（8）结点……； 5、  每次展开所有未展开的结点中距离最小的那个结点，直到展开的新结点中出现目标情况（结点含有5个字母）时，即得到了结果。 由上可见，A＊算法和等代价搜索法并没有象宽度优先搜索一样展开所有结点，只是根据某一原则（或某一估价函数值）每次展开距离A点最近的那个结点（或是估价函数计算出的最可能的那个结点），反复下去即可最终得到答案。虽然中途有时也展开了一些并不是答案的结点，但这种展开并不是大规模的，不是全部展开，因而耗时要比宽度优先搜索小得多。  
: {. u* k1 ~1 E

大爱中国

最短路径是图论中的一个经典算法，可以采取Dijkstra算法来解决最短路问题，关于如何运用，可以在论坛中下载关于图论的课件，进行深入学习，加油！