四川理工学院算法剖析.pptx

第八章 分枝-限界法;分支限界法离不开对问题状态空间树的搜索，基本搜索方法是先进先出（FIFO）搜索，它类似BFS；或者是后进先出（LIFO）搜索，它类似于DFS。 FIFO搜索法与LIFO搜索法的定义如下：对当前E-结点，先从左至右地产生它的儿子，用限界函数对这些儿子进行检查，如果不是死结点，就将它放入活结点表中，然后从活结点表中依次取出一个结点作为E-结点在生成问题的状态的方法中，需要一张活结点表。对E-结点检索完毕之后检测以队列或栈的，重复前面过程，如果只要求找出一个解，搜索进行到产生一个解为止；如果要求找出全部解，搜索进行到活结点表空为止。以队列形式存放活结点的表的检索方式称为FIFO-检索；以栈形式存放活结点的表的检索方式称为LIFO-检索。这两种方法都用限界函数杀死还没有全部生成其儿子结点的那些活结点。 ; 回溯法和分枝-限界法不一样。回溯法是当??E-结点R一旦生成一个新的儿子C，这个儿子结点就变成一个新的E-结点，当完全检索了子树C之后，R再次成为E-结点，在检索中不断地用限界函数杀死不可能成为答案结点的那些结点。回溯法相当于图的深度优先，再配之递归。而分枝-限界法中，下一个E-结点取自于对头元素或栈顶元素，一个E-结点一直保持到变成死结点为止，在检索过程中也不断地用限界函数杀死那些不可能成为答案结点的结点。它的检索顺序完全由活结点表控制，并且分支限界法适合与最优化问题。 ;为了说明这两种检索方式再看4-后问题（例4.1） 设想棋盘的风格用A(1:n,1:n)的下标标记，假定两个皇后被放置在(i,j)和(k,l)位置上，那么当且仅当i-j=k-l或i+j=k+l时，这两个皇后在同一斜角线上，将这两个等式变形j-l=i-k和j-l=k-i，因此|j-l|≠|i-k|，描述了隐式约束的第二条规定，以|j-l|≠|i-k|作为限界函数。;用FIFO检索4-后问题的状态空间树(如图8.1)的过程如下： 起初，只有一个活结点①，它表示没有皇后放入棋盘这一状态，扩展这个结点，生成它的儿子结点②，18， 34， 50，这些结点分别表示皇后1放在第一行上的1或2 或3或4列的情况下所成的棋盘格局，此刻将活结点②，18，34，50依次放入队列，从队列中取出②，作为E-结点，扩展②生成③，⑧，13，利用限界函数③被杀死，将⑧，13加入活结点队列，此时队列形如 ; 接下来，从队列中取出18作为E-结点，生成19，24,29,限界函数杀死⒆，24，结点29加入活结点队列，下一个E-结点是34，…，图8.4说明了用FIFO分枝-限界检索的过程，用限界函数杀死的那些结点的下方有一个B字，在到达答案结点31时，仅剩下活结点38以及54 仔细分析用FIFO分枝-限界检索4-后问题的状态空间树的过程，在结点29之后，30并不是马上成为E-结点，而是从活结点表中取得35作为E-结点，如果能将30作为E-结点的话，生成的儿子结点31便是答案结点。FIFO没有把如果变为现实，尽管距获得答案结点仅一步之遥，可FIFO毫不理会，固执地按活结点表的先进先出原则决定谁是下一个E-结点，直到按此刻板的顺序，轮到30作为E-结点，才生成31这个答案结点。这是一个刻板的、寻规蹈矩的方法。如果能让30有着比其它活结点表中的结点更高的优先权，在选择下一个E-结点时，按优先权作出选择，那么可大大地提前找到答案结点。如果只需找到一个答案结点，那么剩下的活结点就不必再检索了。FIFO检索带有盲目性，LIFO检索也亦如此，不再累赘叙述。下面介绍LC-检索，它克服了这种盲目性。;8.1.2 LC-检索; 如果X是答案结点，则C(X)是状态空间树中从根到X的成本（所谓成本，可以是级数，可以是上述“距离”，也可以是计算复杂度）； 如果X不是答案结点，且子树X不包含任何答案结点C(X)=∞；否则C(X)等于子树X中具有最小成本的答案结点的成本。 这个定义是递归的，用计算结点的成本函数，对结点赋予优先权是很合理的，但是仔细想一想，计算结点X的成本函数值C(X)并不容易，它和解决原问题有同样的复杂度，因此，虽然C(X)是精确的，但是却是不容易的。因此，试图在解决问题中计算结点X的成本，C(X)的方法是不可取的。; 既然精确成本不易求得，那么可以考虑计算结点的估计成本，估计成本函数g(X)≤C(X)。 g(X)易于计算。在选择下一个E-结点时，选择活结点表中g(X)最小的活结点，作为下一个E-结点。但是如果仅用g(X)作为选择下一个E-结点的标准也未必就合理，因为它会导致检索偏向纵深进行。设X是当前的E-结点，它的儿子为Y，那么g(Y)≤C(X)。因此在活结点表中的其它结点的估计成本均大于g(Y)，于是Y在X之后变成E-结点，然后