分支限界法的概念

一种在问题的解空间树上搜索问题解的算法

解空间

将问题的解表示成一个多元组(x1, x2, …, xn)的形式，满足问题显约束的所有多元组定义为关于输入(x1, x2, …, xn)的解空间。

解空间树

树上的每一个结点定义了一个“问题状态”，从根到每一个结点的所有路径定义了这个问题的“状态空间”。从根到叶结点的每一条路径定义了解空间中的一个多元组。

搜索策略

1）结点的构造
2）结点的扩展
3）下一个活结点的生成
4）结点舍弃原则（剪支）

1）结点的构造

活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结点
扩展结点：一个正在产生儿子的结点称为扩展结点
死结点：一个所有儿子已经产生的结点称做死结点
回答结点：满足问题的全部约束的结点
构造结点：与具体问题有关

2）活结点的扩展
每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

3）下一个扩展结点的生成

（1）队列式(FIFO)分支限界法
按照队列先进先出（FIFO）原则选取下一个点为扩展节点。
（2）优先队列式分支限界法
按照优先队列中规定的优先级选取优先级最高的活结点成为当前扩展节点。

4）结点舍弃原则（剪支策略）

导致不可行解或导致非最优解的儿子结点被舍弃；
在算法扩展结点的过程中，一旦发现一个结点的下界不小于（上界不大于）当前找到的最优值，则算法剪去以该结点为根的子树；
结点间的控制关系进行；
考点
分支限界
1、以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法
2、分支限界法主要有 队列式（FIFO） 分支限界法和 优先队列式 分支限界法。
3、分支限界法是一种既带有 系统性 又带有 跳跃性 的搜索算法。
4、分支限界法解最大团问题时，活结点表的组织形式是（ B ）。
A、最小堆 B、最大堆 C、栈 D、数组
5、分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。
A、最小堆 B、最大堆 C、栈 D、数组
6、优先队列式分支限界法选取扩展结点的原则是（ C ）。
A、先进先出 B、后进先出 C、结点的优先级 D、随机
7、在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ).
A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题
8、从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,除(C)之外都是最常见的方式.
A.队列式分支限界法 B.优先队列式分支限界法
C.栈式分支限界法 D.FIFO分支限界法
9、最大效益优先是（ A ）的一搜索方式。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
10、下面不是分支界限法搜索方式的是（ D ）。
A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先
11、舍伍德算法是（ B ）的一种。
A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法
分支限界法：
这是一种用于求解组合优化问题的排除非解的搜索算法。类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间。然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。因此，可以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。
算法思想：分枝限界（branch and bound）是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成扩展节点。当一个节点变为扩展节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。
有两种常用的方法可用来选择下一扩展节点（虽然也可能存在其他的方法）：
1) 先进先出（FIFO）即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活节点表的性质与队列相同。
2) （优先队列）最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个 E-节点是具有最大收益的活节点

10、用分支限界法设计算法的步骤是：
(1)针对所给问题，定义问题的解空间（对解进行编码）；
(2)确定易于搜索的解空间结构（按树或图组织解）；
(3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
11、常见的两种分支限界法的算法框架：
（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
12、分支限界法的搜索策略是：
在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。
13、请说明：
(1)优先队列可用什么数据结构实现？
(2)优先队列插入算法基本思想？
(3)优先队列插入算法时间复杂度？
（1）堆。
（2）在小根堆中，将元素x插入到堆的末尾，然后将元素x的关键字与其双亲的关键字比较，若元素x的关键字小于其双亲的关键字，则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比，直到元素x的关键字大于双亲的关键字，或元素x到根为止。
（3）O( log n)

回溯与分支限界

14、回溯算法和分支限界法的问题的解空间树不会是(D ).
A.有序树 B.子集树 C.排列树 D.无序树
15、分支限界法与回溯法
相同点：都是一种在问题的解空间树T中搜索问题解的算法。
不同点：
（1）求解目标不同；
（2）搜索方式不同；
（3）对扩展结点的扩展方式不同；
（4）存储空间的要求不同。
16、比较分支限界法与回溯法
回溯法：
求解目标：找出解空间树中满足约束条件的所有解
搜索方式：以深度优先的方式搜索解空间树
分支限界法：
求解目标：找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解
搜索方式：以广度优先或以最小耗费优先的方式搜索解空间树。

分支限界