《数据结构域算法设计-第3章 动态规划(part1) 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第3章 动态规划(part1) 课件（73页珍藏版）》请在金锄头文库上搜索。
1、第3章 动态规划 Part 1,上海大学计算机学院 沈云付,学习要点,理解动态规划算法的概念与基本思想。 掌握动态规划算法的两个基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法方法 求解步骤-4步 自上而下自下而上求解方式；备忘录（打表）的应用 动态规划典型问题 矩阵连乘、最长公共子序列、0-1背包问题、最大子段和、流水作业调度（Johnson调度法则）等等,引言 几个典型问题,问题1：最短路径,有一个棋盘形街道，某人从西南角O走到东北角U，想选择一条路线使所走的路径最短，如何走法？,O,B,A,C,D,E,F,G,H,I,N,K,L,M,P,Q,R,S,T,U,1
2、3 2 3,2 2 1 4,2 3 4 5,2 3 1 2,2 1 2 2 3,3 4 1 2 3,2 2 1 3 4,问题2：最短路径,对有向无环图，求从s到t的一条最短路径,问题3：背包问题,有一旅行者要从n种物品中选取体积不超过C的行李随身携带，要求包装得最满。 例：设有n=8个体积分别为54，45，43，29，23，21，14，1的物体和一个容积为C=110的背包，问选择哪几个物体装入背包可以使其装的最满。,问题4：文本相似度问题,给定两篇文章（或代码）的文本x=和y=,两者公共部分的最长长度是多少？,3.1 矩阵连乘问题,3.1 矩阵连乘问题,给定n个矩阵A1，A2，An，其中，Ai
3、与Aj+1是可乘的，i=1，2，n-l，现要计算出这n个矩阵的连乘积A1A2An。,矩阵连乘问题：确定一种运算次序，使总的运算次数达到最少。,一、问题叙述,矩阵乘法,A=(aij)mk，B=(bij)kn，C=(cij)mn计算C：每个元素需k次乘法，k-1次加法 C有mn个元素：计算C，需mnk次乘法，mn(k-1)次加法 举例：设A1，A2，A3，分别为10100，1005，550的矩阵，求连乘积A1A2A3时需多少次乘法运算？,矩阵连乘方法数与添括号方式数一一对应,完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）若矩阵连乘积A是完全加括号的，则A可表示为2个
4、完全加括号的矩阵连乘积B和C的乘积并加括号，即 A=(BC),矩阵连乘积与加括号,设有四个矩阵 A,B,C,D，它们的维数分别是：,16000, 10500, 36000, 87500, 34500,总共有五种完全加括号的方式,乘法运算数,二、算法分析-穷举法行吗？,列举所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数,所有可能的计算次序有多少？,设矩阵序列的加括号方式为P(n)，可得：,1 ( n = 1),P(n) =,P(n)是Catalan数 P(N)=(4n/n3/2),二、算法分析-新思路,采用一个新方法,（1）分析最优解的结构,记Ai：j为AiAi+1Aj，记mij是
5、计算AiAi+1Aj时的最少乘法次数,显然，Ai：i=Ai，mii=0,问题变为：计算A1：n、求m1n,二、算法分析-新思路,（2）建立递归关系,m1n= m1k+ mk+1n+ p0pkpn,一般情况假定计算Ai：j的一个最优次序在矩阵Ak和Ak+1之间将矩阵链断开，i k j,mij= mik+ mk+1j+ pi-1pkpj,假定计算A1：n的一个最优次序在矩阵Ak和Ak+1之间将矩阵链断开，1 k n,分析最优解的特征和结构,特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子
6、结构性质。问题的最优子结构性质是该问题可用这一算法求解的显著特征。,矩阵链问题的一般递推关系,mij=,0 i=j,（3）计算最优值,1、简单递归,2、动态规划的求解方法 按自底向上方式求解,对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有,mij=,计算最优值程序,void MatrixChain(int *p, int n, int *m)int i,r,j,k,t;for (i = 1; i = n; i+) mii = 0;for (r = 2; r = n; r+ )for (i = 1; i = n - r+ l; i+) j = i + r -
7、 1;mij = mi+1j + pi - 1*pi* pj;for (k = i+1; k j; k+)t = mik + mk + 1j+ pi 1* pk * pj;if (t mij)mij = t; ,算法过程,算法复杂度分析,算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。,（4）算法分析-构造最优解,void Traceback(int i, int j, int *s)if (i = j) return;Traceback(
8、i, sij, s);Traceback(sij + 1, j,s);cout “Multiply A “ i “, “ sij;cout “ and A “ (sij + 1) “ , “ j endl,引入分割点标记sij，确定加括号方式，构造最优解,3.2 动态规划算法的基本要素,动态规划的基本思想,算法目标：求解具有某种最优性质的问题。它可能有许多可行解，希望找到具有最优值的解。,算法思想： 动态规划算法将待求解问题分解成若干个子问题，先求解子问题， 从这些子问题的解得到原问题的解。这些子问题往往不互相独立。 分解时得到的子问题数目可能很多，有些子问题被重复计算了很多次。,求解方法,自
9、底向上方式、自上而下方式 采用备忘录方法：求解过程中需保存已解决的子问题的解，而在需要时再找出已求得的解，就可避免大量的重复计算，节省时间。动态规划法用表记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。,动态规划中的概念、名词术语(1),1.阶段：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。,2.状态：某一阶段的出发位置称为状态。通常一个阶段包含若干状态。,3.决策：从某阶段的一个状态演变到下一个阶段某状态的选择。特点：前一阶段的终点是后一阶段的起点，前一阶段的决策影响后一阶段的状态。 4.策略：由开始到终点的全过程中，由每段决策组
10、成的决策序列。,动态规划中的概念、名词术语(2),5.状态转移方程：描述由k阶段到k+1阶段状态的演变规律称为状态转移方程（用数学形式表达）。 6.目标函数与最优化概念：目标函数是衡量多阶段决策过程优劣的准则。最优化概念是在一定条件件下找到一个途径，经过按题目具体性质所确定的运算以后，使全过程的总效益达到最优。,7.动态规划：在多阶段决策问题中，各阶段采取的决策依赖于目前状态，并引起状态的转移，以期求得最优化的过程,最佳原理 一个最优化策略的子策略总是最优的。,动态规划的求解步骤,1、找出最优解的性质，并刻画其结构特征 2、递归地定义最优值（写出动态规划方程） 3、以自底向上（或自顶向下）的方
11、式计算出最优值 4、根据计算最优值时得到的信息，构造一个最优解,注意：1、步骤1-3：是动态规划算法的基本步骤。2、如只求最优值，步骤4可以省略；3、若需求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。,动态规划的求解方法,按自底向上方式求解 是动态规划方法的一种 所有子问题计算一次，无需递归代价 效率较高,程序（next page）,void MatrixChain(int p, int n, int *m, int *s)for (int i = 1; i = n; i+) mii = 0;for (int r = 2; r = n; r+ )for (
12、int i = 1; i = n - r+ l; i+) int j = i + r - 1;mij = mi+1j + Pi - 1*Pi* Pj;sij = i;for (int k = i+1; k j; k+)int t = mik + mk + 1j+ Pi 1* pk * pj;if (t mij)mij = t; sij = k;,备忘录方法,动态规划算法的基本要素,动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。,1最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。,如何说明问题具有最优子结构性质？,用反证法
13、：先假设由问题的最优解导出的子问题的解不是最优的，然后再设法证明在这个假设下可构造出一个比原问题最优解更好的解，从而导致矛盾。,动态规划算法的基本要素,2重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。,矩阵计算次序,重叠子结构性质,动态规划算法利用子问题的重叠性质，对每一个子问题只解一次，并将解保存在一个表格中，在以后尽可能多地利用这些子问题的解。,特征：不同的子问题个数随问题的大小呈多项式增长，而不是指数增长。 用动态规划算法只需要多项式时间，从而获得较高的解题效率。,动态规划法与分治策略,共性：都通过子问题
14、求解原问题 方法：分治法是把一个规模为的问题分成多个与原问题类型相同的较小的子问题，通过对子问题的求解，并把子问题的解合并起来，构造出整个问题的解；动态规划法也先求子问题的解，通过求解子问题，构造原问题的解。,动态规划法与分治策略（续）,差异： 独立性：分治法各子问题互相独立，动态规划法的各子问题可不独立 子问题数目：动态规划法中涉及的子问题，不独立的有很多，而独立的应只有多项式级;分治法涉及的子问题数一般达指数级 动态规划法把问题分成许多子问题，每个子问题的解都是局部最优；分治法未必考虑最优性 动态规划法可采用备忘录方法。,备忘录方法,备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。,
