算法

分支限界法

 活结点：自己已经被生成，但还没有被检测的结点。

“分支”是采用广度优先的策略，依次生成E-结点所有分支，也就是所有的儿子结点。和回溯法一样，可以在生成的结点中，抛弃那些不满足约束条件的结点，其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点。

选择下一个E-结点方式的不同导致几种分支搜索方式：

搜索方式

活节点存储结构

活结点选择

FIFO搜索

First In First Out,BFS

队列

取出队首结点

LIFO搜索

Last In First Out,D-Search

栈

栈弹出一个结点

优先队列式搜索

Least Cost（最小代价）

堆

优先级最高的结点

1.一开始，根结点是唯一的活结点，根结点入队。

2.从活结点队中取出根结点后，作为当前扩展结点。

3.对当前扩展结点，先从左到右地产生它的所有儿子,用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。

4.再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。

LIFO和FIFO分枝-限界法存在的问题

对下一个E-结点的选择规则过于死板、盲目。对于有可能快速检索到一个答案结点的结点没有给出任何优先权。

对于任一结点，用该结点导致答案结点的成本（代价）来衡量该结点的优先级——成本越小越优先。

    1）如果X是答案结点，则C(X)是由状态空间树的根结点到X的成本(即所用的代价，可以是级数、计算复杂度等)

    2)  如果X不是答案结点且子树X不包含任何答案结点，则C(X)＝∞

    3)  如果X不是答案结点但子树X包含答案结点，则C(X)等于子树X中具有最小成本的答案结点的成本

计算一个结点的代价通常要检索包含一个答案结点的子树X才能确定，因此计算C(X)的工作量和复杂度与解原始问题是相同的。要得到精确的成本函数一般是不现实的,需要成本估计函数g^(X)

出现的新问题：仅利用g^(X) 会导致算法偏向纵深检查，无法有效处理下面这种情况：即g^(W)=g^(Y)，

在结点的生成过程中，需要用限界函数杀死还没有全部生成儿子结点的一些活结点——这些活结点无法满足限界函数的条件，不可能导致问题的答案。剪枝函数给出每个可行节点相应的子树可能获得的最大价值的上界，若这上界不比当前最大价值大，则剪枝。

初始U可取∞，随回答结点值的求出逐步更新为U=c(x*),x*为已知回答结点中值最小者。

在问题的解空间树中进行广度优先搜索. 找一个回答结点使其对应路径的权最小(最大)。当搜索到达一个扩展结点时,一次性扩展它的所有儿子,将那些满足约束条件且最小耗费函数≤目标函数限界的儿子,插入活动结点表中, 再从活动结点表中取下一结点同样扩展. 直到找到所需的解或活动结点表为空为止。

在当前节点（扩展节点）处，先生成其所有的儿子节点（分支），然后再从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。为了有效地选择下一个扩展节点，加速搜索的进程，在每一个活节点处，分别估算这些孩子结点的目标函数的可能取值（对最小化问题，估算结点的down，对最大化问题，估算结点的up）。如果某孩子结点的目标函数值超出目标函数的界，则将其丢弃（从此结点生成的解不会比目前已得的更好），否则入待处理表。，并根据函数值，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题。 

1.取U=U(T).

2.扩展根结点的所有儿子.对每一子结点x判定其是否满足约束条件, 

   对满足约束条件的x计算 , 将≤U的x加入活动结点表.

3. x为叶结点时,检查是否c(x)15-谜问题 分支限界---->装载问题 分支限界---->0/1背包问题