您所在位置：网站首页 > 办公文档 > 解决方案动态规划-最短路径问题

动态规划-最短路径问题

4页

卖家[上传人]：汽***

文档编号：431736244

上传时间：2022-10-16

文档格式：DOCX

文档大小：53.24KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 金贝

/ 4 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、最短路径问题下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。ClBl6C2E38B2D3C43求城市who与城市E的最短距离找到目标城市初始化最短路径为最大S 未访问置访问标志累加城市E至城市Who的路径长度回溯后，恢复城市i未访问状态如果最短则记下返回最短路径长度计算最短路径长度现在，我们想从城市a到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？设DiS x为城市x到城市E的最短路径长度(x表示任意一个城市)；mapi, j表示i, j两个城市间的距离，若mapi, j=0,则两个城市不通；我们可以使用回溯法来计算DiS 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

2、-j； end； thensearch-min；End； elseEnd； searchbeginS-除E外的所有城市；Disa -search(a)；输出 Disa；endmain这个程序的效率如何呢？我们可以看到,每次除了已经访问过的城市外,其他城市都要访问，所以时间复杂度为O (n!)，这是一个“指数级”的算法。那么，还有没有效率更高的解题方法呢？首先，我们来观察上述算法。在求bl到E的最短路径的时候，先求出从C2到E的最短路径；而在求从b2刭E的最短路径的时候，又求了一遍从C2刭E的最短路径。也就是说，从C2 到E的最短路径求了两遍。同样可以发现，在求从Cl、C2刭E的最短路径的过程中，从Dl到E 的最短路径也被求了两遍。而在整个程序中，从Dl到E的最短路径被求了四遍，这是多么大的一个浪费啊！如果在求解的过程中，同时将求得的最短路径的距离“记录在案”，以便将来随时调用，则可以避免这种重复计算。至此，一个新的思路产生了，即由后往前依次推出每个Dis值，直到推出Disa为止。问题是，究竟什么是“由后往前”呢？所谓前后关系是指对于任意一对城市i和j来说，如果满足“或者城市

3、i和城市j不连通或者disi+mapi, j三disj ”的条件，则定义为城市i在前、城市j在后。因为如果城市i和城市j连通且Disi+ma pi，j Disj，则说明城市j至城市E的最短路径长度应该比Disj更优。可城市j位于城市i后不可能推出此情况，以至于影响最后的解。那么，我们应该如何划分先后次序呢？如上图所示，从城市a出发，按照与城市a的路径长度划分阶段。阶段0包含的出发城市有a阶段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。由此得

4、出程序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!)要小得多。总结：此题是动态规划的基础题。讲解也比较详细。在求解最短路经问题时，必须对图进行拓扑排序，即划分明确的阶段、状态。出师表两汉：诸葛亮先帝创业未半而中道崩殂，今天下三分，益州疲弊，此诚危急存亡之秋也。然侍卫之臣不懈于内，忠志之士忘身于外者，盖追先帝之殊遇，欲报之于陛下也。诚宜开张圣听，以光先帝遗德，恢弘志士之气，不宜妄自菲薄，引喻失义，以塞忠谏之路也。宫中府中，俱为一体；陟罚臧否，不宜异同。若有作奸犯科及为忠善者，宜付有司论其刑赏，以昭陛下平明之理；不宜偏私，使内外异法也。侍中、侍郎郭攸之、费祎、董允等，此皆良实，志虑忠纯，是以先帝简拔以遗陛下：愚以为宫中之事，事无大小，悉以咨之，

5、然后施行，必能裨补阙漏，有所广益。将军向宠，性行淑均，晓畅军事，试用于昔日，先帝称之曰“能”，是以众议举宠为督：愚以为营中之事，悉以咨之，必能使行阵和睦，优劣得所。亲贤臣，远小人，此先汉所以兴隆也；亲小人，远贤臣，此后汉所以倾颓也。先帝在时，每与臣论此事，未尝不叹息痛恨于桓、灵也。侍中、尚书、长史、参军，此悉贞良死节之臣，愿陛下亲之、信之，则汉室之隆，可计日而待也。臣本布衣，躬耕于南阳，苟全性命于乱世，不求闻达于诸侯。先帝不以臣卑鄙，猥自枉屈，三顾臣于草庐之中，咨臣以当世之事，由是感激，遂许先帝以驱驰。后值倾覆，受任于败军之际，奉命于危难之间，尔来二十有一年矣。先帝知臣谨慎，故临崩寄臣以大事也。受命以来，夙夜忧叹，恐托付不效，以伤先帝之明；故五月渡泸，深入不毛。今南方已定，兵甲已足，当奖率三军，北定中原，庶竭驽钝，攘除奸凶，兴复汉室，还于旧都。此臣所以报先帝而忠陛下之职分也。至于斟酌损益，进尽忠言，则攸之、祎、允之任也。愿陛下托臣以讨贼兴复之效，不效，则治臣之罪，以告先帝之灵。若无兴德之言，则责攸之、祎、允等之慢，以彰其咎；陛下亦宜自谋，以咨诹善道，察纳雅言，深追先帝遗诏。臣不胜受恩感激。今当远离，临表涕零，不知所言。

《动态规划-最短路径问题》由会员汽***分享，可在线阅读，更多相关《动态规划-最短路径问题》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源