《[工学]高级算法设计10年动规加作业》由会员分享，可在线阅读，更多相关《[工学]高级算法设计10年动规加作业（65页珍藏版）》请在金锄头文库上搜索。
1、动态规划法*1方法概述: 发展及研究内容n动态规划(dynamic programming)是运筹学的一个分 支，20世纪50年代初美国数学家R.E.Bellman等人 在研究多阶段决策过程(multistep decision process)的 优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段 问题，逐个求解，创立了解决这类过程优化问 题的新方法动态规划。n动态规划问世以来，在经济管理、生产调度、 工程技术和最优控制等方面得到了广泛的应用 。例如最短路线、资源分配、设备更新等问题 ，用动态规划比用其它方法求解更为方便。Da
2、te2方法概述: 发展及研究内容n虽然动态规划主要用于求解以时间划分阶段的 动态过程的优化问题，但是一些与时间无关的 静态规划(如线性规划、非线性规划)，可以人为 地引进时间因素，把它视为多阶段决策过程， 也可以用动态规划方法方便地求解。Date3方法概述: 基本思想 n动态规划的思想实质是分治思想和解决冗余。 n与分治法类似的是，将原问题分解成若干个子问题， 先求解子问题，然后从这些子问题的解得到原问题的 解。n与分治法不同的是，经分解的子问题往往不是互相独 立的。若用分治法来解，有些共同部分（子问题或子 子问题）被重复计算了很多次。n如果能够保存已解决的子问题的答案，在需要时再查 找，这样
3、就可以避免重复计算、节省时间。动态规划 法用一个表来记录所有已解的子问题的答案。n这就是动态规划法的基本思路。具体的动态规划算法 多种多样，但它们具有相同的填表方式。Date4方法概述: 求解步骤 1、找出最优解的性质，并刻画其结构特征； 2、递归地定义最优值（写出动态规划方程）； 3、以自底向上的方式计算出最优值； 4、根据计算最优值时记录的信息，构造最优解。Date5方法概述: 适用条件 动态规划法的有效性依赖于问题本身所具有的 两个重要性质n最优子结构：当问题的最优解包含了其子问题 的最优解时，称该问题具有最优子结构性质。n重叠子问题：在用递归算法自顶向下解问题时 ，每次产生的子问题并不
4、总是新问题，有些子 问题被反复计算多次。动态规划算法正是利用 了这种子问题的重叠性质，对每一个子问题只 解一次，而后将其解保存在一个表格中，在以 后尽可能多地利用这些子问题的解。Date6方法概述: 最优性原理及举例 nBellman给出这个原理作为动态规划的适用条 件，后来Morin在1982年证明了这只是一个充 分条件而非必要条件。Bellman的原定义如下 ：n An optimal policy has the property that whatever the initial state and initial decision are, then remaining decisi
5、ons must constitute an optimal policy with regard to the state resulting from first decision. n最优性原理又称为最优子结构性质：n 如果有一决策序列包含有非最优的决策子序列，则该决 策序列一定不是最优的。即一个最优策略的子策略总是最 优的。Date7l例1：多段图的最短路问题多段图：设G=是一个有向连通图， 其中|V|=n, |E|=m, V有划分V1,V2,Vk， 这里V1 =s,s称为源点， Vk =t,t称为 终点，其中k 2 。对于每条有向边 E都存在Vi V，使得u Vi 和v Vi+1,
6、其中1i均 附有代价C(u,v)，则称G是一个k段图。Date8123456789101112s97324212711118654356425V1V2V3V4V5tDate9l最短路：从源点s到终点t的整条路上的 代价之和为最小。每个子集Vi构成图中的一段。由于E的 约束，每条从s到t的路径都是从第一段 开始，然后顺次经过第2段，第3段， ，最后在第k段终止。Date10l假设s,v2,v3,vk-1,t是一条从s到t的最短路径， 还假定从源点s（初始状态）开始，已做出了到 结点v2的决策（初始决策），因此v2就是初始决 策所产生的状态。如果把v2看成是原问题的一个 子问题的初始状态，解这个子
7、问题就是找出一 条由v2到t的最短路径。这条路径显然是 v2,v3,vk-1,t，否则设v2,q3,qk-1,t是一条由v2到 t的更短路径，则s,v2,q3,qk-1,t是一条比路径 s,v2,v3,vk-1,t 更短的由s到t的路径，与假设矛 盾，故最优化原理成立。 Date11cost(i,j)=minC(j,r)+cost(i+1,r)rVi+1E jrtViVi+1最短最短向前处理法：设P(i,j)是从Vi中的点j到 t的一条最短路，cost(i,j)是这条路线的 耗费。由后向前推算，得到Date12123456789101112s9 7324212 71111 86543 5642
8、5V1V2V3V4V5tcost(4,9)=4cost(i,j)=minC(j,r)+cost(i+1,r) cost(4,10) =2 cost(4,11)=5 cost(3,6)=min6+cost(4,9),5+cost(4,10) =min6+4,5+2=7从第3段的顶点6到t的最短路径是6-10-t5+2Date13123456789101112s9 7324212 71111 86543 56425V1V2V3V4V5tcost(3,7)= min4+cost(4,9),3+cost(4,10) =min4+4,3+2=5 从第3段的顶点7到t的最短路径是7-10-tcost(3,
9、8)=7从第3段的顶点8到t的最短路径是8-10-tDate14123456789101112s9 7324212 71111 86543 56425V1V2V3V4V5tcost(2,2)=7 从第2段顶点2到t的最短路是2-7-10-tcost(2,3)=9从第2段顶点3到t的最短路是3-6-10-tcost(2,4)=18从第2段顶点4到t的最短路是4-8-10-tcost(2,5)=15从第2段顶点5到t的最短路是5-8-10-tcost(1,1)=16 从第1段顶点1到t的最短路径由两条：1-2-7-10-t和1-3-6-10-tDate15为了便于描述算法，对一个k段图的顶点，按
10、段的顺序给它的每个顶点编号。设图中有n个 顶点，则编号为1，2，n。首先，给s编为 1号；然后给V2中的各个顶点分别编为2，3， ，| V2 |+1号；以此类推，最后t编号为n。 这样编号使Vi+1中的任何顶点的编号大于Vi中 所有顶点的编号。 于是，可以按n-1,n-2,1的顺序计算出 cost(i,j)和D(i,j)。算法中可以利用顺序编号 的特点，而不再考虑顶点所在的段。Date16设顶点的编号已知，边已知及边的代价函 数C(i,j)已知。用costi表示顶点i到t的最小 代价， 1i n。用Di表示从顶点i到t的最 短路径上顶点i的后继顶点号，用Pi表示 最短路径经过第i级的顶点号，
11、1i kDate17求两点间最短路径的算法： Procedure Fgraph 1. for i 1 to n costi 0； 2. for j =n-1 step 1 to 1 do 3. 找顶点r,使 E,且C(j,r)+costr最小 ； 4. costjC(j,r)+costr; 5. Dj r ; 6. P1 1 ; Pk n; 7. for j=2 to k-1 do Pj DPj-1O(n+|E|)Date18123456789101112s9 7324212 71111 86543 56425V1V2V3V4V5t（从前）向后：设BPij是从源点s到Vi 中顶点j的最小成本路
12、径，bcost(i,j)是这 条路径的代价bcost(i,j)=minbcost(i-1,r) + C(r,j) r Vi-1EDate19l格路问题：求从起点O(0,0)到终点 E(m,n)的最短路。则分别用穷举法和动态 规划法的加法次数和比较次数各是多少？E(m,n)O(0,0)xyDate20E(m,n)O(0,0)xyDate21E(m,n)O(0,0)xymn个点 Date22l例2：货郎担问题124310 5209 1289 13156810 10 15 205 9 106 13 128 8 9 v1 v2v3v4v1 v2 v3 v4Date23不失一般性，考虑以结点1为起点和终
13、 点的一条哈密顿回路。每一条这样的路 线都由一条边和一条由结点k到结 点1的路径组成，其中kV-1,而这条 由结点k到结点1的路径通过V-1，k的 每个结点各一次。如果这条周游路线是 最优的，则这条由结点k到结点1的路径 必定是通过V-1，k的每个结点各一次 的由k到1的最短路径。Date24l设T( i,S)是由结点 i出发，经过结点集S中 每个结点各一次并回到初始结点1的一条最 短路径长度，则T(1,V-1)就是一条最优的周游路线长度。动态规划模型：T(1,V-1)=mind1k+T(k,V-1,k) 2 k nT( i,s)=mindij+T(j,S-j) j S,i SDate25 1
14、0 15 205 9 106 13 128 8 9 v1 v2v3v4v1 v2 v3 v4T(1, 2,3,4)=mind12+T(2,3,4) ,d13+T(3,2,4) , d14+T(4,2,3) T(2,3,4) =mind23+T(3,4) , d24+T(4,3) T(3,4) = d34+T(4,) T(4,)=d41Date26T(1,2,3,4)T(2,3,4)T(3,2,4)T(4,2,3)T(3,4)T(4,3) T(2,4)T(4,2) T(2,3)T(3,2)T(4,) T(3,)T(4,) T(2,)T(3,) T(4,)Date27T(1,2,3,4,5)T(2
15、,3,4,5 )T(3,2,4,5)T(3,4,5)T(4,5) T(5,4)T(2,4,5)T(5,4)T(4,5)Date28矩阵链乘法n问题描述n加括号的方案数 n动态规划法 Date29矩阵链乘法: 问题描述给定n个矩阵A1,A2, An，Ai的维数为pi-1pi(1in), 要求计算连乘积A1A2 An 由于矩阵乘法满足结合率，所以可以 有许多不同的计算次序，这种计算次 序可以用加括号的方式来确定。比如： A1,A2,A3,A4(A1 ( A2 ( A3 (A4) ) ) (A1 ( A2 A3 ) A4 ) )(A1 A2 )( A3 A4 ) ( A1 ( A2 A3) ) A4 )( A1 A2 ) A3) A4 )Date30不同的计算次序有不同的计算量注：1.设Apq,Aq
