分支限界法 ppt

《分支限界法 ppt》由会员分享，可在线阅读，更多相关《分支限界法 ppt（38页珍藏版）》请在金锄头文库上搜索。

1、第6章 分支限界法(Branch and Bound) 6.1 分支限界法的基本思想用于求解最优化问题1、分支限界法与回溯法的不同分支限界法与回溯法类似，也是在问题的解空间上搜索问 题解的算法。其不同点如下：1）求解目标：回溯法的求解目标是找出解空间树中满足 约束条件的所有解，而分支限界法的求解目标则是找出满足约 束条件的一个解，或是在满足约束条件的解中找出在某种意义 下的最优解。 2）搜索方式的不同：回溯法以深度优先的方式搜索解空 间树，而分支限界法则以广度优先或以最小耗费优先的方式搜 索解空间树。2. 分支限界法基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先 的方式搜索问题的解

2、空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结 点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点 。在这些儿子结点中，导致不可行解或导致非最优解的儿子结 点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重 复上述结点扩展过程。这个过程一直持续到找到所需的解或活 结点表为空时为止。 由此可见，两种算法的最主要区别在于它们对当前扩展节 点所采用的扩展方式不同。在分支限界法中，每个或结点只有 一次机会成为扩展节点。3. 常见的两种分支限界法从活结点表中选择下一扩展结点的不同方式导致不同的 分支界限法。最常见的有以下两种方式： （1）队列式(F

3、IFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展 节点。 （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成 为当前扩展节点。 优先队列中规定的节点优先级通常用一个与该节点相关 的数值p来表示。结点优先级的高低与p值的大小有关。最大优 先队列规定p值较大的结点优先级高。在算法实现是通常采用 最大堆来实现最大优先队列，用最大堆的Deletemax运算抽取 堆中下一结点成为当前扩展节点，体现最大利益优先的原则。 类似的，最小优先队列用最小堆实现。在问题的边带权的解空间树中进行广度优先搜索. 找一个回答 结点使其对应路径的权最小(最大)。当搜索到达一

4、个扩展结点时,一 次性扩展它的所有儿子,将那些满足约束条件且最小耗费函数目标 函数限界的儿子,插入活动结点表中, 再从活动结点表中取下一结点 同样扩展. 直到找到所需的解或活动结点表为空为止。4、形式化描述算法设计与分析 分支限界法通常采用优先队列方式组织, c(x)小者优先。结点x的最小耗费函数c(x):以x为根的子树所包含的回答结点中,路权 最小者。若x是回答结点, 则c(x)即为该点的目标函数值; 若x是根结 点, 则c(x)即为最优解值。c(x)为单增函数。若x*是任一回答结点, 且c(x*)U时, x将不必扩展(剪枝)。 目标函数限界U的调整:初始U可取，随回答结点值的求出逐步更新

5、为U=c(x*), x*为已知回答结点中值最小者。活动结点表:算法设计与分析 分支限界法1.取U=U(T). 2.扩展根结点的所有儿子.对每一子结点x判定其是否满足约束条件, 对满足约束条件的 x 计算 , 将 U的x 加入活动结点表. 3. x为叶结点时,检查是否c(x)分枝限界法设N=3, W=(16,15,15), P=(45,25,25), C=30实例：0-1背包问题(0-1Knapsack Problem )C=14 U=45U=0U=45C=15 U=25U=50 C=0U=0B, C, C,E, E,F,G, F,G, G, C=14 U=45队列式分支限界法 活动结点表:设N

6、=3, W=(16,15,15), P=(45,25,25), C=30C=14 U=45U=0U=45U=25U=50U=0B, C, E, C, C, F, G, GC=14 U=45优先队列式分支界限法 活动结点表:6.3 装载问题1. 问题描述有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其 中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装 箱装上这2艘轮船。如果有，找出一种装载方案。 容易证明：如果一个给定装载问题有解，则采用下面的策略 可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。 这个问题是一个

7、子集选择问题，它的解空间被 组织成一个子集树。问题描述及界限函数见5.2节。利用分支限界法设计算法MaxLoading实施对解 空间的分支限界搜索。链表队列Q用于保存活节点，它的 值记录着各活节点对应的权值。队列还记录了权值- 1， 以标识每一层的活节点的结尾。函数EnQueue用于增加节点（即把节点对应的权 值加入活节点队列）2. 队列式分支限界法函数EnQueue用于增加节点（即把节点对应的权 值加入活节点队列），该函数首先检验i（当前E-节点在 解空间树中的层）是否等于n，如果相等，则已到达了叶 节点。叶节点不被加入队列中，因为它们不被展开。搜索 中所到达的每个叶节点都对应着一个可行的解

8、，而每个解 都会与目前的最优解来比较，以确定最优解。如果in， 则节点i 就会被加入队列中template void EnQueue (LinkedQueue else Q.Add(wt); / 不是叶子 MaxLoading函数首先初始化i = 1（因为当前E- 节点是根节点），bestw=0（目前最优解的对应值），此 时，活节点队列为空。下一步， 将同层结点尾部标志-1 加入队列，表示此时正处在第一层的末尾。Ew存储当前 扩展结点所相应的重量。template Type MaxLoading (Type w, Type c, int n) / 返回最优装载值 使用F I F O分枝定界算法

9、 /为层次1 初始化 Queue Q; / 活节点队列 Q.Add(-1); /标记本层的尾部 int i = 1; /扩展节点的层 Type Ew = 0, / 扩展节点所相应的载重量bestw = 0; / 目前的最优值while (true) / 搜索子集空间树 / 检查扩展节点的左孩子if (Ew + wi bestw) bestw = wt;/ 加入活结点队列if (i bestw bestxn = ch;return; QNode *b; / 不是叶子, 添加到队列中b = new QNode;b-weight = wt;b-parent = E;b-LChild = ch;Q.A

10、dd(b); 算法可以在搜索子集树的过程中保存当前已构造出的 子集树中的路径，从而可在结束搜索找到最优值后，从子集 树中与与最优值相应的节点处根据parent向根节点回溯，找 到最优解。/ 构造当前最优解for (int j = n; j 0; j-) bestxj = (e.leftChild) ? 1 : 0;e = e.parent; 5. 优先队列式分支限界法解装载问题的优先队列式分支限界法用最大优先队列存 储活结点表。活结点x在优先队列中的优先级定义为从根结点 到结点x的路径所相应的载重量再加上剩余集装箱的重量之和 。优先队列中优先级最大的活结点成为下一个扩展结点。 以结点x为根的子

11、树中所有结点相应的路径的载重量不超过它 的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当 前扩展结点，则可以断言该叶结点所相应的解即为最优解。此 时可终止算法。两种实现方法：方法一，最大优先级队列中的活节点都是互相独立 的，因此每个活节点内部必须记录从子集树的根到此节点的路 径。一旦找到了最优装载所对应的叶节点，就利用这些路径信 息来计算x 值。方法二，除了把节点加入最大优先队列之外，节点 还必须放在另一个独立的树结构中，这个树结构用来表示所生 成的子集树的一部分。当找到最大装载之后，就可以沿着路径 从叶节点一步一步返回到根，从而计算出x

12、值。下面介绍第二种方法，最大优先队列可用HeapNode 类型的最大堆来表示。 uweight 是活节点的重量上限，level 是活节点所在子集树的 层， ptr 是指向活节点在子集树中位置的指针。子集树中节 点的类型是bbnode。节点按uweight值从最大堆中取出。布线问题的解空间是一个图，适合采用队列式分支限界法来解决。从起 始位置a开始将它作为第一个扩展结点。与该结点相邻并且可达的方格被 加入到活结点队列中，并且将这些方格标记为1，表示它们到a的距离为1接着从活结点队列中取出队首作为下一个扩展结点，并将与当前扩展 结点相邻且未标记过的方格标记为2，并存入活节点队列。这个过程一直 继续

13、到算法搜索到目标方格b或活结点队列为空时为止（表示没有通路）6.4布线问题问题描述：印刷电路板将布线区域划分成n*m个方格阵列。精确 的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线 方案。在布线时，电路只能沿直线或直角布线。为了避免线路相交， 已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格现在来看上面两张图。演示了分支限 界法的过程。最开始，队列中的活结点为标 1的格子，随后经过一个轮次，活结点变为 标2的格子，以此类推，一旦b方格成为活节 点便表示找到了最优方案。为什么这条路径 一定就是最短的呢？这是由于我们这个搜索 过程的特点所决定的，假设存在一条由a至b 的更

14、短的路径，b结点一定会更早地被加入 到活结点队列中并得到处理。 最后一个图表示了a和b之间的最短布 线路径。值得一提的是，在搜索的过程中我 们虽然可以知道结点距起点的路径长度，却 无法直接获得具体的路径描述。为了构造出 具体的路径，我们需要从目标方格开始向起 始方格回溯，逐步构造出最优解，也就是每 次向标记距离比当前方格距离少1的相邻方 格移动，直至到达起始方格时为止。算法实现：1)定义小方格位置定义一个表示电路板上小方格位置的类Position，它 的两个私有成员row和col分别表示小方格所在的行和列。在电路 板的任何一个方格处，布线可沿右、下、左、上4个方向进行。 沿这4个方向的移动分别

15、记为0，1，2，3。沿着这4个方向前进一 步相对于当前方格的位移如下表所示。移动i方向offseti.row offseti.col0右011下102左0-13上-10算法实现：2) 实现方格阵列用二维数组grid表示所给的方格阵列。初始时， gridij=0，表示该方格允许布线，而gridij=1表示该方 格被封锁，不允许布线。为了便于处理方格边界的情况，算法在所给方格阵列 四周设置一圈标记为“1”的附加方格，即可识别方阵边界。3)初始化算法开始时，测试初始方格与目标方格是否相同。如 果相同，则不必计算，直接放回最短距离0，否则算法设置方格 阵列的边界，初始化位移矩阵offset。算法将起始

16、位置的距离标记为2。由于数字0和1用于表 示方格的开放或封锁状态，所以在表示距离时不用这两个数字， 将距离的值都加2。实际距离应为标记距离减2。4）算法搜索步骤算法从start开始，标记所有标记距离为3的方格并存入 或节点队列，然后依次标记所有标记距离为4，5的方格，直 到到达目标方格finish或或节点队列为空时为止现在我们来考虑，为什么这个问题用回溯法来处理就是相 当低效的。回溯法的搜索是依据深度优先的原则进行的，如果我们把 上下左右四个方向规定一个固定的优先顺序去进行搜索，搜索 会沿着某个路径一直进行下去直到碰壁才换到另一个子路径， 但是我们最开始根本无法判断正确的路径方向是什么，这就造 成了搜索的盲目和浪费。更为致命的是，即使我们搜索到了一 条由a至b的路径，我们根本无法保证它就是所有路径中最短的 ，这要求我们必须把整个区域的所有路径逐一搜索后才能得到 最优解。