《算法设计与分析实用教程-电子教案-杨克昌第6章 动态规划》由会员分享，可在线阅读，更多相关《算法设计与分析实用教程-电子教案-杨克昌第6章 动态规划（30页珍藏版）》请在金锄头文库上搜索。
1、教学要求 掌握最优性原理与动态规划设计的基本步骤 掌握应用动态规划设计求解0-1背包问题、三角形划分、最长子序列与最优路径问题等多阶段决策典型案例 本章重点 根据案例的实际构建状态转移方程 在案例求解基础上理解与掌握最优性原理,第 6 章 动态规划,6.1 动态规划概述,1. 动态规划的概念 (1) 动态规划（Dynamic programming）是运筹学的一个分支，是求解决策过程最优化的数学方法。 (2) 动态规划处理的对象是多阶段决策问题。 (3) 多阶段决策问题，是指这样的一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也称为
2、一个策略。对于每一个决策序列，可以在满足问题的约束条件下用一个数值函数（即目标函数）衡量该策略的优劣。多阶段决策问题的最优化目标是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。,2. 最优性原理,作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。最优决策序列中的任何子序列都是最优的。 “最优性原理”用数学语言描述： 假设为了解决某一多阶段决策过程的优化问题，需要依次作出n个决策D1,D2,Dn，如若这个决策序列是最优的，对于任何一个整数k，1kn，不论前面k个决策D1,D2,Dk是怎样的，以后的最优决策只取
3、决于由前面决策所确定的当前状态，即以后的决策序列Dk+1,Dk+2,Dn也是最优的。 最优性原理体现为问题的最优子结构特性。最优子结构特性是动态规划求解问题的必要条件。,例如，在数字串847313926中插入5个乘号，分为6个整数相乘，使乘积最大的最优解为： 8*4*731*3*92*6=38737152 该最优解包含了以下子问题的最优解： 在84731中插入2个乘号使乘积最大为：8*4*731； 在7313中插入1个乘号使乘积最大为：731*3； 在3926中插入2个乘号使乘积最大为：3*92*6； 在4731392中插入3个乘号使乘积最大为：4*731*3*92。 这些子问题的最优解都包含
4、在原问题的最优解中。 最优性原理是动态规划的基础。,3. 最优子结构特性举例,（1）把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其结构特性。 （2）将问题各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递推关系，并确定初始条件。 分析归纳出各个阶段状态之间的转移关系是应用动态规划的关键。 （3）应用递推求解最优值。 递推计算最优值是动态规划算法的实施过程。 （4）根据计算最优值时所得到的信息，构造最优解。 构造最优解就是具体求出最优决策序列。,4. 动态规划实施步骤,6.2 0-1背包问题,6.2.1 一般01背包问题 案例提出：,1. 动态规划设计逆推求解要点,2) 逆推
5、计算最优值 for(j=0;j=wn ) mnj=pn; / 首先计算m(n,j) else mnj=0; for(i=n1;i=1;i) / 逆推计算m(i,j) for(j=0;j=wi ,3) 构造最优解 若m(i,cw)m(i+1,cw), i=1,2,n1 则xi=1；装载w(i)。 其中cw=c开始，cw=cwx(i)*w(i)。 否则，x(i)=0,不装载w(i)。 最后，所装载的物品效益之和与最优值比较，决定w(n)是否装载。,2. 动态规划设计顺推求解要点,6.3 西瓜分堆,动态规划设计要点： 一般把n个整数分成两组，每组的个数不限，使两组数据和之差为最小。 两组数据之和不一
6、定能相等，不妨把数据之和较小的一组称为第1组。设n个整数b(i)之和为s，则第1组数据之和s1s/2，这里x为x的取整。 问题要求在满足s1s/2前提下求s1最大值maxc，这样两组数据和之差的最小值为mind=s-2*maxc。如果maxc=s/2=s/2，则mind=0, 即两组数据和相等。 递推关系：,6.4 凸n边形的三角形划分,给定凸n边形P=1,2,n,每一个顶点i带一个权数r(i)(i=1,2,n)。要求在该凸n边形的顶点间连n-3条互不相交的连线，把凸n边形分成n-2个三角形，每个三角形的值为三角形的三个顶点权数之积。 试确定一种三角剖分，使得剖分的n-2个三角形的值之和最小。
7、 例如一个各顶点带权数的凸7边形，如何连接对角线分割成5个三角形，使得这5个三角形的值之和最小？,（1） 建立递推关系 设m(i,j)是求多边形 划分的最小值，则有递推关系 (j=i+2时，即三角形) (ikj) 初始（边界）条件： (不构成三角形) 显然m(1,n)为最优值。 （2） 求最优值的递推结构 注意到当ikj，要求m(i,j)时，要用到m(i,k)与m(k,j)。为此，设置循环： for(d=2;d=n-1;d+) for(i=1;i=n-d;i+) j=i+d; 这样，可按d从2开始递增取值,先得m(i,k)与m(k,j)，为比较进而求m(i,j)提供可能。,（3） 构造最优解
8、设置s(i,j)，在递推赋值时记录最优划分点k。注意到分划线分布为二叉结构，应用s(i,j)定义实现最优解的递归函数f(a,b)： 设置c=s(a,b)记录参数a,b的最优划分点； 若 ca+1，则输出ac； 若 cb-1，则输出cb； 然后调用下一层递归函数f(a,c);f(c,b)； (4) 算法时间复杂度分析 动态规划在三重循环中实现，算法的时间复杂度为O(n3)。,6.5 最长子序列探索,6.5.1 最长非降子序列 案例提出： 由n个正整数组成的序列，从该序列中删除若干个整数，使剩下的整数组成非降子序列，求最长的非降子序列。 例如，由12个正整数组成的序列为： 48，16，45，47，
9、52，46，36，28，46，69，14，42 请在序列中删除若干项，使剩下的项为非降（即后面的项不小于前面的项）序列，非降序列最多为多少项？,设序列的各项为a1,a2,an ，对每一个整数操作为一个阶段，共为n个阶段。 （1）建立递推关系 设置b数组，bi表示序列的第i个数（含第i个数）到第n个数中的最长非降子序列的长度，i=1,2,n。对所有的ji，比较当ajai时的bj的最大值，显然bi为这一最大值加1，表示加上ai本身这一项。 因而有递推关系： bi=max(bj)+1 (ajai,1ijn) 边界条件：bn=1,1. 动态规划设计要点,（2）递推计算最优值 bn=1; for(i=n
10、1;i=1;i) max=0;for(j=i+1;jmax) max=bj; bi=max+1; / 逆推得bi 逆推依次求得bn1,b1，比较这n1个值得其中的最大值lmax，即为最优值。 以上动态规划算法的时间复杂度为O(n2)。,案例提出： 在指定数字串中插入运算符号问题，包括插入若干个乘号求积的最大最小，或插入若干个加号求和的最大最小，都是比较新颖且有一定难度的最优化问题。 在一个由n个数字组成的数字串中插入r个乘号(1rn)，将它分成r+1个整数，找出一种乘号的插入方法，使得这r+1个整数的乘积最大。 例如，对给定的数串847313926，如何插入5个乘号，使其乘积最大?,6.6 插
11、入乘号问题,1） 建立递推关系 设f(i,k)表示在前i位数中插入k个乘号所得乘积的最大值，a(i,j)表示从第i个数字到第j个数字所组成的ji+1(ij)位整数值。 一般地，为了求取f(i,k)，考察数字串的前i个数字，设前j（kji）个数字中已插入k1个乘号的基础上，在第j个数字后插入第k个乘号，显然此时的最大乘积为f(j,k1)*a(j+1,i)。 于是可以得递推关系式： f(i,k)=max(f(j,k1)*a(j+1,i) （kji） 前j个数字没有插入乘号时的值显然为前j个数字组成的整数，因而得边界值： f(j,0)=a(1,j) (1ji),6.6.1 动态规划求解,2) 递推计
12、算最优值 for(d=0,j=1;j=n;j+) d=d*10+bj1; /在设计中可省略a数组，用变量d替代 fj0=d; / 计算初始值fj0 for(k=1;k=r;k+) for(i=k+1;i=n;i+) for(j=k;ji;j+) for(d=0,u=j+1;u=i;u+) d=d*10+bu1; / 计算d即为a(j+1,i) if(fikfjk1*d) / 递推求取fik fik=fjk1*d; printf(“最优值为%.0f“，fnr);,3) 构造最优解 为了能打印相应的插入乘号的乘积式，设置标注位置的数组t(k)与c(i,k)，其中c(i,k)为相应的f(i,k)的第
13、k个乘号的位置，而t(k)标明第k个乘号“*”的位置，例如，t(2)=3，表明第2个“*”号在在第3个数字后面。 当给数组元素赋值f(i,k)=f(j,k1)*d时，作相应赋值c(i,k)=j，表明f(i,k)的第k个乘号的位置是j。在求得f(n,r)的第r个乘号位置t(r)=c(n,r)=j的基础上，其他t(k)(1kr1)可应用下式逆推产生 t(k)=c(t(k+1),k) 根据t数组的值，可直接按字符形式打印出所求得的插入乘号的乘积式。,注意到n个数字之间共有n1个插入乘号的位置，在这n1个位置中组合选取r个位置t(1),t(2),t(r)供插入乘号。计算被这r个乘号分成的r+1个整数的
14、积d。每计算一个d与存储最大乘积的变量max比较，若dmax，则作赋值max=d，同时乘号位置t数组赋值给s数组。 完成所有组合枚举后，得乘积最大值max，按s数组的值打印插入乘号的乘积式及其最大乘积max。,6.6.2 基于组合枚举求解,6.7 数阵中的最优路径,6.7.2 矩阵中的最大路径 在一个给定的n行m列矩阵中，从矩阵的左上角走到右下角，路径中每一步能往右、往下走到相邻格子，不能斜着走，也不能走出矩阵。 试在所有路径中搜索路径上各数和最大的最大路径。 例如，所示108矩阵中，如何确定最大路径？,设（i,j）第i行第j列格，数组a(i,j)存储该格(i,j)中的数字； 数组b(i,j)
15、为(i,j)至矩阵右下角(n,m)路径的最大数字和； 数组c(i,j)存储(i,j)下步方向标：向下为“D”，向右为“R”； 数组d(i,j)为从格(i,j)至右下角(n,m)不同最大路径的条数。 显然，最优路径的数字和为b(1,1)。 （1） 求路径最优值的递推关系 b(i,j)与c(i,j)（i=n，.，2，1；j=m，.，2，1）的值由整数b(i+1,j)与整数b(i,j+1)的大小决定： 若 b(i+1,j)=b(i,j+1)，则 b(i,j)=a(i,j)+b(i+1,j);c(i,j)=D; 若 b(i+1,j)b(i,j+1)，则 b(i,j)=a(i,j)+b(i,j+1);c(i,j)=R; 这样反推所得b(1,1)即为所求的最大路径数字和。,动态规划设计要点：,（2） 求最优路径数的递推关系 若 b(i+1,j)b(i,j+1)，则d(i,j)=d(i+1,j); 若 b(i+1,j)b(i,j+1)，则d(i,j)=d(i,j+1); 若 b(i+1,j)=b(i,j+1)，则d(i,j)=d(i+1,j)+d(i,j+1); （3） 确定边界条件 最后一行与最后一列只有一出口，由bnm=anm开始： 向左逐个推出同行的b(n,j)（j=m-1，.，2,1）: b(
