限界(xiànjiè)剪枝法第六章分支(fēnzhī)限界法一限界剪枝(jiǎnzhī)法的基本思想2.限界剪枝法基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些(zhèxiē)儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。3.常见的两种分支限界(xiànjiè)法（1）队列式(FIFO)分支限界(xiànjiè)法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界(xiànjiè)法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。基本(jīběn)思想二最小耗费(hàofèi)搜索法最小耗费(hàofèi)搜索法最小耗费(hàofèi)搜索法最小耗费(hàofèi)搜索法最小耗费(hàofèi)搜索法最小耗费(hàofèi)搜索法最小耗费(hàofèi)搜索法在找到一个回答结点或当整个状态空间(kōngjiān)树被搜索完，算法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的每一个(yīꞬè)儿子结点doifx满足约束条件thenbegin计算C(x)‘；INSERT(x,Q)；x↑.parent:=e；end；end；print“没有回答结点”；end；三限界(xiànjiè)剪枝法限界(xiànjiè)剪枝法限界(xiànjiè)剪枝法限界(xiànjiè)剪枝法限界(xiànjiè)剪枝法限界(xiànjiè)剪枝法∞各行的约数分别为r(1)＝10，r(2)＝2，r(3)=2，r(4)=3，r(5)=4。各列的约数分别为r‘(1)＝l，r’(2)=0，r‘(3)＝3，r’(4)=0，r＇(5)＝0。该矩阵(jǔzhèn)的约数为r＝25。从归约矩阵(jǔzhèn)的定义可以推知，对于G中的任意一条周游路线有：由此可以得出结论：求带耗费矩阵(jǔzhèn)C的有向图G的最小耗费周游路线，等价于求带有耗费矩阵(jǔzhèn)C＇的有向图G的最小耗费周游路线，而且，前者的周游路线的耗费以r为下界。因此，约数(yuēshù)r可用来作为状态空间树根结点的估值函数值。即令C＇(T)＝r，而C＇是根结点对应的归约矩阵。对于状态空间树中的其他任意结点x，我们也可建立与之相应的C＇(x)和相应的归约矩阵(jǔzhèn)。设y是任一非叶结点，Ay是与结点y相对应的归约矩阵(jǔzhèn)，x是y的儿子结点，状态空间树中的边(y，x)对应于选择图G的边(y,x)加入周游路线。旅行(lǚxíng)售货员问题从状态空间树的根出发，定义非根结点x的估值函数如下：若x不是解结点，则：设x的父结点y的归约矩阵Ay，设x是由加入边(i,j)得到的，则将Ay的第i行和第j列均置为∞，以避免选入其他以i为起点和以j为终点的边；将Aj1置为∞，以避免选入(j,1)；如此得到的矩阵就是x的归约矩阵Ax，归约于Ax的归约数(yuēshù)为rx，则定义：~C(x)=~C(y)+rx归约于矩阵Ax的归约数rx是指Ax相对于Ay的归约数的增量——由于取消了某些边的选择，可能会删除原矩阵上的行列(hángliè)归约数，而产生新的行列(hángliè)归约数；若x是解结点，则：~C(x)=C(x)若x不是叶结点，则与x相对应的归约矩阵A，可按下法得到：(1)、将Ay的第i行和第j列的所有项，除Ay(i，j)不变外，均改为∞，这将使得在后续的搜索中不会选择其他从顶点i出发的边和到达顶点j的边加入周游路线。(2)置Ay(j,1)为∞,这将使得后续搜索不会选择边(j,1)，避免(bìmiǎn)产生非周游路线的回路。(3)归约经前两步处理得到的矩阵便是所要的Ax。而x的估值函数值C＇(x)定义为C’(y)+rx。其中rx是归约于Ax的归约数。若x是叶结点，则从根到x是一条周游路线，因此可定义C＇(X)＝C(X)，而相应的归约矩阵已没有必要