第1页:第六章 动态规划章节封面
第六章动态规划
第2页:6.1 一般方法与多阶段决策
6.1一般方法
- 最优化问题
- 动态规划--多阶段决策问题的通用方法
- 有这样一类问题,它们的活动过程可分为若干个阶段,在任一阶段i后的行为都依赖于i阶段的过程状态,而与i阶段之前的过程如何达到这种状态的方式无关,这样的过程就构成了一个多阶段决策过程。
- 每一阶段都有多种可供选择的决策,必须从中选取一种。一旦各个阶段的决策选定之后,就构成了一个决策序列。决策序列不同会导致问题结果也不同。
- 目标是选取一个会获得问题最优解的决策序列,即最优决策序列。
第3页:最优性原理
- 20世纪50年代,美国数学家Richard Bellman提出,利用最优性原理及得到的递推关系式解决该类问题。
- 最优性原理(Principle of Optimality)过程的最优决策序列具有如下性质:无论过程的初始状态和初始决策是什么,其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。
- 如果对于所求解的问题最优性原理成立,则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获取各阶段间的递推关系式。6.1一般方法
第4页:动态规划的适用条件
动态规划适用条件
- 最优性原理(最优子结构性质)
- 无后向性(无后效性)
- 子问题的重叠性6.1一般方法实质:以空间换时间穷举法:计算量分治法:子问题独立贪心法:决策不可撤回
第5页:动态规划的一般步骤
6.1一般方法
- 动态规划方法的一般步骤
- 找出最优解的性质,刻画特征;
- 递归地定义最优值---递归关系式;
- 以自底向上的方式计算出最优值;
- 根据计算最优值时得到的信息,构造最优决策序列。
第6页:多段图问题的描述
- 图中的结点被划分成k≥2个不相交的集合Vi,1≤i≤k,其中V1和Vk分别只有一个结点s (源点)和t(汇点)。
- 图中所有的边<u, v>均具有如下性质:若u∈Vi,则v∈Vi+1,1≤i≤k,且每条边<u, v>均附有成本c(u, v).
- 从s到t的一条路径成本是这条路径上边的成本和。
- 多段图问题是求由s到t的最小成本路径。例:多段图问题(multistage graph problem)多段图G=(V, E)是一个有向图,它具有如下特性:6.1一般方法
第7页:多段图问题实例
例:多段图问题(multistage graph problem)2345876111091s12t97324227111118654356524V1V2V3V4V5
第8页:最短路的最优性原理
- 假设s,v2,v3,…,vk-1,t是一条由s到t的最短路径
- 再假设从源点s开始,已作出了到结点v2的决策,因此v2就是初始决策所产生的状态
- 如果把v2看成是原问题的一个子问题的初始状态,解决这个子问题就是找出一条由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路径短,这与假设矛盾,因此最优性原理成立.最优性原理对多段图成立6.1一般方法证明满足最优性原理:①设最优决策序列的形式②确定初始状态和初始决策③初始决策所产生的状态④其余决策相对于③
第9页:0/1背包问题的表示
6.1一般方法
- 例:0/1背包问题背包问题中的xj限定只能取0或1值,
- 用KNAP(l,j, X)来表示这个问题极大化约束条件xi= 0或1, 1≤i≤j
- 若对于有n个物品,容量为M的背包,则0/1背包问题就可表示为KNAP(1,n,M)效益值背包重量
第10页:0/1背包的最优性原理
最优性原理对于0/1背包问题成立
- 设y1,y2,…,yn分别为x1,x2,…,xn的0/1值的最优序列。
- 若y1=0,则y2,y3,…,yn必须相对于KNAP(2,n,M)问题构成一个最优序列。如若不然,则y1,y2,…,yn就不是KNAP(1,n,M)的最优序列。
- 若y1=1,则y2,y3,…,yn必须是KNAP(2,n,M−w1)的最优序列。如若不然,则必有另一个0/1序列z2,z3,…,zn使得Σwizi≤M−w1(2≤i≤n)且Σpizi>Σpiyi(2≤i≤n),序列y1,z2,z3,…,zn是一个对问题KNAP(1,n,M)具有更大效益值的序列,这与假设相矛盾。
- 所以0/1背包问题的最优性原理成立。
第11页:最优决策序列的表示
最优决策序列的表示
- 设S0是问题的初始状态,假定要作n次决策xi, 1≤i≤n
- X1={r1, 1, r1, 2, … , r1, p1}是x1的可能决策值的集合,而S1, j1是在选取决策值r1, j1以后所产生的状态, 1≤j1≤p11≤j1≤p1
- 又设Γ1, j1是相应于状态S1, j1的最优决策序列;则相应于S0的最优决策序列就是{r1, j1Γ1, j1| 1≤j1≤p1}中最优的序列,记为OPT {r1, j1Γ1, j1}= r1Γ16.1一般方法
第12页:多阶段决策的状态递推
- 如果已作了k−1次决策, 1≤k−1<n,设x1,…xk-1的最优决策值是r1,..,rk-1,它们所产生的状态为S1,…Sk-1
- 又设Xk={rk, 1, rk, 2, …, rk, pk}是xk的可能值的集合,Sk, jk是选取rk, jk决策之后所产生的状态, 1≤jk≤pk
- Γk, jk是相应于Sk, jk的最优决策序列
- 因此相应于Sk−1的最优决策序列是:1≤jk≤pkOPT {rk, jkΓk, jk}= rkΓk
- 于是相应于S0的最优决策序列为:r1,…,rk−1, rk,Γk
第13页:向前处理法与向后处理法
- 向前处理法(forward approach)最优决策序列的表示法启发我们从最后阶段开始,以逐步向前递推的方式,列出求解前一阶段决策值的递推关系式,即根据xi+1, … xn的那些最优决策序列来列出求取xi决策值的关系式。
- 向后处理法(backward approach)从初始阶段开始,以逐步向后递推的方式,列出求解后一阶段决策值的递推关系式,即根据x1, … xi-1的那些最优决策序列来列出求取xi决策值的关系式。多段图:min{s-v2,j2, v2,j2…t}0/1背包问题:gj(x):KNAP(j+1,n,x)gj(X) = max { gj+1(X) , gj+1(X−wj)+pj}
第14页:动态规划的实质
6.1一般方法
- 无论向前处理法还是向后处理法,都将所有子问题的最优解保存下来,便于逐步递推得到原问题的最优解并避免重复计算。
- 在递推求解过程中,对包含次优子序列的决策序列不予考虑,因此节省了计算量。
第15页:多段图的向前处理法
6.2多段图
- 向前处理法:从最后阶段开始,逐步向前递推,根据xi+1, … xn的那些最优决策子序列来求取xi决策值的关系式。
- P(i, j)是一条从Vi中的节点j到汇点t的最小成本路径,COST(i, j)表示这条路径的成本。V2Vk-1V3tsVi
第16页:向前递推的求解次序
6.2多段图k段图中,对于k−1段,若<j,t>∈E,有COST(k−1, j)= c(j, t),所以可以通过公式6.5,对所有j∈Vk-2,计算COST(k−2, j),再对所有的j∈Vk−3,计算COST(k−3, j),依次向前求解,最后计算出COST(1, s).1s9732V123454227111118V2876654356V31110912t524V4V5
第17页:向前处理计算过程一
- 多段图向前处理算法的计算过程COST(4, 9)=c(9,12)=4COST(4,10)=c(10,12)=2COST(4,11)=c(11,12)=51110912t524V4V5876654356V3COST(3,6)=min{c(6,9)+COST(4,9),c(6,10)+COST(4,10)}=min{6+4,5+2}=7COST(3,7)=min{c(7,9)+COST(4,9),c(7,10)+COST(4,10)}=min{4+4,3+2}=5COST(3,8)=min{c(8,10)+COST(4,10),c(8,11)+COST(4,11)}=min{5+2,6+5}=7COST(i, j)=min{ c(j,l)+ COST(i+1,l)}l∈Vi+1, c(j,l)表示该边的成本
第18页:向前处理计算过程二
1s9732V123454227111118V21110912t524V4V5876654356V3COST(2,2)=min{c(2,6)+COST(3,6),c(2,7)+COST(3,7),c(2,8)+COST(3,8)}=min{4+7,2+5, 1+7}=7COST(3,6)=7COST(3,7)=5COST(3,8)=7COST(2,3)=min{2+7,7+5}=9COST(2,4)=min{11+7}=18COST(2,5)=min{11+5,8+7}=15COST(1,1)=min{c(1,2)+COST(2,2),c(1,3)+COST(2,3),c(1,4)+COST(2,4),c(1,5)+COST(2,5)}=min{9+7,7+9,3+18,2+15}=16
第19页:最小成本路径的记录
在计算每个COST(i, j)的同时,记下每个状态(结点j)所做出的决策(即l的取值),令D(i, j)=l,则容易求出这条最小成本的路径COST(2,2)=min{c(2,6)+COST(3,6),c(2,7)+COST(3,7),c(2,8)+COST(3,8)} =7COST(1,1)=min{c(1,2)+COST(2,2), c(1,3)+COST(2,3),c(1,4)+COST(2,4), c(1,5)+COST(2,5)}=16D(1, 1)=2D(2, 2)=7D(2, 3)=6D(2, 4)=8D(2, 5)=8D(3, 6)=10D(3, 7)=10D(3, 8)=10COST(3,6)=min{c(6,9)+COST(4,9) ,c(6,10)+COST(4,10)}=71→2→7→10→12最小成本的路径为:
第20页:FGRAPH过程
多段图的向前处理算法 procedure FGRAPH(E,k,n,P) real COST(n); integer D(n−1), P(k), r, j, k, n;COST(n)←0; for j=n−1 to 1by−1 do寻找结点r,满足<j, r>∈E且使c(j,r)+COST(r)值最小COST(j)←c(j,r)+COST(r);D(j)←r ; repeatP(1)←1; P(k)←n; for j←2 to k−1 do P(j)←D(P(j−1)); end FGRAPH为了算法描述的简单,对结点进行编号,从V1开始s编为1号,然后V2中的结点依次编为2,3,4,5号,按此规则编下去,最后V5的结点t编为12号,有了编号可以将COST, D中表示段数的第一个下标省略通过计算找到一条最小成本的路径数组p用来保存最小成本路径上结点编程实现算法时要先将多段图用邻接表表示
第21页:邻接表存储结构
- 1s9732234542271111181110912t524876654356
- 邻接表:邻接表是图的一种链式存储结构,对图中的每个顶点建立一个单链表,链表中的结点有3个域,分别存储顶点,边的成本和下一个结点的指针.1234567891011∧12∧118∧412∧212∧512927334∧254627∧1826∧77117∧8869∧51049∧310510∧611
第22页:FGRAPH执行过程
- k=5; n=12;COST(12)=0;for j=11downto1 do{ COST(j)=min{c(j,r)+COST(r)};D(j)=r ; }P(1)=1; P(k)=12;for j=2 to 4 do P(j)=D(P(j-1));1211109876543210111098765432154321121COSTDPCOST(11)=5COST(10)=2COST(9)=4512241212COST(8)=7COST(7)=5COST(6)=7D(8)=10D(7)=10D(6)=10710571010COST(5)=15COST(4)=18COST(3)=9COST(2)=7D(11)=12D(10)=12D(9)=12D(5)=8D(4)=8D(3)=6D(2)=71581897867D(1)=2COST(1)=161622710
- 算法的执行过程
第23页:多段图的向后处理法
- 多段图向后处理的算法对于k段图,当i=2时,有BCOST(2, j)= c(1, j),所以可以通过上述公式,对所有j∈V3,计算BCOST(3, j),依次向后求解,最后计算出BCOST(k, t);同样的,在计算每个BCOST(i, j)的同时,记下每个状态所做出的决策(即l的取值),令D(i, j)=l由于我们已经按规则对结点进行了编号,所以这里可以省略BCOST和D中的第一个下标设BP(i, j)是一条从源点s到Vi中的结点j的最小成本路径,BCOST(i, j)表示这条路径的成本,根据向后处理方法有公式6.6 :BCOST(i, j)= min{BCOST(i−1,l)+ c(l, j )}其中:l∈Vi−1,边<l, j >∈E, c(l, j)表示该边的成本
第24页:向后处理计算过程
- 多段图向后处理算法的计算过程1s97322345BCOST(j)=min{BCOST(l)+ c(l,j)}4227111118876BCOST(2)=c(1,2)=9BCOST(3)=c(1,3)=7BCOST(4)=c(1,4)=3BCOST(5)=c(1,5)=2BCOST(6)=min{BCOST(2)+c(2,6),BCOST(3)+c(3,6)}= min{9+4,7+2}=9BCOST(7)=11BCOST(8)=10D(2)=1D(3)=1D(4)=1D(5)=1D(6)=3D(7)=2D(8)=2D(9)=6D(10)=6D(11)=8BCOST(9)=15BCOST(10)=14BCOST(11)=16BCOST(12)=16D(12)=101→3→6→10→12最小成本的路径为:
第25页:BGRAPH过程
procedure BGRAPH(E,k,n,P) real BCOST(n); int D(n−1), P(k), r, j, k, n;BCOST(1)←0; for j←2 to n do寻找结点r,满足<r, j>∈E且使BCOST(r)+c(r, j)值最小BCOST(j)←BCOST(r)+c(r, j);D(j)←r ; repeatP(1)←1; P(k)←n; for j←k−1downto2 do P(j)←D(P(j+1)) ; end BGRAPH 多段图的向后处理算法
第26页:逆邻接表存储结构
- 1s9732234542271111181110912t524876654356
- 对于向后处理算法多段图用逆邻接表来存储∧123456789101112∧91∧71∧31∧212273∧11542∧2312114∧11549210∧51166∧475637∧58∧68
第27页:资源分配问题
应用—资源分配(n个资源分配给r个项目)
- N(i,j):将j个资源分配给项目i时获得的净利,1≤j≤n
- 用r+1段图表示该问题;
- 第1段和第r+1段分别只包含一个结点,第2段至第r段分别包含n+1个结点;
- V(i,j):第i段的结点,2≤i≤r;表示将j个资源分配给前i−1个项目;
- <V(i,j),V(i+1,l)>:图中的边,当j≤l,1≤i<r时,赋予权值N(i,l−j);
- <V(r,j),V(r+1,n)>:成本值为max{N(r,p)}0≤p≤n−j项目i分配l−j个资源时的净利r段到r+1段的边的权值
第28页:二分检索树的定义
6.4最优二分检索树
- 二分检索树: T是一个二叉树,它或者为空,或者其每个结点含有一个可比较大小的数据元素,并且:①T的左子树的所有元素比根结点T中的元素小②T的右子树的所有元素比根结点T中的元素大③T的左、右子树也是二分检索树注意:二分检索树中的所有结点的数据元素是互异的whileifrepeatforlooprepeatifloopforwhile
第29页:检索二分检索树的算法
检索二分检索树的算法: procedure SEARCH(T, X, i)i←T; while i≠0 do case:X<IDENT(i): i←LCHILD(i);:X=IDENT(i): return;:X>IDENT(i): i←RCHILD(i); end case repeat end SEARCH二分检索树的每个结点有3个信息段, LCHILD, RCHILD,IDENT;若X不在T中,则i=06.4最优二分检索树
第30页:不同检索树的比较次数
例:标识符集(a1,a2,a3,a4,a5)=(for,if,loop,repeat,while)对于以下2种不同的二分检索树在最坏情况下检索一个标识符,图a所示的树需要进行4次比较,而图b所示的树只需要3次比较假设检索每个标识符具有相同的概率1/5,并设都能成功检索,则在平均情况下,图a的树需要12/5次比较,图b的树需要11/5次比较ifforwhilelooprepeat图aa1a2a3a4a5图bifforwhilelooprepeata1a2a3a4a5
第31页:成功与不成功检索的概率
- 一般情况下,要检索的那些标识符具有不同的概率,而且存在不成功检索的情况。设给定的标识符集是(a1, a2, …an),P(i)是对ai成功检索的概率,Q(i)是X不成功检索的概率,则有∑P(i) +∑Q(i) =11≤i≤n0≤i≤na2a1a5a3a4E0E1E2E3E4E5一次成功检索在一个内结点(l级)处终止,算法中的循环要执行l次,所以内结点ai的预期成本为P(i)×level(ai)一次不成功检索在一个外结点处(l级)终止,算法中循环要执行l-1次,所以外结点Ei的预期成本为Q(i)×(level(Ei)−1)
- 二分检索树的预期成本为:∑P(i)×level(ai)+∑Q(i)×(level(Ei)−1)1≤i≤n0≤i≤n6.4最优二分检索树
第32页:最优二分检索树的定义
- 定义标识符集(a1, a2, …an)的最优二分检索树是一棵使∑P(i)×level(ai)+∑Q(i)×(level(Ei)−1)取最小值的树。
- 例:标识符集(a1, a2, a3)=(do, if, stop)有5种可能的二分检索树图adoa1ifa2stopa3E3E0E1E21.设内外结点具有相同的概率P(i)=Q(i)=1/72.设内外结点的概率不同P(i)=(0.5, 0.1, 0.05), Q(i)=(0.15,0.1,0.05,0.05)cost(a)=P(1)*3+P(2)*2+P(3)*1+Q(0)*3+Q(1)*3+Q(2)*2+Q(3)*1cost(a1)=3*1/7+2*1/7+1/7+3*1/7+3*1/7+2*1/7+1/7 =15/7cost(a2)=3*0.5+2*0.1+0.05+3*0.15+3*0.1+2*0.05+0.05 =2.656.4最优二分检索树
第33页:五种候选树及其成本
doa1ifa2stopa3E3E0E1E2图cdoa1ifa2stopa3E3E0E1E2图bcost(b1)=13/7cost(b2)=1.9cost(c1)=15/7cost(c2)=1.5cost(d1)=15/7cost(d2)=2.15cost(e1)=15/7cost(e2)=1.6图ddoa1ifa2stopa3E3E0E1E2doa1ifa2stopa3E3E0E1E2图ecost(a1)=15/7cost(a2)=2.65对于第1种情况内、外结点概率相同,图b所示的树最优对于第2种情况内、外结点概率不同,图c所示的树最优P(i)=(0.5, 0.1, 0.05), Q(i)=(0.15,0.1,0.05,0.05)
第34页:最优二分检索树的递推
- 将动态规划应用于最优二分检索树对于ai, 1≤i≤n,决策出哪一个作为T的根结点,如果选择ak作为根结点,那么内结点a1,a2,…ak-1和外结点E0,E1,…Ek-1都将位于这个根的左子树上,而内结点ak+1,…an和外结点Ek,…En将位于这个根的右子树上akLR1≤i<k定义左子树的成本:COST(L)=∑P(i)*level(ai)+∑Q(i)*(level(Ei)−1)0≤i<kk<i≤n定义右子树的成本:COST(R)=∑P(i)*level(ai)+∑Q(i)*(level(Ei)−1)k≤i≤n注意:上式中级数的测定是把各子树的根作为第一级,所以在计算整棵树的成本时还要加上一部分成本
第35页:树的预期成本
6.4最优二分检索树
- 树T的预期成本:P(k)+COST(L)+COST(R)+W(0,k−1)+W(k,n)用C(i,j)表示包含ai+1,… aj和Ei,…Ej的最优二分检索树的成本,
- 若树T是最优的:P(k)+C(0, k−1)+C(k, n)+W(0, k−1)+W(k, n)l=i+1用W(i,j)表示W(i,j)=Q(i)+∑(Q(l)+P(l))jC(0,n)=min{C(0, k−1)+C(k, n)+P(k)+W(0, k−1)+W(k, n)}1≤k≤nC(i,j)=min{C(i, k−1)+C(k, j)+P(k)+W(i, k−1)+W(k, j)}i<k≤j=min{C(i, k−1)+C(k, j)}+W(i, j)i<k≤j将上式一般化,对于任何c(i,j)有下式:P(k)+Q(i)+Q(i+1)+P(i+1)+…+Q(k−1)+P(k−1)+Q(k)+Q(k+1)+P(k+1)+…+Q(j)+P(j)=W(i,j)
第36页:C(i,j)的递推关系式
6.4最优二分检索树
- C(i,j)=min{C(i, k−1)+C(k, j)}+W(i, j)
- 按上式逐步计算,最后可求出C(0,n).
- 首先计算j−i=1时的C(i , j)(注意: C(i, i)=0, W(i, i)=Q(i),0≤i≤n),然后依次计算j−i=2时的C(i , j),j−i=3时的C(i , j)…… , j−i=n时的C(i , j).
- 在计算期间记下每棵树Tij的根R(i,j),那么最优二分检索树就由这些R(i,j)构造出来。( R(i,j)是使C(i,j)=min{C(i, k−1)+C(k, j)}+W(i, j)取最小值的k值)i<k≤ji<k≤j
第37页:最优二分检索树实例
例: n=4,(a1,a2,a3,a4)=(do, if, read, while)P(1:4)=(3,3,1,1);
Q(0:4)=(2,3,1,1,1)(为计算方便P,Q的值都乘了16)C(i,j)=min{C(i, k-1)+C(k, j)}+W(i, j)i<k≤jW(i,j)=Q(i)+∑Q(l)+P(l)l=i+1jW(0,1)=Q(0)+Q(1)+P(1)=2+3+3=8R(0,1)=k=1k=10<k≤1C(0,1)=min{C(0,0)+C(1,1)}+W(0,1)=0+8=8W(1,2)=Q(1)+Q(2)+P(2)=3+1+3=7k=21<k≤2C(1,2)=min{C(1,1)+C(2,2)}+W(1,2)=0+7=7R(1,2)=k=2W(2,3)=3C(2,3)=3R(2,3)=k=3W(3,4)=3C(3,4)=3R(3,4)=k=4j–i=1时, 0≤i<4
第38页:j-i=2时的计算
j–i=2时, 0≤i<3W(0,2)=W(0,1)+Q(2)+P(2)=8+1+3=12P(1:4)=(3,3,1,1);
Q(0:4)=(2,3,1,1,1)=min{0+7,8+0}+12=190<k≤2C(0,2)=min {C(0,0)+C(1,2), C(0,1)+C(2,2)}+W(0,2)k=1k=2R(0,2)=k=1W(1,3)=W(1,2)+Q(3)+P(3)=7+1+1=91<k≤3C(1,3)=min {C(1,1)+C(2,3), C(1,2)+C(3,3)}+W(1,3)k=2k=3=min{0+3,7+0}+9=11R(1,3)=k=2W(2,4)=5 C(2,4)=8 R(2,4)=k=3C(i,j)=min{C(i, k-1)+C(k, j)}+W(i, j)i<k≤jW(i,j)=Q(i)+∑Q(l)+P(l)l=i+1j
第39页:j-i=3时的计算
j–i=3时, 0≤i<2W(0,3)=W(0,2)+Q(3)+P(3)=12+1+1=14P(1:4)=(3,3,1,1);
Q(0:4)=(2,3,1,1,1)=min{0+12,8+3,19+0}+14=11+14=25R(0,3)=k=2W(1,4)=11 C(1,4)=19 R(1,4)=k=20<k≤3C(0,3)=min {C(0,0)+C(1,3), C(0,1)+C(2,3),C(0,2)+C(3,3)}+W(0,3)k=1k=2k=3j–i=4时, 0≤i<1W(0,4)=W(0,3)+Q(4)+P(4)=16=min{0+19,8+8,19+3,25+0}+16=16+16=32R(0,4)=k=2C(0,4)=min{C(0,0)+C(1,4),C(0,1)+C(2,4),C(0,2)+C(3,4),C(0,3)+C(4,4)}+W(0,4)k=1k=2k=3k=40<k≤4C(i,j)=min{C(i, k-1)+C(k, j)}+W(i, j)i<k≤jW(i,j)=Q(i)+∑Q(l)+P(l)l=i+1j
第40页:最优二分检索树构造结果
432101,0,01,0,01,0,03,0,02,0,003,3,43,3,37,7,28,8,115,8,39,12,212,19,1211,19,214,25,2316,32,24ifa2T01doa1E0E1E2E3E4T24reada3T34whilea416,32,28,8,15,8,33,3,4
第41页:Knuth的优化结论
6.4最优二分检索树
- 时间复杂性分析j−i=1时,计算了n个C(i,j)j−i=2时,计算了n−1个C(i,j)……j−i=m时,计算了n−m+1个C(i,j)在m个数值中取最小值……
- D.E.Knuth得出这样的结论:使C(i,j)取最小值的k可以在区间R(i,j−1)≤k≤R(i+1,j)中求出,而不必在i≤k≤j这个相对较大的范围内求出.
第42页:OBST过程
procedure OBST(P,Q,n) real P(1:n), Q(0:n), C(0:n, 0:n), W(0:n, 0:n), integer R(0:n, 0:n), for i←0 to n−1 do( W(i,i), R(i,i), C(i,i))←(Q(i),0,0)(W(i,i+1),R(i,i+1) ,C(i,i+1))←(Q(i)+Q(i+1)+P(i+1),i+1,Q(i)+Q(i+1)+P(i+1)). repeat(W(n,n), R(n,n) , C(n,n) )←(Q(n),0,0) for m←2 to n do for i←0 to n−m doj←i+mW(i,j)←W(i,j−1)+P(j)+Q(j)k←区间[R(i,j−1),R(i+1,j)]中使{C(i,l−1)+C(l,j)}取最小值的l值C(i,j)←C(i,k−1)+C(k,j)+W(i,j)R(i,j)←k. repeat repeat end OBST初始化,j−i=0, j−i=1相邻m个元素的最优二分检索树的成本树根为ak第43页:0/1背包问题的形式描述
6.5 0/1背包问题
- 0/1背包问题的形式描述KNAP(1, n, M)极大化Σpixixi=0或1, pi>0约束条件Σwixi≤M wi>0, 1≤i≤n1≤i≤n1≤i≤n0/1背包问题要求物品或者整件装入背包中,或者根本不装入(即不能装入物品的一部分),所以xi限定只能取0或1值,可以用KNAP(1, n, M)表示这个问题
第44页:0/1背包的递推关系式
如果设fi(X)是KNAP(1,i,X)最优解的值,那么fn(M)可表示为:fn(M) = max { fn−1(M) , fn−1(M−wn)+pn}对于任意的fi(X), i>0有以下公式:fi(X) = max { fi−1(X) , fi−1(X−wi)+pi}为了求解出fn(M),必须从f0(X)开始,根据递推关系式进行计算递推求解过程如下:X<0时, f0(X) =−∞;
X≥0时, f0(X)= 0X<0时, f1(X) =−∞0≤X<2时, f1(X)=max{f0(X) , f0(X−2)+1}=max{0,−∞+1}=0X≥2时, f1(X)=max{f0(X) , f0(X−2)+1} =max{0, 0+1}=1例: n=3, (w1,w2,w3)=(2,3,4) , (p1,p2,p3)=(1,2,5) , M=6
第45页:fi(X)的分段计算
公式:fi(X) = max { fi-1(X) , fi-1(X-wi)+pi}X<0时, f2(X) =−∞0≤X<2时, f2(X)=max{f1(X) , f1(X−3)+2}=max{0 ,−∞+2}=02≤X<3时, f2(X)=max{f1(X) , f1(X−3)+2}=max{1 ,−∞+2}=13≤X<5时, f2(X)=max{f1(X) , f1(X−3)+2}=max{1 , 0+2 }=2X≥5时, f2(X)=max{f1(X) , f1(X−3)+2}=max{1 , 1+2 }=3X<0时, f3(X) =-∞0≤X<2时, f3(X)=max{f2(X), f2(X−4)+5}=max{0,−∞+5}= 02≤X<3时, f3(X)=max{f2(X), f2(X−4)+5}=max{1,−∞+5}= 13≤X<4时, f3(X)=max{f2(X), f2(X−4)+5}=max{2,−∞+5} = 24≤X<5时, f3(X)=max{f2(X), f2(X−4)+5}=max{2 , 0 + 5 } = 55≤X<6时, f3(X)=max{f2(X), f2(X−4)+5}=max{3 , 0 + 5 } = 56≤X<7时, f3(X)=max{f2(X), f2(X−4)+5}=max{3 , 1 + 5 } = 67≤X<9时, f3(X)=max{f2(X), f2(X−4)+5}=max{3 , 2 + 5 } = 7X≥9时, f3(X)=max{f2(X), f2(X−4)+5}=max{3 , 3 + 5 } = 8
第46页:递推值的逐层回代
- f3(X)=max{f2(X),f2(X−4)+5}=max{3,1+5}=6f2(X)=max{f1(X), f1(X−3)+2}=max{1,−∞+2}=1f1(X)=max{f0(X),f0(X−2)+1}=max{0,0+1}=1X3=1X2=0X1=1最优决策序列为: (x1,x2,x3)=(1,0,1)
- 通过检测fi的取值情况可以确定最优决策序列
- 用图解法求解该问题fi−1(X−wi)+pi的图像可由fi-1(X)在x轴上右移wi个单位,然后上移pi个单位得到fi(X)的图像由fi−1(X)和fi−1(X−wi)+pi的函数图像按X相同时取最大值的规则归并而成
第47页:0/1背包的图解法
- 0/1背包问题实例—图解法fi-1(X-wi)+pifi(X)i=0:函数不存在f0(X)=0i=1: f0(X-2)+1f1(X)f0(X) =-∞X<00 X≥0f1(X) =-∞X<0max{0, 0+1}=1 X≥2max{0,-∞+1}=0 0≤X<21 2 3 4 5 6211 2 3 4 5 6211 2 3 4 5 621实例: n=3, (w1,w2,w3)=(2,3,4) , (p1,p2,p3)=(1,2,5) , M=6
第48页:f2(X)的函数图像
f2(X) =-∞X<0max{1,1+2}=3 X≥5max{1,0+2}=2 3≤X<500≤X<21 2≤X<3f1(X)1 2 3 4 5 6211 2 3 4 5 6321i=2: f1(X-3)+2f2(X)1 2 3 4 5 6321
第49页:f3(X)的分段表达式
-∞X<0max{0,-∞+5}= 0 0≤X<2max{1,-∞+5}= 1 2≤X<3max{2,-∞+5} = 2 3≤X<4max{2 , 0 + 5 } = 5 4≤X<5max{3 , 0 + 5 } = 5 5≤X<6max{3 , 1 + 5 } = 6 6≤X<7max{3 , 2 + 5 } = 7 7≤X<9max{3 , 3 + 5 } = 8 X≥9f3(X) =1 2 3 4 5 6 7 8 9876543211 2 3 4 5 6 7 8 9876543211 2 3 4 5 6321f2(X)i=3:f2(X-4)+5f3(X)
第50页:序偶表示法
- 由图可以看出以下几点:1.每一个fi完全由一些序偶(Pj,Wj)组成的集合所说明,其中Wj是使fi在其处产生一次阶跃的X值,Pj=fi(Wj)Pj是p1,p2,…pn的某些值之和, Wj是w1,w2, …wn的某些值之和.2.第一对序偶(P0,W0)=(0,0);3.若有r次阶跃,就还有r对序偶(Pj,Wj), 1≤j≤r;①Wj<Wj+1,则有Pj<Pj+1②0≤j<r时,当Wj≤X<Wj+1,有fi(X)=fi(Wj);③X≥Wr,有fi(X)=fi(Wr)f2(X)1 2 3 4 5 63213≤4<5 , fi(4)=fi(3)=2X≥5,有fi(X)=fi(5)=3有r =3次阶跃,有3对序偶:(P1,W1)=(1,2)(P2,W2)=(2,3),(P3,W3)=(3,5); f2是由序偶(0,0),(1,2), (2,3), (3,5)组成的集合所说明WP
第51页:序偶集的归并
- 设Si-1表示fi-1(X)的所有序偶的集合,Si1表示fi-1(X-wi)+pi的所有序偶的集合,将(pi,wi)加到Si-1的每一对序偶上就得到Si1,然后在支配规则下将Si-1和Si1归并成Sif0(X)=01 2 3 4 5 621i=1: f0(X-2)+11 2 3 4 5 621f1(X)1 2 3 4 5 621S0={(0, 0)}S11={(1, 2)}S1={(0, 0), (1, 2)}S11=S0+(p1,w1)=(0,0)+(1,2)=(1,2)
第52页:S1与S2的序偶集合
f1(X)1 2 3 4 5 621i=2: f1(X-3)+21 2 3 4 5 63211 2 3 4 5 6321f2(X)S1={(0, 0), (1, 2)}S21={(2, 3), (3, 5)}S2={(0, 0), (1, 2), (2, 3), (3, 5)}S21=S1+(p2,w2)={(0,0), (1,2)}+(2,3)={(2,3), (3,5)}
第53页:支配规则
- 例: S2={(0,0),(1,2),(2,3),(3,5)}S31={(5,4),(6,6),(7,7),(8,9)}
- 支配规则:如果Si-1和Si1中一个有(Pj,Wj),另一个有(Pk,Wk),并且在Wj≥Wk的同时有Pj≤Pk,那么,序偶(Pj,Wj)被放弃S3={(0,0), (1,2), (2,3),(5,4), (6,6), (7,7), (8,9)}根据支配规则, 5>4且3<5,所以序偶(3, 5)被舍弃
第54页:序偶集的性质
对Si的总结1.(Pj,Wj)最多有2n个Pj是p1,p2,…pn的某些值之和, Pj=ΣpixiWj是w1,w2, …wn的某些值之和. Wj=Σwixix1,x2,…xn或者取0,或者取1.最优解是Wj≤M且Pj最大的值。
2.Si中的序偶①xi=0,则相应序偶是从Si-1得到的xi=1,则相应序偶是从Si1得到的Si1={(P+pi,W+wi)|(P,W)∈Si-1}②支配规则
第55页:决策值的回溯
- 对Si的总结3.生成Si时,将W>M的序偶去掉4.KNAP(1,n,M)的最优解fn(M)由Sn中的最后一对序偶生成,设为(Pl,Wl)5.x1,x2,…xn的决策值由Si决定:①若(Pl,Wl)∈Sn-1,则xn=0③再判断序偶(Pl,Wl)或(Pl-pn,Wl-wn)是否属于Sn-2是:xn-1=0;否:xn-1=1•S3的最末序偶(Pl,Wl)=(6,6)②若(Pl,Wl)∈Sn-1,且(Pl-pn,Wl-wn)∈Sn-1,则xn=1;•(6,6)∈S2,并且(6-p3,6-w3)=(1,2)∈S2,所以x3=1•再判断留在S2的序偶(1,2),因(1,2)∈S1,所以x2=0•(1,2)∈S0, (1-p1,2-w1)=(0,0)∈S0,所以x1=1
- 最优解fn(M)的最优决策序列是(x1,x2,x3)=(1,0,1)
第56页:最末序偶的确定
对Si的总结6.没必要生成Sn,Sn的最末序偶←Sn-1的最末序偶←Sn1的最末序偶
第57页:DKP算法思想
- 1.初始化S02.从1至n-1求Si3.由Sn-1求Sn的最末序偶4.回溯构造最优决策序列
- 0/1背包问题非形式化的DKP算法思想
第58页:DKP过程
0/1背包问题非形式化的DKP算法 procedure DKP(p,w,n,M)S0←{(0,0)}; for i←1 to n−1 doSi1←{(Pl,Wl)|(Pl−pi,Wl−wi)∈Si-1and Wl≤M}Si←MERGE_PURGE(Si-1,Si1) repeat(Px,Wx)←Sn-1的最末序偶(Py,Wy)←(Pl+pn,Wl+wn) ;其中Wl是Sn-1中使得W+wn≤M的所有序偶中取最大值的Wl if Px>Py then xn←0else xn←1endif沿Sn-1, … S1回溯确定xn-1,…,x1的值 end DKPS1={(0,0),(1,2)}S2={(0,0),(1,2),(2,3),(3,5)}(PX,WX)=(3,5)(p3,w3)=(5,4) ,Wl=2(PY,WY)=(1+5,2+4)=(6,6)(PX=3)<(PY=6)所以x3=1第59页:DKP算法的实现
- 0/1背包问题DKP算法的实现1.可用两个一维数组P和W来存放所有的序偶(Pl,Wl)
- 序偶集S0,S1,…,Sn-1互相邻接的存放
- 每个集合的起始位置用指针F(i)来指示, 0≤i≤n, F(i)指示Si中的第一个元素所在的位置S0={(0,0)}S1={(0,0),(1,2)}S2={(0,0),(1,2),(2,3),(3,5)}8765432132101005320200PWF(0)F(1)F(3)F(2)2.在生成Si1的过程中,同时将Si-1和Si1按支配规则进行归并而生成Si,因此不需要附加空间存放Si1
- 在Si-1中序偶是按P和W的递增次序排列的,因此Si的序偶也按这种次序生成
第60页:生成序偶与支配判断
0/1背包问题DKP算法的实现生成Si1中的下一序偶(pp,ww)①将Si-1中W<ww的序偶(P,W)加入Si②由支配规则看(pp,ww)是否加入Sia.若Si-1中有Wg+1= ww,则pp←max{pg+1,pp}b.若Si-1中有pg>pp,则舍弃(pp,ww)c.若不舍弃(pp,ww),则(pp,ww)→Si③考虑Si-1中W>ww的序偶有无被(pp,ww)支配若Pg+1<pp, (pg+1,Wg+1)被舍弃
第61页:DKP实现中的变量含义
0/1背包问题DKP算法的实现
- F(i):Si中第一对序偶在数组中的位置(下标)
- l, h:Si-1的第一对序偶和最后一对序偶在数组中的位置,即F(i−1)和F(i)−1.
- k: Si−1中当前要加入Si的序偶的位置.
- u:在Si-1能够产生Si1序偶的最后一个位置,即对于u+1≤v≤h的序偶(Pv,Wv),有Wv+wi>M.
- j:当前正在生成Si1的Si−1中序偶的位置.
- next: Si中要加入序偶的位置.
第62页:DKP算法的执行流程
算法思想1.初始化最初只有S0的信息,F(0),P(1),W(1),l,h,F(1),next2.生成Si对k,u赋值(1)依次生成Si1中的序偶(pp,ww)在Si-1中,重量比ww小的序偶(P(k),W(k))加入Si中(pp,ww)是否被支配;
Si-1中(pp,ww)被支配的序偶(2) Si1中的序偶都生成后,Si-1中若还有序偶没有加入Si中,则全部加入;
l,h,F(i+1)赋值3.生成最末序偶,回溯构造最优决策序列
第63页:DKNAP过程
procedure DKNAP(p,w,n,M,m)F(0)←1; P(1)←W(1)←0;l←h←1; F(1)←next←2; for i←1 to n-1 dok←l;u←r ; r是在l≤r≤h中,使得W(r)+wi≤M最大 for j←lto u do(pp,ww)=(P(j)+pi,W(j)+wi) while ( k≤h and W(k)<ww ) do{P(next)←P(k); W(next)←W(k); next←next+1; k←k+1; } if ( k≤h and W(k)=ww) then pp←max{pp,P(k)} ; k←k+1;} if ( pp>P(next-1)) {(P(next),W(next))←(pp,ww); next←next+1;} while ( k≤h and P(k)≤P(next-1)) do { k←k+1; } repeat while k≤h do{ (P(next),W(next))←(P(k),W(k)); next←next+1; k←k+1 ; }l←h+1; h←next−1; F(i+1)←next; repeat call PARTS end DKNAP计算S1到Sn-1//要加代码才能实现//将(pi,wi)加到Si-1中的序偶上//将Si-1中的序偶并入Si中//将Si-1中剩余的序偶并入Si中//l和h分别指向Si的首端和末端F(i+1)指向Si+1的第一个元素Si-1和Si1按支配规则进行归并,生成Si第64页:DKP的复杂性分析
6.5 0/1背包问题
- 时间、空间复杂性分析Si的序偶数量用|Si|表示|Si|=|Si−1|+ |Si1|如果物品的重量wi和效益pi都是整数,则Si中每个序偶的P和W也是整数,并且在Si中序偶的P和W是互异的。
第65页:启发式剪枝方法
6.5 0/1背包问题
- 启发式方法设L是最优解的估计值,有L≤fn(M),设PLEFT(i)=Σpj若(P,W)∈Si,且P+ PLEFT(i)<L,则(P,W)就可以从Si中清除掉。L的选取:Si的最末序偶(P,W)的P作为L;将某些剩余物品的p值与这个P值加在一起作为L.i<j≤n
第66页:启发式方法实例
6.5 0/1背包问题例:n=6,(p1,…p6)=(W1, …W6)=(100,50,20,10,7,3),M=165取估计值L=163,PLEFT(0)=190, PLEFT(1)=90, PLEFT(2)=40,PLEFT(3)=20, PLEFT(4)=10, PLEFT(5)=3,PLEFT(6)=0,S0={0}, S11={100}S1={100}, S21={150}S2={150}, S31=∅S3={150}, S41={160}S4={160}, S51=∅S5={160},
第67页:可靠性设计问题
6.6可靠性设计
- 乘数最优化问题D1D2D3Dn
- 设ri是设备Di正常运转的概率,则整个系统的可靠性就是D2D2DnDnDnD3D3D3D3D1D1D1
- 第i级每个设备出故障的概率为1−ri,第i级有mi个设备并联,则同时出故障的概率为(1−ri)mi,可靠性为
第68页:可靠性与成本约束
6.6可靠性设计
- 第i级设备的可靠性由函数φi(mi)给定,1≤i≤n,那么整个系统的可靠性是
- 设计系统时需考虑成本,ci表示第i级一台设备的成本,C表示要设计的系统允许的最大成本。
- 系统中每种设备至少有一台,设备i允许配置的台数至多为
第69页:可靠性设计的形式描述
6.6可靠性设计
- RELI(l,i,X)
- 极大化
- 约束条件且mi为整数,l≤j≤iRELI(1,n,c)
第70页:可靠性设计的递推
6.6可靠性设计
- 最优解是对m1,m2,…,mn的一系列决策,每次决策可以确定一个mi,
- 设fi(X)是在成本不超过X的约束下,前i种设备组成的子系统的可靠性的最优值,
- 当0≤X≤C时,对于所有的X,有f0(X)=1.fn(c)
第71页:序偶与支配规则
6.6可靠性设计
- 使用类似于解0/1背包问题的方法可以求解递归关系式
- Si由(f,X)形式的序偶所组成,其中f=fi(X).
- 支配规则对这个问题也适用,即当且仅当f1≥f2而X1≤X2时,(f1, X1)支配(f2, X2)
- Sij:第i级配备了j个设备时前i级子系统的可靠性。
第72页:序偶集的生成
6.6可靠性设计
- Si的生成:1.S0={(1,0)}2.由Si-1求Si①分别求Sij,1≤j≤ui②合并所有的Sij为Si,使用支配规则。Sij={(f×φi(j),x+j×ci)|(f,x)∈Si-1}
第73页:三级系统设计实例
三级系统可靠性设计实例:三种设备的价格与可靠性如下表,系统投资不超过105元。
三级系统中各设备的单价与可靠性| 设备 | 单价(元) | 可靠性 |
|---|
| D1 | 30 | 0.9 |
|---|
| D2 | 15 | 0.8 |
|---|
| D3 | 20 | 0.5 |
|---|
各级设备允许配置的台数上界由投资上限扣除其余各级最低成本后除以本设备单价得出。
第74页:S1与S2的序偶计算
6.6可靠性设计
- u2=3, c2=15,r2=0.8,
- S1= {(0.9,30),(0.99,60)}
- φ2(1)=0.8,φ2(2)=1-(1-0.8)2=0.96,φ2(3)=1-(1-0.8)3=0.992S21={(0.9×0.8,30+15), (0.99×0.8, 60+15)}={(0.72, 45),(0.792, 75)}S22={(0.9×0.96,30+15×2), (0.99×0.96, 60+15×2)}={(0.864, 60)}S23={(0.9×0.992,30+15×3), (0.99×0.992, 60+15×3) }={(0.8928,75)}S2={(0.72, 45),(0.792, 75),(0.864,60), (0.8928,75)}如果第二级设备配备2台,第三级设备不能购买
第75页:S3的序偶计算
6.6可靠性设计
- u3=3, c2=20,r2=0.5,
- S2={(0.72, 45),(0.864,60), (0.8928,75)}
- φ3(1)=0.5,φ3(2)=1-(1-0.5)2=0.75,φ3(3)=1-(1-0.5)3=0.875S31={(0.72×0.5,45+20), (0.864×0.5, 60+20),(0.8928×0.5, 75+20)}={(0.36, 65),(0.432, 80), (0.4464, 95)}S32={(0.72×0.75,45+20×2), (0.864×0.75, 60+20×2),(0.8928, 75+20×2)}={(0.54,85), (0.648,100)}S33={(0.72×0.875,45+20×3)}={(0.63,105)}S3={(0.36, 65),(0.432, 80), (0.4464, 95),(0.54,85), (0.648,100),(0.63,105)}
第76页:回溯求各级设备台数
6.6可靠性设计
- 由Sn, Sn-1…S1回溯求mn, mn-1, ……m1
- 判断由Sn中f最大的序偶来自哪个Snj,则n级设备上的设备数量为j.
- S3={(0.36, 65),(0.432, 80),(0.54,85),(0.648,100)}
- (0.648,100)∈S32,所以m3=2S32={(0.72×0.75,45+20×2), (0.864×0.75, 60+20×2)}={(0.54,85), (0.648,100)}(0.864,60)∈S22,所以m2=2S22={(0.9×0.96,30+15×2)}={(0.864, 60)}(0.9, 30)∈S11, m1=1
第77页:货郎担问题描述
6.7货郎担问题
- 问题描述:某售货员要到若干个村庄售货,各村庄之间的路程是已知的,为了提高效率,售货员决定从所在商店出发,到每个村庄售货一次,然后返回商店,问他应选择一条什么路线才能使所走的总路程最短?设G(V,E)是一个具有边成本cij的有向图, G的一条周游路线是包含V中每个结点的一个有向环,周游路线的成本是此路线上所有边的成本之和。
- 货郎担问题就是求取具有最小成本的周游路线问题。1432156820129913510108类似问题邮车收集邮件的邮路问题机械手臂在装配线上的移动问题产品的生产安排问题
第78页:货郎担问题的最优性原理
- 假设周游路线是开始于结点1并终止于结点1的一条简单路径。
- 每一条周游路线都是由一条边<1, k>和一条由结点k到结点1的路径所组成的,其中k∈V−{1};
- 这条由结点k到结点1的路径通过V−{1,k}的每个结点各一次,
- 最优性原理对货郎担问题成立
- 如果这条周游路线是最优的,则这条由k到1的路径必定是通过V−{1,k}中所有结点的由k到1的最短路径,因此最优性原理成立.1432156820129913510108
- 设g(i,S)是由结点i开始,通过S中的所有结点,在结点1终止的一条最短路径的长度,2≤k≤n
- g(1,V-{1})是一条最优的周游路线长度于是可以得到:g(1,V-{1})=min{c1k+g(k,V-{1,k})}j∈S
- 上式一般化可得:g(i,S)=min{cij+g(j,V-{j})}
第79页:货郎担的递推关系式
6.7货郎担问题
- g(i,∅)=ci1,
- 计算|S|=0时,g(i,S)= g(i,∅)=ci1|S|=1时,g(i,S)……|S|=n−1时,g(1,V−{1})
第80页:货郎担计算过程一
- 4321201510011090521201363098841432156820129913510108|S|=0
- g(2,∅)=c21=5
- g(3,∅)=c31=6
- g(4,∅)=c41=8
- g(2,{3})=c23+g(3,∅)=9+6=15
- g(2,{4})=c24+g(4,∅)=10+8=18g(i,S)表示由结点i经过S中所有结点到结点1的最短路线长度
- g(3,{2})=c32+g(2,∅)=13+5=18
- g(3,{4})=c34+g(4,∅)=12+8=20
- g(4,{2})=c42+g(2,∅)=8+5=13
- g(4,{3})=c43+g(3,∅)=9+6=15|S|=1
第81页:货郎担计算过程二
- g(2,{3,4})=min{c23+g(3,{4}),c24+g(4,{3})}=min{9+20,10+15} =25
- g(3,{2,4})=min{c32+g(2,{4}),c34+g(4,{2})}=min{13+18,12+13} =25
- g(4,{2,3})=min{c42+g(2,{3}), c43+g(3,{2})}=min{8+15,9+18} =23
- g(1,{2,3,4})=min{c12+g(2,{3,4}), c13+g(3,{2,4}), c14+g(4,{2,3})}=min{10+25, 15+25 , 20+23} =35
- 可得这条最优周游路线是: 1↔2↔4↔3↔11432156820129913510108|S|=2
第82页:货郎担的时间复杂性
6.7货郎担问题
- 时间复杂性分析
- |S|=0时,g(i,S)= g(i,∅)(n-1)×C(n-2,0)|S|=1时,g(i,S)(n-1)×C(n-2,1)……|S|=n-3时,g(i,S)(n-1)×C(n-2,n-3)|S|=n-2时,g(i,S)(n-1)×C(n-2,n-2)|S|=n-1时,g(1,V-{1})因此,g(i,S)的个数为Σ(n-1)×C(n-2,k)=(n-1)2n-2i的个数为n-10≤k≤n-2n-1次加法和比较计算时间为Θ(n22n)
第83页:流水线调度问题描述
6.8流水线调度问题
- 大型作业往往由一系列任务组成
- n个作业要在m台设备组成的流水线上完成加工,每个作业加工的顺序都是先在P1上加工,然后在P2上加工,……,最后在Pm上加工
- 每个任务Tj,i,1≤j≤m,1≤i≤n
- Tj,i只能在Pj上执行
- 任何时刻在同一台设备上不能同时处理一个以上的任务
- Tj-1,i完成后,Tj,i才能开始执行,每个任务的执行时间tj,i
- 如何将n×m个任务分配给m台设备,使得n个作业完成?
第84页:非抢先与抢先调度
6.8流水线调度问题
- 例:考虑在三台设备上调度两个作业,每个作业包含三项任务,完成这些任务要求的时间由矩阵J给出,
- 非抢先调度:在任何一台设备处理一个任务,一直到它完成才能处理另一个任务,不允许被中断。
- 抢先调度:设备在处理某任务时被中断,而优先处理优先级更高的任务。
- 作业i的完成时间fi(S):在S调度方案下作业i的所有任务得以完成的时间。
第85页:完成时间与平均流动时间
6.8流水线调度问题
- 调度S的完成时间F(S)
- 平均流动时间MFT(S)
- 一组给定作业的最优完成时间OFT调度是一种非抢先调度S,它对所有非抢先调度而言,F(S)的值最小。
- POFT,OMFT,POMFT
- 当m>2时,得到OFT(非抢先调度下最优时间)和POFT(抢先调度下最优时间)的调度的一般问题是难于计算的问题。
第86页:两台设备的OFT调度
6.8流水线调度问题
- m=2, OFT调度
- 直观上,一个最优调度应使机器P1没有空闲时间,且机器P2的空闲时间最少。
- ai表示t1i,bi表示t2i
- 在两台设备上按同样的顺序处理作业,不比分别采用不同的处理次序处理作业花费更多的时间
- 如果允许有ai=0的作业,那么最优调度可通过下法构造出来:首先对于所有ai≠0的作业求出一种最优调度的排列,然后把所有的ai=0的作业以任意次序加到这一排列的前面。
第87页:g(S,t)的定义
6.8流水线调度问题
- hl和h2分别是在设备P1和P2上完成作业1,2…,k的时间, t=h2-hl
- g(S,t):是在t下作业集合S的最优调度长度
- 作业集合{1, 2,…,n}的最优调度是g({1,2,…,n},0)g(∅,t)=max(t,0)
第88页:g(S,t)的递推关系式
6.8流水线调度问题
- 用上节的方法求递推关系式,时间O(2n)
- 设i和j是S的调度R中排在前面的两个作业
- g(S,t)=ai+g(S-{i},bi+max{t-ai,0})= ai+aj+g(S-{i,j},bj+max{bi+max{t-ai,0}−aj,0})= ai+aj+g(S-{i,j},tij)
- 将作业i,j在R中易位
- g’(S,t)=ai+aj+g(S-{i,j},tji)t’t’min{bi,aj}≥min{bj,ai}tij≤tjig(S,t)≤g’(S,t)作业i和j,若ai,aj,bi,bj中ai最小,则首先处理作业i更优;若bj最小,则最后处理作业j更优。
第89页:调度规则
6.8流水线调度问题
- 调度规则:①把全部ai和bj分类成非降序列;②按照这一分类次序考察此序列
- 如果序列中下一个数是aj且作业j还没调度,那么在还没使用的最左位置调度作业j;
- 如果下个数是bj且作业j还没调度,那么在还没使用的最右位置调度作业j;
- 如果已经调度了作业j,则转到该序列的下一个数。
第90页:调度规则实例
- 例6.19设n=4,(a1,a2,a3,a4)=(3,4,8,10),(b1,b2,b3,b4)=(6,2,9,15)
- 求解
- 非降次序排列,获得序列
- (b2,a1,a2,b1,a3,b3,a4,b4) =(2,3,4,6,8,9,10,15)σ4σ3σ2σ1调度序列2134a2b22538a4b42136a3b31120a1P10b1P239