此时,活结点队列为空。由于从图G的顶点1到顶点2、3和4均有 边相连,B的儿子C、D和E都是可行结点,它们被依次加入到活结 点队列中,并舍弃当前扩展结点B。当前活结点队列中的队首结点C 成为下一个扩展结点。由于图G的顶点2到顶点3和4有边相连,故 结点C的二个儿子F和G均为可行结点,可以加入活结点队列。接下 来,结点D和结点E相继成为扩展结点。此时活结点队列中的结点依 次为F、G、H、I、J、K。结点F成为下一个扩展结点,但其儿子L 是解空间树的叶结点,我们找到了一条 Hamilton圈(1,2,3,4,1), 其费用为59。下一个扩展结点G的儿子M也是叶结点,得到另一条 Hamilton圈(1,2,4,3,1),其费用为66。结点H成为当前扩展 结点,其儿子N也是叶结点,得到第三条 Hamilton圈,其费用为25, 这是当前知道的最短 Hamilton圈。下一个扩展结点是I,由于从根 结点到结点I的费用26已经超过当前最优值,故没有必要扩展I 以Ⅰ为根的子树被剪掉。最后J和K被依次扩展,活结点队列称为空 集,算法终止。算法搜索到的最优值是25,相应的最优解是从根结 点到结点N的路径(1,3,2,4,1)。 采用优先队列式分支限界法,用一个最小堆存储活结点表,优先 级函数是结点的当前费用。算法还是排列树的结点B和空优先队列开 始。结点B被扩展后,它的3个儿子C、D和E被依次插入堆中。此 时,由于E是堆中具有最小当前费用(为4)的结点,所以处于堆顶 的位置,它自然成为下一个扩展结点。结点E被扩展后,其儿子J和 K被插入当前堆中,它们的费用分别为14和24。此时,堆顶元素是此时，活结点队列为空。由于从图 G 的顶点 1 到顶点 2、3 和 4 均有 边相连，B 的儿子 C、D 和 E 都是可行结点，它们被依次加入到活结 点队列中，并舍弃当前扩展结点 B。当前活结点队列中的队首结点 C 成为下一个扩展结点。由于图 G 的顶点 2 到顶点 3 和 4 有边相连，故 结点 C 的二个儿子 F 和 G 均为可行结点，可以加入活结点队列。接下 来，结点 D 和结点 E 相继成为扩展结点。此时活结点队列中的结点依 次为 F、G、H、I、J、K。结点 F 成为下一个扩展结点，但其儿子 L 是解空间树的叶结点，我们找到了一条 Hamilton 圈（1，2，3，4，1）， 其费用为 59。下一个扩展结点 G 的儿子 M 也是叶结点，得到另一条 Hamilton 圈（1，2，4，3，1），其费用为 66。结点 H 成为当前扩展 结点，其儿子 N 也是叶结点，得到第三条 Hamilton 圈，其费用为 25， 这是当前知道的最短 Hamilton 圈。下一个扩展结点是 I，由于从根 结点到结点 I 的费用 26 已经超过当前最优值，故没有必要扩展 I， 以 I 为根的子树被剪掉。最后 J 和 K 被依次扩展，活结点队列称为空 集，算法终止。算法搜索到的最优值是 25，相应的最优解是从根结 点到结点 N 的路径（1，3，2，4，1）。 采用优先队列式分支限界法，用一个最小堆存储活结点表，优先 级函数是结点的当前费用。算法还是排列树的结点 B 和空优先队列开 始。结点 B 被扩展后，它的 3 个儿子 C、D 和 E 被依次插入堆中。此 时，由于 E 是堆中具有最小当前费用（为 4）的结点，所以处于堆顶 的位置，它自然成为下一个扩展结点。结点 E 被扩展后，其儿子 J 和 K 被插入当前堆中，它们的费用分别为 14 和 24。此时，堆顶元素是