下载

1下载券

加入VIP
  • 专属下载券
  • 上传内容扩展
  • 资料优先审核
  • 免费资料无限下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 分支限界法的基本思想

分支限界法的基本思想.ppt

分支限界法的基本思想

oi111
2011-10-26 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《分支限界法的基本思想ppt》,可适用于IT/计算机领域

分支限界法的基本思想分支限界法的基本思想分支限界法与回溯法的不同()求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解而分支限界法的求解目标则是找出满足约束条件的一个解或是在满足约束条件的解中找出在某种意义下的最优解。()搜索方式的不同:回溯法以深度优先的方式搜索解空间树而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。分支限界法的基本思想分支限界法的基本思想分支限界法基本思想分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。在分支限界法中每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点就一次性产生其所有儿子结点。在这些儿子结点中导致不可行解或导致非最优解的儿子结点被舍弃其余儿子结点被加入活结点表中。此后从活结点表中取下一结点成为当前扩展结点并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。分支限界法的基本思想分支限界法的基本思想常见的两种分支限界法()队列式(FIFO)分支限界法按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。()优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。分支限界法(BranchandBound)在问题的边带权的解空间树中进行广度优先搜索找一个回答结点使其对应路径的权最小(最大)。当搜索到达一个扩展结点时,一次性扩展它的所有儿子,将那些满足约束条件且最小耗费函数目标函数限界的儿子,插入活动结点表中,再从活动结点表中取下一结点同样扩展直到找到所需的解或活动结点表为空为止。基本思想算法设计与分析>分支限界法用于求解最优化问题通常采用优先队列方式组织,c(x)小者优先。结点x的最小耗费函数c(x):以x为根的子树所包含的回答结点中,路权最小者。若x是回答结点,则c(x)即为该点的目标函数值若x是根结点,则c(x)即为最优解值。c(x)为单增函数。若x*是任一回答结点,且c(x*)<U,则当搜索到结点x,而c(x)>U时,x将不必扩展(剪枝)。目标函数限界U的调整:初始U可取随回答结点值的求出逐步更新为U=c(x*),x*为已知回答结点中值最小者。活动结点表:算法设计与分析>分支限界法取U=U(T)扩展根结点的所有儿子对每一子结点x判定其是否满足约束条件,对满足约束条件的x计算,将U的x加入活动结点表x为叶结点时,检查是否c(x)<U,是则用c(x)更新U取活动结点表中的第一个结点为根,重复分支限界法解题步骤:最小耗费函数c(x)的估算:c(x)不能即时求得,为此取能即时计算的下界函数代替,应具有单调性,且在回答结点上=c(x)分支限界法不仅通过约束条件,而且可通过目标函数的限界来减少无效搜索回溯法是深度优先搜索,而分支限界法是广度优先搜索采用广度优先搜索策略的目的是:尽早发现剪枝点分支限界法与回溯法的差别:问题陈述设有n个物体和一个背包,物体i的重量为wi价值为pi,背包的载荷为M,若将物体i(in,)装入背包,则有价值为pi目标是找到一个方案,使得能放入背包的物体总价值最高算法设计与分析>分枝限界法设N=,W=(,,),P=(,,),M=算法思路:问题的解可表示为n元向量{x,x,xn},xi{,}则可用排序树表示解空间,在树中做广度优先搜索,约束条件:<M目标函数:目标函数限界初值:U=c(x):以x为根的叶子中路径权值最大者:从根至x的部分路径的权值背包问题(KnapsackProblem)C=C=C=C=C=C=活动结点表:{B,C},{E,C,},{K,C,},{C},U={F,G,},{L,M,G,},C=装载问题装载问题问题描述有一批共个集装箱要装上艘载重量分别为C和C的轮船其中集装箱i的重量为Wi且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这艘轮船。如果有找出一种装载方案。容易证明:如果一个给定装载问题有解则采用下面的策略可得到最优装载方案。()首先将第一艘轮船尽可能装满()将剩余的集装箱装上第二艘轮船。装载问题装载问题队列式分支限界法在算法的while循环中首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。个儿子结点都产生后当前扩展结点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点由于队列中每一层结点之后都有一个尾部标记故在取队首元素时活结点队列一定不空。当取出的元素是时再判断当前队列是否为空。如果队列非空则将尾部标记加入活结点队列算法开始处理下一层的活结点。装载问题装载问题队列式分支限界法while(true){if(ewwi<=c)enQueue(ewwi,i)检查左儿子结点enQueue(ew,i)右儿子结点总是可行的ew=((Integer)queueremove())intValue()取下一扩展结点if(ew==){if(queueisEmpty())returnbestwqueueput(newInteger())同层结点尾部标志ew=((Integer)queueremove())intValue()取下一扩展结点i进入下一层}}装载问题装载问题算法的改进节点的左子树表示将此集装箱装上船右子树表示不将此集装箱装上船。设bestw是当前最优解ew是当前扩展结点所相应的重量r是剩余集装箱的重量。则当ewrbestw时可将其右子树剪去因为此时若要船装最多集装箱就应该把此箱装上船。另外为了确保右子树成功剪枝应该在算法每一次进入左子树的时候更新bestw的值。装载问题装载问题算法的改进检查左儿子结点intwt=ewwiif(wt<=c){可行结点if(wt>bestw)bestw=wt加入活结点队列if(i<n)queueput(newInteger(wt))}提前更新bestw检查右儿子结点if(ewr>bestwi<n)可能含最优解queueput(newInteger(ew))ew=((Integer)queueremove())intValue()取下一扩展结点右儿子剪枝装载问题装载问题构造最优解为了在算法结束后能方便地构造出与最优值相应的最优解算法必须存储相应子集树中从活结点到根结点的路径。为此目的可在每个结点处设置指向其父结点的指针并设置左、右儿子标志。privatestaticclassQNode{QNodeparent父结点booleanleftChild左儿子标志intweight结点所相应的载重量装载问题装载问题找到最优值后可以根据parent回溯到根节点找到最优解。构造当前最优解for(intj=nj>j){bestxj=(eleftChild):e=eparent}装载问题装载问题优先队列式分支限界法解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中一旦有一个叶结点成为当前扩展结点则可以断言该叶结点所相应的解即为最优解。此时可终止算法。布线问题的解空间是一个图适合采用队列式分支限界法来解决。从起始位置a开始将它作为第一个扩展结点。与该结点相邻并且可达的方格被加入到活结点队列中并且将这些方格标记为表示它们到a的距离为。接着从活结点队列中取出队首作为下一个扩展结点并将与当前扩展结点相邻且未标记过的方格标记为并存入活节点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止(表示没有通路)。布线问题:印刷电路板将布线区域划分成n*m个方格阵列。精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时电路只能沿直线或直角布线。为了避免线路相交已布了线的方格做了封锁标记其他线路不允许穿过被封锁的方格。现在来看上面两张图。演示了分支限界法的过程。最开始队列中的活结点为标的格子随后经过一个轮次活结点变为标的格子以此类推一旦b方格成为活节点便表示找到了最优方案。为什么这条路径一定就是最短的呢?这是由于我们这个搜索过程的特点所决定的假设存在一条由a至b的更短的路径b结点一定会更早地被加入到活结点队列中并得到处理。最后一个图表示了a和b之间的最短布线路径。值得一提的是在搜索的过程中我们虽然可以知道结点距起点的路径长度却无法直接获得具体的路径描述。为了构造出具体的路径我们需要从目标方格开始向起始方格回溯逐步构造出最优解也就是每次向标记距离比当前方格距离少的相邻方格移动直至到达起始方格时为止。现在我们来考虑为什么这个问题用回溯法来处理就是相当低效的。回溯法的搜索是依据深度优先的原则进行的如果我们把上下左右四个方向规定一个固定的优先顺序去进行搜索搜索会沿着某个路径一直进行下去直到碰壁才换到另一个子路径但是我们最开始根本无法判断正确的路径方向是什么这就造成了搜索的盲目和浪费。更为致命的是即使我们搜索到了一条由a至b的路径我们根本无法保证它就是所有路径中最短的这要求我们必须把整个区域的所有路径逐一搜索后才能得到最优解。正因为如此布线问题不适合用回溯法解决。算法思路:设周游路线从结点开始,解为等长数组X=(,x,xn)xi{,,n}则解空间树为排列树在树中做广度优先搜索,约束条件:xixj,ij目标函数:解向量对应的边权之和目标函数限界初值:U=c(x):以x为根的叶子中路权最大值:从根至x的部分路径的权值()()()()()()()()问题陈述:设G(V,E)是一带权有向图,V={,,…n},其耗费矩阵C=(ci,j)当(i,j)E时,记ci,j=且ci,i=问如何选择周游路线使耗费最小。算法设计与分析>分枝限界法货郎担问题()()算法设计与分析>分枝限界法规约矩阵和规约数:从耗费矩阵(ci,j)的i行(或j列)减去此行(或列)中的最小元素值称为对i行(或j列的)归约,减去的最小元素值称为该行约数,记作r(i)(r’(j)),各行各列都归约后的矩阵称为原矩阵的归约矩阵c’所有约数之和r=称为矩阵c的约数对图G的任一周游路线P,其耗费为:=r因此,求耗费矩阵为c的最小周游路线等价于求耗费矩阵为c’的最小周游路线,且r为原周游路线耗费的下界取约数r为根结点的下界函数,而c’为根结点对应的归约矩阵用同样方法求出每一点x的归约矩阵及约数(下界函数)下界函数的改进算法设计与分析>分枝限界法C=算法设计与分析>分枝限界法电路板排列例如n=,m=B={,}L={N,,N}N={,,},N={,}N={,},N={,}N={,)一种可能的排列density=问题陈述:将n个电路板B={,n}放置到机箱的插槽中,n个电路板的每一种排列定义了一种放置方法其中电路板之间若有一根导线相连的,视为一组,共有L={N,Nm}组设x表示n块电路板的一个排列即在机箱的第i个插槽中插入电路板xi电路板排列密度density(x)定义为跨越相邻电路板插槽的最大连线数。问题要求对给定电路板连接条件,确定电路板的一个排列,使density(x)最小电路板排列问题是一个NP难问题算法思路:问题的解为n元向量X={X,X,Xn},xi{n}解空间为排序树,在树中做广度优先搜索,D:()XiXj,ij时()totalj:连接块Nj中的电路板数。nowj:部分解x:i中所包含的Nj中的电路板数。连接块Ni的连线跨越插槽i和iiffnowj>且nowjtotalj目标函数:density(X)c(i):以i为根的叶子中路权(density值)最大者:从根至i的部分路径长算法设计与分析>分枝限界法算法设计与分析>回溯法第七章概率算法简介概率算法是指某些步骤中的某些动作时随机性的解决实际问题P的概率算法A’定义如下:设I是P的一个实例,I的规模|I|=n在用A’解I的某些时刻随机地选取一数b(<=b<=n),bi表示第i次选择br=(bbbm)表示m次随机选取b的序列。由b决定算法的下一步选取除了选取bi的动作外A’的其它动作是确定的。为简单起见设选取r的概率是相等的。概率算法是一般算法随机化后的结果它没有扩大原有的可计算函数的范围所以不会影响已有的可计算性概念和结果。设计概率算法的步骤如下:()对给定问题设计一个确定算法A()分析算法A的各个步骤及每一步骤的有关操作以选定随机化的入口和随机化方式从而将算法A随机化得到概率算法A’()论证A’是一个好的算法即证明:A’的正确性和A’比A更好。在分析算法A’的耗费时,要确定随机变量的耗费函数并根据问题的特征和采取的随机模式(通常等概率)进行平均耗费的估算算法设计与分析>回溯法设b、n是自然数,<b<n,令W(b)表示条件:bnlmodn或存在i,(n)i=k是整数且<GCD(bk,b)<n当W(b)成立时n必为合数,这时称b是n为合数的证人。例判定n是否为素数的概率算法算法:随机选取m个数<=b,bm<=n,对每个bi检查W(bi)否成立如有一成立,则n必为合数,如对所选序列r=(b,b,bm)W(bi)都不成立则可推得n为素数该算法的出错概率为/m耗费为O(mlogn)通常的方法是求出n的全部因子以判断n是否为素数这种方法的耗费为O(n)。

用户评价(0)

关闭

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

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

提示

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

评分:

/24

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利