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

《《算法设计与分析》第08章概要优秀PPT.ppt》由会员分享，可在线阅读，更多相关《《算法设计与分析》第08章概要优秀PPT.ppt（72页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析算法设计与分析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批处理作业

2、调度批处理作业调度批处理作业调度批处理作业调度 8.1一般方法一般方法 8.1.1基本概念基本概念解以向量形式表示：解以向量形式表示：(x0,x2,xn-1)规规定定每每个个xi取取值值的的约约束束条条件件称称为为显显式式约约束束（explicitconstraint）。）。对对给给定定的的一一个个问问题题实实例例，显显式式约约束束规规定定了了全全部部可可能能的的元元组组(候候选选解解)，它它们们组组成成问问题题的的候候选选解解集集，被称为该问题实例的解空间（被称为该问题实例的解空间（solutionspace）。）。隐隐式式约约束束（implicitconstraint）给给出出了了判判定定

3、一一个候选解是否为可行解的条件。个候选解是否为可行解的条件。目目目目标标标标函函函函数数数数，也也也也称称称称代代代代价价价价函函函函数数数数（costcostfunctionfunction），用用用用来来来来衡衡衡衡量量量量每每每每个个个个可可可可行行行行解解解解的的的的优优优优劣劣劣劣。使使使使目目目目标标标标函函函函数数数数取取取取最最最最大大大大（或或或或最最最最小）值的可行解为问题的最优解。小）值的可行解为问题的最优解。小）值的可行解为问题的最优解。小）值的可行解为问题的最优解。状状状状态态态态空空空空间间间间树树树树（statestatespacespace）是是是是描描描描述述

4、述述问问问问题题题题解解解解空空空空间间间间的的的的树树树树形形形形 结结结结 构构构构。树树树树 中中中中 每每每每 个个个个 结结结结 点点点点 称称称称 为为为为 一一一一 个个个个 问问问问 题题题题 状状状状 态态态态（problemproblemstatestate）。假假假假如如如如从从从从根根根根到到到到树树树树中中中中某某某某个个个个状状状状态态态态的的的的路路路路径径径径代代代代表表表表了了了了一一一一个个个个作作作作为为为为候候候候选选选选解解解解的的的的元元元元组组组组，则则则则称称称称该该该该状状状状态态态态为为为为解解解解状状状状态态态态（solutionsolut

5、ionstatestate）。假假假假如如如如从从从从根根根根到到到到某某某某个个个个解解解解状状状状态态态态的的的的路路路路径径径径代代代代表表表表一一一一个个个个作作作作为为为为可可可可行行行行解解解解的的的的元元元元组组组组，则则则则称称称称该该该该解解解解状状状状态态态态为为为为答案状态答案状态答案状态答案状态(answerstate)(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隐式约束：隐式约束：隐式约束：隐式约束

6、：xxi iw wi iMM目标函数：目标函数：目标函数：目标函数：xxi 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背包问题背包问题元素元素

7、元素元素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(ij)(ij)隐式约束：隐式约束：隐式约束：隐式约束：x xi ixxj j(ij)(ij)无目标函数无目标函数无目标函数无目标函数(13,24,09)(13,24,09)树中总结点数树中总结点数树中总结点数树中总结点数n!n!8.1.2剪枝函数和回溯法剪枝函数和回溯法为为了了提提高高搜搜寻寻效效率率，在在搜搜寻寻

8、过过程程中中运运用用约约束束函函数数（constraintfunction），可可以以避避开开无无谓谓地地搜搜寻寻那那些些已知不含答案状态的子树。已知不含答案状态的子树。假假如如是是最最优优化化问问题题，还还可可运运用用限限界界函函数数（boundfunction）剪剪去去那那些些不不行行能能包包含含最最优优答答案案结结点点的的子子树树。约约束束函函数数和和限限界界函函数数的的目目的的是是相相同同的的，都都为为了了剪剪去去不不必必要要搜搜寻寻的的子子树树，削削减减问问题题求求解解所所需需实实际际生生成成的的状状态态结结点点数数，它它们们统统称称为为剪剪枝枝函函数数（pruningfunctio

9、n）。）。运运用用剪剪枝枝函函数数的的深深度度优优先先生生成成状状态态空空间间树树中中结结点点的求解方法称为回溯法（的求解方法称为回溯法（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)是一个可行解是

10、一个可行解)输出输出(x0,x1,xk);RBacktrack(k+1);T(x0,T(x0,xk-1),xk-1)代表代表xkxk全部可能取值全部可能取值约束函数约束函数 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

11、)是一个可行解是一个可行解)输出输出(x0,x1,xk);k+;elsek-;回溯法的效率分析回溯法的效率分析状态空间树种总结点数为：状态空间树种总结点数为：2n,n!,nn2n,n!,nnp(n)p(n)是是n n的多项式，是生成一个结点所需的时间的多项式，是生成一个结点所需的时间回溯算法的最坏状况时间困难度可达回溯算法的最坏状况时间困难度可达O(p(n)n!)O(p(n)n!)（或（或O(p(n)2n)O(p(n)2n)或或O(p(n)nn)O(p(n)nn)）。）。蒙特卡罗方法（蒙特卡罗方法（蒙特卡罗方法（蒙特卡罗方法（MonteCarloMonteCarlo）。这种估计方法的）。这种估

12、计方法的）。这种估计方法的）。这种估计方法的基本思想是在状态空间树中随机选择一条路径基本思想是在状态空间树中随机选择一条路径基本思想是在状态空间树中随机选择一条路径基本思想是在状态空间树中随机选择一条路径(x0,(x0,x1,xnx1,xn1)1)。设。设。设。设X X是这条随机路径上，代表部分向是这条随机路径上，代表部分向是这条随机路径上，代表部分向是这条随机路径上，代表部分向量量量量(x0,x1,xk(x0,x1,xk1)1)的结点，假如在的结点，假如在的结点，假如在的结点，假如在X X处不受限制的处不受限制的处不受限制的处不受限制的孩子数目是孩子数目是孩子数目是孩子数目是mkmk，则认为

13、与，则认为与，则认为与，则认为与X X同层的其他结点不受限同层的其他结点不受限同层的其他结点不受限同层的其他结点不受限制的孩子数目也都是制的孩子数目也都是制的孩子数目也都是制的孩子数目也都是mkmk。整个状态空间树上将实际生成的结点数估计为整个状态空间树上将实际生成的结点数估计为整个状态空间树上将实际生成的结点数估计为整个状态空间树上将实际生成的结点数估计为m=1+m0+m0m1+m0m1m2+m=1+m0+m0m1+m0m1m2+【程序程序程序程序8-38-3】蒙特卡罗算法蒙特卡罗算法蒙特卡罗算法蒙特卡罗算法intEstimate(SType*x)intk=0,m=1,r=1;doSetTy

14、peS=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的的棋棋盘盘上

15、上放放置置n n个个皇皇后后，使使得得它它们们彼彼此此不不受受“攻攻击击”。n-n-皇皇后后问问题题要要求求找找寻寻在在棋棋盘盘上上放放置置这这n n个个皇皇后后的的方方案案，使使得得它它们们中中任任何何两两个都不在同一行、同一列或同一斜线上。个都不在同一行、同一列或同一斜线上。8.2.2回溯法求解回溯法求解皇后问题皇后问题皇后问题皇后问题可可可可用用用用n-n-n-n-元元元元组组组组（x0,x0,x0,x0,x1,x1,x1,x1,xnxnxnxn1 1 1 1）表表表表示示示示n-n-n-n-皇皇皇皇后后后后问问问问题题题题的的的的解解解解，其其其其中中中中xixixixi表表表表示示示

16、示第第第第i i i i行行行行的的的的皇皇皇皇后后后后所所所所处处处处的的的的列列列列号号号号(0 xi(0 xi(0 xi(0 xin)n)n)n)。显显显显式式式式约约约约束束束束的的的的一一一一种种种种观观观观点点点点是是是是：Si=0,Si=0,Si=0,Si=0,1,1,1,1,n n n n1111，0i0i0i0in n n n。相相相相应应应应的的的的隐隐隐隐式式式式约约约约束束束束为为为为：对对对对随随随随意意意意0i,0i,0i,0i,j j j jn n n n，当当当当i i i i j j j j时，时，时，时，xixixixi xjxjxjxj且且且且 。此时的解

17、空间大小为。此时的解空间大小为。此时的解空间大小为。此时的解空间大小为nnnnnnnn。另另另另一一一一种种种种显显显显式式式式约约约约束束束束的的的的观观观观点点点点是是是是：Si=0,Si=0,Si=0,Si=0,1,1,1,1,n n n n1111，0i0i0i0in n n n，且且且且xi xi xi xi xj(0i,xj(0i,xj(0i,xj(0i,j j j jn,n,n,n,i i i i j)j)j)j)。相相相相应应应应的的的的隐隐隐隐式式式式约约约约束束束束为为为为：对对对对随随随随意意意意0i,0i,0i,0i,j j j jn n n n，当当当当i i i i

18、 j j j j时时时时，。与与与与此相对应的解空间大小为此相对应的解空间大小为此相对应的解空间大小为此相对应的解空间大小为n!n!n!n!。皇皇后后问问题题的的状状态态空空间间树树是是一一棵棵排排排排列列列列树树树树。排排列列树树有有n!个叶结点，遍历排列树的时间为个叶结点，遍历排列树的时间为(n!)。4 4 4 4皇后问题对应的排列图皇后问题对应的排列图皇后问题对应的排列图皇后问题对应的排列图 8.2.3 n-皇后算法皇后算法 【程序程序程序程序8-48-4】n-n-皇后问题的回溯算法皇后问题的回溯算法皇后问题的回溯算法皇后问题的回溯算法boolPlace(intk,inti,int*x)

19、/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皇后问题的两个可行解皇后问题

20、的两个可行解 其中一个可行解的回溯过程其中一个可行解的回溯过程 实际生成的树结点实际生成的树结点 8.2.4时间分析时间分析可可通通过过蒙蒙特特卡卡罗罗法法计计算算5次次试试验验中中实实际际须须要要生生成成的的结结点点数数的的平平均均值值为为1625。8-皇皇后后问问题题状状态态空空间间树树的结点总数是：的结点总数是：因因此此，须须要要实实际际生生成成的的结结点点数数目目大大约约占占总总结结点点数数的的1.55%。8.3子集和数子集和数 问题描述问题描述已已已已知知知知n n个个个个不不不不同同同同正正正正数数数数wiwi，0 0i in-1n-1，的的的的集集集集合合合合，求求求求该该该该集

21、集集集合合合合的的的的全全全全部部部部满满满满足足足足条条条条件件件件的的的的子子子子集集集集，使使使使得得得得每每每每个个个个子子子子集集集集中中中中的的的的正正正正数数数数之之之之和和和和等等等等于另一个给定的正数于另一个给定的正数于另一个给定的正数于另一个给定的正数MM。例例例例8 822设有设有设有设有n=4n=4个正数的集合个正数的集合个正数的集合个正数的集合W=w0,w1,w2,w3=(11,13,24,7)W=w0,w1,w2,w3=(11,13,24,7)和和和和整整整整数数数数M=31M=31，求求求求WW的的的的全全全全部部部部满满满满足足足足条条条条件件件件的的的的子子子

22、子集集集集，使使使使得得得得子子子子集集集集中中中中的的的的正正正正数数数数之之之之和和和和等等等等于于于于MM。8.3.2回溯法求解回溯法求解 解结构形式：可变长度元组和固定长度元组。解结构形式：可变长度元组和固定长度元组。解结构形式：可变长度元组和固定长度元组。解结构形式：可变长度元组和固定长度元组。可可可可变变变变长长长长度度度度元元元元组组组组（x0,x0,xk,xk1,xk1,xk），0 0knkn。元元元元组组组组的的的的每每每每个个个个重重重重量量量量的的的的取取取取值值值值可可可可以以以以是是是是元元元元素素素素值值值值，也也也也可可可可以以以以是是是是选选选选入入入入子子子子

23、集集集集的正数的下标。的正数的下标。的正数的下标。的正数的下标。固固固固定定定定长长长长度度度度n-n-元元元元组组组组（x0,x1,x0,x1,xn,xn1 1），xixi 0,1,0,1,0 0inin。xi=0 xi=0，表表表表示示示示wiwi未未未未选选选选入入入入子子子子集集集集，xi=1xi=1，表表表表示示示示wiwi入入入入选子集。选子集。选子集。选子集。称称这这种种从从n个个元元素素的的集集合合中中找找出出满满足足某某些些性性质质的的子子集集的的状状态态空空间间树树为为子子集集树树。子子集集树树有有2n个个解解状状态态，遍历子集树的时间为遍历子集树的时间为(2n)。约约束函

24、数：束函数：束函数：束函数：（约约定定定定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-

25、1n-1下面令下面令下面令下面令ss部分和部分和 r r剩余和剩余和x x x xk k k k=1=1=1=1x x x xk k k k=0?=0?=0?=0?子集和数算法子集和数算法【程序【程序【程序【程序8 85 5】子集和数的回溯算法子集和数的回溯算法子集和数的回溯算法子集和数的回溯算法 voidvoidSumOfSubSumOfSub(float(floats,s,intintk,k,floatfloatr,r,int*int*x,x,floatfloatm,float*w)m,float*w)/s/s部分和部分和部分和部分和rr剩余和剩余和剩余和剩余和xk=1;xk=1;if(s

26、+wk=m)if(s+wk=m)/得到一个可行解得到一个可行解得到一个可行解得到一个可行解for(intj=0;j=k;j+)coutxj;for(intj=0;j=k;j+)coutxj;coutendl;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 833设设设设有有有有n=6n=6个

27、个个个正正正正数数数数的的的的集集集集合合合合W=(5,10,12,13,15,18)W=(5,10,12,13,15,18)和和和和整整整整数数数数M=30M=30，求，求，求，求WW的全部元素之和为的全部元素之和为的全部元素之和为的全部元素之和为MM的子集。的子集。的子集。的子集。8.4 图的着色图的着色 问题描述问题描述已已已已知知知知无无无无向向向向图图图图G=(V,E)G=(V,E)和和和和mm种种种种不不不不同同同同的的的的颜颜颜颜色色色色，假假假假如如如如只只只只允允允允许许许许运运运运用用用用这这这这mm种种种种颜颜颜颜色色色色对对对对图图图图GG的的的的结结结结点点点点着着着

28、着色色色色，每每每每个个个个结结结结点点点点着着着着一一一一种种种种颜颜颜颜色色色色。问问问问是是是是否否否否存存存存在在在在一一一一种种种种着着着着色色色色方方方方案案案案，使使使使得得得得图图图图中中中中随随随随意意意意相相相相邻邻邻邻的的的的两两两两个个个个结结结结点点点点都都都都有有有有不不不不同同同同的的的的颜颜颜颜色色色色。这这这这就就就就是是是是m-m-着着着着色色色色判判判判定问题（定问题（定问题（定问题（m-colorabilitydecisionproblemm-colorabilitydecisionproblem）如：地图着色问题如：地图着色问题如：地图着色问题如：地图

29、着色问题、四色猜想、四色猜想、四色猜想、四色猜想 回溯法求解回溯法求解设无向图设无向图设无向图设无向图G=(V,E)G=(V,E)接受如下定义的邻接矩阵接受如下定义的邻接矩阵接受如下定义的邻接矩阵接受如下定义的邻接矩阵a a表示：表示：表示：表示：解的形式：解的形式：解的形式：解的形式：n-n-元组元组元组元组(x0,x1,(x0,x1,xn,xn1),1),xixi 11，m,m,0 0inin，表表表表示示示示结结结结点点点点i i的的的的颜颜颜颜色色色色，这这这这就就就就是是是是显显显显式式式式约约约约束束束束。xi=0 xi=0表表表表示示示示没没没没有有有有可可可可用用用用的的的的颜

30、颜颜颜色色色色。因因因因此此此此解解解解空空空空间间间间的大小为的大小为的大小为的大小为mnmn。隐式约束可描述为：假如边隐式约束可描述为：假如边隐式约束可描述为：假如边隐式约束可描述为：假如边(i,j)(i,j)E E，则，则，则，则xixi xjxj。约约束束函函数数：对对全全部部i和和j，0i,jk，i j，若若aij=1，则则xi xj。8.4.3图着色算法图着色算法【程序【程序【程序【程序8 86 6】图的图的图的图的mm着色算法着色算法着色算法着色算法 templatetemplatevoidMGraph:NextValue(intk,intm,int*x)voidMGraph:N

31、extValue(intk,intm,int*x)/确定重量确定重量确定重量确定重量xkxk的取值。的取值。的取值。的取值。1,m1,m。xkxk初始值初始值初始值初始值=0=0dodoxk=(xk+1)%(m+1);xk=(xk+1)%(m+1);/尝尝尝尝试试试试下下下下一一一一种种种种颜颜颜颜色色色色if(!xk)return;if(!xk)return;/没没没没有有有有可可可可用用用用颜色颜色颜色颜色 for(intj=0;jk;j+)for(intj=0;jk;j+)/可行判定可行判定可行判定可行判定if(akj&xk=xj)break;if(akj&xk=xj)break;if(

32、j=k)return;if(j=k)return;/成功成功成功成功 while(1);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)

33、mColoring(0,m,x);8.4.4时间分析时间分析算法的计算时间上界可由状态空间树的结点数算法的计算时间上界可由状态空间树的结点数确定。确定。每每个个结结点点的的处处理理时时间间即即NextValue的的执执行行时时间间，为为O(mn)。因此总时间为因此总时间为 8.5哈密顿环哈密顿环 问题描述问题描述已知图已知图G=(V,E)是一个是一个n个结点的连通图。连通图个结点的连通图。连通图G的一个哈密顿环的一个哈密顿环(Hamiltonlancycle)是图是图G的一个的一个回路，它经过图中每个结点，且只经过一次。一个回路，它经过图中每个结点，且只经过一次。一个哈密顿环是从某个结点哈密顿

34、环是从某个结点v0 V起先，沿着图起先，沿着图G的的n条条边环行的一条路径（边环行的一条路径（v0,v1,vn1,vn），其中，），其中，(vi,vi+1)E,0in，它访问图中每个结点且只访问，它访问图中每个结点且只访问一次，最终返回起先结点，即除一次，最终返回起先结点，即除v0=vn，路径上其，路径上其余结点各不相同。余结点各不相同。8.5.2哈密顿环算法哈密顿环算法对于对于对于对于n n个结点的图个结点的图个结点的图个结点的图G=(V,E)G=(V,E)的哈密顿环问题，的哈密顿环问题，的哈密顿环问题，的哈密顿环问题，接受接受接受接受n-n-元组表示问题的解元组表示问题的解元组表示问题的解

35、元组表示问题的解(x0,x1,(x0,x1,xn,xn1)1)。显显显显式式式式约约约约束束束束：每每每每个个个个xixi 0,1,n-1,0,1,n-1,0 0inin，代代代代表表表表路路路路径上一个结点的编号。因此解空间的大小为径上一个结点的编号。因此解空间的大小为径上一个结点的编号。因此解空间的大小为径上一个结点的编号。因此解空间的大小为nnnn。隐隐隐隐 式式式式 约约约约 束束束束：可可可可 描描描描 述述述述 为为为为：xixi xj,0 xj,0i,jni,jn，i i j j，且且且且（xi,xi+1xi,xi+1）E E，xi,xi+1xi,xi+1 V V，i=0,1,n

36、i=0,1,n2 2，又又又又（xnxn1 1，x0 x0）E E。哈哈哈哈密密密密顿顿顿顿环环环环问问问问题题题题的的的的分分分分析析析析和和和和求求求求解解解解方方方方法法法法与与与与图图图图的的的的m-m-着着着着色色色色问问问问题特殊相像题特殊相像题特殊相像题特殊相像 【程序【程序【程序【程序8 87 7】哈密顿环算法】哈密顿环算法】哈密顿环算法】哈密顿环算法 templatetemplatevoidMGraph:NextValue(intk,int*x)voidMGraph:NextValue(intk,int*x)/求第求第求第求第k k个重量的取值，结点从个重量的取值，结点从个重

37、量的取值，结点从个重量的取值，结点从1 1起先编号起先编号起先编号起先编号dodoxk=(xk+1)%n;/xk=(xk+1)%n;/循环去下一个结点编号循环去下一个结点编号循环去下一个结点编号循环去下一个结点编号if(!xk)return;/if(!xk)return;/为为为为0 0值，表示无可取值值，表示无可取值值，表示无可取值值，表示无可取值if(axk-1xk)/if(axk-1xk)/可行性判定可行性判定可行性判定可行性判定for(intj=0;jk;j+)if(xj=xk)break;for(intj=0;jk;j+)if(xj=xk)break;if(j=k)if(j=k)if

38、if(kn-1)|(k=n-1)(kn-1)|(k=n-1)&axn-axn-1x0)1x0)return;return;while(1);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

39、);templatevoidExtMGraph:Hamiltonian(int*x)Hamiltonian(1,x);/结点从结点从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,1wwi ix xi i=M=M求最优解求最优解目标函数：目标函数：目标函数：目标函数：ppi ix xi i 8.6 0/1背包问题背包问题

40、n=4的状态空间树的状态空间树 8.6 0/1背包问题背包问题记记记记cwcw表示当前考虑表示当前考虑表示当前考虑表示当前考虑k-1k-1个物品后，已选入物品的个物品后，已选入物品的个物品后，已选入物品的个物品后，已选入物品的重量重量重量重量记记记记cpcp表示当前考虑表示当前考虑表示当前考虑表示当前考虑k-1k-1个物品后，已选入物品的收个物品后，已选入物品的收个物品后，已选入物品的收个物品后，已选入物品的收益益益益设计约束函数设计约束函数设计约束函数设计约束函数Bk(x0,x1,xk)Bk(x0,x1,xk)：第第第第k k个物品要选入（个物品要选入（个物品要选入（个物品要选入（xk=1x

41、k=1）必需满足：）必需满足：）必需满足：）必需满足：cw+wkMcw+wkM设计限界函数：剪去不含最优解的分枝设计限界函数：剪去不含最优解的分枝设计限界函数：剪去不含最优解的分枝设计限界函数：剪去不含最优解的分枝 8.6 0/1背包问题背包问题l l设计限界函数：设计限界函数：设计限界函数：设计限界函数：l l中间状态中间状态中间状态中间状态X X：l l剩余物品剩余物品剩余物品剩余物品k+1,k+2,n-1k+1,k+2,n-1l l剩余载重为剩余载重为剩余载重为剩余载重为M=M-cwM=M-cwl l记记记记Y Y、rprp分别表示对应一般分别表示对应一般分别表示对应一般分别表示对应一般

42、l l背包问题的最优解和最优解背包问题的最优解和最优解背包问题的最优解和最优解背包问题的最优解和最优解值值值值l lZ Z表示对应表示对应表示对应表示对应0/10/1背包问题的背包问题的背包问题的背包问题的l l随意可行解随意可行解随意可行解随意可行解l lY=yk+1,yk+2,yn-1Y=yk+1,yk+2,yn-1l lZ=xk+1,xk+2,xn-1Z=xk+1,xk+2,xn-1l l则有：则有：则有：则有：因此以因此以因此以因此以bp=cp+rpbp=cp+rpbp=cp+rpbp=cp+rp作为作为作为作为X X X X结点的上界值结点的上界值结点的上界值结点的上界值 8.6 0

43、/1背包问题背包问题限界函数的实现限界函数的实现通过发觉的可行解确定当前最优解值通过发觉的可行解确定当前最优解值L，后，后续的可行解收益续的可行解收益fp，必需不小于，必需不小于L，也就是以，也就是以L为下界为下界任一中间状态任一中间状态X：若其上界值：若其上界值bpL，代表其，代表其下不含最优解，应剪去以下不含最优解，应剪去以X为根的子树。为根的子树。限界函数作用示例限界函数作用示例M=110,n=8,W=(1,11,21,23,33,43,45,55),P=(11,21,31,33,43,53,55,65)关键程序关键程序上界函数值上界函数值templatetemplateTKnapsac

44、k:Bound(intk,Tcp,Tcw)TKnapsack:Bound(intk,Tcp,Tcw)/cp/cp是当前收益，是当前收益，是当前收益，是当前收益，cwcw是当前背包重量，是当前背包重量，是当前背包重量，是当前背包重量，k k是当前待考察是当前待考察是当前待考察是当前待考察的物品编号的物品编号的物品编号的物品编号 Tb=cp,c=cw;Tb=cp,c=cw;for(inti=k+1;in;i+)for(inti=k+1;in;i+)c+=wi;c+=wi;if(cm)b+=pi;if(cm)b+=pi;elsereturn(b+(1-(c-m)/wi)*pi);elsereturn

45、(b+(1-(c-m)/wi)*pi);returnb;returnb;8.7批处理作业调度批处理作业调度(最小平均完成时间最小平均完成时间)8.7.1问题描述问题描述设设设设有有有有n n n n个个个个作作作作业业业业的的的的集集集集合合合合0,1,n-10,1,n-10,1,n-10,1,n-1，每每每每个个个个作作作作业业业业有有有有两两两两项项项项任任任任务务务务要要要要求求求求分分分分别别别别在在在在2 2 2 2台台台台设设设设备备备备P1P1P1P1和和和和P2P2P2P2上上上上完完完完成成成成。每每每每个个个个作作作作业业业业必必必必需需需需先先先先在在在在P1P1P1P1

46、上上上上加加加加工工工工，然然然然后后后后在在在在P2P2P2P2上上上上加加加加工工工工。P1P1P1P1和和和和P2P2P2P2加加加加工工工工作作作作业业业业i i i i所所所所需需需需的的的的时时时时间间间间分分分分别别别别为为为为aiaiaiai和和和和bibibibi。作作作作业业业业i i i i的的的的完完完完成成成成时时时时间间间间fi(S)fi(S)fi(S)fi(S)是是是是指指指指在在在在调调调调度度度度方方方方案案案案S S S S下下下下，该该该该作作作作业业业业的的的的全全全全部部部部任任任任务务务务得得得得以以以以完完完完成的时间，则成的时间，则成的时间，则成

47、的时间，则是接受调度方案是接受调度方案是接受调度方案是接受调度方案S S S S的平均完成时间。的平均完成时间。的平均完成时间。的平均完成时间。批批批批处处处处理理理理作作作作业业业业调调调调度度度度(batch(batch(batch(batch job job job job schedule)schedule)schedule)schedule)问问问问题题题题要要要要求求求求确确确确定定定定这这这这n n n n个个个个作作作作业业业业的的的的最最最最优优优优作作作作业业业业调调调调度度度度方方方方案案案案使使使使其其其其MFTMFTMFTMFT最最最最小小小小。这这这这等等等等价于求

48、使得全部作业的完成时间之和价于求使得全部作业的完成时间之和价于求使得全部作业的完成时间之和价于求使得全部作业的完成时间之和最小的调度方案。最小的调度方案。最小的调度方案。最小的调度方案。例例例例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

49、,20,21,19,19其中，最佳调度方案其中，最佳调度方案S=(0,2,1)。在在这一调度方案下，这一调度方案下，f0(S)=3，f1(S)=7，f2(S)=8，FT=3+7+8=18。回溯法求解回溯法求解对对对对于于于于双双双双机机机机批批批批处处处处理理理理作作作作业业业业调调调调度度度度问问问问题题题题，其其其其可可可可行行行行解解解解是是是是n n个个个个作作作作业业业业全全全全部部部部可可可可能能能能的的的的排排排排列列列列，每每每每一一一一种种种种排排排排列列列列代代代代表表表表一一一一种种种种作作作作业业业业调调调调度度度度方方方方案案案案S S，批批批批处处处处理理理理作作作

50、作业业业业调调调调度度度度问问问问题题题题的的的的状状状状态态态态空空空空间间间间树树树树解解解解空空空空间间间间的的的的大大大大小小小小为为为为nn！。！。！。！。目标函数是目标函数是目标函数是目标函数是使使使使FT(S)FT(S)具具具具有有有有最最最最小小小小值值值值的的的的调调调调度度度度方方方方案案案案或或或或作作作作业业业业排排排排列列列列是是是是问问问问题题题题的的的的最优解。最优解。最优解。最优解。对对对对于于于于双双双双机机机机作作作作业业业业调调调调度度度度，存存存存在在在在一一一一个个个个最最最最优优优优非非非非抢抢抢抢先先先先调调调调度度度度方方方方案案案案，使得在使得