文档介绍：第7章分支限界法
概述
复杂的有限期作业调度问题
贷郞担问题的分支限界法
其他分支限界问题
分支限界法与回溯法的比较
概述
分支限界法是一个用途十分广泛的算法,运用这种算法的技巧性很强,不同类型的问题解法也各不相同。本节主要讲述分支限界法的定义、基本思想和几种不同的分支限界方法。其中,分支限界方法主要有FIFO分支限界方法、LIFO分支限界方法和LC分支限界方法。
什么是分支限界法
将问题分支为子问题、采用广度优先产生状态空间树的结点并使用剪枝函数对这些子问题限界而求解问题的方法称为分支限界法。
分支限界法是按照广度优先搜索的原则,一个活结点一旦成为扩展结点(E结点)R后,算法将依次生成它的全部孩子结点,并将它们——加入活结点表,此时R自身成为死结点。算法从活结点表中另选一个活结点作为E结点。
分支限界的基本思想
分支限界法的基本思想是对有约束条件的最优化问题的所有可行解(数目有限)空间进行搜索。
复杂的有限期作业调度问题
对于单处理机的带时限作业排序问题,如果每个作业具有相同的处理时间,则可以用贪心法求解。如果每个作业的处理时间允许不同,即取消处理每个作业需要一个单位时间的假设,带时限的作业排序问题可描述为:设有n个作业和一台处理机,每个作业所需的处理时间、要求的时限和收益可用三元组(ti,di,pi)表示,0≤i<n。其中,作业i的所需时间为ti,如果作业i能够在时限di内完成,将可收益pi,且ti ≤ di,i = 1,2,…,n。问题的要求是从n个作业中找到一个子集J,使得J中的作业可以在各自的期限内由一台处理机完成,并获得最大总收益。求使得总收益最大的作业子集J。
(复杂的有限期作业调度问题)设n = 4,(p1,t1,d1)=(5,l,l),(p2,t2,d2)=(10,2,3),(p3,t3,d3)=(6,1,2),(p4,t4,d4)=(3,l,l)。
贷郞担问题的分支限界法
从矩阵的一行(或列)的各元素中,减去该行(或列)的最小元素,使得该行(或列)至少包含一个零且其他元素均为非负值,称此操作为对此行(或列)“归约”。第i行(或第j列)中各元素减去的最小数ri(或tj)叫做第i行(或第j列)的“约数”。如果下个矩阵的所有行和列都已归约,则称此矩阵为原矩阵的“归约矩阵”。和数:
L= + 称为原矩阵的“约数”。
利用LC检索,找出在图7-3(a)中所给出的图的最小周游路线。
按LC检索,每次将把活结点表中具有最小C的那个结点作为当前分支点,其余的比较或删除等过程与FIFO并无区别。图7-3给出了按LC检索产生状态空间树的过程。
其他分支限界问题
目前,分支限界法已经得到了广泛的应用。除了复杂的有限期作业调度问题和贷郞担问题的分支限界法,还有布线问题、0/1背包问题以及单源最短路径的分支限界法。
布线问题
印刷电路板将布线区域划分成n×n个方格阵列如图(a)所示。精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时,电路只能沿直线或直角布线,如图(b)所示。为了避免线路相交,已布了线的方格做了封锁标记,其他线路不允许穿过被封锁的方格