它成为下一个扩展结点。它的2个儿子H和I被插入堆中。此时 堆中元素是结点C、H、Ⅰ、J、K。在这些结点中,H具有最小费用, 成为下一个扩展结点。扩展结点H后得到一条 Hamilton圈(1,3,2, 4,1),相应的费用为25。接下来,结点J成为扩展结点,并由此得 到一条 Hamilton圈(1,4,2,3,1),费用仍为25。此后的两个扩 展结点是K和I。由结点K得到的 Hamilton圈的费用高于当前所知 最小费用,结点Ⅰ当前的费用已经高于当前所知最小费用,因而,它 们都不能得到最优解。最后,优先队列为空,算法终止。 §2优先级的确定与LC-检索 对于优先队列式分支限界法,结点优先级的确定直接影响着算法 性能。我们当然希望这样的活结点X成为当前扩展结点 1).以X为根的子树中含有问题的答案结点 2).在所有满足条件1)的活结点中,X距离答案结点“最近”。 但是,要给出可能导致答案结点的活结点附以优先级,必须要附加若 干计算工作,即要付出代价。对于任一结点,要付出的代价可以使用 两种标准来度量 (i).在生成一个答案结点之前,子树X需要生成的结点数; (ii).在子树X中离X最近的那个答案结点到X的路径长度 容易看出,如果使用度量(ⅱ),在对于每一种分枝限界算法,总是生 成最小数目的结点;如果采用度量(ii),则要成为扩展结点的结点只 是由根到最近的那个答案结点路径上的那些结点。用c(·)表示一个 理想的优先级函数,定义如下:D，它成为下一个扩展结点。它的 2 个儿子 H 和 I 被插入堆中。此时， 堆中元素是结点 C、H、I、J、K。在这些结点中，H 具有最小费用， 成为下一个扩展结点。扩展结点 H 后得到一条 Hamilton 圈（1，3，2， 4，1），相应的费用为 25。接下来，结点 J 成为扩展结点，并由此得 到一条 Hamilton 圈（1，4，2，3，1），费用仍为 25。此后的两个扩 展结点是 K 和 I。由结点 K 得到的 Hamilton 圈的费用高于当前所知 最小费用，结点 I 当前的费用已经高于当前所知最小费用，因而，它 们都不能得到最优解。最后，优先队列为空，算法终止。 §2 优先级的确定与 LC-检索 对于优先队列式分支限界法，结点优先级的确定直接影响着算法 性能。我们当然希望这样的活结点 X 成为当前扩展结点： 1).以 X 为根的子树中含有问题的答案结点； 2).在所有满足条件 1)的活结点中，X 距离答案结点“最近”。 但是，要给出可能导致答案结点的活结点附以优先级，必须要附加若 干计算工作，即要付出代价。对于任一结点，要付出的代价可以使用 两种标准来度量： (i).在生成一个答案结点之前，子树 X 需要生成的结点数； (ii).在子树 X 中离 X 最近的那个答案结点到 X 的路径长度。 容易看出，如果使用度量(i)，在对于每一种分枝限界算法，总是生 成最小数目的结点；如果采用度量(ii),则要成为扩展结点的结点只 是由根到最近的那个答案结点路径上的那些结点。用 c(·)表示一个 理想的优先级函数，定义如下：