求解目标：分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
搜索方式：以广度优先或以最小耗费优先的方式搜索解空间树。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
分支限界法示例：
单源最短路径：
问题：给定一个带权 有向图 G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有各顶点的 最短路径 长度。这里的长度就是指路上各边权之和。
分析：
分支限界法的步骤如下：
1)按宽度优先策略遍历解空间树
2)在遍历过程中，对处理的每个结点i，根据界限函数，估计沿该结点向下搜索所可能达到的完全解的目标函数的可能取值范围—界限bound(i)=[dow(i), up(i)]
3) 从中选择使目标函数取的极小值的结点优先进行宽度优先搜索，从而不断调整搜索方向，尽快找到问题解。
在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。
将这个图转化成树的形式，如下所示：
创建队列。 1．节点1入队列，Q＝｛1｝。
我们取出队头节点，作为扩散节点，更新他的后代的值。此题中更新节点2，3，4 的距离，并将他们加入队列，Q＝｛1，2，3，4｝。 完成后节点1出队。Q＝｛2，3，4｝。
2.同样，重复1的步骤，Q＝｛3，4，5，6｝；
3.当我们取到节点3时，我们发现源点－＞节点3－＞节点6的距离为11，大于1－2－6这条路径的权重，所以1－3－6这条路径之后我们不再考虑。 这就是“限界”（称为”剪枝“）的思想。
4. 重复步骤，直到Q为空。优先队列法方法和FIFO方法类似，区别在于优先队列每次取队列元素中到源点距离最短的点。
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 7 19:03:09 2021
@author: iron
"""
# Author:Iron
# 初始化图参数 用字典初始初始化这个图
G = {1: { 2: 4, 3: 2,4:5},
2: { 5: 7, 6: 5},
3: {6: 9},
4: {5: 2, 7: 7},
5: {8: 4},
6: {10:6},
7: {9: 3},
8: {10:7},
9: {10:8},
10:{}
}
inf=9999
#保存源点到各点的距离，为了让顶点和下标一致，前面多了一个inf不用在意。
length=[inf,0,inf,inf,inf,inf,inf,inf,inf,inf,inf]
Q=[]
#FIFO队列实现
def branch(G,v0):
Q.append(v0)
dict=G[1]
while len(Q)!=0:
#队列头元素出队
head=Q[0]
#松弛操作，并且满足条件的后代入队
for key in dict:
if length[head]+G[head][key]<=length[key]:
length[key]=length[head]+G[head][key]
Q.append(key)
#松弛完毕，队头出列
del Q[0]
if len(Q)!=0:
dict=G[Q[0]]
'''
#优先队列法实现
def branch(G, v0):
Q.append(v0)
while len(Q) != 0:
min=99999
flag=0
#找到队列中距离源点最近的点
for v in Q:
if min >length[v]:
min=length[v]
flag = v
head = flag
dict=G[head]
#找到扩散点后进行松弛操作
for key in dict:
if length[head] + G[head][key] <= length[key]:
length[key] = length[head] + G[head][key]
Q.append(key)
#松弛完毕后，该扩散点出队
Q.remove(head)
'''
branch(G,1)
print(length)
运行结果：[9999, 0, 4, 2, 5, 7, 9, 12, 11, 15, 15]。
与回溯法的异同：
充分利用限界函数和约束函数来剪去无效的枝并把搜索集中在可以得到解的分支上。
不同于回溯法，在分支限界法中， 每一个活结点只有一次机会成为扩展结点 。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，通过 剪枝函数 将导致不可行解或导致非最优解的儿子结点舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到 找到所需的解 或 活结点表为空 时为止。
不同的活结点表形成不同的分枝限界法，分为：FIFO分支限界法、LIFO分支限界法和LC(least cost)分支限界法。三种不同的活结点表，规定了从活结点表中选取下一个E-结点的不同次序。
在LIFO和FIFO分支限界法中，对下一个E-结点的选择规则死板，在某种意义上是盲目的搜索。
LC分支限界法在选择活结点时根据活结点的优先权来选择下一代活结点。结点优先权定义为：“ 在其分支下搜索一个答案状态需要花费的代价，代价越小，越优先 ”
分枝限界法的特性：
代价函数如同一个“有智力的”排序函数，基于其值选取下一个E-结点往往可以加快到达一答案结点的速度。
代价是答案结点到根节点的搜索代价，相对代价是子树下的答案结点到子树根X的搜索代价
由定义知，直接求c(.)和g(.)是十分困难
LC检索(即最小成本检索)：总是选取值最小的活结点为下一个E结点。
选择与目标函数有关的度量值
不直接求c(X)
与回溯法一样，分支限界法也是在问题的解空间树上搜索问题的解的一种算法。
两者很类似，很容易混淆，但有如下显著的区别可区分两者：
1、求解目标不同
回溯法的求解目标一般是找出解空间树中满足条件的 所有解 。
分支限界法则是尽快找出满足约束条件的 一个解 ，或是在满足约束条件的解中找出在某种意义下的 最优解 。
2、搜索方式不同
回溯法——> 深度优先 遍历结点搜索解空间树。
分支限界法——> 广度优先或最小耗费优先 搜索解空间树。
3、存储空间不同
分支限界法由于加入了 活结点表 ，所以存储空间比回溯法大得多。因此当内存容量有限时，回溯法的成功率要大一些。
4、扩展结点的方式不同
分支限界法中，每个活结点只有一次机会变成扩展结点，一旦成为扩展结点便一次性生成其所有子结点。
区别小结：回溯法空间效率更高，分支限界法由于只需要求到一个解，所以往往更“快”。
就拿0/1背包问题做例子，回溯法求解0/1背包问题实际上是盲目地搜索解空间树，回溯法只会不断地往下走，虽然通过剪枝函数能减少一定的计算，但是当经过一个结点时，并不知晓其子结点会是怎样的情况，从而盲目继续搜索。而分支限界法则不一样，在经过某一结点时，会根据限界条件判断其结点之下的情况是否能够导出最优解，如若不能，直接不走这条路。这样虽然在空间上不占优势，但是搜索并不盲目，速度上快了很多。
1、定义解空间（对解编码）
2、确定解空间树结构（得解空间树）
3、按BFS广度优先方式搜索解空间树：
（1）：每个活结点只有一次机会变成扩展结点。
（2）：由扩展结点生成一步可达的新结点。
（3）：在新结点中删除不可能导出最优解的结点（限界策略，利用限界函数）。
（4）：将剩余新结点加入到活结点表中。
（5）：在活结点表中再取每个结点（按顺序）进行扩展（分支策略）。
（6）：直到活结点表为空。
注：活结点表通常采用堆结构，当求解极大值问题时用大顶堆，极小值问题时用小顶堆。
1、约束函数：问题定义时需给出的约束条件，如0/1背包问题不能超过其容量。
2、目标函数：是问题要求解的目标函数，分支限界法中需给出一个关于该函数的上下界，方便之后剪枝。
3、限界函数：用于记录当前结点之下可得的最优值，若超出上下界，则可放弃该结点；还用于活结点表中结点排序，限界函数值最优的在第一位，优先扩展遍历。
1、队列式分支限界法：在活结点表中，按照FIFO先进先出原则选取下一个结点做扩展结点。
2、优先队列式分支限界法：活结点表中的每个结点对应了一个耗费或收益（其实就是如果扩展该结点，会带来多大的效益），以此决定结点的优先级。
0/1背包问题、单源最短路径问题、最优装载问题。
