| |
|
|
| 分支限界法类似于回溯法，也是一种在问题的解空间树上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。由于求解目标不同，导致分支限界法与回溯法在解空间树上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。分支限界法的搜索策略是，每一个活节点只有一次机会成为扩展节点。活节点一旦成为扩展节点，就一次性产生其所有儿子节点。在这些儿子节点中，那些导致不可行解或非最优解的儿子节点被舍弃，其余儿子节点被加入到活节点表中。此后，从活节点表中取下一节点成为当前扩展节点，并重复上述节点扩展过程。这个过程一直持续到找到所需的解或活节点表为空时为止。
|
|
|
| 从活节点表中选择下一扩展节点的不同方式导致不同的分支限界法。最常用的有队列式分支限界法和优先队列分支限界法。
|
|
|
|
|
|
|
|
|
|
|
|
