《动态规划-最短路径问题》由会员分享，可在线阅读，更多相关《动态规划-最短路径问题（4页珍藏版）》请在金锄头文库上搜索。
1、最短路径问题下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连 线上的数值代表道路长度。ClBl6C2E38B2D3C43求城市who与城市E的最短距离找到目标城市初始化最短路径为最大S 未访问置访问标志累加城市E至城市Who的路径长度 回溯后，恢复城市i未访问状态 如果最短则记下返回最短路径长度 计算最短路径长度现在，我们想从城市a到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？设DiS x为城市x到城市E的最短路径长度(x表示任意一个城市)；mapi, j表示i, j两个城市间的距离，若mapi, j=0,则两个城市不通； 我们可以使用回溯法来计算DiS
2、 x： varS：未访问的城市集合；function search(whox)： integer；beginif Who = E Then SearchOElse beginmin maxi nt；for i 取遍所有城市 Do if (mapWho, i0有路) and (i then beginS-Si；jmapWho, i+ search(i)； S-Si；if jVmin Then min-j； end； thensearch-min；End； elseEnd； searchbeginS-除E外的所有城市；Disa -search(a)；输出 Disa；endmain这个程序的效率如何
3、呢？我们可以看到,每次除了已经访问过的城市外,其他城市都 要访问，所以时间复杂度为O (n!)，这是一个“指数级”的算法。那么，还有没有效率更 高的解题方法呢？首先，我们来观察上述算法。在求bl到E的最短路径的时候，先求出从C2到E的最短路 径；而在求从b2刭E的最短路径的时候，又求了一遍从C2刭E的最短路径。也就是说，从C2 到E的最短路径求了两遍。同样可以发现，在求从Cl、C2刭E的最短路径的过程中，从Dl到E 的最短路径也被求了两遍。而在整个程序中，从Dl到E的最短路径被求了四遍，这是多么大 的一个浪费啊！如果在求解的过程中，同时将求得的最短路径的距离“记录在案”，以便将 来随时调用，则
4、可以避免这种重复计算。至此，一个新的思路产生了，即由后往前依次推出每个Dis值，直到推出Disa为止。问题是，究竟什么是“由后往前”呢？所谓前后关系是指对于任意一对城市i和j来说， 如果满足“或者城市i和城市j不连通或者disi+mapi, j三disj ”的条件，则定义为城 市i在前、城市j在后。因为如果城市i和城市j连通且Disi+ma pi，j Disj，则说 明城市j至城市E的最短路径长度应该比Disj更优。可城市j位于城市i后不可能推出此情 况，以至于影响最后的解。那么，我们应该如何划分先后次序呢？如上图所示，从城市a出发，按照与城市a的路径长度划分阶段。阶段0包含的出发城市有a阶段
5、1所含的城市有bl，b2阶段2包含的出发城市有Cl，C2, C3, C4阶段3包含的出发城市有Dl，D2, D3阶段4包含城市E 这种划分可以明确每个城市的次序，因为阶段的划分具有如下性质阶段i的取值只与阶段i+1有关，阶段i+1的取值只对阶段i的取值产生影响：每个阶段的顺序是确定的，不可以调换任两个阶段的顺序；我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用 了 k阶段与k+1阶段之间的如下关系o- mindisy + mapx,y|(x,y) & Gdisk X=歹弍+1阶段的城市集dis4E=0k=4, 3,0,其中disk x甘业阶段的城市x。由此得
6、出程序disE -*-0；for k3 down to 0 do倒序枚举阶段for x取遍k阶段的所有城市dobegindisx一8；初始化最短路径为最大for y取遍k+1 阶段的所有城市do if disy+mapx,ydisx then disxdisy+mapx,y；累计消耗，更新最短路径end；for输出disa；这个程序的时间复杂度为W(n2)，比回溯法的时间复杂度0 (n!)要小得多。总结：此题是动态规划的基础题。讲解也比较详细。在求解最短路经问题 时，必须对图进行拓扑排序，即划分明确的阶段、状 态。出师表两汉：诸葛亮先帝创业未半而中道崩殂，今天下三分，益州疲弊，此诚危急存亡之秋
7、也。然侍卫之臣 不懈于内，忠志之士忘身于外者，盖追先帝之殊遇，欲报之于陛下也。诚宜开张圣听，以光 先帝遗德，恢弘志士之气，不宜妄自菲薄，引喻失义，以塞忠谏之路也。宫中府中，俱为一体；陟罚臧否，不宜异同。若有作奸犯科及为忠善者，宜付有司论其 刑赏，以昭陛下平明之理；不宜偏私，使内外异法也。侍中、侍郎郭攸之、费祎、董允等，此皆良实，志虑忠纯，是以先帝简拔以遗陛下：愚 以为宫中之事，事无大小，悉以咨之，然后施行，必能裨补阙漏，有所广益。将军向宠，性行淑均，晓畅军事，试用于昔日，先帝称之曰“能”，是以众议举宠为督： 愚以为营中之事，悉以咨之，必能使行阵和睦，优劣得所。亲贤臣，远小人，此先汉所以兴隆也；
8、亲小人，远贤臣，此后汉所以倾颓也。先帝在时， 每与臣论此事，未尝不叹息痛恨于桓、灵也。侍中、尚书、长史、参军，此悉贞良死节之臣， 愿陛下亲之、信之，则汉室之隆，可计日而待也。臣本布衣，躬耕于南阳，苟全性命于乱世，不求闻达于诸侯。先帝不以臣卑鄙，猥自枉 屈，三顾臣于草庐之中，咨臣以当世之事，由是感激，遂许先帝以驱驰。后值倾覆，受任于 败军之际，奉命于危难之间，尔来二十有一年矣。先帝知臣谨慎，故临崩寄臣以大事也。受命以来，夙夜忧叹，恐托付不效，以伤先帝之 明；故五月渡泸，深入不毛。今南方已定，兵甲已足，当奖率三军，北定中原，庶竭驽钝， 攘除奸凶，兴复汉室，还于旧都。此臣所以报先帝而忠陛下之职分也。至于斟酌损益，进尽 忠言，则攸之、祎、允之任也。愿陛下托臣以讨贼兴复之效，不效，则治臣之罪，以告先帝之灵。若无兴德之言，则责 攸之、祎、允等之慢，以彰其咎；陛下亦宜自谋，以咨诹善道，察纳雅言，深追先帝遗诏。 臣不胜受恩感激。今当远离，临表涕零，不知所言。
