关闭

关闭

关闭

封号提示

内容

首页 算法分析与设计[动态规划]课件.ppt

算法分析与设计[动态规划]课件.ppt

算法分析与设计[动态规划]课件.ppt

上传者: 用户141575 2018-06-10 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《算法分析与设计[动态规划]课件ppt》,可适用于高等教育领域,主题内容包含第四章动态规划西南科技大学计算机学院软件教研室第四章动态规划什么是动态规划多段图最优二分检索树背包问题可靠性设计货郎担问题西南科技大学计算机学院软件符等。

第四章动态规划西南科技大学计算机学院软件教研室第四章动态规划什么是动态规划多段图最优二分检索树背包问题可靠性设计货郎担问题西南科技大学计算机学院软件教研室在实际生活中有这么一类问题它们的活动过程可以分为若干个阶段而且在任一阶段后的行为都依赖于i阶段的过程状态而与i阶段之前的过程是如何达到这种状态的方式无关这样的过程就构成了一个多阶段决策过程。根据这类问题的多阶段决策的特性提出了解决这类问题的“最优性原理”从而创建了最优化问题的一种新的算法设计方法动态规划。一般方法西南科技大学计算机学院软件教研室什么是动态规划在多阶段决策过程的每一个阶段都可能有多种选择的决策但必须从中选取一种决策。一旦各种阶段的决策选定之后就构成了解决这一问题的一个决策序列。决策序列不同导致的问题结果也不同。动态规划的目标就是要在所有容许选择的决策序列中选取一个会获得问题最优解的决策序列即最优决策序列。西南科技大学计算机学院软件教研室最优性原理最优性原理(PrincipleofOptimality)过程的最优决策序列具有如下性质:无论过程的初始状态和初始决策是什么其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。利用动态规划求解问题的前提)证明问题满足最优性原理如果对所求解问题证明满足最优性原理则说明用动态规划方法有可能解决该问题)获得问题状态的递推关系式获得各阶段间的递推关系式是解决问题的关键。西南科技大学计算机学院软件教研室多段图问题多段图问题西南科技大学计算机学院软件教研室多段图问题多段图G=(V,E)是个有向图。它具有如下特性:图中的结点被划分成k个不相交的集合Vi,ik,其中V和Vk分别只有一个结点s(源点)和t(汇点)。图中所有的边<u,v>均具有如下性质:若uVi则vVi,ik,且每条边<u,v>均附有成本c(u,v)。从s到t的一条路径成本是这条路径上边的成本和。多段图问题(multistagegraphproblem)是求由s到t的最小成本路径。西南科技大学计算机学院软件教研室多段图问题最优性原理对多段图成立假设s,v,v,…,vk,t是一条由s到t的最短路径再假设从源点s开始已作出了到结点V的决策因此V就是初始决策所产生的状态如果把V看成是原问题的一个子问题的初始状态解决这个子问题就是找出一条由V到t的最短路径这条最短路径显然是v,v,…,vk,t如果不是设v,q,…,qk,t由V到t的更短路径则这条路径肯定比v,v,…,vk,t路径短这与假设矛盾因此最优性原理成立西南科技大学计算机学院软件教研室背包问题背包问题中的xj限定只能取或值用KNAP(,j,X)来表示这个问题效益值背包容量则背包问题就是KNAP(,n,M)西南科技大学计算机学院软件教研室最优化决策序列的表示设S是问题的初始状态。假定要作n次决策xi,inX={r,,r,,…,r,pj}是x的可能决策值的集合而S,是在选取决策值r,j以后所产生的状态jp又设F,j是相应于状态S,j的最优决策序列则相应于S的最优决策序列就是{r,jF,j|jp}中最优的序列记作如果已作了k次决策k<n。设x,…xk的最优决策值是r,,rk他们所产生的状态为S,…Sk西南科技大学计算机学院软件教研室最优化决策序列的表示又设Xk={{rk,,rk,,…,rk,pk}是xk的可能值的集合。Sk,jk是选取rk,jk决策之后所产生的状态,jkpkFk,jk是相应于Sk,jk的最优决策序列。因此相应于Sk的最优决策序列是于是相应于S的最优决策序列为:r,…,rk,rk,Fk西南科技大学计算机学院软件教研室向前处理法(forwardapproach)从最后阶段开始以逐步向前递推的方式列出求前一阶段决策值的递推关系式即根据xi,…,xn的那些最优决策序列来列出求取xi决策值的关系式这就是动态规划的向前处理法向后处理方法(backwardapproach)就是根据x,…,xi的那些最优决策序列列出求xi的递推关系式。多段图的向前处理和向后处理背包问题的向前处理和向后处理西南科技大学计算机学院软件教研室多段图多段图向前处理的算法设P(i,j)是一条从Vi中的节点j到汇点t的最小成本路径COST(i,j)表示这条路径的成本根据向前处理方法有公式:西南科技大学计算机学院软件教研室因为若<j,t>E成立,有COST(k,j)=c(j,t),若<j,t>E不成立则有COST(k,j)=所以可以通过如下步骤解式公式()并求出COST(,s)。首先对于所有jVk计算COST(k,j)然后对所有的jVk计算计算COST(k,j)等等最后计算出计算COST(,s)多段图的向前处理算法西南科技大学计算机学院软件教研室例子中段图的实现计算步骤:COST(,)=COST(,)=COST(,)=COST(,)=min{COST(,),COST(,)}=COST(,)=min{COST(,),COST(,)}=COST(,)=min{COST(,),COST(,)}=多段图的向前处理算法西南科技大学计算机学院软件教研室多段图的向前处理算法COST(,)=min{COST(,),COST(,),COST(,)}=COST(,)=COST(,)=COST(,)=COST(,)=min{COST(,),COST(,),COST(,),COST(,)}=西南科技大学计算机学院软件教研室多段图的向前处理算法例子中段图的实现计算步骤:在计算每一个COST(i,j)的同时记下每个状态(结点j)所做出的决策设为D(i,j)则可容易地求出这条最小成本路径。D(,)=D(,)=D(,)=D(,)=D(,)=D(,)=D(,)=D(,)=设这条最小成本路径是s=l,v,v,…,vk,t=。则可得知:v=D(,)=v=D(,D(,))=和v=D(,D(,D(,)))=D(,)=西南科技大学计算机学院软件教研室多段图的向前处理算法procedureFGRAP(E,k,n,P)realCOST(n),integerD(n),P(k),r,j,k,nCOST(n)forjntoby–do设r是一个这样的结点,<j,r>E且使c(j,r)COST(r)取小值COST(j)c(j,r)COST(r)D(j)rrepeatP()P(k)nforjtokdoP(j)D(P(j))repeatEndFGRAPH计算出COST(j)的值并找出一条最小成本路径找出最小成本路径上的第j个结点西南科技大学计算机学院软件教研室多段图的向后处理算法向后处理方法(backwardapproach)就是根据x,…,xi的那些最优决策序列列出求xi的递推关系式。西南科技大学计算机学院软件教研室多段图的向后处理算法设BP(i,j)是一条由源点s到Vi中结点j的最小成本路径BCOST(i,j)表示BP(i,j)的成本由向后处理方法得到公式:即由源点s到Vi中结点j的最小成本等于由源点s到Vi中任一结点l的最小成本加上Vi中结点l到Vi中结点j的边长,所得的所有和中最小的那个值。西南科技大学计算机学院软件教研室因为若<,j>E成立,BCOST(,j)=c(,j),若<,j>E不成立则有BCOST(,j)=所以可以通过如下步骤解式公式()首先对i=计算BCOST然后对i=计算BCOST等最后计算出BCOST(kt)。BCOST()=BCOST()=BCOST()=BCOST()=多段图的向后处理算法西南科技大学计算机学院软件教研室stBCOST(,)=min{BCOST(,),BCOST(,)}=BCOST(,)=min{BCOST(,),BCOST(,),BCOST(,)}=BCOST(,)=min{BCOST(,),BCOST(,),BCOST(,)}=西南科技大学计算机学院软件教研室stBCOST(,)=min{BCOST(,),BCOST(,)}=BCOST(,)=min{BCOST(,),BCOST(,),BCOST(,)}=BCOST(,)=西南科技大学计算机学院软件教研室stBCOST(,)=min{BCOST(,),BCOST(,),BCOST(,)}=西南科技大学计算机学院软件教研室多段图的向后处理算法在计算每一个BCOST(i,j)的同时记下每个状态(结点j)所做出的决策(即,使BCOST(i,j)c(l,j)取最小值的l值),设为D(i,j)则可容易地求出这条最小成本路径。西南科技大学计算机学院软件教研室对于实例中的最小成本路径如下所示:D(,)=D(,)=D(,)=D(,)=D(,)=D(,)=D(,)=西南科技大学计算机学院软件教研室多段图的向后处理算法LineprocedureBGRAP(E,k,n,P)realBCOST(n),integerD(n),P(k),r,j,k,nBCOST()forjtondo设r是一个这样的结点<r,j>E且使BCOST(r)c(r,j)取小值BCOST(j)BCOST(r)c(r,j)D(j)rrepeatP()P(k)nforjktobydoP(j)D(P(j))repeatEndBGRAPH计算出BCOST(j)的值并找出一条最小成本路径找出最小成本路径上的第j个结点西南科技大学计算机学院软件教研室每对结点之间的最短路径复习(略)西南科技大学计算机学院软件教研室最优二分检索树问题的描述)二分检索树定义 二分检索树T是一棵二元树它或者为空或者其每个结点含有一个可以比较大小的数据元素且有:   T的左子树的所有元素比根结点中的元素小   T的右子树的所有元素比根结点中的元素大   T的左子树和右子树也是二分检索树。注:二分检索树要求树中所有结点的元素值互异西南科技大学计算机学院软件教研室二分检索树对于一个给定的标识符集合可能有若干棵不同的二分检索树:不同形态的二分检索树对标识符的检索性能是不同的。西南科技大学计算机学院软件教研室二分检索树检索一棵二分检索树算法procedureSEARCH(T,X,i)i=Twhilei<>docase:X<IDENT(i):i=LCHILD(i):X=IDENT(i):return:X>IDENT(i):i=RCHILD(i)endcaserepeatendREARCH西南科技大学计算机学院软件教研室最优二分检索树问题设给定的标识符集合是{a,a,…,an}并假定a<a<…<an。设P(i)是对ai检索的概率Q(i)是正被检索的标识符X恰好满足:ai<X<aiin(设a=,an=)时的概率即一种不成功检索情况下的概率。则表示所有成功检索的概率表示所有不成功检索的概率考虑所有可能的成功和不成功检索情况共n种可能的情况有西南科技大学计算机学院软件教研室二分检索树二分检索树(如右图所示)内结点:代表成功检索情况刚好有n个。外结点:代表不成功检索情况刚好有n+个。西南科技大学计算机学院软件教研室二分检索树的预期成本预期成本:算法对于所有可能的成功检索情况和不成功检索情况平均所要做的比较次数。根据期望值计算方法平均检索成本=Σ每种情况出现的概率该情况下所需的比较次数平均检索成本的构成:成功检索成分+不成功检索成分成功检索:在l级内结点终止的成功检索需要做l次比较运算(基于二分检索树结构)。该级上的任意结点ai的成本检索的成本分担额为:P(i)*level(ai)其中level(ai)=结点ai的级数=l西南科技大学计算机学院软件教研室二分检索树的预期成本不成功检索:不成功检索的等价类:每种不成功检索情况定义了一个等价类共有n个等价类Ei(in)。其中E={X|X<a}Ei={X|ai<X<ai(i<n)}En={X|X>an}若Ei处于l级则算法需作l次迭代。则l级上的外部结点的不成功检索的成本分担额为:Q(i)*(level(Ei))则预期总的成本公式表示如下:西南科技大学计算机学院软件教研室最优二分检索树最优二分检索树问题:求一棵使得预期成本最小的二分检索树例标识符集合(a,a,a)=(do,if,stop)。可能的二分检索树如下所示。成功检索:种不成功情况:种西南科技大学计算机学院软件教研室最优二分检索树西南科技大学计算机学院软件教研室最优二分检索树)等概率:P(i)=Q(i)=cost(a)=cost(b)=最优cost(c)=cost(d)=cost(e)=)不等概率:P()=P()=P()=Q()=Q()=Q()=Q()=cost(a)=cost(b)=cost(c)=最优cost(d)=cost(e)=西南科技大学计算机学院软件教研室多阶段决策过程把构造二分检索树的过程看成一系列决策的结果。决策的策略:决策树根如果{a,a,…,an}存在一棵二分检索树ak是该树的根则内结点a,a,…,ak和外部结点E,E,…,Ek将位于根ak的左子树中而其余的结点将位于右子树中。西南科技大学计算机学院软件教研室定义含义:左、右子树的预期成本左、右子树的根处于第一级左、右子树中所有结点的级数相对于子树的根测定而相对于原树的根少西南科技大学计算机学院软件教研室定义记:则原二分检索树的预期成本可表示为:COST(T)=P(k)COST(L)COST(R)W(,k)W(k,n)最优二分检索树:COST(T)有最小值最优性原理成立若T最优二分检索树则COST(L)和COST(R)将分别是包含a,a,…,ak和E,E,…,Ek、及ak+,ak,…,an和Ek,Ek,…,En的最优二分检索(子)树。记由ai,ai,…,aj和Ei,Ei!,…,Ej构成的二分检索树的成本为C(i,j)则对于最优二分检索树T有COST(L)=C(,k)COST(R)=C(k,n)西南科技大学计算机学院软件教研室定义则对任何C(i,j)有向前递推过程:首先计算所有ji=的C(i,j)然后依次计算ji=,,…,n的C(i,j)。C(,n)=最优二分检索树的成本。初始值C(i,i)=W(i,i)=Q(i)in西南科技大学计算机学院软件教研室用动态归划求最优二分检索树首先计算所有使得ji=的C(i,j)接着计算所有使得ji=的C(i,j)……如果在这一计算期间记下每棵Tij树的根R(i,j),那么最优二分检索树就可以由这些R(i,j)构造出来。西南科技大学计算机学院软件教研室用动态归划求最优二分检索树例设n=,且(a,a,a,a)=(do,if,read,while)。设P(:)=(,,,)Q(:)=(,,,,)(概率值“扩大”了倍)初始:W(i,i)=Q(i)C(i,i)=R(i,i)=且有W(i,j)=P(j)Q(j)W(i,j)ji=阶段的计算:W(,)=P()Q()W(,)=C(,)=W(,)min{C(,)C(,)}=R(,)=W(,)=P()Q()W(,)=C(,)=W(,)min{C(,)C(,)}=R(,)=W(,)=P()Q()W(,)=C(,)=W(,)min{C(,)C(,)}=R(,)=W(,)=P()Q()W(,)=C(,)=W(,)min{C(,)C(,)}=R(,)=例(P)西南科技大学计算机学院软件教研室用动态归划求最优二分检索树W,C,R计算结果则C(,)=二分检索树:T==>T(左子树)T(右子树)T==>T(左子树)T(右子树)T==>T(左子树)T(右子树)ji西南科技大学计算机学院软件教研室用动态归划求最优二分检索树树的形态西南科技大学计算机学院软件教研室算法描述procedureOBST(P,Q,n)给定n个标识符a<a<…<an。已知成功检索的概率P(i),不成功检索概率Q(i),in。算法对于标识符ai,…,aj计算最优二分检索树Tij的成本C(i,j)、根R(i,j)、权W(i,j)realP(:n),Q(:n),C(:n,:n),W(:n,:n)integerR(:n,:n)foritondo(W(i,i),R(i,i),C(i,i))(Q(i),,)置初值(W(i,i),R(i,i),C(i,i))(Q(i)Q(i)P(i),i,Q(i)Q(i)P(i))repeat含有一个结点的最优树(W(n,n),R(n,n),C(n,n))(Q(n),,)formtondo找有m个结点的最优树foritonmdojimW(i,j)W(i,j)P(j)Q(j)k区间R(i,j),R(i,j)中使{C(i,l)C(l,j)}取最小值的l值Knuth结论C(i,j)W(i,j)C(i,k)C(k,j)R(i,j)krepeatrepeatendOBST西南科技大学计算机学院软件教研室计算时间当ji=m时有nm个C(i,j)要计算C(i,j)的计算:O(m)每个C(i,j)要求找出m个量中的最小值。则nm个C(i,j)的计算时间:O(nmm)对所有可能的m总计算时间为:西南科技大学计算机学院软件教研室背包问题问题描述背包问题中的xj限定只能取或值用KNAP(,j,X)来表示这个问题效益值背包容量则背包问题就是KNAP(,n,M)西南科技大学计算机学院软件教研室背包问题最优化原理证明若y,y,…,yn是最优解则y,y,…,yn将是是背包问题的子问题的最优解。因为若y’,y’,…,yn’是子问题的最优解且使得西南科技大学计算机学院软件教研室背包问题最优化原理证明则y,y’,y’,…,yn’将是原问题的可行解并且使得这与假设y,y,…,yn是最优解相矛盾。因此背包问题具有最优子结构性质得以证明可以用动态规划的方法求最优解。西南科技大学计算机学院软件教研室背包问题解决方法根据问题描述可通过作出变量x,x,…,xn的一个决策序列来得到它的解。假定决策x的次序为x,x,…,xn则在对x作出决策后问题处于下列两种状态:X=,背包的剩余容量为M没有产生任何效益X=,背包剩余容量为Mw效益值增加了p显然剩下来对x,…,xn的决策相对于决策了x后所产生的问题状态应该是最优的否则x,x,…,xn就不可能是最优的决策序列。西南科技大学计算机学院软件教研室背包问题解决方法设fj(X)是KNAP(,j,X)最优解的值则fn(M)(KNAP(,n,M))可表示为:fn(M)=max{fn(M),fn(Mwn)pn}则对于任意的fi(X)(KNAP(,i,X))可表示公式为:fi(X)=max{fi(X),fi(Xwi)pi}为了能由前向后递推而最后求解出fn(M),须从f(X)开始对于所有的X有f(X)=当X<时有f(X)=根据递推关系式马上可求出X<w和Xw情况下的f(X)的值西南科技大学计算机学院软件教研室背包问题实例例:n=,(w,w,w)=(,,),(p,p,p)=(,,),M=。利用公式递推求解如下:当X<时,f(X)=当X时,有f(X)=当X<时,f(X)=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X时,f(X)=max{f(X),f(X)}=max{,}=西南科技大学计算机学院软件教研室背包问题实例当X<时,f(X)=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X时,f(X)=max{f(X),f(X)}=max{,}=例:n=,(w,w,w)=(,,),(p,p,p)=(,,),M=。西南科技大学计算机学院软件教研室背包问题实例当X<时,f(X)=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X时,f(X)=max{f(X),f(X)}=max{,}=例:n=,(w,w,w)=(,,),(p,p,p)=(,,),M=。西南科技大学计算机学院软件教研室背包问题实例西南科技大学计算机学院软件教研室背包问题算法procedureDynamicKnapsack(p,w,n,M,f)二维数组f(:n,:M)的定义与fj(X)相同foritoMdof(,i)repeatforitondof(i,)repeatforitondoforjtoMdoifw(i)jthenf(i,j)=max{f(i,jw(i))p(i),f(i,j)}elsef(i,j)=f(i,j)endifrepeatrepeat输出f(n,M)endDynamicKnapsack西南科技大学计算机学院软件教研室背包问题实例可通过检测fi的取值情况可以确定获得最优解的最优决策序列f(M)=是在X=的情况下取得的因此X=f(M)p=f(X)和f(X)都可取则x=f不能取值故x=于是最优决策序列为(x,x,x)=(,,)也可通过图解法得到fi(Xwi)pi的图像可由fi(X)在x轴上右移wi个单位然后上移pi个单位得到fi(X)的图像由fi(X)和fi(Xwi)pi的函数曲线按X相同时取最大值的规则归并而成西南科技大学计算机学院软件教研室背包问题实例图解法fi(Xwi)pifi(X)i=:函数不存在f(X)i=:f(X)f(X)当X<时,f(X)=当X时,有f(X)=当X<时,f(X)=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X时,f(X)=max{f(X),f(X)}=max{,}=西南科技大学计算机学院软件教研室i=:f(X)f(X)f(X)当X<时,f(X)=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X时,f(X)=max{f(X),f(X)}=max{,}=西南科技大学计算机学院软件教研室i=:f(x)f(X)当X<时,f(X)=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X<时,f(X)=max{f(X),f(X)}=max{,}=当X时,f(X)=max{f(X),f(X)}=max{,}=西南科技大学计算机学院软件教研室背包问题实例图解法由图可看出以下几点:每一个fi完全由一些序偶(Pj,Wj)组成的集合所说明其中Wj是使fi在其处产生一次阶跃的X值Pj=fi(Wi)。第一对序偶(P,W)=(,)如果有r次阶跃就还要知道r对序偶(Pj,Wj),jrr对序偶中假定Wj<Wj由公式可得Pj<Pj设Si表示fi的所有序偶的集合Si表示fi(Xwi)pi的所有序偶的集合。把(pi,wi)加到Si中,每一对序偶就得到Si西南科技大学计算机学院软件教研室背包问题实例支配规则由于取fi(X)和fi(Xwi)pi的最大值也就是将Si和Si归并成Si如果Si和Si中一个有序偶(Pj,Wj)另一个有序偶(Pk,Wk)并且在WjWk的同时有PjPk那么序偶(Pj,Wj)被放弃。也就是递推关系式中求最大值的运算fi(Wj)=max(Pj,Pk)=Pk西南科技大学计算机学院软件教研室背包问题实例例:n=,(p,p,p)=(,,),(w,w,w)=(,,),M=S={(,)}S={(P,W)|(Pp,Ww)S}={(,)}S={(,),(,)}S={(P,W)|(Pp,Ww)S}={(,),(,)}S={(,),(,),(,),(,)}S={(P,W)|(Pp,Ww)S}={(,),(,),(,),(,)}S={(,),(,),(,),(,),(,),(,),(,)}根据支配规则在S中删去了序偶(,)西南科技大学计算机学院软件教研室Si的推导过程在用直接枚举法求解背包问题时由于每个xi的取值只能为或因此x,x,…,xn有n个不同的、值序列。对于每一个序列若把wlxl记为Wjplxl记为Pj则此序列产生一对与之对应的序偶(Pj,Wj)在这n个序偶中满足WjM且使Pj取最大值的序偶就是背包问题的最优解。在用动态规划的向后处理法求解时Si表示的就是由x,x,…,xi的i个决策序列中一些可能的序列所产生的序偶(Pj,Wj)。西南科技大学计算机学院软件教研室Si的推导过程若已知Si则求Si可有下述步骤得到:在xi=的情况下产生的序偶集与Si相同在xi=的情况下产生的序偶集是将(pi,wi)加到Si的每一对序偶(Pj,Wj)得到的也就是Si再根据支配规则将Si和Si归并在一起就得到Si此外在生成序偶集Si同时还应将W>M的那些序偶(Pj,Wj)除掉。西南科技大学计算机学院软件教研室最优解序列的确定这样生成的Si的所有序偶是背包问题KNAP(,i,X)在XM各种情况下的最优解。KNAP(,n,M)的最优解fn(M)由Sn的最后一对序偶的P值给出。如果已找到Sn的最末序偶(Pl,Wl),那么使pixi=Pl,wixi=Wl的x,…,xn的决策值可以通过检索这些Si来确定。若(Pl,Wl)Snxn=若(Pl,Wl)Sn且(Plpn,Wlwn)Snxn=再判断留在Sn的序偶(Pl,Wl)或(Plpn,Wlwn)是否属于Sn以确定xn的取值。西南科技大学计算机学院软件教研室最优解序列的确定例:n=,(p,p,p)=(,,),(w,w,w)=(,,),M=f()的值由S中的序偶(,)给出(,)S,并且(p,w)=(,)S,因此x=。(,)S,又因为(,)S,于是x=。(,)S,(p,w)=(,)S所以x=。f()=的最优决策序列是(x,x,x)=(,,)西南科技大学计算机学院软件教研室背包问题DKP算法procedureDKP(p,w,n,M)S{(,)}foritondoSi{(Pl,Wl)|(Plpi,Wlwi)SiandWlM}SiMERGEPURGE(Si,Si)repeat(PX,WX)Sn的最末序偶(PY,WY)(Plpn,Wlwn)其中Wl是Sn中使得WwnM的所有序偶中取最大值的WifPX>PYthenxnPX是Sn的最末序偶xnPY是Sn的最末序偶endif回溯确定xn,…,xEndDKP初始值利用支配规则生成Si的序偶集合确定最优解序列确定xi取还是西南科技大学计算机学院软件教研室可靠性设计假定要设计一个系统,这个系统由若干个以串联方式连接在一起的不同设备所组成。设ri是设备Di的可靠性(正常运转的概率)则整个系统的可靠性就是若第i级的设备Di的台数为mi,则这mi台设备同时出现故障的概率为(ri)mi从而第i级的可靠性就变成(ri)mi。西南科技大学计算机学院软件教研室可靠性设计()假设第i级的可靠性由函数i(mi)给定这个多级系统的可靠性是假设Cj是一台设备j的成本由于系统中每种设备至少有一台故设备j允许配置的台数至多为西南科技大学计算机学院软件教研室可靠性设计()如果RELI(,i,X)表示在可容许成本X约束下对第种到第i种设备的可靠性设计问题它的形式描述为极大化约束条件西南科技大学计算机学院软件教研室可靠性设计()于是整个系统的可靠性设计问题可用RELI(,n,c)表示。它的一个最优解是对m,…,mn的一系列决策的结果。每得到一个mi都要对其取值进行一次决策。设fi(X)是在容许成本值X约束下对前i种设备组成的子系统可靠性设计的最优值。西南科技大学计算机学院软件教研室可靠性设计()于是最优解的可靠性是fn(c)一般性况: 西南科技大学计算机学院软件教研室货郎担问题问题描述:某售货员要到若干个村庄售货各村庄之间的路程是己知的为了提高效率售货员决定从所在商店出发到每个村庄售一次货然后返回商店问他应选择一条什么路线才能使所走的总路程最短设G(V,E)是一个具有边成本cij的有向图。G的一条周游路线是包含V中每个结点的一个有向环。周游路线的成本是此路线上所有边的成本之和货郎担问题(travelingsalespersonproblem)是求取具有最小成本的周游路线问题。西南科技大学计算机学院软件教研室货郎担问题实例邮路问题在一条装配线上用一个机械手取紧固待装配部件上的螺帽问题产品的生产安排问题……西南科技大学计算机学院软件教研室是否能用动态规划解决假设周游路线是开始于结点并终止于结点的一条简单路径。每一条周游路线都由一条边<,k>和一条由结点k到结点的路径所组成其中kV{}而这条由结点k到结点的路径通过V{,k}的每个结点各一次。容易看出如果这条周游路线是最优的那么这条由k到的路径必定是通过V{,k}中所有结点的由k到的最短路径因此最优性原理成立。西南科技大学计算机学院软件教研室动态规划的解决方法假设g(i,S)是由结点i开始通过S中的所有结点在结点终止的一条最段路径长度。g(,V{})是一条最优的周游路线长度。于是可以得到:西南科技大学计算机学院软件教研室货郎担问题实例西南科技大学计算机学院软件教研室货郎担问题实例g(,Ø)=c=,g(,Ø)=c=,g(,Ø)=c=g(,{})=cg(,Ø)==(结点经过结点到结点的路线长度)g(,{})=cg(,Ø)==g(,{})=cg(,Ø)==g(,{})=cg(,Ø)==g(,{})=cg(,Ø)==g(,{})=cg(,Ø)==西南科技大学计算机学院软件教研室货郎担问题实例g(,{,})=min{cg(,{}),cg(,{})}=min{,}=(结点经过结点、到结点的路线长度)g(,{,})=min{cg(,{}),cg(,{})}=min{,}=g(,{,})=min{cg(,{}),cg(,{})}=min{,}=西南科技大学计算机学院软件教研室货郎担问题实例最后可得g(,{,,})=min{cg(,{,}),cg(,{,}),cg(,{,})}=min{,,}=(结点经过结点、、最后到达结点的路线长度)因此可得这条最优周游路线是:>>>>西南科技大学计算机学院软件教研室流水线调度问题设有n个作业每个作业要执行m个任务:Ti,Ti,…,Tmi,(in)任务Tji只能在设备Pj上执行。对任一作业i,在任务Tji没完成以前不能对任务Tji开始处理。同一台设备在任何时刻不能同时处理一个以上的任务。假设完成任务Tji所要求的时间是tji。如何将这n*m个任务分配给这m台设备才能使这n个作业在以上要求下顺利完成?西南科技大学计算机学院软件教研室两种可能的调度非抢先调度抢先调度例(P)西南科技大学计算机学院软件教研室最优完成时间OFT调度一组给定作业的最优完成时间OFT调度是一种非抢先调度S它对所有非抢先调度而言调度S完成时间F(S)的值最小。本节只讨论当m=时获取OFT调度这种特殊情况的算法。为方便起见用ai表示tibi表示ti西南科技大学计算机学院软件教研室最优调度排列具有的性质在给出了这个排列的第一个作业后剩下的排列相对于这两台设备在完成第一个作业时所处的状态而言是最何优。西南科技大学计算机学院软件教研室递推关系式假设对作业,,…,k的一种调度排列为a,a,…,ak。对于这种调度设h和h分别是在设备P和P上完成任务(T,T,…,Tk)和(T,T,…,Tk)的时间。设t=hh则在t这段时间及其以前设备P不能用来处理别的作业的任务。西南科技大学计算机学院软件教研室递推关系式假设g(S,t)是上述t下S的最优调度长度。g({,,…,n},)=min{aig({,,,n}{i},bi)}in一般情况:g(S,t)=min{aig(S{i},bimax{tai,})}(in)西南科技大学计算机学院软件教研室递推关系式g(S,t)=aig(S{i},bimax{tai,})=aiajg(S{i,j},bjmax{bimax{tai,}aj,})令tij=bjmax{bimax{tai,}aj,}=bjbiajaimax{t,aiajbi,ai}如果作业i和j互易其位则完成时间为:g’(S,t)=aiajg(S{i,j},tji)若max{t,aiajbi,ai}max{t,aiajbi,ai}或min{bi,aj}min{bj,ai}则g(S,t)g’(S,t)西南科技大学计算机学院软件教研室调度规则把全部ai和bi分类成非降序列按照这一分类次序考察些序列:如果序列中下一个数是aj且作j还没调度那么在还没使用的最左位置调度作业j如果下个数是bj且作业j还没有调度那么在还没有使用的最右位置调度作业j如果已经调度了作业j则转到该序列的下一个数。西南科技大学计算机学院软件教研室

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +2积分

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

资料评价:

/91
¥19.9 购买

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部