《算法设计与分析第07章》由会员分享，可在线阅读，更多相关《算法设计与分析第07章（79页珍藏版）》请在金锄头文库上搜索。
1、第七章 动态规划7.1 一般方法1. 多阶段决策问题 多阶段决策过程：问题的活动过程分为若干相互联系的阶段，任一阶段i以后的行为仅依赖于i阶段的过程状态，而与i阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策，这一系列的决策称为多阶段决策过程(multistep decision process) 。 最优化问题：问题的每一阶段可能有多种可供选择的决策，必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所导致的问题的结果可能不同。 多阶段决策的最优化问题就是：求能够获得问题最优解的决策序列最优决策序列。2021/6/712. 多阶段决策过程的求解策略1）枚举法
2、 穷举可能的决策序列，从中选取可以获得最优解的决策序列2）动态规划 20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，创立了解决这类过程优化问题的新方法动态规划。 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。 应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等
3、问题，用动态规划方法比用其它方法求解更为方便。2021/6/723. 最优性原理(Principle of Optimality) 过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。 利用动态规划求解问题的前提 1) 证明问题满足最优性原理 如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题 2) 获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键。2021/6/73例7.1 多段图问题多段图G=(V,E)是一个有向图，且具有特性: 结点：结点集V被分成k2个不相交的集合Vi
4、，1ik， 其中V1和Vk分别只有一个结点s(源点)和t(汇点)。 每一集合Vi定义图中的一段。 边： 所有的边(u,v)均具有如下性质： 若E，则 该边将是从某段i指向i+1段，即若uVi，则vVi1, 1ik1。才 每条边(u,v)均附有成本c(u,v)。 s到t的路径：从第1段开始，至第2段、第3段、最后 在第k段终止。路径的成本是这条路径上边的成本 和。 多段图问题：求由s到t的最小成本路径。2021/6/7412345678910111297324227111181456356425V1V2V3V4V55段图2021/6/75 多段图问题的多阶段决策过程：生成从s到t的最小成本路径是
5、在k-2个阶段（除s和t外）进行某种决策的过程：从s开始，第i次决策决定Vi+1(1ik-2)中的哪个结点在从s到t的最短路径上。最优性原理对多段图问题成立 假设s,v2,v3,vk-1,t是一条由s到t的最短路径。 初始状态：s 初始决策：(s,v2)， v2V2 初始决策产生的状态：v2 则，其余的决策：v3,.,vk-1相对于v2将构成一个最优决策序列最优性原理成立。 反证：若不然，设v2,q3,qk-1,t是一条由v2到t的更短的路径，则s, v2,q3,qk-1,t将是比s,v2,v3,vk-1,t更短的从s到t的路径。与假设矛盾。 故，最优性原理成立2021/6/76n例例7.20
6、/1背包问题背包问题 KNAP(l,j,X)n已知一个载重为已知一个载重为M M的背包和的背包和n n件物品，物品编号从件物品，物品编号从1 1到到n n。第第i i件物品的重量为件物品的重量为 wwi i，如果将第如果将第i i种物品种物品装入背包将获益装入背包将获益p pi i，这里，这里，w wi i00，p pi i00，0 0 inin。所谓所谓0/10/1背包问题是指在物品不能分割，只能整件背包问题是指在物品不能分割，只能整件装入背包或不装入的情况下，求一种最佳装载方装入背包或不装入的情况下，求一种最佳装载方案使得总收益最大。案使得总收益最大。2021/6/77例7.20/1背包问
7、题 KNAP(l,j,X) 目标函数： 约束条件： 0/1背包问题：KNAP(1,n,M) 2021/6/78最优性原理对0/1背包问题成立： 设y1,y2,yn是x1,x2,xn的0/1值最优序列。 若y10, KNAP(2,n,M)是初始决策产生的状态。则y2,yn相对于KNAP(2,n,M)将构成一个最优序列。否则，y1,y2,yn将不是KNAP(1,n,M)的最优解 若y11, KNAP(2,n,Mw1)是初始决策产生的状态。则y2,yn相对于KNAP(2,n,Mw1)将构成一个最优序列。 否则，设存在另一0/1序列z1,z2,zn,使得 且 则序列y1,z2,zn将是一个对于KNAP
8、(1,n,M)具有更大效益值的序列。 故，最优性原理成立2021/6/797. 动态规划模型的基本要素一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素：1) 阶段 阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k=1,2,.,n表示。12345678910111297324227111181456356425V1V2V3V4V55段图2021/6/710例7.1 多段图问题多段图G=(V,E)是一个有向图，且具有特性: 结点：结点集V被分成k2个不相交的集合Vi，1ik， 其中V1和Vk分别只有一个结点s(源点
9、)和t(汇点)。 每一集合Vi定义图中的一段。 边： 所有的边(u,v)均具有如下性质： 若E，则 该边将是从某段i指向i+1段，即若uVi，则vVi1, 1ik1。 每条边(u,v)均附有成本c(u,v)。 s到t的路径：从第1段开始，至第2段、第3段、最后 在第k段终止。路径的成本是这条路径上边的成本 和。 多段图问题：求由s到t的最小成本路径。2021/6/71112345678910111297324227111181456356425V1V2V3V4V55段图2021/6/7122） 状态 状态(state)表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有无后向
10、性，即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。 描述状态的变量称状态变量(state variable)。变量允许取值的范围称允许状态集合(set of admissible states)。用xk表示第k阶段的状态变量，它可以是一个数或一个向量。用大写Xk表示第k阶段的允许状态集合。 状态变量简称为状态2021/6/7133）决策 当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策(decision) 。 描述决策的变量称决策变量(decisi
11、on variable)。变量允许取值的范围称允许决策集合(set of admissible decisions)。用uk(xk)表示第k阶段处于状态xk时的决策变量，它是xk的函数，用Uk(xk)表示了xk的允许决策集合。 决策变量简称决策。2021/6/7144）策略 决策组成的序列称为策略(policy)。由初始状态x1开始的全过程（由1到n）的策略记作p1,n(x1)，即p1,n(x1)=u1(x1),u2(x2),.，un(xn)。 由第k阶段的状态xk开始到终止状态（由k到n）的后部子过程的策略记作pk,n(xk)，即pk,n(xk)=uk(xk),uk+1(xk+1),.，un
12、(xn)。类似地， 由第k到第j阶段的子过程的策略记作 pk,j(xk)=uk(xk),uk+1(xk+1),.，uj(xj)。 对于每一个阶段k的某一给定的状态xk，可供选择的策略pk,j(xk)有一定的范围，称为允许策略集合(set of admissible policies)，用P1,n(x1),Pk,n(xk),Pk,j(xk)表示。2021/6/7155) 状态转移方程 在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程(equation of state)表示这种演变规律，写作2021/6/7166) 指标函数和最优值函数 指标函数(object
13、ive function)是衡量过程优劣的数量指标，它是关于策略的数量函数，从阶段k到阶段n的指标函数用Vk,n(xk,pk,n(xk)表示，k=1,2,.,n。 能够用动态规划解决的问题的指标函数应具有可分离性，即Vk,n可表为xk,uk,Vk+1, n 的函数，记为：2021/6/7175. 递推策略1）向前处理法 列出根据xi+1,xn的最优决策序列求取xi决策值的关系式。 从最后一个阶段，逐步向前递推求出各阶段的决策值。决策序列x1,x2,xn就是问题的最优解。 xn-1,1xn-1,pn-1xn2021/6/7192） 向后处理法 列出根据x1,xi-1的最优决策序列求取xi决策值的
14、关系式。 从第一个阶段，逐步向后递推求出各阶段的决策值。决策序列x1,x2,xn就是问题的最优解。 2021/6/720动态规划的基本思想：动态规划的基本思想：（1）动态规划方法的关键在于正确写出基本的递推关系式）动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条件。要做到这一点，必须将问题的过程分和恰当的边界条件。要做到这一点，必须将问题的过程分成几个相互联系的阶段，恰当选择状态变量，决策变量和成几个相互联系的阶段，恰当选择状态变量，决策变量和定义最优值函数，从而把一个大问题化成一族同类型的子定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解。即从边界条件开始，逐
15、段递推寻优，问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题的最优解，就是整优化结果，依次进行，最后一个子问题的最优解，就是整个问题的最优解。个问题的最优解。（2）在多阶段决策过程中，动态规划方法是既把当前一段）在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前的效益和未来效益综合起来考和未来各段分开，又把当前的效益和未来效益综合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来虑的一种最优化方法。因此，每段决策的选取是从全局来考虑
16、的，与该段的最优选择答案一般是不同的。考虑的，与该段的最优选择答案一般是不同的。（3）在求整个问题的最优策略时，由于初始状态是已知的，）在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经的各而每段的决策都是该段状态的函数，故最优策略所经的各段状态便可逐次变换得到，从而确定最优路线。段状态便可逐次变换得到，从而确定最优路线。2021/6/721关于动态规划求解策略的进一步说明采用枚举法：若问题的决策序列由n次决策构成，而每次决策有p种选择，则可能的决策序列将有pn个。利用动态规划策略的求解过程中保存了所有子问题的最优解，而舍去了所有不能导致问题最优解的
17、次优决策序列动态规划：可能有多项式的计算复杂度。2021/6/722与非线性规划相比，动态规划的优点：与非线性规划相比，动态规划的优点：（1）易于确定全局最优解。动态规划方法是一种逐步改善法，）易于确定全局最优解。动态规划方法是一种逐步改善法，它把原问题化为一系列结构相似的最优化子问题，而每个子它把原问题化为一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少的多，约束集合也要简单得多。问题的变量个数比原问题少的多，约束集合也要简单得多。（2）能得到一族解，有利于分析结果）能得到一族解，有利于分析结果（3）能利用经验，提高求解的效率。动态规划方法反映了过）能利用经验，提高求解的效率。
18、动态规划方法反映了过程逐段演变的前后联系，较之非线性规划与实际过程联系得程逐段演变的前后联系，较之非线性规划与实际过程联系得更紧密。更紧密。不足之处不足之处：（1）没有一个统一的标准模型可供应用。）没有一个统一的标准模型可供应用。（2）应用的局限性。要求状态变量满足）应用的局限性。要求状态变量满足“无后效性无后效性”条件，不条件，不少实际问题在取其自然特征作为状态变量往往不能满足这条少实际问题在取其自然特征作为状态变量往往不能满足这条件。件。（3）在数值求解中，存在）在数值求解中，存在“维数障碍维数障碍”。在计算机中，每递推。在计算机中，每递推一段，必须把前一段的最优值函数在相应的状态集合上的
19、全一段，必须把前一段的最优值函数在相应的状态集合上的全部值存入内存中。当维数增大时，所需的内存量成指数倍增部值存入内存中。当维数增大时，所需的内存量成指数倍增长。长。2021/6/723例7.1 多段图问题多段图G=(V,E)是一个有向图，且具有特性: 结点：结点集V被分成k2个不相交的集合Vi，1ik， 其中V1和Vk分别只有一个结点s(源点)和t(汇点)。 每一集合Vi定义图中的一段。 边： 所有的边(u,v)均具有如下性质： 若E，则 该边将是从某段i指向i+1段，即若uVi，则vVi1, 1ik1。 每条边(u,v)均附有成本c(u,v)。 s到t的路径：从第1段开始，至第2段、第3段
20、、最后 在第k段终止。路径的成本是这条路径上边的成本 和。 多段图问题：求由s到t的最小成本路径。2021/6/7247.2 多段图问题1. 问题的描述 在多段图中求从s到t的一条最小成本的路径，可以看 作是在k-2个段作出某种决策的结果。 第i次决策决定Vi+1中的哪个结点在这条路径上，这里 1ik-2； 最优性原理对多段图问题成立，因此用动态规划方法有可能找到s到t的最小成本路径。本节首先根据上节介绍的向前处理法求s到t的最小成本路径，继而给出2021/6/72512345678910111297324227111181456356425V1V2V3V4V55段图2021/6/7262.
21、向前处理策略求解 设 P(i,j)是一条从Vi中的结点j到汇点t的最小成本路径， COST(i,j)是这条路径的成本。 1) 向前递推式 2) 递推过程 第k-1段 c(j,t) E COST(k-1,j) = 2021/6/727l1l2.lpi+1tjViVi+12021/6/72812345678910111297324227111181456356425V1V2V3V4V55段图2021/6/729各递推结果第4段 COST(4,9) = c(9,12) = 4 COST(4,10) = c(10,12) = 2 COST(4,11) = c(11,12) = 5第3段 COST(3,
22、6) = min6+COST(4,9),5+COST(4,10) = 7 COST(3,7) = min4+COST(4,9),3+COST(4,10) = 5 COST(3,8) = min5+COST(4,10),6+COST(4,11) = 7第2段 COST(2,2) = min4+COST(3,6) , 2+COST(3,7), 1+COST(3,8) = 7 COST(2,3) = min2+COST(3,6) , 7+COST(3,7 ) = 9 COST(2,4) = min1 1+COST(3,8)= 18 COST(2,5) = min11+COST(3,7), 8+COS
23、T(3,8) =15第1段 COST(1,1) = min9+COST(2,2),7+COST(2,3), 3+COST(2,4),2+COST(2,5) = 16S到t的最小成本路径的成本 16V2V3V4V512123456789101197324227111181456356425V15段图2021/6/730 最小路径的求取 记 D(i,j)每一COST(i,j)的决策 即，使c(j,l)+COST(i+1,l)取得最小值的l值。 例：D(3,6) = 10, D(3,7)= 10 D(3,8) = 10 D(2,2) = 7, D(2,3) = 6,D(2,4) = 8,D(2,5)
24、 = 8 D(1,1) = 2 根据D(1,1)的决策值向后递推求取最小成本路径： v2=D(1,1)=2 v3 = D(2,D(1,1)= D(2,2) = 7 v4 = D(3,D(2,D(1,1) = D(3,7) = 10 故由s到t的最小成本路径是：1271012 2021/6/7313) 算法描述 结点的编号规则 源点s编号为1,然后依次对V2、V3Vk-1中的结点编号，汇点t编号为n。 目的：使对COST和D的计算仅按n-1,n-2,1的次序计算即可，无需考虑标示结点所在段的第一个下标。 算法描述2021/6/732算法7.1 多段图的向前处理算法1. procedure FGR
25、APH(E,k,n,P)2. /输入是按段的顺序给结点编号的，有n个结点的k段图。E是边3. 集，c(i,j)是边的成本。P(1:k)带出最小成本路径/4. real COST(n); integer D(n-1),P(k),r,j,k,n5. COST(n)06. for jn-1 to 1 by -1 do /计算COST(j)/7. 设r是具有性质：E且使c(j,r)+COST(r)取最小值的结点8. COST(j)c(j,r) + COST(r)9. D(j) r /记录决策值/10. repeat11. P(1)1; P(k)n12. for j2 to k-1 do /找路径上的第
26、j个结点/13. P(j) D(P(j-1) /回溯求出该路径/14. repeat15. end FGRAPH2021/6/7337.3矩阵连乘2021/6/734矩阵连乘问题给定n个矩阵 ， 其中 与 是可乘的， 。考察这n个矩阵的连乘积 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积矩阵连乘问题是确定计算矩阵连乘积的计算次序，使得按照这一次序计算矩阵连乘积，需要的“数乘”次数最少。2021/6/735（1
27、）单个矩阵是完全加括号的；（2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 16000, 10500, 36000, 87500, 34500u完全加括号的矩阵连乘积可递归地定义为：u设有四个矩阵 ，它们的维数分别是：u总共有五种完全加括号的方式完全加括号的矩阵连乘积2021/6/736假设有矩阵A和B,A是m*n矩阵，B是n*p矩阵，则A和B是可乘的，矩阵乘积D=AB是m*p矩阵，它的元素矩阵相乘的数乘次数为：n*m*p通常以矩阵乘法种需要执行的数乘次数作为两矩阵相乘的计算量。2021/6/737矩阵连乘问题-穷举搜索法问题描述：给定n个矩阵
28、A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。 算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序方案数目为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下： 也就是说，P(n)是随n的增长成指数增长的。2021/6/738 例例例例7 74 4 4个个矩矩阵阵连连乘乘积积ABCD，设设它它们们的的维维
29、数数分分别别为为A:50 10，B:10 40, C:40 30, D:30 5。2021/6/7397.3.2动态规划法 -分析最优解的结构下面我们考虑用求解。预处理：将矩阵连乘积AiAi+1.Aj简记为Ai:j，这里ij。考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为（AiAi+1. Ak）（Ak+1 Ak+2. Aj ）。计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量。分析最优解的结构特征特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的
30、。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。2021/6/740特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。分析最优解的结构2021/6/7412.建立递归关系设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n。当i=j时，Ai:j=Ai，因此，mi,i=
31、0，i=1,2,n。当ij时，mi,j=mi,k+mk+1,j+pi-1pkpj，这里Ai的维数为pi-1pi。可以递归地定义mi,j为： k的位置只有j-i种可能。2021/6/742使得上式取最小值的k就是Ai,j的最优计算次序中的断开位置，如果将k保存在sij 后，由S构造出相应的最优解，2021/6/743计算最优值对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多许多子问题被重复计算多次次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计
32、算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法2021/6/744算法描述算法描述：2021/6/745算法描述算法描述：void MatrixChain(int *p，int n，int *m，int *s)for (int i = 1; i = n; i+) mii = 0;/先计算出mii = 0for (int r = 2; r = n; r+)/然后从主对角线上一条次对角线开始，依次计算m的n-2条对角线，并且记录使得mij取最小值的k存在 sij 中，另用一个函数对矩阵序列添加括号for (in
33、t i = 1; i = n - r+1; 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 00，p pi i00，0 0 ini0，vi0，1i n。2021/6/756证明：证明：0/1背包问题满足最优性原理。背包问题满足最优性原理。 设设(x1, x2, , xn)是是所所给给0/1背背包包问问题题的的一一个个最最优优解解，则则( x2, , xn)是下面一个子问题的最优解：是下面一个子问题的最优解：如若不然，
34、设如若不然，设(y2, , yn)是上述子问题的一个最优解，则是上述子问题的一个最优解，则 因此，因此， 这说明这说明(x1, y2, , yn)是所给是所给0/1背包问题比背包问题比(x1, x2, , xn)更优的更优的解，从而导致矛盾。解，从而导致矛盾。 2021/6/7572.最优解的递归算法0/1背包的最优解具有最优子结构特性。 ，那么，(x2, , xn) 必然是0/1背包子问题的最优解给定实例KNAP(0,n-1,M),可以通过对物品是否加入背包做出一系列决策进行求解， xi0,1是0/1背包的最优解， xi= 0,表示物品i不放入背包， xi= 1,表示物品i放入背包，假定对这
35、些xi 做出决策的次序是xn-1, , x0,那么在对xn-1做出决策后存在两种情况： xn-1=1 ,将编号为n-1的物品放入背包，接着求解子问题KNAP(0,n-2,M-wn-1)xn-1=0 , 编号为n-1的物品不放入背包，接着求解子问题KNAP(0,n-2,M)2021/6/7582.最优解的递归算法 假设 为当背包载重为X，可供选择的物品为，0，1，2，j时的最优解，那么f(n-1,M),可以表示为, f(n-1,M)=maxf(n-2,M), f(n-2,M- wn-1)+ p1,对任意的j有，如果物品wi被装入背包，则对任意的j，上述分析得到如下递归式2021/6/759例例例
36、例7 7 7 78 8 8 8 设设有有0/1背背包包问问题题n=3，（w0,w1,w2）=（2,3,4），（p0,p1,p2）=（1,2,4）和）和M=6。递归式递归式递归式递归式2021/6/760f(2,M)= f(2,6)代表最优解值，递归计算过程如下,f(2,6)=maxf(1,6),f(1,6-4)+4=5f(1,6)=maxf(0,6),f(0,6-3)+2=3f(1,2)=f(0,2)=1f(0,6)=1, f(0,3)=1, f(0,2)=1f(-1,y)=0,y大于0从上述递归过程可以看出，最优解值f(2,6)的计算被转化为求解f(1,6) f(1,2)两个子问题，而这两个
37、子问题又可以转化为f(0,6) f(0,3) f(0,2)三个子问题一来求解，最后得到最优解值f(2,6)=5如果物品重量和背包载重为实数，那么子问题的最优解值， f(j,X) 是X的连续函数，不能使用上述方法。2021/6/7617.6.30/1背包算法框架2021/6/7622021/6/763图图7-14（a）表表示示f(j,X)的的函函数数图图像像，图图7-14（b）为为函函数数f(j-1,X-wj)+pj的图像的图像将将f(j-1,X)的的图图像像，在在X轴轴上上右右移移w wj j个个单单位位，然然后后，上上移移p pj j 个个单单位位，就就可可以以得得到到f(j-1,X-wj)
38、+pj的的图图像像，函函数数f(j,X)的的函函数数图图像像是是由由f(j-1,X)与与f(j-1,X-wj)+pj的的函函数数曲曲线线按按X相相同时取大值的方式生成的同时取大值的方式生成的。现现用用Sj表表示示函函数数曲曲线线f(j,X)的的全全部部阶阶跃跃点点的的集集合合，Sj=(Xi,Pi)| 函函数数曲曲线线f(j,X)的的全全部部阶阶跃跃点点，-1 j n-1，其其中中S-1=(0,0)。用用S1j表表示示函函数数曲曲线线f(j-1,X-wj)+pj的的全全部部阶阶跃跃点点的的集集合合，S1j=(Xj,Pj)| 函函 数数 曲曲 线线 f(j-1,X-wj)+pj的的 全全 部部 阶
39、阶 跃跃 点点 ，0 jM的阶跃点得到。的阶跃点得到。 假设假设A（X1,P1）与）与B（X2,P2）是两个跃点，如果）是两个跃点，如果X1P2,则称则称A支配支配B2021/6/765对于对于例例例例7 78 8有有S1=(0,0)，S10=(2,1) S0=(0,0),(2,1)，S11=(3,2),(5,3)S1=(0,0),(2,1),(3,2),(5,3)，S12=(4,4),(6,5)，(7,6),(9,7)S2=(0,0),(2,1),(3,2),(4,4),(6,5)2021/6/766【程序程序程序程序7 79 9】0/10/1背包算法的粗略描述背包算法的粗略描述背包算法的粗
40、略描述背包算法的粗略描述void DKP(float *p,float *w,int n, float M, float &P,int *x) S1=(0,0); for (i=0;iP1) xn1=1; else xn1=0;回溯确定回溯确定xn2,xn-3,x0;2021/6/7687.7 流水作业调度 2021/6/7697.7.1问题描述假定处理一个作业需要执行若干项不同类型的任务，每一类任务只能在某一台设备上执行。设一条流水线上有n个作业J=J0,J1,Jn1和m台设备P=P1,P2,Pm。每个作业需依次执行m个任务，其中第j个任务只能在第j台设备上执行，1jm。设第i个作业的第j项
41、任务Tji所需时间为tji，1jm，0i2则不然）。 n个作业1，2，n要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。2021/6/776流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器P1上开始加工，到最后一个作业在机器P2上加工完成所需的时间最少。分析：分析：直观上，一个最优调度应使机器P1没有空闲时间，且机器P2的空闲时间最少。在一般情况下，机器P2上会有机器空闲和作业积压2种情况。设全部作业的集合为N=0，2，n-1。SN是N的作业子集。在一般情况下，机器P1开始加工S中作业时，机器P2还在加工其它作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。2021/6/777 定理定理定理定理7 73 3 流水作业调度问题具有最优子结构的性质。流水作业调度问题具有最优子结构的性质。2021/6/778部分资料从网络收集整理而来，供大家参考，感谢您的关注！
