下载文档原格式
分支限界算法
通俗来讲，分支限界法是一种将一个具有相互冲突和复杂约束的大型优化问题划分成一系列规模较小的子问题的方法，并以此最终获得给定问题的最优解。
它把原问题分割成几个小子问题，每个子问题都有一个限制条件，分支限界法从一个子集中选择，分支出若干解法，并把选出的最优解作为下一次算法迭代的初始解，继续作为一个新的子集挑选优解，以此迭代直至找到了全局最优解。
分支限界法的运行流程主要包括以下几个步骤：
1.初始化：确定问题的规模大小及初始解；
2.分支：根据某种规则，将现有的一个节点分成若干个候选子节点，并构建子节点与父节点之间的映射关系；
3.限界：每个候选子节点都有一个下限价值，以降低算法计算量；
4.剪枝：根据某种明确的剪枝规则，去除那些应该剪枝的节点，减少计算量；
5.搜索：递归搜索下一个更优解，直至得出最优解。
算法——分⽀限界法（装载问题）对⽐回溯法回溯法的求解⽬标是找出解空间中满⾜约束条件的所有解，想必之下，分⽀限界法的求解⽬标则是找出满⾜约束条件的⼀个解，或是满⾜约束条件的解中找出使某⼀⽬标函数值达到极⼤或极⼩的解，即在某种意义下的最优解。
另外还有⼀个⾮常⼤的不同点就是，回溯法以深度优先的⽅式搜索解空间，⽽分⽀界限法则以⼴度优先的⽅式或以最⼩耗费优先的⽅式搜索解空间。
分⽀限界法的搜索策略在当前节点（扩展节点）处，先⽣成其所有的⼉⼦节点（分⽀），然后再从当前的活节点（当前节点的⼦节点）表中选择下⼀个扩展节点。
为了有效地选择下⼀个扩展节点，加速搜索的进程，在每⼀个活节点处，计算⼀个函数值（限界），并根据函数值，从当前活节点表中选择⼀个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分⽀推进，以便尽快地找出⼀个最优解。
分⽀限界法解决了⼤量离散最优化的问题。
选择⽅法1.队列式（FIFO）分⽀限界法队列式分⽀限界法将活节点表组织成⼀个队列，并将队列的先进先出原则选取下⼀个节点为当前扩展节点。
2.优先队列式分⽀限界法优先队列式分⽀限界法将活节点表组织成⼀个优先队列，并将优先队列中规定的节点优先级选取优先级最⾼的下⼀个节点成为当前扩展节点。
如果选择这种选择⽅式，往往将数据排成最⼤堆或者最⼩堆来实现。
例⼦：装载问题有⼀批共n个集装箱要装上2艘载重量分别为c1，c2的轮船，其中集装箱i的重量为wi，且要求确定是否有⼀个合理的装载⽅案可将这n个集装箱装上这2艘轮船。
可证明，采⽤如下策略可以得到⼀个最优装载⽅案：先尽可能的将第⼀艘船装满，其次将剩余的集装箱装到第⼆艘船上。
代码如下：//分⽀限界法解装载问题//⼦函数，将当前活节点加⼊队列template<class Type>void EnQueue(Queue<Type> &Q, Type wt, Type &bestw, int i, int n){if(i == n) //可⾏叶结点{if(wt>bestw) bestw = wt ;}else Q.Add(wt) ; //⾮叶结点}//装载问题先尽量将第⼀艘船装满//队列式分⽀限界法，返回最优载重量template<class Type>Type MaxLoading(Type w[],Type c,int n){//初始化数据Queue<Type> Q; //保存活节点的队列Q.Add(-1); //-1的标志是标识分层int i=1; //i表⽰当前扩展节点所在的层数Type Ew=0; //Ew表⽰当前扩展节点的重量Type bestw=0; //bestw表⽰当前最优载重量//搜索⼦集空间树while(true){if(Ew+w[i]<=c) //检查左⼉⼦EnQueue(Q,Ew+w[i],bestw,i,n); //将左⼉⼦添加到队列//将右⼉⼦添加到队列即表⽰不将当前货物装载在第⼀艘船EnQueue(Q,Ew,bestw,i,n);Q.Delete(Ew); //取下⼀个节点为扩展节点并将重量保存在Ewif(Ew==-1) //检查是否到了同层结束{if(Q.IsEmpty()) return bestw; //遍历完毕，返回最优值Q.Add(-1); //添加分层标志Q.Delete(Ew); //删除分层标志，进⼊下⼀层i++;}}}算法MaxLoading的计算时间和空间复杂度为O(2^n).上述算法可以改进，设r为剩余集装箱的重量，当Ew+r<=bestw的时候，可以将右⼦树剪去。
分支限界法基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。
这个过程一直持续到找到所需的解或活结点表为空时为止。
常见的两种分支限界法（1）队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
分支限界法与回溯法的不同（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
解空间树的动态搜索（1）回溯求解0/1背包问题，虽剪枝减少了搜索空间，但整个搜索按深度优先机械进行，是盲目搜索（不可预测本结点以下的结点进行的如何）。
（2）回溯求解TSP也是盲目的（虽有目标函数，也只有找到一个可行解后才有意义）（3）分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down, up]；然后按照广度优先策略遍历问题的解空间树，在某一分支上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值（对最小化问题，估算结点的down，对最大化问题，估算结点的up）。
如果某孩子结点的目标函数值超出目标函数的界，则将其丢弃（从此结点生成的解不会比目前已得的更好），否则入待处理表。
分支限界法的设计思路设求解最大化问题，解向量为X=(x1,…,xn)，xi的取值范围为Si，|Si|=ri。
分支限界法和回溯法
分支限界法和回溯法都是求解优化问题的算法策略。
但它们在求解问题的过程和方法上存在明显的不同。
1. 分支限界法：
分支限界法是一种在穷举法的基础上，设法避免其缺点、提高效率的算法。
它的基本思想是将原始问题分解为若干个子问题，然后逐个求解。
在求解过程中，分支限界法会不断地扩展子树的分支，然后在满足限界条件的情况下，剪去不符合限界条件的分支。
分支限界法的核心思想是：在每一步选择中，算法会优先选择约束条件最少的子节点进行扩展，从而在搜索过程中限制了生成的子节点的数量。
2. 回溯法：
回溯法是一种按照深度优先搜索策略的穷举搜索法。
它通过深度优先搜索解空间树，从根节点出发深度搜索解空间树，当搜索到某一节点时，如果该节点可能包含问题的解，则继续向下搜索；反之回溯到其祖先节点，尝试其他路径搜索。
回溯法的核心思想是：通过深度优先搜索，从上到下、从左到右地搜索解空间树。
当搜索到某一节点时，如果该节点可能包含问题的解，则继续向下搜索；否则回溯到其祖先节点，继续尝试其他路径搜索。
总结：
分支限界法和回溯法都是求解优化问题的算法策略。
分支限界法通过分解问题和优先选择约束条件最少的子节点来提高效率；而回溯
法则通过深度优先搜索解空间树和回溯到祖先节点来尝试其他路径搜索。
在实际应用中，应根据具体问题的特点和要求选择合适的算法策略。
