第6章-限界剪枝法.ppt

算法设计与分析第6章限界剪枝法,第六章分支限界法,本章主要知识点6.1分支限界法的基本思想6.2单源最短路径问题6.3装载问题6.4布线问题6.501背包问题6.6最大团问题6.7旅行售货员问题6.8电路板排列问题6.9批处理作业调度,2,一限界剪枝法的基本思想,1.限界剪枝法与回溯法的不同（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,2.限界剪枝法基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,3.常见的两种分支限界法（1）队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。,基本思想,2、启发式搜索,3、提前剪去不含最优解的分枝,1、以回溯为基础，求最优解,二最小耗费搜索法,D(y2),C(x)=minD(y)|yTxA,D(y1),C(x)=,最小耗费搜索法,10,5,12,7,14,9,17,最小耗费搜索法,10,5,12,7,14,9,17,5,5,14,9,9,14,5,10,10,5,最小耗费搜索法,下界估值函数C(x)C(x)是C(x)的下界估值C(x)可即时计算当x为解结点时，C(x)=C(x)=D(x),下界估值越小，分枝含有最优解的可能越大。,优先搜索下界估值最小的结点，则第一个待扩展的解结点为最优解。,最小耗费搜索法,最小耗费搜索法最小耗费搜索法的算法描述设T为状态空间树的根结点；C(x)为耗费估计函数；初始化优先队列Q；计算C(T)，并将T入队；循环，直到队列Q空（无解）：结点e出队；若e是回答结点，则输出解或求解路径，求解结束；否则检查e的所有子结点x：若x满足约束条件，则计算C(x)，并将x入队；记录搜索路径；当C(x)满足：C(x)C(x)，C(x)单调，解结点的C(x)=C(x)时，上述算法可以正确找到C(x)的最小耗费解；,对活结点表中的任一结点x，有C(e)C(x)，对x分枝中的任一解结点y，有C(x)C(y)=D(y)，又知：C(e)=C(e)=D(e)，则D(e)D(y)。,最小耗费搜索法,最小耗费搜索法15迷问题用布局作为问题状态，用空格的移动来表述状态的演化；用根结点到解结点的路径长度作为耗费函数；而用根到当前结点的路径长度加上当前结点与目标解的差异量作为耗费估计函数；,最小耗费搜索法,最小耗费搜索法15迷问题布局结构描述布局结点不仅包括数字位的分布情况，还包括已经推演的步数和与目标布局的差异，以及指向父结点的指针。算法描述初始化集合S=，记录曾经出现过的布局；初始化优先队列Q，以布局的C(x)作为权值；起始布局入队，并记入S；循环，直至队列空布局T出队；若T为目标布局，则从T倒推出移动步骤，求解结束；将T的所有未处理的可推演布局入队，并记入S；,procedureLC(T,C)(EMPTY(Q)在Q为空时返回true，否则返回false。)beginifT的根是一个回答结点then输出T的根elsebeginMAKENULL(Q);计算C（T）;INSERT(T,Q);whilenotEMPTY(Q)dobegine:=DELETEMIN(Q)；fore的每个儿子结点xdoifx满足约束条件thenbeginifx是回答结点thenbegin输出从T到x的逆路径;return;end；计算C(x)；INSERT(x,Q);x.parent=e;end;end；print“没有回答结点”end;end；,在找到一个回答结点或当整个状态空间树被搜索完，算法LC(T，C)才终止。对算法LC作适当修改，可以使算法在找到一个最小C(x)回答结点时结束。下面的算法LCl(T，C)是经过修改后的算法，它的终止条件改为当前扩展结点是一个回答结点。,procedureLC1(T,C)beginMAKENULL(Q)；计算C(T)；INSERT(T,Q)；whilenotEMPTY(Q)dobegine:=DELETEMIN(Q)；ife是回答结点thenbegin输出从T到e的逆路径；return；end；fore的每一个儿子结点doifx满足约束条件thenbegin计算C(x)；INSERT(x,Q)；x.parent:=e；end；end；print“没有回答结点”；end；,三限界剪枝法,限界与剪枝在解结点集合上定义目标函数F(x)，求解解结点集上的离散最优化问题；类似最小耗费搜索法，定义耗费函数C(x)：C(x)=minD(y)|yTxATxAC(x)=TxA=C(x)为单调非减函数；同样地，由于C(x)无法做即时计算，引入估值函数C(x)，满足条件：C(x)C(x)；对解结点x，C(x)=C(x)；,限界剪枝法,限界与剪枝为了进一步避免无效搜索，若能找到最优解的耗费上界U，即对于最优解结点x*，有C(x*)U，则：在进行最小耗费搜索时，对于待展开的状态结点y，若C(y)U，则由C(x)的单调性和C(x)是C(x)的下界可知：UU，则该结点不入队（不激活）；在结点x入队时，检查，若u(x)U，则不须对x进行扩展，避免无效搜索；,限界剪枝法,限界与剪枝限界剪枝法的算法描述设T为状态空间树的根结点；C(x)为耗费估计函数；初始化优先队列Q，初始化U=u(T)；计算C(T)，并将T入队；循环，直到队列Q空（无解）：结点e出队；若e是回答结点，则输出解或求解路径，求解结束；否则，若C(e)U，则检查e的所有子结点x，若x满足约束条件，则计算C(x)，若C(x)U，则将x入队，并计算u(x)；若u(x)U，于是结束搜索。找到的周游路线为1，4，2，5，3，1，其耗费28是最小。,关于旅行售货员问题的