动态程序设计方法

1、第十三章动态程序设计方法§13.1 问题的引出在近几年的联赛中，动态程序设计方法作为一种解题工具，其应用范围愈来愈广，愈来愈受到选手的重视。为什么要学习动态程序设计方法？这个解题方法与其它算法究竟有什么区别？它有什么应用价值？我们先通过一个具体实例来回答这些问题。【例题13.1】最短路径问题下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。现在，我们想从城市a到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？设DiSx为城市x到城市E的最短路径长度（x表示任意一个城市）；mapi，j表示i，j两个城市间的距离，若mapi，j=

2、0，则两个城市不通；我们可以使用回溯法来计算DiSx：varS：末访问的城市集合；function search(who)：integer； 求城市who与城市E的最短距离beginif WhoE Then Search0Else beginminmaxint；for i取遍所有城市Doif（mapWho，i0）and（iS）then beginSSi； 城市i已访问jmapWho，i+ search(i)； 计算城市E至城市Who的路径长度SSi； 恢复城市i未访问状态if jmin Then minj； 若城市E至城市Who的路径长度为目前最短，则记下End；thensearchmin；

3、返回城市E至城市的最短路径长度End；elseEnd；searchbeginS除E外的所有城市；Disasearch（a）； 计算城市a到城市E的最短路径长度输出Disa；endmain这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要访问，所以时间复杂度为O（n！），这是一个“指数级”的算法。那么，还有没有效率更高的解题方法呢？首先，我们来观察上述算法。在求b1到E的最短路径的时候，先求出从C2到E的最短路径；而在求从b2刭E的最短路径的时候，又求了一遍从C2刭E的最短路径。也就是说，从C2到E的最短路径求了两遍。同样可以发现，在求从Cl、C2刭E的最短路径的过程中

4、，从Dl到E的最短路径也被求了两遍。而在整个程序中，从Dl到E的最短路径被求了四遍，这是多么大的一个浪费啊！如果在求解的过程中，同时将求得的最短路径的距离“记录在案”，以便将来随时调用，则可以避免这种重复计算。至此，一个新的思路产生了，即由后往前依次推出每个Dis值，直到推出Disa为止。问题是，究竟什么是“由后往前”呢？所谓前后关系是指对于任意一对城市i和j来说，如果满足“或者城市i和城市j不连通或者disi+mapi，jdisj”的条件，则定义为城市i在前、城市j在后。因为如果城市i和城市j连通且Disimapi，jDisj，则说明城市j至城市E的最短路径长度应该比Disj更优。可城市j位

5、于城市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阶段之间的如下关系disk

6、x=dis4E=0 k=4，3，0，其中diskx指k阶段的城市x。由此得出程序disE0； for k3 downto 0 do for x取遍k阶段的所有城市do begin disx； for y取遍k+1阶段的所有城市do if disy+mapx,y<disx then disxdisy+mapx,y； end；for输出disa；这个程序的时间复杂度为W(n2)，比回溯法的时间复杂度O（n!）要小得多，其解题的思路就是本章要讲的动态程序设计方法。§13.2动态程序设计方法的基本概念通过上面例子，我们对动态程序设计方法有了一个初步的认识，它所处理的问题是一个“多阶段决

7、策问题”。下面讲解该方法涉及的一些基本概念一、阶段和状态1、阶段k将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。设阶段变量为k。阶段是问题的属性。多阶段决策问题中通常存在着若干个阶段，如上面的例子就由四个阶段组成。在一般情况下，阶段是和时间有关的，但是在很多问题中，阶段和时间并无直接关系。从阶段的定义中，可以看出阶段的两个特点，一是“相互联系”，二是“次序”。阶段之间相互联系的方式是通过状态和状态转移体现的。2、状态Sk各阶段开始时的客观条件叫做状态，如上例中，城市a、b1、D2、E等都为单个状态。描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的

8、状态变量，状态变量sk的取值集合称为状态集合，用Sk表示。例如S2=C1，C2，C3，C4。状态是阶段的属性。每个阶段通常包含若干个状态，用以描述问题发展到这个阶段时所处在的一种客观情况。在上面的例子中，我们从点E倒推三个阶段之后，可能出现的情况有两种，或处于b1或处于b2点，即S1=b1，b2。每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为状态转移（暂不定义）。例如倒推过程中C1点可以从D1点过来，也可以从D2点过来；从阶段1的b1或b2状态倒推到阶段0的a状态就是状态转移。状态转移是导出状态的途径，也是联系各阶段的途径。说到这里，可以提出应用动态程序设计方法的一

9、个重要条件。那就是将各阶段按照一定的次序排列好之后，对于阶段i的状态只能由阶段i+1的状态通过状态转移方程得来，与其它状态没有关系，尤其是与未发生的状态没有关系。换句话说，每个状态都是“过去历史的一个完整总结”。这就是无后效性。例如上例，计算城市b1至城市E的最短路径，必须在城市C1至城市E的最短路径、城市C2至城市E的最短路径和城市C3至城市E的最短路径已经求出的基础上才能得到，与其他城市、尤其是城市a没有关系。二、决策和策略上面的阶段与状态只是多阶段决策问题的一个方面的要素，下面是另一个方面的要素决策。1、决策uk(sk)当各段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，

10、这种决定称为决策。表示决策的变量称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合。常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。显然有uk(sk) ÎDk(sk)。决策是问题解的属性。决策的目的就是“确定下一阶段的状态”。还是回到上例，从阶段1的b1状态出发有三条路，也就是三个决策，分别导向阶段2的C1、C2、C3三个状态，即D1(b1)=C1，C2，C3。有了决策，我们可以定义状态转移：动态程序设计方法中本阶段的状态往往是上一阶段和上一阶段的决策结果，由第k段的状态sk和本阶

11、段的决策uk确定第k+1段的状态sk+1的过程叫状态转移。状态转移规律的形式化表示sk+1=Tk(sk，uk)称为状态转移方程。决策的目的是转移状态，状态转移的途径是决策。2、策略pl，n各段决策确定后，整个问题的决策序列就构成一个策略，用p1，n=u1(s1)，u2(s2)， un(sn)表示。对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作P1，n，使整个问题达到最有效果的策略就是最优策略。例如上例中，城市a到城市E的一条路径的决策序列构成了一个策略，其中最短路径的决策序列即为最优策略。说到这里，又可以提出运用动态程序设计方法的一个前提。即这个过程的最优策略应具有这样的性质

12、：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。这就是最优化原理。简言之，就是最优策略的子策略也是最优策略。例如上例通过动态程序设计方法求解后，不仅a到E的路径是所有这样的路径中的最短者，而且该路径上任何一个城市至城市E的路径长度也是最短的。三、最优化原理与无后效性什么类型的试题可以采用动态程序设计方法：1、该问题的解必须符合最优化原理是前提。这是因为是否符合最优化原理是一个问题的本质特征。对于不满足最优化原理的一个多阶段决策问题，整体上的最优策略p1，n同任何一个阶段k上的决策uk或任何一组阶段k1k2上的子策略pk1，k2都不存在任何关系。如果要

13、对这样的问题进行动态程序设计的话，我们从一开始所作的划分阶段等努力都将是徒劳的。2、问题的求解过程必须具备无后效性的特点是条件。因为动态程序设计方法是按次序去求每阶段的解，如果一个问题有后效性，那么这样的次序便是不合理的。但是，我们可以通过重新划分阶段或选定状态，或者增加状态变量个数等手段，来使得问题满足无后效性这个条件。说到底，还是要确定一个“序”。在联赛的多阶段决策问题中，绝大部分都是能够满足最优化原理的，但出题者往往会在后效性这一点上来设置障碍。所以在解题过程中，我们会特别关心“序”。对于有序的问题，就会考虑到动态动态程序设计方法；对于无序的问题，也会想方设法来使其有序。四 、最优指标函

14、数和状态转移方程1. 最优指标函数用于衡量所选定策略优劣的数量指标称为指标函数，最优指标函数记为fk(sk)，它表示从第k段状态sk采用最优策略p*k，n到过程终止时的最佳效益值。最优指标函数其实就是我们真正关心的问题的解。在上面的例子中，f1(b1)就表示从b1点到终点E1点的最短路径长度。我们求解的最终目标就是f0(a)。最优指标函数的求法一般是一个从目标状态出发的递推公式，称为状态转移方程： （边界条件）其中sk是第k段的某个状态，uk是从sk出发的允许决策集合Dk(sk)中的一个决策，Tk(sk，uk)是由sk和uk所导出的第k+1段的某个状态sk+1，g(x，uk)是定义在数值x和决

15、策uk上的一个函数，而函数opt表示最优化，根据具体问题分别表为max或min。【例题13.1】最短路径问题的状态转移方程就是diskx=dis4E=0 k=4，3，0，其中diskx指阶段k的城市x。§13.3动态程序设计的基本思维方式使用动态程序设计方法解题一般要经历如下步骤1、确定问题的研究对象，即状态。我们衡量一个算法的标准，无外乎时间、空间两项指标。“动态程序设计”的时间大多数为“多项式级”，比起同样解决这个问题的搜索算法“指数级”的时间来说，“动态程序设计”的时间需要是很少的。对于一个“动态程序设计”算法来说，状态的设计与存储比阶段的划分更重要，因为阶段只是一些可以等同处

16、理的状态的集合，状态的选定对整个问题的处理起了决定性的作用。我们选定的状态必须满足如下两点：状态必须完全描述出事物的性质，两个不同事物的状态是不同的；必须存在状态与状态之间的“转移方程”，以便我们可以由初始状态逐渐转化为目标状态。由于状态是描述事物性质的量，所以我们应该以上述要求为标准，具体情况具体分析；2、划分阶段，确定阶段之间的状态转移方程；3、考察此问题可否用动态程序设计方法解决，即问题是否具备最优子结构和无后效性的特征4、如果发现问题目前不能用动态程序设计方法解决，则调整阶段的划分和状态的定义，使其具备最优子结构和无后效性的特征。程序设计部分比较简单，一般格式为；for kn-1 do

17、wnto 1 do 枚举阶段 for s取遍所有状态 do for u取遍所有决策 do ；这里是一种从目标状态往回推的逆序求法，适用于目标状态确定的问题。而很多试题是确定了初始状态的。当然，对于初始状态确定的问题，我们也可以采用从初始状态出发往前推的顺序求法。事实上，这种方法对我们来说要更为直观、更易设计一些，从而更多地出现在我们的解题过程中。由于动态程序设计方法的模式性比较强，因此应该把主要精力放在状态定义、阶段划分和状态转移方程的设计上。一旦这些问题解决了，事情成功了一大半。下面，我们来分析一个具体实例，并给出多种解法。对于这些解法，我们将指出好的算法好在哪里，差一点的算法差在哪里，通过

18、不同算法的比较，让读者更深刻的领会动态程序设计方法的基本思维方式是“不做已经做过的工作”。【例题13.3.2】理想收入问题理想收入是指在股票交易中，以1元为本金可能获得的最高收入，并且在理想收入中允许有非整数股票买卖。已知股票在第i天每股价格是Vi元，1im，求m天后的理想收入。1、一种动态程序设计的解法很容易想到用动态程序设计方法解这道题目。因为要使得第i天获得理想收入，则前一次卖出股票的收入必须最高，否则第i天所持的股票数不可能最多。而要使得第i天所持的股票数最多，则必须检查第i-1天、第i-2天、第1天卖出股票的理想收入。理想收入问题具备了最优子结构和无后效性的特征。设阶段i：将所持的股

19、票全部卖出的日期（1im）状态j：前一次卖出股票的日期（0ji-1）决策k：第j天后买入股票的日期（jki-1）fi表示在第i天收盘时能达到的最高收入，则状态转移方为公式1的含义是：在第i天收盘时能达到的最高收入，是将第j天收盘后的收入，全部用于买入第k天的股票，再在第i天将所持的股票全部卖出所得的收入。采用公式1，可以得到算法1，其时间复杂度是W(m3)，空间复杂度是W(m)。算法1：f01；V01； 以1元为本金设定f和v的初始值f1.m0；for i1 to m do 阶段：枚举最后卖出全部股票的日期i for j0 to i-1 do 状态：枚举前一次卖出股票的日期j for kj t

20、o i-1 do 决策：枚举第j天第i-1天间买入股票的日期k fimaxfi，fj/Vk*Vi； 计算状态转移方程2、改变状态表示的含义改变动态程序设计中状态表示的含义，是优化动态程序设计的常用方法。例如此题，我们可以采用两种不同的状态表示方法优化算法2-1。方法1：设Pi表示前i天能获得的最多股票数，可列出如下状态转移方程：这是因为前i天所能获得的最多股票数，或者是前i-1天获得的最多股票数，或者是在第j天将前j天所能获得的最多的股票全部卖出，再买入第i天的股票。显然，前i-1天能获得的最多股票数乘以第i天的股价，就是第i天能达到的最大收入。方法2：设Qi表示前i天能达到的最大收入，可列出

21、如下状态转移方程：就是说前i天所能达到的最大收入，或者是前i-1天所能达到的的最大收入，或者是在第j天买入股票，再在第i天卖出，所能获得的最大收入。上述两种方法的时间复杂度都是W(m2)。这表明，改变状态表示的含义，在一定程度上提高了算法的效率。但对于这道题目，仅仅改变状态表示的含义，很难进一步优化算法。3、粗略利用信息算法1粗体部分的功能是确定fi所能达到的最大值。由于Vi不变，因此fi达到最大值，当且仅当fj/Vk达到最大值，其中0jk<i。算法1中，采用了二重循环来确定fj/Vk的最大值。但在确定fi-1所能达到最大值的时候，我们实际上已经求出当0jk<i-1时，fj/Vk所

22、能达到的最大值。如果能充分利用这一信息，就可以更快地确定fi 所能达到的最大值。如下图所示，要确定粗线下部的最大值，只需比较虚线下部的最大值和灰色部分的最大值即可。为了表示出上图的思想，这样，我们得到如下递推关系式：从公式4中可以看出，在确定maxfVi时，较充分的利用了确定maxfVi-1时产生的结果。采用公式4可得算法2，它的时间复杂度为W(m2)，空间复杂度是W(m)。算法2：f0 1； V0 1； 以1元为本金设定f和v的初始值maxfV0 0； 交易前没有股票for i1 to m do begin 计算每一天所持的最多股票数 maxfVimaxfVi-1； 将第i-1天所持的最多股

23、票数设为maxfVi的初始值 for j0 to i-1 do 枚举前i-1天购买股票的方案，将最多股票数设为maxfVi maxfVimaxmaxfVi，fj/Vi-1； fimaxfVi*Vi； 在第i天将maxfVi张股票全部抛出end；for将公式4化简，有在这个公式中，maxfVi可以看作是前i-1天所能获得的最多股票数。这种状态表示方法和公式2中Pi的含义本质上是相同的。这样，我们通过对已知信息的利用，达到了改变动态程序设计中状态表示含义的效果。4、充分利用信息在算法2中，进一步利用信息，很容易得到时间复杂度为W(m)的算法。算法2的粗体部分的功能是确定maxfVi所能达到的最大值

24、。由于Vi-1不变，因此fj/Vi-1达到最大值，当且仅当fj达到最大值，其中0j<i。算法2中内层循环实质上是在确定maxfVi时，找到f0，f1，fi-1中的最大值。而在确定maxfVi-1时，我们已经找到了f0，f1，fi-2中的最大值。如果把这个信息利用起来，就可以更快的确定f0，f1，fi-1中的最大值。这样，我们得到如下递推关系式：从公式5中可以看出，在确定maxfi时，充分利用了确定maxfi-1时所产生的信息。采用公式5可得算法3，它的时间复杂度是W(m)。从公式5中的三个递推关系式可以看出，当前状态都只与前一个状态有关，因此，空间复杂度可以进一步降到W(1)。算法3：f

25、1；V01； 以1元为本金设定f和v的初始值maxf0；maxfV0； 最大收益和最多股票数初始化for i1 to m do begin if f>maxf then maxff;若抛出第i-1天的股票可获得最大的收益，则确定第i-1天将股票抛出 if maxf/Vi-1>maxfV then maxfVmaxf/Vi-1；若购买第i-1天的股票可获得最多的股票数，则确定第i-1天购买股票 fmaxfV*Vi 计算抛出第i天股票的收益end；for公式4中的maxfi可以看作是前i-1天能达到的最大收入。虽然这种状态表示方法和公式3中Qi是类似的，但算法的时间复杂度却从W(m2)

26、降到了W(m)，空间复杂度也从W(m)降到了W(1)。这样，我们通过充分利用已知信息，达到了改变状态表示难以达到的优化效果。由此可见，动态程序设计方法之所以效率高，是因为它把已经做过的工作结果存储起来，每次需要的时候，直接读入即可，不做已经做过的工作。当然，对于同一个问题，由于各人看问题的角度不同，对阶段、状态和状态转移方式的理解可能不一样，因此有些状态转移方程仍存在冗余运算。是否充分利用信息是提高时间效率的关键。此外，充分利用信息并不一定要以牺牲空间为代价，只要方法得当，同样可以优化算法的空间复杂度。§13.4动态程序设计方法的应用实例动态程序设计是一种很灵活的解题方法，其应用的范

27、围愈来愈广。例如不是最优化问题能不能使用该方法；对于不具备最优子结构的问题能不能借用动态程序设计方法的思想解决；如果在两点之间求两条或多条最佳路径时，动态程序设计方法还灵不灵等等，历届联赛复赛曾围绕这些问题出过相应的试题，参与培训的学生也把这些问题作为深入学习动态程序设计的方法的课题。一、 计算所有方案对于一些阶段性强、但不属于最优化的问题，是否也可以借助动态程序设计方法呢？如果我们可以找出状态转移的关系，并在状态转移方程中去掉最佳性要求opt（min或max），将扩展子状态的所有行动作为决策，则可以例举出由初始状态至目标状态的所有方案。显然，在计数类问题中使用这种方法要比回溯法等搜索算法简捷

28、许多。【例题13.4.1】骑士游历问题设有一个n*m的棋盘(2n50，2m50)，如下图。在棋盘上任一点有一个中国象棋马，马走的规则为：1.马走日字 2.马只能向右走。即下图所示：当n，m 给出之后，同时给出马起始的位置和终点的位置，试找出从起点到终点的所有路径的数目。例如：(n=10，m=10)，(1，5)(起点)，(3，5)(终点)。应输出2(即由(1，5)到(3，5)共有2条路径，如下图)：输入：n，m，x1，y1，x2，y2(分别表示n，m，起点坐标，终点坐标)输出：路径数目(若不存在从起点到终点的路径，输出0)分析：使用回溯法是可以计算路径数目，但问题是搜索效率太低，根本不可能在较短

29、的时间内出解。因为题目并不要求每一条路径的具体走法。在这种情况下，是否非得通过枚举所有路径方案后才能得出路径数目，有没有一条简便和快效的“捷径”呢。从(x1，y1)出发，按照由左而右的顺序定义阶段的方向。位于（x，y）左方且可达（x，y）的跳马位置集合都是（x，y）的子问题，起点至（x，y）的路径数实际上等于起点至这些位置集的路径数之和（如下图）。如此一来，状态转移关系便凸显出来。设状态转移方程map，其中mapi，j为起点（x1，y1）至（i，j）的路径数目。由于棋盘规模的上限为50*50，可能导致路径数目大得惊人，因此不妨设map数组的元素类型为extended。初始时，除mapx1，y1

30、=1外其余为。显然。我们采用动态程序设计的方法计算起点（x1，y1）至终点（x2，y2）的路径数目mapx2，y2：阶段j：中国象棋马当前的列位置(y1jy2)；状态i：中国象棋马在j列的行位置（1in）；决策k：中国象棋马在（i，j）的起跳方向(1k4)；计算过程如下：fillchar(map，sizeof(map)，0)；mapx1，y1 1； 从（x1，y1）出发for jy1 to y2 do 递推中国象棋马的列位置 for i1 to n do 递推中国象棋马在j列的行位置for k1 to 4 do 递推中国象棋马在（i，j）的4个跳动方向 begin中国象棋马由（i，j）出发，沿

31、着k方向跳至（x，y）；if (x.n)(y1.y2) 计算状态转移方程 then mapx，y mapi，j+mapx，y end；forwriteln(mapx2，y2：0：0)； 输出从（x1，y1）到（x2，y2）的路径数目上述算法的时间复杂度为O（n2），明显优于回溯法的效率。二、计算一些阶段性明显、但不具备最优子结构特征的问题对于一些阶段性明显、但不具备最优子结构特征的问题，可以考虑将指标函数值当作“状态”，从而变最优化问题为判定性问题。再借用动态程序设计思想，用递推方式计算最佳值。【例题13.4.2】mod 4 最优路径问题 3 1 0 1 2 2 0 2 31234在上图中找出

32、从第1点到第4点的一条路径，要求路径长度mod 4的余数最小。分析：这个图是一个多段图，而且是一个特殊的多段图。虽然这个图的形式比一般的多段图要简单，但是这个最优路径问题却不能用动态程序设计方法来做。因为一条从第1点到第4点的最优路径，在它走到第2点、第3点时，路径长度mod 4的余数不一定是最小，也就是说最优策略的子策略不一定最优这个问题不满足最优化原理。但是我们可以把它转换成判定性问题，用递推法来解决。设fk(sk)从第1点到第k点的长度mod 4为sk的路径是否存在的标志。显然（边界条件）（这里lenk，i表示从第k-1点到第k点之间的第i条边的长度）最后的结果就是可以使f4(s4)值为

33、真的最小的s4值。fillchar(f，sizeof(f)，false)；f1，0true； 边界条件for k2 to n do 阶段：逐条边延伸 for s0 to 3 do 状态：枚举当前路径长度对4的每一个余数 for u1 to k-1点出发的边数 do 决策：枚举k-1点出发的每一条边fk，sfk，s or fk-1，($10000+s-k-1点出发的第u条边)mod 4；加上$10000是为防止出现负数for i0 to 3 do if fn，i then break；输出i；这个递推法的递推公式和动态程序设计方法的规划方程非常相似，我们在这里借用了动态程序设计方法的符号也就是为

34、了更清楚地显示这一点。其实它们的思想也是非常相像的，可以说是递推法借用了动态程序设计方法的思想解决了动态程序设计方法不能解决的问题。有的多阶段决策问题（像这一题的阶段特征就很明显），由于不能满足最优化原理等使用动态程序设计方法的先决条件，而无法应用动态程序设计方法。在这时可以将最优指标函数的值当作“状态”放到下标中去，从而变最优化问题为判定性问题，再借用动态程序设计方法的思想，用递推法来解决问题。三、双重动态程序设计在求任两点之间的最短路径时，有一个比较著名的算法floyd-Warshall算法，其算法的中心思想是这样的：求a至b的满足中间结点不超过k的最短路径。而后，随着k由1逐渐增加至n而

35、求出a至b的最短路径 。则其算法的结构如下： for k1 to n do 中间结点k从1增至n for a1 to n do 求每一对结点的中间结点不超过k的最短路径 for b1 to n do if (mapa，k>0) and (map k，b>0) Then 如果a与k，k与b均可达 if (mapa，b=0)or (mapa，b>mapa，k+mapk，b) Then 如果a、b不可达，或者a、b之间的路径不如a-k-b这条路径短，则改变mapa，b的值 mapa，bmapa，k+mapk，b；注：mapa，b为从a到b的最短路的距离，如果a，b不可达，则mapa

36、，b=0。 这个解题方法实质上就是一个动态程序设计方法。它是以最短路中间结点的取值来划分阶段的,第k个阶段为所有最短路的中间结点k时的情况。而第k个阶段只与前(k-1)个阶段有关系，所以，这个问题同时满足“无后效性”与“最优子问题”这两个性质，采用动态程序设计方法是正确的。双重动态程序设计是在floyd-Warshall算法的基础是提出来的。我们来看一个实例【例题13.4.3】城市交通某城市有n（1n50）个街区，某些街区由公共汽车线路相连，如在下图中，街区1，2有一条公共汽车线路相连，且由街区1至街区2的时间为34分钟。由于街区与街区之间的距离较近，与等车时间相比可忽略不记，所以这个时间为两

37、趟公共汽车的间隔时间，即平均的等车时间。由街区1至街区5的最快走法为1-3-5，总时间为44分钟。现在市政府为了提高城市交通质量，决定加开m(1m10)条公共汽车线路。若在某两个街区a，b之间加开线路（前提是a、b之间必须已有线路），则从a到b的旅行时间缩小为原来的一半（距离未变，只是等车的时间缩短了一半）。例如，若在1，2之间加开一条线路，则时间变为17分钟，加开两条线路，时间变为8.5分钟，以此类推。所有的线路都是环路，即如果由1至2的时间变为17分钟，则由2至1的时间也变为17分钟。求加开某些线路，能使由城市1至城市n的时间最少。例如，在上图中，如果m=2，则改变1-3，3-5的线路，总

38、的时间可以减少为22分钟。输入： 第一行为城市数n与加开线路数m。第二行至第n+1行，每行为n个实数，第i+1行第j列表示由城市i到城市j的时间。如果时间为0，则城市i不可能到城市j。注意：输入数据中，从城市1到城市n至少有一条路线。输出： 第一行为由城市1到城市n的最小时间X（保留小数点后两位）。 第二行至第m+1行为更改的线路。每行由两个整数（x，y）构成。表示将城市x与城市y之间增加一条线路。分析：城市交通问题的图论模型很简单。如果只考虑从城市1到城市n的最少时间，那么，这个问题就是一道经典的最短路径问题。因此，这个问题乍看上去，就给人一种熟悉的感觉。而实质呢？问题的“变数”在于市政府的

39、改革措施很奇特（每加一条公共汽车路线，两个街区之间的旅行时间就缩短为原来的一半），这就弄得人不知所措。显然，这个改革不能分步执行，即它不具有“贪心法”的要求，而如果采用搜索的方法，时间效率会很低。那么该如何解决呢？ 还是采用floyd-Warshall的算法思想。在计算增加m条边的最优解（使最短路下降最快）的过程中，我们同样可以发现：1、将道路a-b上增加的m条边可以分为如下两个问题（如果k是最短路上的一点）2. 求a-k增加t条边；3. 求k-b增加m-t条边。t可以取从0至m的任意值。问题a-b增加m条边的最优解取决与这两个子问题的最优解。2、在求m条边的过程中，始终只与增加t条边与增加m

40、-t条边的子问题发生联系。以上两个特点即为“无后效性”与“最优子问题”。所以，“城市交通”问题可采用动态程序设计方法。设vala，b，m的值为增加m条线路后城市a到城市b的最短路长。其中vala，b，0的值为原交通图中边城市a至城市b的最短路，可以直接使用floyd算法计算；vala，b，m=minvala，k，t+valk，b，m-t(其中t为从0到m中的一个数，k为a到b中间的一点)在两条道路增加的边数确定的条件下，采用floyd算法计算最优解。所以这个问题实质上是一个双重动态程序设计问题。具体算法如下： 直接使用floyd算法计算vala，b，0（1an，1bn）；for g1 to m

41、 do 按照新增加的边数g划分阶段 begin 对任一对城市（i，j）来说，(i，j)的边权减半；vali，j，g= (i，j)的边权； for k1 to n do 枚举中间城市 for i1 to n do 枚举经由城市k的所有城市对（ikj）for j1 to n do begin vali，j，g=； 计算状态转移方程 vali，j，g=minvali，j，g，vali，k，0+valk，j，gvalk，j，g>0，valk，j，0+vali，k，gvali，k，g>0 ；End；forend；for说明：这个问题的val数组的初始值与上一个floyd算法不一样，初始值均为

42、maxint。这个算法的时间复杂度为W(n3*m2)，约为W(n5)，还是一个多项式级的算法。值得注意的是， 程序还要求可打印出增加的边，由于问题规模大，存储也需要一些技巧，这些小问题的解决请参看程序样例Const big=1000000； 极大值Type maps=array1.50，1.50 of Real； 地图类型Var map:maps； 城市交通图 Val:array0.10 of maps； Valki，j加入k条边后城市i和城市j的最短路长 Way:array0.10，1.50，1.50，1.2 of byte；最优结果记录表。wayp，i，j存储ij 的路径上新增p条线路的最

43、佳方案。其中中间城市为wayp，i，j，2，ik 的路径上新增的线路数为wayp，i，j，1条 n，m:integer； 城市数和加开的线路数 Procedure init； 初始化过程，输入数据 Var i，j:integer； begin Readln(n，m)； 读城市数和加开的线路数 new(map)； 为城市交通图申请内存 for i1 to n do 读城市交通图 begin for j1 to n do read(mapi，j)； readln； end；for end；init Procedure main； 应用动态程序设计方法求解 Var i，j，k，p，q:integer

44、； R:real； begin R1； fillchar(way，sizeof(way)，0)； 最优结果记录表初始化 new(Val0)； 通过floyd-Warshall算法计算新增线路前任两个顶点的最短路 val0 map； for k1 to n do for i1 to n do if val0i，k>0 then for j1 to n do if (Val0k，j>0) and (i<>j) then if (val0i，j=0) or (Val0i，j>Val0i，k+Val0k，j) then begin Val0i，j Val0i，k+Val0k，j； Way0i，j，1 0； Way0i，j，2 k； end；then for p1 to m do 按照新增加的线路数p划分阶段 begin for i1 to n do 计算每条边在新增第p条线路后的距离 for j1 to n do