第十三章动态程序设计方法§13.1问题的引出在近几年的联赛中，动态程序设计方法作为一种解题工具，其应用范围愈来愈广，愈来愈受到选手的重视。为什么要学习动态程序设计方法？这个解题方法与其它算法究竟有什么区别？它有什么应用价值？我们先通过一个具体实例来回答这些问题。【例题13.1】最短路径问题下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。现在，我们想从城市a到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？设DiS［x］为城市x到城市E的最短路径长度（x表示任意一个城市）；map[i，j]表示i，j两个城市间的距离，若map[i，j]=0，则两个城市不通；我们可以使用回溯法来计算DiS［x］：varS：末访问的城市集合；functionsearch(who)：integer；{求城市who与城市E的最短距离}beginifWho＝EThenSearch←0Elsebeginmin←maxint；fori取遍所有城市Doif（map[Who，i]＞0）and（iS）thenbeginS←S－[i]；{城市i已访问}j←map[Who，i]+search(i)；{计算城市E至城市Who的路径长度}S←S＋[i]；{恢复城市i未访问状态}ifj＜minThenmin←j；{若城市E至城市Who的路径长度为目前最短，则记下}End；{then}search←min；{返回城市E至城市的最短路径长度}End；{else}End；{search}beginS←除E外的所有城市；Dis[a]←search（a）；{计算城市a到城市E的最短路径长度}输出Dis[a]；end．{main}这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要访问，所以时间复杂度为O（n！），这是一个“指数级”的算法。那么，还有没有效率更高的解题方法呢？首先，我们来观察上述算法。在求b1到E的最短路径的时候，先求出从C2到E的最短路径；而在求从b2刭E的最短路径的时候，又求了一遍从C2刭E的最短路径。也就是说，从C2到E的最短路径求了两遍。同样可以发现，在求从Cl、C2刭E的最短路径的过程中，从Dl到E的最短路径也被求了两遍。而在整个程序中，从Dl到E的最短路径被求了四遍，这是多么大的一个浪费啊！如果在求解的过程中，同时将求得的最短路径的距离“记录在案”，以便将来随时调用，则可以避免这种重复计算。至此，一个新的思路产生了，即由后往前依次推出每个Dis值，直到推出Dis「a」为止。问题是，究竟什么是“由后往前”呢？所谓前后关系是指对于任意一对城市i和j来说，如果满足“或者城市i和城市j不连通或者dis[i]+map[i，j]≥dis[j]”的条件，则定义为城市i在前、城市j在后。因为如果城市i和城市j连通且Dis[i]＋map[i，j]＜Dis「j」，则说明城市j至城市E的最短路径长度应该比Dis[j]更优。可城市j位于城市i后不可能推出此情况，以至于影响最后的解。那么，我们应该如何划分先后次序呢？如上图所示，从城市a出发，按照与城市a的路径长度划分阶段。阶段0包含的出发城市有{a}阶段1所含的城市有{b1，b2}阶段2包含的出发城市有{C1，C2，C3，C4}阶段3包含的出发城市有{D1，D2，D3}阶段4包含城市{E}这种划分可以明确每个城市的次序，因为阶段的划分具有如下性质⑴阶段i的取值只与阶段i+1有关，阶段i+1的取值只对阶段i的取值产生影响：⑵每个阶段的顺序是确定的，不可以调换任两个阶段的顺序；我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系dis[k][x]=dis[4][E]=0k=4，3…，0，其中dis[k][x]指k阶段的城市x。由此得出程序dis[E]←0；fork←3downto0doforx取遍k阶段的所有城市dobegindis[x]←∞；fory取遍k+1阶段的所有城市doifdis[y]+map[x,y]<dis[x]thendis[x]←dis[y]+map[x,y]；end；{for}输出dis[a]；这个程序的时间复杂度为W(n2)，比回溯法的时间复杂度O（n!）要小得多，其解题的思路就是本章要讲的动态程序设计方法。§13.2动态程序设计方法的基本概念通过上面例子，我们对动态程序设计方法有了一个初步的认识，它所处理的问题是一个“多阶段决策问题”。下面讲解该方法涉及的一些基本概念一、阶段和状态1、阶段k将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。设阶段变量为k。阶...