背包问题之动态规划法.pptx

会计学1.概述多段图的最短路径问题2设G是一个有向加权图，则G从顶点i到顶点j之间的最短路径问题满足最优性原理。

证明：设i～ip～iq～j是一条最短路径，但其中子路径ip～iq～j不是最优的，
假设最优的路径为ip～iq’～j，
则我们重新构造一条路径：i～ip～iq’～j
显然该路径长度小于i～ip～iq～j，与i～ip～iq～j是顶点i到顶点j的最短路径相矛盾.
所以，原问题满足最优性原理。对多段图的边(u,v)，用cuv表示边上的权值，将从源点s到终点t的最短路径记为d(s,t)，则从源点0到终点9的最短路径d(0,9)由下式确定：
d(0,9)=min{c01+d(1,9),c02+d(2,9),c03+d(3,9)}
这是最后一个阶段的决策，它依赖于d(1,9)、d(2,9)和d(3,9)的计算结果，而
d(1,9)=min{c14+d(4,9),c15+d(5,9)}
d(2,9)=min{c24+d(4,9),c25+d(5,9),c26+d(6,9)}
d(3,9)=min{c35+d(5,9),c36+d(6,9)}
这一阶段的决策又依赖于d(4,9)、d(5,9)和d(6,9)的计算结果：d(4,9)=min{c47+d(7,9),c48+d(8,9)}
d(5,9)=min{c57+d(7,9),c58+d(8,9)}
d(6,9)=min{c67+d(7,9),c68+d(8,9)}
这一阶段的决策依赖于d(7,9)和d(8,9)的计算，而d(7,9)和d(8,9)可以直接获得（括号中给出了决策产生的状态转移）：
d(7,9)=c79＝7(7→9)
d(8,9)=c89＝3(8→9)
再向前推导，有：
d(6,9)=min{c67+d(7,9),c68+d(8,9)}=min{6+7,5+3}=8(6→8)
d(5,9)=min{c57+d(7,9),c58+d(8,9)}=min{8+7,6+3}=9(5→8)
d(4,9)=min{c47+d(7,9),c48+d(8,9)}=min{5+7,6+3}=9(4→8)d(3,9)=min{c35+d(5,9),c36+d(6,9)}=min{4+9,7+8}=13(3→5)
d(2,9)=min{c24+d(4,9),c25+d(5,9),c26+d(6,9)}=min{6+9,7+9,8+8}=15(2→4)
d(1,9)=min{c14+d(4,9),c15+d(5,9)}=min{9+9,8+9}=17(1→5)
d(0,9)=min{c01+d(1,9),c02+d(2,9),c03+d(3,9)}=min{4+17,2+15,3+13}=16(0→3)
得到最短路径为0→3→5→8→9，长度为16。
在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。 动态规划是运筹学的一个分支。与其说动态规划是一种算法，不如说是一种思维方法来得更贴切。因为动态规划没有固定的框架，即便是应用到同一道题上，也可以建立多种形式的求解算法。许多隐式图上的算法，例如求单源最短路径的Dijkstra算法、广度优先搜索算法，都渗透着动态规划的思想。
因此，动态规划不像深度或广度优先那样可以提供一套模式，需要的时候，取来就可以使用；它必须对具体问题进行具体分析处理，需要丰富的想象力去建立模型，需要创造性的思想去求解。 准确地说，动态规划不是万能的，它只适于解决一定条件的最优策略问题。或许，大家听到这个结论会很失望：其实，这个结论并没有削减动态规划的光辉，因为属于上面范围内的问题极多，还有许多看似不是这个范围中的问题都可以转化成这类问题。
上面所说的“满足一定条件”主要指下面两点：
(1)状态必须满足最优化原理；
(2)状态必须满足无后效性。
这条特征说明什么呢?它说明动态规划适于解决当前决策和过去状态无关的问题。状态，出现在策略的任何一个位置，它的地位都是相同的，都可以实施同样的决策。这就是无后效性的内涵。作为整个过程的最优策略具有如下性质：无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。
可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解，非最优解对问题的求解没有影响。在例题1最短路径问题中，A到E的最优路径上的任一点到终点E的路径也必然是该点到终点E的一条最优路径，满足最优化原理。下面来讨论另外一个问题。例题余数最少的路径【分析】在这个问题中，如果还按照例题