分支限界法PPT课件

1、学习要点: 理解分支限界法的剪枝搜索策略 掌握分支限界法的算法框架 队列式(FIFO)分支限界法 优先队列式分支限界法 通过应用范例学习分支限界算法设计策略第1页/共53页分支限界法 分支限界法类似于回溯法，也是一种在问题的解空间树T中搜索问题解的算法。 分支限界法常以广度优先或以最小耗费(LC)优先的方式搜索问题的解空间树。 在遍历过程中，对已经扩展出的每一个结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。 适用于求解最优化问题。9.1 概述第2页/共53页分支限界法的设计思想 首先，确定一个合理的限界函数

2、，并根据限界函数确定问题的目标函数的界down, up(具体问题可以只有下界down，或上界up)； 然后，按照广度优先策略遍历问题的解空间树： 当搜索到达一个扩展结点时，一次性扩展它的所有孩子，估算每一个孩子结点的目标函数的可能取值(又称为耗费函数值)； 将那些满足约束条件且耗费函数值不超过目标函数的界的孩子，插入活动结点表PT中，再从PT表中取耗费函数值极大(小)的下一结点同样扩展； 直到找到所需的解或PT表为空为止。怎样确定怎样确定“限界函数限界函数”？又如何求得目标函数的界呢？又如何求得目标函数的界呢？第3页/共53页 对于PT中的叶子结点： 其耗费函数值是极值(极大或极小)，则该叶子

3、结点对应的解就是问题的最优解； 否则，将问题目标函数的界(down, up)调整为该叶子结点的耗费函数值，然后丢弃PT表中超出目标函数界的结点，再次选取结点继续扩展。第4页/共53页 例9-1：0/1背包问题。实例：假设有4个物品，其重量分别为(4, 7, 5, 3)，价值分别为(40, 42, 25, 12)，背包容量W=10。将给定物品按单位重量价值从大到小排序，结果如下：物品重量(w)价值(v)价值/重量(v/w)144010274263525543124第5页/共53页 分析：问题的解可表示为n元向量x1, x2, . xn , xi0,1，则可用子集树表示解空间, 在树中做广度优先搜

4、索。 约束条件: 目标函数: 下界Vdb =40 (1, 0, 0, 0)贪心思想； 上界Vub =0+(W-0)(v1/w1) =0+(10-0)10=100； 上限界函数： (式9.1)()(11iiwvwWvubWxwniii1niiixvV1max目标函数的界：目标函数的界：40, 10011111100000001124891011121314157653前前i个物品获得的价值个物品获得的价值剩余容量全部装入物品剩余容量全部装入物品i+1，最多能够获得的价值最多能够获得的价值第6页/共53页 分支限界法求解0/1背包问题：w=0, v=0ub=100w=4, v=40ub=76w=0

5、, v=0ub=60w=11w=4, v=40ub=70w=9, v=65ub=69w=4, v=40ub=64w=12w=9, v=65ub=65234567891PT=2, 3无效解无效解PT=5, 3PT=6, 7, 3无效解无效解x1=1x1=0 x2=1x2=0 x3=1x3=0 x4=1x4=0PT=9, 7, 3V=65X=(1, 0, 1, 0)目标函数范围：目标函数范围：40, 100wi=(4, 7, 5, 3)vi= (40, 42, 25, 12)vi/wi=(10, 6, 5, 4)()(11iiwvwWvub第7页/共53页 分支限界法的一般过程：1根据限界函数确定

6、目标函数的界根据限界函数确定目标函数的界down, up；2将待处理结点表将待处理结点表PT初始化为空；初始化为空；3对根结点的每个孩子结点对根结点的每个孩子结点x执行下列操作执行下列操作 3.1 估算结点估算结点x的目标函数值的目标函数值value; 3.2 若若(value=down)，则将结点，则将结点x加入表加入表PT中；中；4循环直到某个叶子结点的目标函数值在表循环直到某个叶子结点的目标函数值在表PT中最大中最大 4.1 i=表表PT中值最大的结点；中值最大的结点； 4.2 对结点对结点i的每个孩子结点的每个孩子结点x执行下列操作执行下列操作 估算结点估算结点x的目标函数值的目标函数

7、值value;若若(value=down)，则将结点，则将结点x加入表加入表PT中；中； 若若(结点结点x是叶子结点且结点是叶子结点且结点x的的value值在表值在表PT中最大中最大)， 则将结点则将结点x对应的解输出，算法结束；对应的解输出，算法结束； 若若(结点结点x是叶子结点但结点是叶子结点但结点x的的value值在表值在表PT中不是最大中不是最大)，则令则令down=value，并且将表，并且将表PT中所有小于中所有小于value的结点删除；的结点删除；第8页/共53页 常见的两种分支限界法： 从表PT中选择下一扩展结点的不同方式导致不同的分支限界法： 队列式(FIFO)分支限界法：从

8、左往右依次插入结点到队尾，按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。最大优先队列：使用最大堆，体现最大效益优先。最小优先队列：使用最小堆，体现最小费用优先。例如，上例0/1背包问题，采用最大优先队列式分支限界法。第9页/共53页 应用分支限界法的其他关键问题： 如何确定最优解中的各个分量？ 对每个扩展结点保存根结点到该结点的路径；例如，0/1背包问题。将部分解(x1, , xi)和该部分解的目标函数的上界值都存储在待处理结点表PT中，在搜索过程中表PT的状态如下：(0)60 (1,0,0)6

9、4 (1,0,1,0)65(a) 扩展根结点后表扩展根结点后表PT状态状态 (b) 扩展结点扩展结点2后表后表PT状态状态(c) 扩展结点扩展结点5后表后表PT状态状态 (d) 扩展结点扩展结点6后表后表PT状态，最优解为状态，最优解为(1,0,1,0)65(0)60 (1,0,1)69 (1,0,0)64(1)76 (0)60(0)60 (1,0)70 结点结点2结点结点3结点结点3结点结点5结点结点3结点结点6结点结点7结点结点3结点结点7结点结点9第10页/共53页 在搜索的过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。例如， 0/1背

10、包问题。设一个表ST，在表PT中取出最大值结点进行扩充时，将最大值结点存储到表ST中，表PT和表ST的数据结构为(物品i-1的选择结果，ub)，在搜索过程中表PT和表ST的状态如下：(a) 扩展根结点后扩展根结点后 (b) 扩展结点扩展结点2后后(c) 扩展结点扩展结点5后后 (d) 扩展结点扩展结点6后，最优解为后，最优解为(1,0,1,0)65(0,76) (0,60)PTST(0,60) (1,70)PTST(0,76)(0,60) (0,69) (0,64)PTST(0,76) (1,70)(0,60) (0,64) (1,65)PTST(0,76) (1,70) (0,69)说明：说

11、明：ST中记录的就是得到最优解的搜索路径上的各个结点！中记录的就是得到最优解的搜索路径上的各个结点！第11页/共53页 分支限界法与回溯法的区别：求解目标不同： 回溯法找出满足约束条件的所有解 分支限界法找出满足条件的一个解，或某种意义下的最优解搜索方式不同： 回溯法深度优先 分支限界法广度优先或最小耗费优先 此外，在分支限界法中，每一个活结点只有一次机会成为扩展结点。第12页/共53页问题例9-2：TSP问题。 问题描述：略。 各个城市间的距离用代价矩阵来表示, 如果(i,j)E，则cij=。 分析：设城市按自然数1, 2, ., n编号 解向量：(x1, x2, ., xn) 约束条件：

12、显式约束：xi=1, 2, ., n (i=1, 2, ., n) 隐式约束：(xixj) (cij)9.2 广度优先分支限界法应用举例第13页/共53页 目标函数： (kV) 下界：ddb= (1+3)+(3+6)+(1+2)+ (3+4)+(2+3)/2=14 上界：dub=16(135421) 下限界函数：设已确定的顶点集合U=(r1, r2, ., rk) (式9.2)2/ )2(111UrjUrikiiijirrrrcdb行最小的两个元素素行不在路径上的最小元目标函数的界：目标函数的界：14, 16),(min) ,(kVkdcVidik271563134253984C= 3 1 5

13、 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (a) 一个无向图一个无向图 (b) 无向图的代价矩阵无向图的代价矩阵从集合从集合U中出来的边中出来的边一条进边，一条出边一条进边，一条出边第14页/共53页 优先队列式分支限界法求解TSP问题:目标函数范围：目标函数范围：14, 16412db=142356781startdb=1413db=1414db=1615db=1923db=1624db=1625db=1932db=1634db=1535db=149101152db=1954db=14121342db=161442db=1845db=15151652db=2017

14、db=19PT=2, 3, 4db=19PT=6, 7 , 9, 10, 11, 4db=18db=19PT=6, 7, 9, 16, 14, 4db=20PT=6, 7, 9, 14, 4PT=6, 7, 9, 10, 13, 4PT=6, 7, 3, 4PT=6, 7, 9, 10, 14, 4d=16135421C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 第15页/共53页 对每个扩展结点保存根结点到该结点的路径：(g) 扩展结点扩展结点16后的状态，最优解为后的状态，最优解为135421(1, 2)14 (1, 3)14 (1, 4)16(a)

15、 扩展根结点后的状态扩展根结点后的状态 (b) 扩展结点扩展结点2后的状态后的状态(c) 扩展结点扩展结点3后的状态后的状态(d) 扩展结点扩展结点11后的状态后的状态(e) 扩展结点扩展结点13后的状态后的状态(1, 3)14 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5)14(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5, 4)14 (1, 4)16 (1,

16、 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5, 4, 2)16(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 5, 4, 2)16 (1, 3, 4, 5)15(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 5, 4, 2)16 (1, 3, 4, 5)15(f) 扩展结点扩展结点10后的状态后的状态第16页/共53页 TSP问题算法的伪代码描述：1根据限界函数计算目标函数的下界down；采用贪心法得到上界up；2将待处理

17、结点表PT初始化为空；3for (i=1; i=1) 5.1 i=k+1; 5.2 xi=1; 5.3 while (xikijpiEvrijjjjvrcrrcdbpi21,11min1段的最短边第与顶点与顶点ri+1相连的边中相连的边中, 代价最小的边代价最小的边( (剩余顶点能够达到剩余顶点能够达到的最小代价的最小代价) )第20页/共53页 优先队列式分支限界法求解：64sAdb=20231startdb=14sBdb=16sCdb=157BDdb=188BEdb=189BFdb=185CEdb=16CFdb=181110EGdb=22EHdb=16目标函数范围：目标函数范围：14, 1

18、8ABsCDEFGHt492386884756866537PT=3, 4PT=3, 5, 6PT=7, 8, 9, 5, 6PT=7, 8, 9, 11, 6c=16sCEHt(4+8+(5+3)第21页/共53页 搜索算法描述：while (true) for (int j = 1; j = n; j+) if (cE.ijinf)&(E.length+cE.ijdistj) / 顶点i到顶点j可达，且满足控制约束 distj=E.length+cE.ij; prevj=E.i; / 加入活结点优先队列 MinHeapNode N; N.i=j; N.length=distj; H.

19、Insert(N); try H.DeleteMin(E); / 取下一扩展结点 catch (OutOfBounds) break; / 优先队列空 顶点i和j间有边，且此路径长小于原先从原点到j的路径长 第22页/共53页装载问题 问题描述：略。 分析： 解空间：X=(x1,x2,xn)，xiSi=0, 1，i=1,2,n 约束函数： 目标函数： 下界： 上界： 上限界函数：11cxwniiiniiixw1max111)(cwEwcEwubi左孩子：左孩子：Ew+wi+1 bestwnijjw1改进改进第23页/共53页 搜索算法设计： 队列式分支限界：while (true) / 检查左

20、儿子结点 Type wt = Ew + wi; / 左儿子结点的重量 if (wt bestw) bestw = wt; / 加入活结点队列 if (i bestw & i n) Q.Add(Ew); / 可能含最优解 Q.Delete(Ew); / 取下一扩展结点if (Ew = -1) / 同层结点尾部 if (Q.IsEmpty() return bestw; Q.Add(-1); / 同层结点尾部标志 Q.Delete(Ew); / 取下一扩展结点 i+; r-=wi; / 进入下一层 提前更新bestw 右儿子剪枝 第24页/共53页 优先队列式分支限界： 采用最大优先队列存

21、储活结点表。活结点x在优先队列中的优先级定义为：从根结点到结点x的路径所相应的载重量Ew + 剩余集装箱的重量r。 子集树中叶结点所相应的载重量与其优先级相同，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。 实现方法：(PT表结点的结构) 在活结点中保存从解空间树的根结点到该活结点的路径； 搜索进程中保存当前已构造出的部分解空间树；第25页/共53页 算法描述（采用第二种方式实现PT表）：template class HeapNode;class bbnode friend void AddLiveNode(MaxHeapHeapNode &

22、, bbbnode *, int, bool, int); friend int MaxLoading(int *, int, int, int *); friend class AdjacencyGraph; private: bbnode * parent; /指向父结点的指针 bool LChild; /左孩子结点标志;templateclass HeapNode friend void AddLiveNode(MaxHeapHeapNode &, bbnode *, Type, bool, int);第26页/共53页 friend Type MaxLoading(Type *

23、, Type, int, int *); public: operator Type() const return uweight; private: bbnode *ptr; /指向活结点在子集树中相应结点的指针 Type uweight; /活结点优先级(上界) int level; /活结点在子集树中所处的层序号;templatevoid AddLiveNode(MaxHeapHeapNode &H, bbnode *E, Type wt, bool ch, int lev)/将活结点加入到表示活结点优先队列的最大堆H中 bbnode *b = new bbnode; b-par

24、ent = E; b-Lchild = ch; HeapNode N;第27页/共53页 N.uweight = wt; N.level = lev; N.ptr = b; H.Inset(N);templateType MaxLoading(Type w, Type c, int n, int bestx)/优先队列式分支限界法, 返回最优装载重量，bestx返回最优解 /定义最大堆的容量为1000 MaxHeapHeapNode H(1000); /定义剩余重量数组r Type *r = new Typen+1; rn = 0; for(int j=n-1; j0; j-) rj = rj

25、+1 + wj+1;第28页/共53页 /初始化 int i = 1; /当前扩展结点所处的层 bbnode * E = 0; /当前扩展结点 Type Ew = 0; /扩展结点所相应的载重量 /搜索子集空间树 while (i != n+1) /非叶子结点 /检查当前扩展结点的孩子结点 if(Ew + wi = c) /左孩子结点为可行结点 AddLiveNode(H, E, Ew+wi+ri, true, i+1); /右孩子结点 AddLiveNode(H, E, Ew+ri, false, i+1); /取下一扩展结点 HeapNode N; H.DeleteMax(N); /非空

26、i = N.level; E = N.prt;第29页/共53页 Ew = N.uweight ri-1; /构造当前最优解 for (int j=n; j0; j-) bestxj = E-Lchild; E = E-parent; return Ew;第30页/共53页批处理作业调度问题例9-4：批处理作业调度问题。 问题描述：给定n个作业的集合J=J1, J2, , Jn，每个作业都有3项任务分别在3台机器上完成，作业Ji需要机器j的处理时间为tij(1in, 1j3)，每个作业必须先由机器1处理，再由机器2处理，最后由机器3处理。 批处理作业调度问题要求确定这n个作业的最优处理顺序，使

27、得从第1个作业在机器1上处理开始，到最后一个作业在机器3上处理结束所需的时间最少。第31页/共53页实例：设J=J1, J2, J3, J4是4个待处理的作业，需要的处理时间如下所示。若处理顺序为(J2, J3, J1, J4)，则从作业2在机器1处理开始到作业4在机器3处理完成的调度方案如下：T 5 7 910 5 2 9 9 5 7 8 10J1J2J3J4机器1 机器2 机器3J2:10 J3:9 J1:5 J4:7机器机器1机器机器2机器机器3( 表示空闲，最后完成处理时间为表示空闲，最后完成处理时间为54)空闲空闲:10 J2:5 空闲空闲:4 J3:9 J1:7 J4:8空闲空闲:

28、15 J2:2 空闲空闲:11 J3:5 空闲空闲:2 J1:9 J4:10等待时间等待时间+处理时间处理时间第32页/共53页 分析： 解向量：X=(x1, x2, ., xn)排列树 约束条件： 显式：xi=J1, J2, ., Jn 目标函数:sum3= 下限界函数：3 2ntnsum3 1 3ntnsum机器机器3有空闲有空闲机器机器3有积压有积压，极小化，极小化minsum2k,1sum1kmax, 132MjkjjMiittdb其中其中， sum2n=maxsum1n, sum2n-1 + tn2 ； sum1n=sum1n-1+ tn1设设M是已安排好的作业集合，是已安排好的作业

29、集合，M 1, 2, ., n, |M|=k。现在要处理作业现在要处理作业k+1，有：，有：sum1k+1=sum1k+ tk+1,1sum2k+1=maxsum1k+1, sum2k + tk+1,2maxsum2n, sum3n-1+tn3 第33页/共53页 目标函数的下界:sum3db= 说明：最理想的情况下，机器1和机器2均无空闲，最后处理的作业恰好是在机器3上处理时间最短的作业。如上实例，sum3db= =36 遍历并估算解空间树上各结点的目标函数的下界值：根结点：sum1=0, sum2=0, M= k=0ikknjjitttmin31212341211tttjjT 5 7 91

30、0 5 2 9 9 5 7 8 10J1J2J3J4机器1 机器2 机器3第34页/共53页 优先队列式分支限界法求解过程：J4, sum1=0+7db=38sum2=152 M= k=1J1, sum1=0+5db=36sum2=5+7=121 M= k=0startsum1=0, sum2=03 M= k=1J2, sum1=0+10db=44sum2=124 M= k=1J3, sum1=0+9db=40sum2=185 M= k=16 M=1 k=2J1J2, sum1=15db=42sum2=207 M=1 k=2J1J3, sum1=14db=38sum2=228 M=1 k=2J

31、1J4, sum1=12db=36sum2=209 M=1, 4 k=3J1J4J2, sum1=22db=41sum2=2710 M=1, 4 k=3J1J4J3, sum1=21db=37sum2=3011 M=1, 4, 3 k=4J1J4J3J2, sum1=31db=36sum24=36PT=2, 3, 4, 5PT=6, 7, 8, 3, 4, 5PT=6, 7, 9, 10, 3, 4, 5PT=6, 7, 9, 11, 3, 4, 5X=(J1, J4, J3, J2)sum3=sum24+t23=38min1-sum2k,sum1kmax,32MjkjjMiittdbsum1

32、k=sum1k-1+ tk,1sum2k=maxsum1k, sum2k-1 + tk,2T 5 7 910 5 2 9 9 5 7 8 10J1J2J3J4机器机器1 机器机器2 机器机器3下界下界sum3db=36第35页/共53页 从上例可知：优先队列式分支限界法中， 扩展结点表PT取得极值的叶子结点就对应的是问题的最优解； 扩展结点的过程，一开始实际类似“深度优先”。 思考： 将例9-2和例9-4改成FIFO式分支限界法，搜索过程有何不同？ 在算法的实现上，FIFO式分支限界法和优先队列式分支限界法的PT表数据结构一样吗？第36页/共53页课后作业 采用分支限界法求解下列作业调度问题，

33、4个作业J1, J2, J3, J4在机器M1, M2上处理的时间矩阵如图所示。求最佳的处理顺序，使得4个作业从开始到结束处理的时间最短。(要求：画出解空间的展开)9710541059CM1M2J1J2J3J4第37页/共53页9.3 最小消耗(LC)搜索法检索 在FIFO分枝限界法中，对下一个E-结点的选择规则相当死板，在某种意义上是盲目的。 对活结点使用一个“有智力”的排序函数 c(.) 来选取下一个E-结点往往可以加快到达一答案结点的速度。 对任意结点x，可用两种标准来量度： 在生成一个答案结点之前，子树x需要生成的结点个数； 在子树x中离x最近的那个答案结点到x的路径长度。第38页/共

34、53页 使用第一种度量： 图中树的根结点付出的代价是4。结点(18和34)，(29和35)以及(30和38)的代价分别是3,2和1。 所有在2,3和4级上剩余结点的代价应分别大于3,2和1。以这些代价作为选择下一个E-结点的依据，则E-结点依次为1,18,29和30。另外，不得已生成的结点为2,34,50,19,24,32。 使用第二种度量，则E-结点只是由根到最近的那个答案结点路径上的那些结点。图图9.1 4-皇后问题皇后问题总是生成最小数目的结点总是生成最小数目的结点第39页/共53页方法要点 对状态空间树上的一个答案结点x, 定义实际代价函数cost(x)。 cost(x)的内涵：从状态

35、空间树根结点出发，到达一个答案结点x，实际需要付出的“代价”。 cost(x)的定义：原则上应根据具体问题加以定义。 对状态空间树上任一结点x，定义代价函数c(x)。c(x)的内涵：从状态空间树根结点出发，经过x结点，在以结点x为根的子树上，搜索到一个答案结点，所需要付出的代价。 定义c(x)的一般原则： 若x是答案结点，则：c(x) = cost(x)；第40页/共53页 若x不是答案结点，但以x为根的子树上至少有一个答案结点，则：c(x) = minc(answer) |answer : x上所有答案结点 若x不是答案结点，且以x为根的子树上也没有答案结点，则：c(x) = + 对状态空间

36、树上结点x, 定义估算函数 ，且使满足： c(x)。 注：与c(x)相比， 应是当前“可计算”的。 设计一个活结点表L，用于存放搜索过程的“活结点”。该表的数据结构可选择有序表或堆。 即要求：活结点表上的所有结点，按照它们估算函数取值，构成一个有序表或堆。)(xc)(xc)(xc=h(x)+g(x)第41页/共53页 LC法搜索过程： 初始：把状态空间树的根结点，做为活结点表L的第一个结点； 重复以下两步，直到找到一个解，或L为空： 从L上选出具有最小 的结点，作为当前E-结点。 依次搜索当前E-结点的所有子结点。若子结点是答案结点，则结束；否则，把子结点加入有序表L。)(xc第42页/共53

37、页方法应用举例 15迷问题。 问题描述：把编号为115的棋子，随意放在44格的棋盘上(空出一个格)。要求：经过有限步的移动，把棋盘上棋子的“初态”，变成棋子号与棋盘号一致的目标状态。(注：“移动”仅限于空格周围棋子)实例： 初态 目标状态124563791012813141115123456789101112131415第43页/共53页 分析： 实际代价函数cost(x): 若x是目标状态，则：cost(x)等于从棋盘初态，经逐步移动棋子而到达目标状态x，实际需要移动棋子总步数。 代价函数c(x): 若x是目标状态，则：c(x) = cost(x) 若x不是目标状态，但x所在子树上存在目标状

38、态结点， 则：c(x) = min c(x) | x：x子树上所有目标状态结点 若x不是目标状态，且x所在子树上也不存在任何目标状态结点，则c(x) = +第44页/共53页 定义估算函数： = h(x) + g(x) 其中，h(x):从状态空间树的根结点到x结点路径长度；g(x)：x状态下，没有达到“目标状态”的棋子数量。124563791012813141115124563791012813141115123456791012813141115124563791012813141115g1=6h1=01g2=7g3=5g4=7234左左下下右右1)(xc第45页/共53页123456791012813141115g3=531123456791012813141115123456791012813141115123456127910813141115123567491012813141115123456789101213141115g5=6657左左右右下下g6=4g7=52g9=3g8=5下下上上983第46页/共53页12345678910121