关闭

关闭

关闭

封号提示

内容

首页 动态规划-最短路径问题.doc

动态规划-最短路径问题.doc

动态规划-最短路径问题.doc

上传者: ncuchengzhibin 2010-12-18 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《动态规划-最短路径问题doc》,可适用于IT/计算机领域,主题内容包含最短路径问题最短路径问题下图给出了一个地图地图中每个顶点代表一个城市两个城市间的连线代表道路连线上的数值代表道路长度。现在我们想从城市a到达城市E。符等。

最短路径问题最短路径问题下图给出了一个地图地图中每个顶点代表一个城市两个城市间的连线代表道路连线上的数值代表道路长度。现在我们想从城市a到达城市E。怎样走才能使得路径最短最短路径的长度是多少?设DiS[x]为城市x到城市E的最短路径长度(x表示任意一个城市)mapij表示ij两个城市间的距离若mapij=则两个城市不通我们可以使用回溯法来计算DiS[x]:varS:未访问的城市集合functionsearch(who{x}):integer{求城市who与城市E的最短距离}beginifWho=EThenSearch{找到目标城市}Elsebeginminmaxint{初始化最短路径为最大}fori取遍所有城市Doif(mapWhoi>{有路})and(iS{未访问})thenbeginSS-i{置访问标志}jmapWhoisearch(i){累加城市E至城市Who的路径长度}SS+i{回溯后恢复城市i未访问状态}ifj<minThenminj{如果最短则记下}end{then}searchmin{返回最短路径长度}End{else}End{search}beginS除E外的所有城市Disasearch(a){计算最短路径长度}输出Disaend.{main}这个程序的效率如何呢?我们可以看到每次除了已经访问过的城市外其他城市都要访问所以时间复杂度为O(n!)这是一个“指数级”的算法。那么还有没有效率更高的解题方法呢?首先我们来观察上述算法。在求b到E的最短路径的时候先求出从C到E的最短路径而在求从b刭E的最短路径的时候又求了一遍从C刭E的最短路径。也就是说从C到E的最短路径求了两遍。同样可以发现在求从Cl、C刭E的最短路径的过程中从Dl到E的最短路径也被求了两遍。而在整个程序中从Dl到E的最短路径被求了四遍这是多么大的一个浪费啊!如果在求解的过程中同时将求得的最短路径的距离“记录在案”以便将来随时调用则可以避免这种重复计算。至此一个新的思路产生了即由后往前依次推出每个Dis值直到推出Dis「a」为止。问题是究竟什么是“由后往前”呢?所谓前后关系是指对于任意一对城市i和j来说如果满足“或者城市i和城市j不连通或者disimapijdisj”的条件则定义为城市i在前、城市j在后。因为如果城市i和城市j连通且Disi+mapij<Dis「j」则说明城市j至城市E的最短路径长度应该比Disj更优。可城市j位于城市i后不可能推出此情况以至于影响最后的解。那么我们应该如何划分先后次序呢?如上图所示从城市a出发按照与城市a的路径长度划分阶段。阶段包含的出发城市有{a}阶段所含的城市有{bb}阶段包含的出发城市有{CCCC}阶段包含的出发城市有{DDD}阶段包含城市{E}这种划分可以明确每个城市的次序因为阶段的划分具有如下性质阶段i的取值只与阶段i有关阶段i的取值只对阶段i的取值产生影响:每个阶段的顺序是确定的不可以调换任两个阶段的顺序我们从阶段的城市E出发按照阶段的顺序倒推至阶段的城市a。在求解的各个阶段利用了k阶段与k阶段之间的如下关系diskx=disE=k=…其中diskx指k阶段的城市x。由此得出程序disEforkdowntodo{倒序枚举阶段}forx取遍k阶段的所有城市dobegindisx{初始化最短路径为最大}fory取遍k阶段的所有城市doifdisymapx,y<disxthendisxdisymapx,y{累计消耗更新最短路径}end{for}输出disa这个程序的时间复杂度为W(n)比回溯法的时间复杂度O(n!)要小得多。总结:此题是动态规划的基础题。讲解也比较详细。在求解最短路经问题时必须对图进行拓扑排序即划分明确的阶段、状态。

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +2积分

资料评价:

/3
0下载券 下载 加入VIP, 送下载券

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部