背包问题之动态规划法

《背包问题之动态规划法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划1.概述3.图问题中的动态规划法2.组合问题中的动态规划法4.查找问题中的动态规划法1.概述1.1例题（多段图）1.4最优性原理1.6动态规划法的设计思想1.5无后效性原则1.3动态规划适于解决什么样的问题1.2什么是动态规划1.1多段图的最短路径问题设图G=(V,E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集Vi（2≤k≤n,1≤i≤k），使得E中的任何一条边(u,v)，必有u∈Vi，v∈Vi+m（1≤i＜k,1＜i+m≤k），则称图G为多段图，称s∈V1为源点，t∈Vk为终点。多段图的最短路径问题是求从源点到终点的最小代

2、价路径。由于多段图将顶点划分为k个互不相交的子集，所以，多段图划分为k段，每一段包含顶点的一个子集。根据多段图的定义，每个子集中的顶点互不邻接。不失一般性，将多段图的顶点按照段的顺序进行编号，同一段内顶点的相互顺序无关紧要。假设图中的顶点个数为n，则源点s的编号为0，终点t的编号为n-1，并且，对图中的任何一条边(u,v)，顶点u的编号小于顶点v的编号。2120345678949387684756866537图1一个多段图设G是一个有向加权图，则G从顶点i到顶点j之间的最短路径问题满足最优性原理。证明：设i～ip～iq～j是一条最短路径，但其中子路径i

3、p～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)=m

4、in{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)

5、可以直接获得（括号中给出了决策产生的状态转移）：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)

6、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。在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序

7、列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。1.2什么是动态规划动态规划是运筹学的一个分支。与其说动态规划是一种算法，不如说是一种思维方法来得更贴切。因为动态规划没有固定的框架，即便是应用到同一道题上，也可以建立多种形式的求解算法。许多隐式图上的算法，例如求单源最短路径的Dijkstra算法、广度优先搜索算法，都渗透着动态规划的思想。因此，动态规划不像深度或广度优先那样可以提供一套模式，需要的时候，取来就可以使用；它必须对具体问题进行具体分析处理，需要丰富的想象力去建立模型，需要创造性的思想去

8、求解。准确地说，动态规划不是万能的，它只适于解决一定条件的最优策略问题。或许，大家听到这个结论