文档介绍：第6章分支限界法(Branch and Bound) 分支限界法的基本思想
用于求解最优化问题
1、分支限界法与回溯法的不同
分支限界法与回溯法类似,也是在问题的解空间上搜索问题解的算法。其不同点如下:
1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。
2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
1
2. 分支限界法基本思想
分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。
在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。
此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
由此可见,两种算法的最主要区别在于它们对当前扩展节点所采用的扩展方式不同。在分支限界法中,每个或结点只有一次机会成为扩展节点。
2
3. 常见的两种分支限界法
从活结点表中选择下一扩展结点的不同方式导致不同的分支界限法。最常见的有以下两种方式:
(1)队列式(FIFO)分支限界法
按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。
(2)优先队列式分支限界法
按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
优先队列中规定的节点优先级通常用一个与该节点相关的数值p来表示。结点优先级的高低与p值的大小有关。最大优先队列规定p值较大的结点优先级高。在算法实现是通常采用最大堆来实现最大优先队列,用最大堆的Deletemax运算抽取堆中下一结点成为当前扩展节点,体现最大利益优先的原则。类似的,最小优先队列用最小堆实现。
3
在问题的边带权的解空间树中进行广度优先搜索. 找一个回答结点使其对应路径的权最小(最大)。当搜索到达一个扩展结点时,一次性扩展它的所有儿子,将那些满足约束条件且最小耗费函数目标函数限界的儿子,插入活动结点表中, 再从活动结点表中取下一结点同样扩展. 直到找到所需的解或活动结点表为空为止。
4、形式化描述
算法设计与分析>分支限界法
通常采用优先队列方式组织, c(x)小者优先。
结点x的最小耗费函数c(x):以x为根的子树所包含的回答结点中,路权最小者。若x是回答结点, 则c(x)即为该点的目标函数值; 若x是根结点, 则c(x)即为最优解值。c(x)为单增函数。若x*是任一回答结点,
且c(x*)<U, 则当搜索到结点x,而c(x)>U时, x将不必扩展(剪枝)。
目标函数限界U的调整:初始U可取,随回答结点值的求出逐步更新
为U=c(x*), x*为已知回答结点中值最小者。
活动结点表:
4
算法设计与分析>分支限界法
=U(T).
,
对满足约束条件的 x 计算, 将U的x 加入活动结点表.
3. x为叶结点时,检查是否c(x)<U, 是则用c(x)更新U.