第七章 分枝-限界法VIP专享VIP免费

第七章分枝-限界法一般方法分枝-限界法是在生成当前E-结点全部儿子之后，再生成其他活结点的儿子，并且使用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。根据对状态空间树中结点检索次序的不同，可将分枝-限界的设计策略分为：–FIFO检索，活结点采用一张先进先出表–LIFO检索，活结点采用一张先进后出表例7.1：4-皇后问题3955本例考察用一个FIFO分支-限界算法检索4-皇后问题的状态空间树的基本过程。起初，只有一个活结点，即结点1。这表示没有皇后被放在棋盘上。扩展这个结点，生成它的儿子结点2,18,34和50。这些结点分别表示皇后1在第1行的1,2,3,4列情况下的棋盘。现在仅有的活结点是2,18,34和50。如果按这样的次序生成这些结点，则下一个E-结点就是结点2。扩展结点2，生成结点3,8和13。利用限界函数，结点3立即被杀死，将结点8和13加到活结点队列。结点18变成下一个E-结点，生成结点19,24和29，限界函数杀死结点19和24，结点29被加到活结点队列。下一个E-结点是34。图中显示了由FIFO分枝-限界检索生成图6.2中的那棵树的一部分。由限界函数杀死的那些结点的下方有一个B字。结点内的数与图6.2所示的结点内的数对应。结点外的数给出了用FIFO分枝-限界法生成结点的次序。在到达答案结点31时，仅剩下活结点38和54。比较图6.6和图7.1可以看出，对于这个问题回溯法占优势。7.1.1LC-检索问题：在LIFO和FIFO分枝-限界法中，对下一个E-结点的选择规则相当死板，在某种意义上是盲目的。方法：对活结点使用一个“有智力”排序函数c(.)来选取下一个E-结点往往可以加快到达一答案结点的速度。对任意结点X，可用两种标准来量度：–在生成一个答案结点之前，子树X需要生成的结点数–在子树X中离X最近的那个答案结点到X的路径长度使用后一种度量，图7.1中树的根结点付出的代价是4。结点（18和34），（29和35）以及（30和38）的代价分别是3,2和1。所有在2,3和4级上剩余结点的代价应分别大于3,2和1。以这些代价作为选择下一个E-结点的依据，则E-结点依次为1,18,29和30。得以生成的其它结点仅是2,34,50,19,24,32和31。易于看出，如果使用度量1，则对于每一种分枝-限界算法，总是生成最小数目的结点。如果使用度量2，则要成为E-结点的结点只是由根到最近的那个答案结点路径上的那些结点。以后用C(.)表示“有智力的”排序函数，有称为结点的成本函数。其定义如下：如果X是答案结点，则C(X)是由状态空间树的根结点到X的成本；如果X不是答案结点且子树X不包含任何答案结点，则C(X)=∞；否则C(X)等于子树X中具有最下成本的答案结点的成本。但要指出的是：要得到结点成本函数C(.)所用的计算工作量与解原问题具有相同的复杂度，所以要得到精确的成本函数一般是不现实的。解决方法：考虑在算法中检测活结点的次序通常可以根据能大致估计结点成的函数^g(.)来排出。设^g(X)是由X到达一个答案结点所需做的附加工作的估计函数。但是单纯使用函数^g(.)并不合适，它会导致算法偏向于作纵深检查。假设结点X是当前的E-结点且它的儿子为Y，由于通常要求^g(Y)≤^g(X)，因此，活结点表中其它结点的成本估计值均大于^g(Y)，于是Y将在X之后变成E-结点；然后Y的儿子中有一个变成E-结点；接着Y的一个孙子变成E-结点等等，直到子树X全部检索完毕才可能生成那些除X子树以外的子树结点。如果^g(X)就是C(X)，这种纵深检索正是所希望的，因为这样可以用最下成本到达离根最近的答案结点，其它子树的结点无需生成。但是^g(X)仅是精确成本的估计值，因此偏向于纵深检查可能导致不能很快找到更接近根的答案结点。例如，对于结点W和Z完全可能有这样一种情况，^g(W)≤^g(Z)且Z比W更接近答案结点。此时若使用^g(.)给结点排序，必然导致对W子树作纵深检查，结果显然是不理想的。解决方法：不仅考虑结点X到一个答案结点的估计成本值，还应考虑由根结点到结点X的成本h(X)。用^c(.)来表示新的成本估计函数，使得：^c(X)=f(h(X))+^g(X)用f(.)不等于0可以减少算法作偏向于纵深检查的可能性，它可以使算法在结点W和Z之间优先检索更靠近答案结点但又离根较近的...