《算法分析与设计AlgoD&ALectureNotesW7章节》由会员分享，可在线阅读，更多相关《算法分析与设计AlgoD&ALectureNotesW7章节（37页珍藏版）》请在金锄头文库上搜索。
1、Last Section,动态规划,动态规划是解决多阶段决策过程最优化的一种方法。 动态规划模型的分类： 离散确定性 顺序解法与可逆过程 两个弱点： 得出目标函数方程后，尚无统一的处理方法，必须根据具体问题的性质结合相应的数学技巧来求解； 维数障碍。,动态规划,最优化原理: 无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略 构成动态规划模型的条件 正确选择状态变量xk, 使它既能描述过程的状态，又要满足无后效性(如果某段状态给定，则在这段以后过程的发展不受前面各阶段状态的影响) 确定决策变量uk及每段的允许决策集合 写出状态转移方程 列出指标函数Vk,n 关
2、系，并要满足递推性,动态规划应用举例,资源分配问题 生产与存储问题 复合系统工作可靠性问题 排序问题 设备更新问题,复合系统工作可靠性问题,若某种机器的工作系统由N个部件组成，只要有一个部件失灵，整个系统就不能正常工作。 这些部件的正常工作关系为串接关系，为提高系统工作的可靠性，在每一个部件上均装有主要元件的备用件，并且设计了备用元件自动投入装置。 显然，备用元件越多，整个系统正常工作的可靠性越大。但备用元件多了，整个系统的成本、重量、体积均相应加大，工作精度也降低。 因此，最优化问题是在考虑上述限制条件下，应如何选择各部件的备用元件数，使整个系统的工作可靠性最大？,复合系统工作可靠性问题,设
3、部件i(i=1,2,N)上装有zi个备用元件时，它正常工作的概率为pi(zi)。则，整个系统正常工作的可靠性，可用它正常工作的概率衡量，即： 设装一个部件i的备用元件费用为ci，重量为wi，要求总费用不超过c，总重量不超过w，则这个问题的模型为： 目标函数 约束集合,复合系统工作可靠性问题,这是一个整数规划问题，因zi要求为整数；且目标函数是非线性的，非线性整数规划是个较为复杂的问题，但是用动态规划方法解这个问题是比较容易的。 为了构造动态规划模型，根据有两个约束条件，选二维状态变量，采用两个状态变量符号xk, yk来表达，其中 xk由第k个到第N个部件所容许使用的总费用。 yk由第k个到第N
4、个部件所容许具有的总重量。 决策变量uk为部件k上装的备用元件数zk（即uk=zk）。（决策变量是一维的。） 状态转移方程为： xk+1 = xk-ukck yk+1 = yk-ukwk (1kN),复合系统工作可靠性问题,允许决策集合为： uk为非负整数 指标函数为： （1kN） 由此可得整机可靠性的动态规划基本方程为： 边界条件为1，因为 均为零时，装置不工作，故可靠性为1。,复合系统工作可靠性问题,该问题的特点是： 指标函数为连乘积形式，而不是连加形式，但仍满足递推关系； 边界条件为1而不是零。它们是由研究对象的特性所决定的。 在该问题中，如果静态模型的约束条件增加为三个，例如总体积不超
5、过v，则状态变量就要选为三维的（xk,yk,zk）。它说明静态规划问题的约束条件增加时，对应的动态规划的状态变量维数也需要增加，而决策变量维数可以不变。,排序问题,在加工工件所需经过的工序、各种工件在各道工序加工需要的时间为给定的条件下，如何确定加工工件的顺序，使得总的加工时间最短，这也可看作是一个多阶段决策问题。 设有n个工件需要在机床A、B 上加工，每个工件都必须经过先A而后B的两道加工工序。以ai、bi分别表示工件 i (1in)在A、B上的加工时间。问： 应如何在两机床上安排各工件加工的顺序，使在机床A上加工第一个工件开始到在机床B上将最后一个工件加工完为止，所用的加工总时间最少？,排
6、序问题,以在机床A上更换工件的时刻作为时段起止。以X表示在机床A上等待加工的按取定顺序排列的工件集合。以x表示不属于X的在A上最后加工完的工件。以t表示在A上加工完x的时刻算起到在B上加工完x所需的时间。这样，在A上加工完一个工件之后，就有（X，t）与之对应。 选取（X，t）作为描述机床A、B在加工过程中的状态变量，则当X包含有s个工件时，过程尚有s段，其时段数已隐含在状态变量之中。,排序问题,令f（X，t）为由状态（X，t）出发，对未加工的工件采取最优加工顺序后，将X中所有工件加工完所需时间。 f（X，t, i）为由状态（X，t）出发，在A上加工工件i，然后再对以后的加工工件采取最优顺序后，
7、把X中工件全部加工完所需要的时间。 f（X，t, i, j）为由状态（X，t）出发，在A上相继加工i与j后，对以后的加工工件采取最优顺序后，将X中工件全部加工完所需要的时间。 则 f（X，t, i）= ai + f（X / i，t ai + bi） 当t ai时 ai + f（X / i，bi） 当t ai时 记 上式就可合并写成 f（X，t, i）= ai + f X / i，zi (t) 其中X / i表示在集合X中去掉工件i后剩下的工件集合。,排序问题,由定义，可得 f（X，t, i, j）= ai + aj + f X / i, j，zij (t) 其中zij (t)是在机床A上从X出
8、发相继加工工件i、j，并从它将j加工完的时刻算起，至在B上相继加工工件i、j并将工件加工完所需时间。 故（X / i, j，zij (t)）是在A加工i、j后所形成的新状态。即在机床A上加工i、j后由状态（X，t）转移到状态 （X / i, j，zij (t)）。 仿照zi (t)的定义， zi (t)代替t，有,排序问题,将i、j对调，可得 f（X，t, j, i）= ai + aj + fX / i, j，zji (t) 由于f（X，t）为t的单调上升函数，故当zij(t) zji(t)时， f（X，t, i, j） f（X，t, j，i）。 由此，对任意t，当zij(t) zji(t)
9、时， 工件i放在工件j之前加工可以使总的结 果时间短些。,排序问题,由zij(t)和zji(t)的表示可知，若 成立时，就可推得 zij(t) zji(t) 将上式两边同减去bi与bj，得 则有,排序问题,以上条件就是工件i应该排在工件j之前的条件。因此，我们得到下面的最优排序规则： 找出a1,a2, an, b1,b2,bn中的最小数； 若最小者为ai, 则将工件i排在第一位，并从工件集合中去掉这个工件； 若最小者为bi, 则将工件i排在最后一位，并从工件集合中去掉这个工件； 对剩下的工件重复上述手续，直至工件集合为空集时停止。,设备更新问题,在工业和交通运输企业中，经常碰到设备陈旧或损坏需
10、要更新的问题： 一种设备应该用多少年后进行更新为最恰当，即更新的合理年限是多少？ 一辆卡车使用的情况： 一辆新卡车第一年使用时，显然出车时间长，故障少，因而一年的运输收入额高，维修费支出较少。 但使用几年后，必然出车时间较少，维修费用增加。 到一定时候，需要更换；卖掉旧车，购买新车。但旧车愈旧，价值就越低，新旧相抵后更新所花的净费用支出就愈多。 另外，设备的更新不能只看当年的收入和支出情况，而应看若干年总的受益效果来决定。,设备更新问题,令t为卡车已经使用过的年数。 设r(t)为已使用t年的卡车每年出车所得的运输收入额。它随t而减少，因车愈旧收入愈少。 u(t)为已使用t年的卡车每年所需的维修
11、费。它随t而增加，因车愈旧愈要维修。 c(t)为更新一辆使用了t年的旧车，卖掉旧车，买进新卡车所需的净费用。则c(t)随t而上升。 如果某年初把使用了t年的旧车，再继续使用一年，则在这一年内所得回收额为： 如果把使用了t年的车更换后买进一辆新车，则这一年所得的回收额为：,设备更新问题,但是，设备的更新不能只比较一年gK(t)和g(P)(t)的大小，而要看若干年总的收益效果，从N年内的总回收额中来决定那年更换旧车为好。为此，引入指标函数f(t)。 f(t)：为一个以使用t 年的旧车，从某年开始在以后继续用到规定的N0年止这几年内的总回收额。如果N=5， 就表示到N0年止还有5年，f(t)就是在这
12、5年内的总回收额。因此，我们有 f(t+1)：为该车已使用了t + 1 年后，继续用到N0年止者几年内的总回收额。 f(1)：为已使用了1年的车，继续用到N0年这段期间中的总回收额。 f(0)：为一辆新车，用到N0年这段期间中的总回收额。 于是，指标函数f(t)的基本关系式为： 其中，P表示更新，K表示保留使用。,设备更新问题,r(t)、u(t)、c(t)一般为非线性函数，解析法求f(t)最优解很难；随车辆数目增多问题愈发复杂。 用动态规划方法，把问题变为多阶段决策过程。先定义指标函数fn(t)为已经使用了t年的卡车，在第n年又继续使用，直到N0年止这几年内所得的总回收额。 在第n年更新的车辆
13、，满足递推关系为： 若第n年不更新，继续使用，则有递推关系： 比较 和 的大小可得第n年的决策和指标函数： 当nN0 + 1时，fn(t) = 0,设备更新问题,以上递推关系说明了第n年使用的车辆， 在以后若干年的总回收额的大小，它决定于第n + 1 年的指标函数。 从而，为求出fn(t)， 必须从继续使用的最后一年（N0年）向回计算，即为逆序算法。 f1(t)即为使用了t年的旧车，按最优策略逐年使用或更新，从第1年到N0年的总回收额。,可基于动态规划思想求解的 问题与算法,计算二项式系数,二项式系数， 记作C（n, k），等于 一个n元素集合的k元素组合（子集）的数量（0kn）。 “二项式系
14、数”这个名字来源于这些数字出现在二项式公式之中： 且有如下特性：当nk0时 以及,计算二项式系数,可以用动态规划技术来对它求解。把二项式系数记录在一张n+1行k+1列的表中，行从0到n 计数，列从0到k计数。 为了计算C（n,k），逐行填充表格，从行0开始，到行n结束。 每一行（0in）从左向右填充，第一个数字填1，因为C（n,0）=1。 行0直到行k也是以1结束在表的主对角线上：当0ik时，C(i,i)=1。 用上述公式计算其他单元格的值，即把前一行前一列那个单元格的值和前一行当前列那个单元格的值相加。（帕斯卡三角形）,计算二项式系数,算法Binomial(n,k) /用动态规划算法计算C(
15、n,k) /输入：一对非负整数nk0 /输出：C(n,k)的值 for i 0 to n do for j0 to min(i,k) do if j= 0 or j=i Ci,j 1 else Ci,j Ci-1,j-1+Ci-1,j return Cn,k,计算二项式系数,该算法的基本操作是加法，所以把A（n,k）记作该算法在计算C(n,k)时所作的加法总次数。 因为表格的前k+1行构成了一个三角形，而余下的n-k行构成了一个矩形，将求和表达式A（n,k）分成两个部分,有：,最长公共子序列,一个给定序列的子序列是在该序列中删去若干元素后得到的序列。 存在一个严格递增下标序列。 例如，序列Z=
16、 B，C，D，B是序列X= A，B，C，B，D，A，B的子序列， 相应的递增下标序列为2，3，5，7。 给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 例如， 若X= A，B，C，B，D，A，B，Y= B，D，C，A，B，A则序列B，C，A是X和Y的一个公共子序列。 最长公共子序列问题：给定两个序列X= x1, x2, , xm和Y= y1, y2, , yn， 找出X和Y的一个最长公共子序列。,最长公共子序列,蛮力搜索的方法： 令A= a1a2an和B= b1b2bm。例举A所有的2n个子序列， 对于每一个子序列在(m) 时间内来确定它是否也是B的子序列。此方法的时间复杂性是 。 动态规划： 寻找一求最长公共子序列长度的递推公式： 令Li, j表示a1a2ai 和b
