为当前扩展结点。 队列式分支限界法的搜索解空间树的方式类似于解空间树的宽 度优先搜索,不同的是队列式分支限界法不搜索以不可行结点(已经 被判定不能导致可行解或不能导致最优解的结点)为根的子树。这是 因为,按照规则,这样的结点未被列入活结点表。 优先队列式分支限界法的搜索方式是根据活结点的优先级确定 下一个扩展结点。结点的优先级常用一个与该结点有关的数值p来表 。最大优先队列规定p值较大的结点点的优先级较髙。在算法实现 时通常用一个最大堆来实现最大优先队列,用最大堆的 Deletemax运 算抽取堆中的下一个结点作为当前扩展结点,体现最大效益优先的原 则。类似地,最小优先队列规定p值较小的结点的优先级较高。在算 法实现时,常用一个最小堆来实现,用最小堆的 Deletemin运算抽取 堆中下一个结点作为当前扩展结点,体现最小优先的原则。采用优先 队列式分支定界算法解决具体问题时,应根据问题的特点选用最大优 先或最小优先队列,确定各个结点点的p值。 例1旅行商问题,n=4,其解空间树是一棵排列树。如文档“旅 行商搜索树”。赋权图G给出如下: 30 求赋权图G的 最小权 Hamilton圈 20 采用队列式分支限界法以排列树中的结点B作为初始扩展结点。为当前扩展结点。 队列式分支限界法的搜索解空间树的方式类似于解空间树的宽 度优先搜索，不同的是队列式分支限界法不搜索以不可行结点（已经 被判定不能导致可行解或不能导致最优解的结点）为根的子树。这是 因为，按照规则，这样的结点未被列入活结点表。 优先队列式分支限界法的搜索方式是根据活结点的优先级确定 下一个扩展结点。结点的优先级常用一个与该结点有关的数值 p 来表 示。最大优先队列规定 p 值较大的结点点的优先级较高。在算法实现 时通常用一个最大堆来实现最大优先队列，用最大堆的 Deletemax 运 算抽取堆中的下一个结点作为当前扩展结点，体现最大效益优先的原 则。类似地，最小优先队列规定 p 值较小的结点的优先级较高。在算 法实现时，常用一个最小堆来实现，用最小堆的 Deletemin 运算抽取 堆中下一个结点作为当前扩展结点，体现最小优先的原则。采用优先 队列式分支定界算法解决具体问题时，应根据问题的特点选用最大优 先或最小优先队列，确定各个结点点的 p 值。 例 1 旅行商问题，n=4，其解空间树是一棵排列树。如文档“旅 行商搜索树”。赋权图 G 给出如下： 30 6 10 求赋权图 G 的 5 4 最小权 Hamilton 圈 20 采用队列式分支限界法以排列树中的结点 B 作为初始扩展结点。 1 4 2 3