《动态规划最短路径问题.docx》由会员分享，可在线阅读，更多相关《动态规划最短路径问题.docx（4页珍藏版）》请在三一办公上搜索。
1、动态规划最短路径问题最短路径问题 下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。 现在，我们想从城市a到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？设 DiSx为城市x到城市E的最短路径长度； mapi，j表示i，j两个城市间的距离，若mapi，j=0，则两个城市不通； 我们可以使用回溯法来计算DiSx： var S：未访问的城市集合； function search(whox)：integer； 求城市who与城市E的最短距离 begin if WhoE Then Search0 找到目标城市 Else begin minma
2、xint； 初始化最短路径为最大 for i 取遍所有城市 Do ifand then begin SSi； 置访问标志 jmapWho，i+ search(i)； 累加城市E至城市Who的路径长度 SSi； 回溯后，恢复城市i未访问状态 if jmin Then minj； 如果最短则记下 end；then searchmin； 返回最短路径长度 End；else End；search begin S除E外的所有城市； Disasearch； 计算最短路径长度 输出Disa； endmain 这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要访问，所以时间复杂度为O
3、，这是一个“指数级”的算法。那么，还有没有效率更高的解题方法呢？ 首先，我们来观察上述算法。在求b1到E的最短路径的时候，先求出从C2到E的最短路径；而在求从b2刭E的最短路径的时候，又求了一遍从C2刭E的最短路径。也就是说，从C2到E的最短路径求了两遍。同样可以发现，在求从Cl、C2刭E的最短路径的过程中，从Dl到E的最短路径也被求了两遍。而在整个程序中，从Dl到E的最短路径被求了四遍，这是多么大的一个浪费啊！如果在求解的过程中，同时将求得的最短路径的距离“记录在案”，以便将来随时调用，则可以避免这种重复计算。至此，一个新的思路产生了，即 由后往前依次推出每个Dis值，直到推出Disa为止。
4、 问题是，究竟什么是“由后往前”呢？所谓前后关系是指对于任意一对城市i和j来说，如果满足“或者城市i和城市j不连通或者disi+mapi，jdisj”的条件，则定义为城市i在前、城市j在后。因为如果城市i和城市j连通且Disimapi，jDisj，则说明城市j至城市E的最短路径长度应该比Disj更优。可城市j位于城市i后不可能推出此情况，以至于影响最后的解。那么，我们应该如何划分先后次序呢？ 如上图所示，从城市a出发，按照与城市a的路径长度划分阶段。 阶段0包含的出发城市有a 阶段1所含的城市有b1，b2 阶段2包含的出发城市有C1，C2，C3，C4 阶段3包含的出发城市有D1，D2，D3 阶
5、段4包含城市E 这种划分可以明确每个城市的次序，因为阶段的划分具有如下性质 阶段i的取值只与阶段i+1有关，阶段i+1的取值只对阶段i的取值产生影响： 每个阶段的顺序是确定的，不可以调换任两个阶段的顺序； 我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系 disx=yk+1阶段的城市集4kmindisy+mapx,y(x,y)GdisE=0 k k=4，3，0，其中disx指k阶段的城市x。由此得出程序 disE0； for k3 downto 0 do 倒序枚举阶段 for x取遍k阶段的所有城市do begin disx； 初始化最短路径为最大 for y取遍k+1阶段的所有城市do if disy+mapx,ydisx then disxdisy+mapx,y； 累计消耗，更新最短路径 end；for 输出disa； 这个程序的时间复杂度为W(n)，比回溯法的时间复杂度O要小得多。 2总结：此题是动态规划的基础题。讲解也比较详细。 在求解最短路经问题时，必须对图进行拓扑排序，即划分明确的阶段、状态。
