《算法设计与分析》第08章概要.ppt

算法设计与分析算法设计与分析DeSign and Analysis of AlgorithmsIn C+“十一五十一五”国家级规划教国家级规划教材材 陈慧南陈慧南陈慧南陈慧南 编著编著编著编著电子工业出版社电子工业出版社电子工业出版社电子工业出版社 第第2部分部分算法设计策略算法设计策略 第第8章章回溯法回溯法 8.18.1一般方法一般方法一般方法一般方法 8.2n-8.2n-皇后皇后皇后皇后 8.38.3子集和数子集和数子集和数子集和数 8.48.4图的着色图的着色图的着色图的着色 8.58.5哈密顿环哈密顿环哈密顿环哈密顿环 8.60/18.60/1背包背包背包背包 8.78.7批处理作业调度批处理作业调度批处理作业调度批处理作业调度 8.1一般方法一般方法 8.1.1基本概念基本概念解以向量形式表示：解以向量形式表示：(x0,x2,xn-1)规规定定每每个个xi取取值值的的约约束束条条件件称称为为 显显显显 式式式式 约约约约 束束束束（explicitconstraint）。）。对对给给定定的的一一个个问问题题实实例例，显显式式约约束束规规定定了了所所有有可可能能的的元元组组(候候选选解解)，它它们们组组成成问问题题的的候候选选解解集集，被称为该问题实例的被称为该问题实例的解空间解空间（solutionspace）。）。隐隐隐隐式式式式约约约约束束束束（implicitconstraint）给给出出了了判判定定一一个候选解是否为可行解的条件。个候选解是否为可行解的条件。目目目目标标标标函函函函数数数数，也也称称代代价价函函数数（costfunction），用用来来衡衡量量每每个个可可行行解解的的优优劣劣。使使目目标标函函数数取取最最大大（或或最最小）值的可行解为问题的最优解。小）值的可行解为问题的最优解。状状状状态态态态空空空空间间间间树树树树（statespace）是是描描述述问问题题解解空空间间的的树树形形 结结 构构。树树 中中 每每 个个 结结 点点 称称 为为 一一 个个 问问问问 题题题题 状状状状 态态态态（problemstate）。如如果果从从根根到到树树中中某某个个状状态态的的路路径径代代表表了了一一个个作作为为候候选选解解的的元元组组，则则称称该该状状态态为为解解解解状状状状态态态态（solutionstate）。如如果果从从根根到到某某个个解解状状态态的的路路径径代代表表一一个个作作为为可可行行解解的的元元组组，则则称称该该解解状状态态为为答案状态答案状态答案状态答案状态(answerstate)。例例 0/1背包问题背包问题MM，n n；w wi i,p,pi i(x(x0 0,x,x1 1,x,x2 2,x,x3 3)显示约束：显示约束：显示约束：显示约束：x xi i00，11隐式约束：隐式约束：隐式约束：隐式约束：x xi iw wi iMM目标函数：目标函数：目标函数：目标函数：x xi ip pi i当当当当n=3n=3时对应的状态空间时对应的状态空间时对应的状态空间时对应的状态空间树树树树树中总结点数树中总结点数树中总结点数树中总结点数2 2n n0 0 0 01 1 1 10 0 0 01 1 1 10 0 0 01 1 1 1 0 0 0 01 1 1 10 0 0 01 1 1 10 0 0 01 1 1 1 0 0 0 01 1 1 1第第第第1 1 1 1层层层层第第第第2 2 2 2层层层层第第第第3 3 3 3层层层层第第第第3 3 3 3层层层层 例例 0/1背包问题背包问题元素元素元素元素a a0 0,a,a1 1,a,an-1n-1排序问题排序问题排序问题排序问题解向量（解向量（解向量（解向量（x x1 1,x,x2 2,x,xn-1n-1),),显示约束：显示约束：显示约束：显示约束：x xi i0,1,n-10,1,n-1且且且且x xi ixxj j(ijij)隐式约束：隐式约束：隐式约束：隐式约束：x xi ixxj j(ij)(ij)无目标函数无目标函数无目标函数无目标函数(13,24,09)(13,24,09)树中总结点数树中总结点数树中总结点数树中总结点数n!n!8.1.2剪枝函数和回溯法剪枝函数和回溯法为为了了提提高高搜搜索索效效率率，在在搜搜索索过过程程中中使使用用约约约约束束束束函函函函数数数数（constraintfunction），可可以以避避免免无无谓谓地地搜搜索索那那些些已知不含答案状态的子树。已知不含答案状态的子树。如如果果是是最最优优化化问问题题，还还可可使使用用限限限限界界界界函函函函数数数数（boundfunction）剪剪去去那那些些不不可可能能包包含含最最优优答答案案结结点点的的子子树树。约约束束函函数数和和限限界界函函数数的的目目的的是是相相同同的的，都都为为了了剪剪去去不不必必要要搜搜索索的的子子树树，减减少少问问题题求求解解所所需需实实际际生生成成的的状状态态结结点点数数，它它们们统统称称为为剪剪剪剪枝枝枝枝函函函函数数数数（pruningfunction）。）。使使用用剪剪枝枝函函数数的的深深度度优优先先生生成成状状态态空空间间树树中中结结点点的求解方法称为的求解方法称为回溯法回溯法回溯法回溯法（backtracking）；）；广广度度优优先先生生成成结结点点，并并使使用用剪剪枝枝函函数数的的方方法法称称为为分枝限界法分枝限界法分枝限界法分枝限界法（branch-and-bound）。）。【程序程序程序程序8 81 1】递归回溯法递归回溯法递归回溯法递归回溯法VoidRBacktrack(intk)/应以应以Rbacktrack(0)调用本函数调用本函数for(每个每个xk,使得使得xk T(x0,xk-1)&(Bk(x0,xk)if(x0,x1,xk)是一个可行解是一个可行解)输出输出(x0,x1,xk);RBacktrack(k+1);T(x0,T(x0,xk-1),xk-1)代表代表x xk k所有可能取值所有可能取值约束函数约束函数 B Bk k(x0,(x0,xk),xk)部分向量部分向量(x0,(x0,xk-1),xk-1)代表从根到一个问题状态代表从根到一个问题状态Y Y的路径的路径 【程序程序程序程序8-28-2】迭代回溯法迭代回溯法迭代回溯法迭代回溯法VoidIBacktrack(intn)intk=0;while(k=0)if(还剩下尚未检测的还剩下尚未检测的xk，使得使得xk T(x0,xk-1)&Bk(x0,xk)if(x0,x1,xk)是一个可行解是一个可行解)输出输出(x0,x1,xk);k+;elsek-;8.1.3回溯法的效率分析回溯法的效率分析状态空间树种总结点数为：状态空间树种总结点数为：2 2n n,n!,n!,n nn np p(n n)是是n n的多项式，是生成一个结点所需的时间的多项式，是生成一个结点所需的时间回溯算法的回溯算法的最坏情况时间复杂度最坏情况时间复杂度最坏情况时间复杂度最坏情况时间复杂度可达可达O(p(n)n!)（或（或O(p(n)2n)或或O(p(n)nn)）。）。蒙特卡罗方法蒙特卡罗方法蒙特卡罗方法蒙特卡罗方法（MonteCarlo）。）。这种估计方法的这种估计方法的基本思想是在状态空间树中随机选择一条路径基本思想是在状态空间树中随机选择一条路径(x0,x1,xn 1)。设。设X是这条随机路径上，代表部分向是这条随机路径上，代表部分向量量(x0,x1,xk 1)的结点，的结点，如果在如果在X处不受限制的处不受限制的孩子数目是孩子数目是mk，则认为与则认为与X同层的其他结点不受限制同层的其他结点不受限制的孩子数目也都是的孩子数目也都是mk。整个状态空间树上将实际生成的结点数估计为整个状态空间树上将实际生成的结点数估计为 m=1+m0+m0m1+m0m1m2+【程序程序程序程序8-38-3】蒙特卡罗算法蒙特卡罗算法蒙特卡罗算法蒙特卡罗算法intEstimate(SType*x)intk=0,m=1,r=1;doSetTypeS=xk|xk T(x1,xk 1)&Bk(x1,xk=true)；if(!Size(S)returnm;r=r*Size(S);m=m+r;xk=Choose(S);k+;while(1);函数函数函数函数sizesizesizesize返回集合返回集合返回集合返回集合S S S S的大小；函数的大小；函数的大小；函数的大小；函数ChooseChooseChooseChoose从集合从集合从集合从集合S S S S中随机选择一个中随机选择一个中随机选择一个中随机选择一个 8.2n-皇后皇后 8.2.1问题描述问题描述n n-皇皇后后问问题题要要求求在在一一个个n n n n的的棋棋盘盘上上放放置置n n个个皇皇后后，使使得得它它们们彼彼此此不不受受“攻攻击击”。n n-皇皇后后问问题题要要求求寻寻找找在在棋棋盘盘上上放放置置这这n n个个皇皇后后的的方方案案，使使得得它它们们中中任任何何两两个都不在同一行、同一列或同一斜线上。个都不在同一行、同一列或同一斜线上。8.2.2回溯法求解回溯法求解皇后问题皇后问题皇后问题皇后问题可可用用n-元元组组（x0,x1,xn 1）表表示示n-皇皇后后问问题题的的解，其中解，其中xi表示第表示第i行的皇后所处的列号行的皇后所处的列号(0 xin)。显显式式约约束束的的一一种种观观点点是是：Si=0,1,n 1，0in。相相应应的的隐隐式式约约束束为为：对对任任意意0i,jn，当当i j时时，xi xj且且。此时的解空间大小为。此时的解空间大小为nn。另另一一种种显显式式约约束束的的观观点点是是：Si=0,1,n 1，0in，且且xi xj(0i,jn,i j)。相相应应的的隐隐式式约约束束为为：对对任任意意0i,jn，当当i j时时，。与与此此相相对对应应的的解解空间大小为空间大小为n!。皇皇后后问问题题的的状状态态空空间间树树是是一一棵棵排排排排列列列列树树树树。排排列列树树有有n!个叶结点，遍历排列树的时间为个叶结点，遍历排列树的时间为(n!)。4 4 4 4皇后问题对应的排列图皇后问题对应的排列图皇后问题对应的排列图皇后问题对应的排列图 8.2.3 n-皇后算法皇后算法 【程序程序程序程序8-48-4】n-n-皇后问题的回溯算法皇后问题的回溯算法皇后问题的回溯算法皇后问题的回溯算法boolPlace(intk,inti,int*x)/xk=i是否可行是否可行/判定两个皇后是否在同一列或在同一斜线上判定两个皇后是否在同一列或在同一斜线上for(intj=0;jk;j+)if(xj=i)|(abs(xj-i)=abs(j-k)returnfalse;returntrue;voidNQueens(intn,int*x)NQueens(0,n,x);voidNQueens(intk,intn,int*x)for(inti=0;in;i+)if(Place(k,i,x)xk=i;if(k=n-1)for(i=0;in;i+)coutxi;coutendl;elseNQueens(k+1,n,x);4 4皇后问题的两个可行解皇后问题的两个可行解 其中一个可行解的回溯过程其中一个可行解的回溯过程 实际生成的树结点实际生成的树结点 8.2.4时间分析时间分析可可通通过过蒙蒙特特卡卡罗罗法法计计算算5次次试试验验中中实实际际需需要要生生成成的的结结点点数数的的平平均均值值为为1625。8-皇皇后后问问题题状状态态空空间间树树的结点总数是：的结点总数是：因因此此，需需要要实实际际生生成成的的结结点点数数目目大大约约占占总总结结点点数数的的1.55%。8.3子集和数子集和数 8.3.1问题描述问题描述已已知知n个个不不同同正正数数wi，0 i n-1，的的集集合合，求求该该集集合合的的所所有有满满足足条条件件的的子子集集，使使得得每每个个子子集集中中的的正正数数之之和等于另一个给定的正数和等于另一个给定的正数M。例例例例8 82 2设有设有n=4个正数的集合个正数的集合W=w0,w1,w2,w3=(11,13,24,7)和和整整数数M=31，求求W的的所所有有满满足足条条件件的的子子集集，使使得得子子集集中中的的正正数数之之和和等等于于M。8.3.2回溯法求解回溯法求解 解结构形式解结构形式解结构形式解结构形式：可变长度元组和固定长度元组。：可变长度元组和固定长度元组。可可可可变变变变长长长长度度度度元元元元组组组组（x0,xk 1,xk），0 kn。元元组组的的每每个个分分量量的的取取值值可可以以是是元元素素值值，也也可可以以是是选选入入子子集的正数的下标。集的正数的下标。固固固固定定定定长长长长度度度度n-n-元元元元组组组组（x0,x1,xn 1），xi 0,1,0 in。xi=0，表表示示wi未未选选入入子子集集，xi=1，表表示示wi入入选子集。选子集。称称这这种种从从n个个元元素素的的集集合合中中找找出出满满足足某某些些性性质质的的子子集集的的状状态态空空间间树树为为子子子子集集集集树树树树。子子集集树树有有2n个个解解状状态态，遍历子集树的时间为遍历子集树的时间为(2n)。约约约约束函数：束函数：束函数：束函数：（约约约约定定定定w w w wi i i i为为为为正数按升序排列）正数按升序排列）正数按升序排列）正数按升序排列）Bk(x0,x1,xk)为为true，当且仅当当且仅当w w w w0 0 0 0,w,w,w,w1 1 1 1,w,w,w,wk-1k-1k-1k-1,w,w,w,wk k k k,w,w,w,wk+1k+1k+1k+1,w,w,w,wn-1n-1n-1n-1x x x x0 0 0 0,x,x,x,x1 1 1 1,x,x,x,xk-1k-1k-1k-1,x,x,x,xk k k k,x,x,x,xk+1k+1k+1k+1,x,x,x,xn-1n-1n-1n-1下面令下面令下面令下面令ss部分和部分和 rr剩余和剩余和x x x xk k k k=1=1=1=1x x x xk k k k=0?=0?=0?=0?8.3.3子集和数算法子集和数算法【程序程序程序程序8 85 5】子集和数的回溯算法子集和数的回溯算法子集和数的回溯算法子集和数的回溯算法 voidSumOfSub(floats,intk,floatr,int*x,floatm,float*w)/s部分和部分和r剩余和剩余和xk=1;if(s+wk=m)/得到一个可行解得到一个可行解for(intj=0;j=k;j+)coutxj;coutendl;elseif(s+wk+wk+1=m)&(s+wk+1=m)/搜索右子树搜索右子树xk=0;SumOfSub(s,k+1,r-wk,x,m,w);voidSumOfSub(int*x,intn,floatm,float*w)floatr=0;for(inti=0;i=m&w0=m)SumOfSub(0,0,r,x,m,w);例例例例8 83 3设设有有n=6个个正正数数的的集集合合W=(5,10,12,13,15,18)和和整整数数M=30，求，求W的所有元素之和为的所有元素之和为M的子集。的子集。8.4 图的着色图的着色 8.4.1问题描述问题描述已已知知无无向向图图G=(V,E)和和m种种不不同同的的颜颜色色，如如果果只只允允许许使使用用这这m种种颜颜色色对对图图G的的结结点点着着色色，每每个个结结点点着着一一种种颜颜色色。问问是是否否存存在在一一种种着着色色方方案案，使使得得图图中中任任意意相相邻邻的的两两个个结结点点都都有有不不同同的的颜颜色色。这这就就是是m-m-着着着着色色色色判判判判定问题定问题定问题定问题（m-colorabilitydecisionproblem）如：地图着色问题如：地图着色问题、四色猜想、四色猜想 8.4.2回溯法求解回溯法求解设无向图设无向图G=(V,E)采用如下定义的邻接矩阵采用如下定义的邻接矩阵a表示：表示：解的形式：解的形式：n-元组元组(x0,x1,xn1),xi 1，m,0 in，表表示示结结点点i的的颜颜色色，这这就就是是显显式式约约束束。xi=0表表示示没没有有可可用用的的颜颜色色。因因此此解解空空间的大小为间的大小为mn。隐式约束隐式约束可描述为：如果边可描述为：如果边(i,j)E，则则xi xj。约约束束函函数数：对对所所有有i和和j，0 i,jk，i j，若若aij=1，则，则xi xj。8.4.3图着色算法图着色算法【程序程序程序程序8 86 6】图的图的图的图的mm着色算法着色算法着色算法着色算法 templatevoidMGraph:NextValue(intk,intm,int*x)/确定分量确定分量xk的取值。的取值。1,m。xk初始值初始值=0doxk=(xk+1)%(m+1);/尝试下一种颜色尝试下一种颜色if(!xk)return;/没有可用颜色没有可用颜色 for(intj=0;jk;j+)/可行判定可行判定if(akj&xk=xj)break;if(j=k)return;/成功成功while(1);templatevoidMGraph:mColoring(intk,intm,int*x)doNextValue(k,m,x);/为为xk分配颜色分配颜色if(!xk)break;if(k=n-1)/得到图得到图G的一种的一种m-着色方案着色方案for(inti=0;in;i+)coutxi;coutendl;elsemColoring(k+1,m,x);/继续深入下一个分量继续深入下一个分量while(1);templatevoidMGraph:mColoring(intm,int*x)mColoring(0,m,x);8.4.4时间分析时间分析算法的计算时间上界可由状态空间树的结点数算法的计算时间上界可由状态空间树的结点数确定。确定。每每个个结结点点的的处处理理时时间间即即NextValue的的执执行行时时间间，为为O(mn)。因此总时间为因此总时间为 8.5哈密顿环哈密顿环 8.5.1问题描述问题描述已知图已知图G=(V,E)是一个是一个n个结点的连通图。连通图个结点的连通图。连通图G的一个的一个哈密顿环哈密顿环哈密顿环哈密顿环(Hamiltonlancycle)是图是图G的一个的一个回路，它经过图中每个结点，且只经过一次。一个回路，它经过图中每个结点，且只经过一次。一个哈密顿环是从某个结点哈密顿环是从某个结点v0 V开始，沿着图开始，沿着图G的的n条条边环行的一条路径（边环行的一条路径（v0,v1,vn 1,vn），），其中，其中，(vi,vi+1)E,0 in，它访问图中每个结点且只访问它访问图中每个结点且只访问一次，最后返回开始结点，即除一次，最后返回开始结点，即除v0=vn，路径上其余路径上其余结点各不相同。结点各不相同。8.5.2哈密顿环算法哈密顿环算法对于对于n个结点的图个结点的图G=(V,E)的哈密顿环问题，的哈密顿环问题，采用采用n-元组表示问题的解元组表示问题的解(x0,x1,xn1)。显显式式约约束束：每每个个xi 0,1,n-1,0 in，代代表表路路径径上上一一个结点的编号。因此解空间的大小为个结点的编号。因此解空间的大小为nn。隐隐式式约约束束：可可描描述述为为：xi xj,0 i,jn，i j，且且（xi,xi+1）E，xi,xi+1 V，i=0,1,n 2，又（又（xn1，x0）E。哈哈密密顿顿环环问问题题的的分分析析和和求求解解方方法法与与图图的的m-着着色色问问题非常相似题非常相似 【程序程序程序程序8 87 7】哈密顿环算法哈密顿环算法哈密顿环算法哈密顿环算法 templatevoidMGraph:NextValue(intk,int*x)/求第求第k个分量的取值，结点从个分量的取值，结点从1开始编号开始编号doxk=(xk+1)%n;/循循环环去去下下一一个个结结点点编编号号if(!xk)return;/为为0值，表示无可取值值，表示无可取值if(axk-1xk)/可行性判定可行性判定for(intj=0;jk;j+)if(xj=xk)break;if(j=k)if(kn-1)|(k=n-1)&axn-1x0)return;while(1);templatevoidExtMGraph:Hamiltonian(intk,int*x)/第第k个分量的递归处理个分量的递归处理doNextValue(k,x);/返回下一个可取值返回下一个可取值if(!xk)return;/无可取值，剪枝处理无可取值，剪枝处理if(k=n-1)for(inti=0;in;i+)coutxi;cout0n;elseHamiltonian(k+1,x);/深度优先进入下一层深度优先进入下一层while(1);templatevoidExtMGraph:Hamiltonian(int*x)Hamiltonian(1,x);/结点从结点从1 1开始编号开始编号 8.6 0/1背包问题背包问题问题：给定问题：给定M0,wi0,pi0(0=in),求一求一个个n元组元组(x0,x1,xn-1),xi0,1,使得使得wixi=M且且pixi最大。最大。解空间中构成一颗子集树，共有解空间中构成一颗子集树，共有2n解状态。解状态。约束条件：约束条件：x xi i0,10,1 w wi ix xi i=M=M求最优解求最优解目标函数：目标函数：目标函数：目标函数：p pi ix xi i 8.6 0/1背包问题背包问题n=4的状态空间树的状态空间树 8.6 0/1背包问题背包问题记记记记cwcw表示当前考虑表示当前考虑表示当前考虑表示当前考虑k-1k-1个物品后，已选入物品的个物品后，已选入物品的个物品后，已选入物品的个物品后，已选入物品的重量重量重量重量记记记记cpcp表示当前考虑表示当前考虑表示当前考虑表示当前考虑k-1k-1个物品后，已选入物品的收个物品后，已选入物品的收个物品后，已选入物品的收个物品后，已选入物品的收益益益益设计约束函数设计约束函数Bk(x0,x1,xk)：第第第第k k个物品要选入（个物品要选入（个物品要选入（个物品要选入（x xk k=1=1）必须满足：）必须满足：）必须满足：）必须满足：cw+wcw+wk kMM设计限界函数：剪去不含最优解的分枝设计限界函数：剪去不含最优解的分枝 8.6 0/1背包问题背包问题设计限界函数：设计限界函数：设计限界函数：设计限界函数：中间状态中间状态中间状态中间状态X X：剩余物品剩余物品k+1,k+2,n-1剩余载重为剩余载重为M=M-cw记记记记Y Y、rprp分别表示对应一般分别表示对应一般分别表示对应一般分别表示对应一般背包问题的最优解和最优解值背包问题的最优解和最优解值背包问题的最优解和最优解值背包问题的最优解和最优解值Z Z表示对应表示对应表示对应表示对应0/10/1背包问题的背包问题的背包问题的背包问题的任意可行解任意可行解任意可行解任意可行解Y=yk+1,yk+2,yn-1Z=xk+1,xk+2,xn-1则有：则有：则有：则有：因此以因此以因此以因此以bpbpbpbp=cp+rpcp+rpcp+rpcp+rp作为作为作为作为X X X X结点的上界值结点的上界值结点的上界值结点的上界值 8.6 0/1背包问题背包问题限界函数的实现限界函数的实现通过发现的可行解确定当前最优解值通过发现的可行解确定当前最优解值通过发现的可行解确定当前最优解值通过发现的可行解确定当前最优解值L L，后续的，后续的，后续的，后续的可行解收益可行解收益可行解收益可行解收益fpfp，必须不小于，必须不小于，必须不小于，必须不小于L L，也就是以，也就是以，也就是以，也就是以L L为下界为下界为下界为下界任一中间状态任一中间状态任一中间状态任一中间状态X X：若其上界值：若其上界值：若其上界值：若其上界值bpbpLL，代表其下不，代表其下不，代表其下不，代表其下不含最优解，应剪去以含最优解，应剪去以含最优解，应剪去以含最优解，应剪去以X X为根的子树。为根的子树。为根的子树。为根的子树。限界函数作用示例限界函数作用示例M=110,n=8,W=(1,11,21,23,33,43,45,55),P=(11,21,31,33,43,53,55,65)关键程序关键程序上界函数值上界函数值templatetemplateTKnapsack:TKnapsack:Bound(intBound(int k,Tk,Tcp,Tcp,Tcwcw)/cp/cp是当前收益，是当前收益，是当前收益，是当前收益，cwcw是当前背包重量，是当前背包重量，是当前背包重量，是当前背包重量，k k是当前待考察是当前待考察是当前待考察是当前待考察的物品编号的物品编号的物品编号的物品编号 Tb=cp,c=Tb=cp,c=cwcw;for(for(intinti=k+1;in;i+)i=k+1;in;i+)c+=c+=wiwi;if(cm)b+=if(cm)b+=pipi;elsereturn(b+(1-(elsereturn(b+(1-(c-m)/wic-m)/wi)*)*pipi););returnb;returnb;8.7批处理作业调度批处理作业调度(最小平均完成时间最小平均完成时间)8.7.1问题描述问题描述设设有有n n个个作作业业的的集集合合00,1 1,n-1n-1，每每个个作作业有有两两项任任务要要求求分分别别在在2 2台台设设备备P P1 1和和P P2 2上上完完成成。每每个个作作业业必必须须先先在在P P1 1上上加加工工，然然后后在在P P2 2上上加加工工。P P1 1和和P P2 2加加工工作作业业i i所所需需的的时时间间分分别别为为a ai i和和b bi i。作作业业i i的的完完成成时时间间f fi i(S(S)是是指指在在调调度度方方案案S S下下，该该作作业业的的所所有有任任务务得得以以完完成成的的时时间，则间，则是采用调度方案是采用调度方案S S的的平均完成时间平均完成时间平均完成时间平均完成时间。批批批批处处处处理理理理作作作作业业业业调调调调度度度度(batch(batch job job schedule)schedule)问问题题要要求求确确定定这这n n个个作作业业的的最最优优作作业业调调度度方方案案使使其其MFTMFT最最小小。这这等等价于求使得所有作业的完成时间之和价于求使得所有作业的完成时间之和最小的调度方案。最小的调度方案。例例例例8 85 5 设有三个作业和两台设备，作业任设有三个作业和两台设备，作业任务的处理时间为（务的处理时间为（a0,a1,a2）=(2,3,2)和（和（b0,b1,b2）=(1,1,3)。这这三个作业有三个作业有6种可能的调度方案：种可能的调度方案：(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0)它们相应的完成时间之和分别是它们相应的完成时间之和分别是19,18,20,21,19,19其中，最佳调度方案其中，最佳调度方案S=(0,2,1)。在在这一调度方案下，这一调度方案下，f0(S)=3，f1(S)=7，f2(S)=8，FT=3+7+8=18。8.7.2回溯法求解回溯法求解对对于于双双机机批批处处理理作作业业调调度度问问题题，其其可可行行解解是是n个个作作业业所所有有可可能能的的排排列列，每每一一种种排排列列代代表表一一种种作作业业调调度度方方案案S，批处理作业调度问题的状态空间树解空间的大小为批处理作业调度问题的状态空间树解空间的大小为n！。！。目标函数目标函数是是使使FT(S)具具有有最最小小值值的的调调度度方方案案或或作作业业排排列列是是问问题题的的最优解。最优解。对对于于双双机机作作业业调调度度，存存在在一一个个最最优优非非抢抢先先调调度度方方案案，使得在使得在P1和和P2上的作业完全以相同次序处理。上的作业完全以相同次序处理。求求解解这这一一问问题题没没有有有有效效的的约约束束函函数数，但但可可以以使使用用最最优优解解的的上上界界值值U U进进行行剪剪枝枝。如如果果对对于于已已经经调调度度的的作作业业子子集集的的某某种种排排列列，所所需需的的完完成成时时间间和和已已经经大大于于迄迄今今为为止止所所记记录录下下的的关关于于最最优优调调度度方方案案的的完完成成时时间间和和的的上上界界值值U,U,则则该该分分枝枝可可以以剪剪去。去。8.7.3批处理作业调度算法批处理作业调度算法 【程序程序程序程序8 8 8 89 9 9 9】批处理作业调度算法批处理作业调度算法批处理作业调度算法批处理作业调度算法classBatchJobpublic:BatchJob(intsz,int*aa,int*bb,intup)/构造构造n=sz;U=up;f=f1=0;a=newintn;b=newintn;f2=newintn;y=newintn;for(inti=0;in;i+)ai=aai;bi=bbi;yi=i;intJobSch(int*x);private:voidJobSch(inti,int*x);int*a,*b;/一维数组一维数组a,b记录作业时间记录作业时间intn,U,f,f1,*f2,*y;voidBatchJob:JobSch(inti,int*x)if(i=n)/记录迄今为止的最优解记录迄今为止的最优解 for(intj=0;jn;j+)xj=yj;U=f;/当前最优解值当前最优解值else for(intj=i;jf1)?f2i 1:f1)+byj;/设设备备2 2上上该该作业完成的时间作业完成的时间f+=f2i;if(fU)Swap(y,i,j);/?JobSch(i+1,x);Swap(y,i,j);/?f1-=ayj;f-=f2i;intBatchJob:JobSch(int*x)JobSch(0,x);returnU;