03-算法思想

6.1.1　算法思想

从根开始，常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。首先将根结点加入活结点表（用于存放活结点的数据结构），接着从活结点表中取出根结点，使其成为当前扩展结点，一次性生成其所有孩子结点，判断孩子结点是舍弃还是保留，舍弃那些导致不可行解或导致非最优解的孩子结点，其余的被保留在活结点表中。再从活结点表中取出一个活结点作为当前扩展结点，重复上述扩展过程，直到找到所需的解或活结点表为空时为止。由此可见，每一个活结点最多只有一次机会成为扩展结点。

活结点表的实现通常有两种形式：一是普通的队列，即先进先出队列；一种是优先级队列，按照某种优先级决定哪个结点为当前扩展结点，优先队列一般使用二叉堆来实现，最大堆实现最大优先队列，即优先级数值越大越优先，通常表示最大效益优先；最小堆实现最小优先队列，即优先级数值越小越优先，通常表示最小耗费优先。因此分支限界法也分为两种：

• 队列式分支限界法。
• 优先队列式分支限界法。