分支限界法是以广度优先或以最小耗费 (最大效益) 优先的方式在问题的解空间树T上搜索问题解的一种搜索方法。其求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出某种意义下的最优解。
分支限界法在人工智能组合问题求解中占据了很重要的地位,，有效地解决了背包问题、旅行商问题等经典问题。
采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分枝限界法。
“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（儿子结点）
“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些分支，从而提高搜索效率。
在当前节点（扩展节点）处，首先，生成当前节点的所有的儿子节点（分支），然后，从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。
为了有效地选择下一个扩展节点，加速搜索的进程，在每一个活节点处，计算一个函数值（限界），根据函数值的大小，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。
从活结点表中选择下一扩展结点的不同方式导致了不同的分支限界法， 最常见的有队列式分支限界法和优先队列式分支限界法两种。
按照队列先进先出(FIFO)原则选取下一个活结点为扩展结点。
起初，根结点是唯一的活结点，根结点入队。从活结点队中取出根结点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。
按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。
对每一活结点计算一个优先级（某些信息的函数值）。根据这些优先级，从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，再从活结点表中下一个优先级别最高的结点为当前扩展结点，......，直到找到一个解或活结点队列为空为止。
都是一种在问题的解空间树
上搜索问题解的算法回溯法：以深度优先的方式搜索解空间，其求解目标是找出解空间中满足约束条件的所有解
分支限界法：以广度优先的方式或以最小耗费优先的方式搜索解空间，其求解目标则是找出满足约束条件的一个解，或是满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
已知：有一批共
个集装箱要装上2艘载重量分别为 ， 的轮船，其中集装箱i的重量为 。问题：是否有一个合理的装载方案可将这 个集装箱装上这2艘轮船？
解：
可证明，采用如下策略可以得到一个最优装载方案：先尽可能的将第一艘船装满，其次将剩余的集装箱装到第二艘船上。
示例代码：
//分支限界法解装载问题 //装载问题先尽量将第一艘船装满 //队列式分支限界法，返回最优载重量 template<class Type> Type MaxLoading(Type w,Type c,int n) { //初始化数据 Queue<Type> Q; //保存活节点的队列10 Q.Add(-1); //-1的标志是标识分层11 int i=1; //i表示当前扩展节点所在的层数 Type Ew=0; //Ew表示当前扩展节点的重量 Type bestw=0; //bestw表示当前最优载重量 //搜索子集空间树 while(true) { //检查左儿子 Type wt=Ew+w; //wt为左儿子节点的重量 if(wt<=c) //若装载之后不超过船体可承受范围 if(wt>bestw) //更新最优装载重量 { bestw=wt;24 if(i<n) Q.Add(wt); //将左儿子添加到队列 } //将右儿子添加到队列 if(Ew+r>bestw&&i<n) Q.Add(Ew); Q.Delete(Ew); //取下一个节点为扩展节点并将重量保存在Ew if(Ew==-1) //检查是否到了同层结束 { if(Q.IsEmpty()) return bestw; //遍历完毕，返回最优值 Q.Add(-1); //添加分层标志 Q.Delete(Ew); //删除分层标志，进入下一层 i++; r-=w; //剩余集装箱重量 } }}
温馨提示：