第七讲-分枝限界法.ppt

1、算法设计与分析,第七讲 分枝限界法,主要内容 FIFO宽度优先检索 LIFO宽度优先检索 LC检索原理 LC, FIFO分枝限界算法 重点 LC检索原理与分枝限界算法的设计思想 难点 限界函数设计,回溯法特点回顾,2) 深度优先的状态空间树扩展,3) 用规范函数判断不可抵达答案节点的节点,4) 终止对某节点的扩展时,生成一个兄弟节点或回溯,1) 用状态空间树的扩展描述解向量的分级求解,7.1 状态空间树的宽度优先扩展方法,例7.1 4皇后问题的状态空间树宽度优先扩展,简单分枝限界算法的分类,1) FIFO分枝限界法,2) LIFO分枝限界法（D检索）,FIFO, LIFO分枝限界法的缺陷,从活

2、节点表中选择活节点存在盲目性,7.2 最小成本(LC: least cost)检索,一、节点成本函数 c(X),表示可能导致抵达答案节点的活节点的成本，定义如下：,如果X是答案节点, 则c(X)是由根节点到答案节点的成本；,如果X不是答案节点, 且子树X不包含任何答案节点, 则c(X)=，,否则, c(X)等于子树X中具有最小成本的答案节点的成本。,精确计算c(X)的复杂度, 等价于求解原问题的复杂度,二、检索成本的估计,用成本估计函数 g(x) 估计c(x) 的值,不恰当的g(x)可能导致纵深检索,改进的节点成本估计函数: c(X) = f(X) + g(X) 其中，f(X)表示由根节点到X

3、检索的成本的非降函数。,三、成本估计函数的构造,初始状态数: 16!20.91012,例7.2 15迷问题,可达状态数: 约为初始状态数的一半,初始状态的状态空间,P(I)：令第I号牌的位置 L(I): JP(I)的牌数,目标状态判定方法,为偶数时, 目标状态可由初始状态到达.,定理1 如图(b)所示, 阴影格X=1, 否则X=0, 当且仅当,(a),(b),15迷问题的成本估计函数,c(X)=f(X)+g(X),f(X): 根节点到X的路径长度； g(X): 不在目标位置的非空白牌数.,四、LC检索 LC检索定义: ,1）g(X)=0, f(X)=X的级数,2）f(X)=0, 且每当Y是X的

4、儿子时g(X)g(Y),两个特例:,LC(TREE T, FUNC (*c) (NODE X) if(T是答案节点) printf(T); return; ActiveList=; E=T; while(1) for(E的每个儿子X) if(X是答案节点) printf(X到T路径上的节点); return; (*c)(X); AddToActiveList(X); Parent(X)=E; if(ActiveList=) printf(“无答案节点”); break; DeleteLeastCost(E) ,检索答案节点的LC算法,存在的问题： 不保证找到有最小成本的答案节点,定理2: 在有

5、限状态空间树T中, 对每一个节点X, 令c(X)是c(X)的估计值, 对每一对节点Y, Z, 当且仅当c(Y)c(Z)时有c(Y)c(Z), 算法LC到达一个最小成本答案节点且终止。,当c(X)c(X), 且答案节点的c(X)=c(X) ,检索最小成本答案节点的LC算法,LC1 (TREE T, FUNC (*c) (NODE X) ActiveList=; E=T; while(1) if(E是答案节点) printf(E到T路径上的节点); return; for(E的每个儿子X) (*c)(X); AddToActiveList(X); Parent(X)=E; if(ActiveLis

6、t=) printf(“无答案节点”); break; DeleteLeastCost(E) ,思考题 如果要求找到状态空间中的所有答案节点，怎样修改LC和LC1算法？,内容回顾,1）基本宽度优先检索的不足之处 2）LC检索的基本原理 3）成本估计函数的设计 4）LC检索过程示例,7.3 分枝-限界算法,一、要点,1) 采用状态空间树描述问题的解空间,5) 用最小成本答案节点的成本上界U对c(X)定界 封杀c(X)U的节点,2) 宽度优先扩展E节点,3) 使用节点的成本函数c(X)来提高搜索效率,4) 节点成本下界估计，c(X)c(X),二、U值的估计方法,1) U的初值不能小于最小成本答案节

7、点的成本,2) 可由启发式方法得到,例如初值可设为, 用u(x)对U进行估计， 在找到一个新的答案节点时, 可以修改U的值.,1) 若U是一个纯粹估计的上界, 保留满足 c(X) U 的活节点X,2) 若U是某个答案节点的成本值, 保留满足 c(X) U 的活节点X,三、节点的封杀方案,3) 统一处理的方法,对非答案节点X, 令U=u(X)+e, 要求满足: u(X)u(Y), u(X)u(X)+eu(Y),对答案节点,令U等于 min ( cost(X), U(X)+e ),满足c(X)U的儿子节点进入活节点表,例7.2 一般化的带限期的作业调度问题,令di表示截止期限, ti表示完成作业需

8、要的时间, pi表示未在截止期限内完成作业所需的罚款。已知： (p1, d1, t1)=(5, 1, 1) (p2, d2, t2)=(10, 3, 2) (p3, d3, t3)=(6, 2, 1) (p4, d4, t4)=(3, 1, 1) 求在截止期限内可完成的且使不能完成的作业罚款最少的作业子集J.,解向量：变长格式或定长格式,四、执行过程举例,(p1, d1, t1)=(5, 1, 1) (p2, d2, t2)=(10, 3, 2) (p3, d3, t3)=(6, 2, 1) (p4, d4, t4)=(3, 1, 1),变长格式的状态空间树,扩展过程,五、BB抽象策略,BB(

9、TREE T) E=T; PARENT(E)=NULL; if(E是解节点) U=min( cost(T), u(T)+e); ans=T; else U=u(T) +e; ans=NULL; ActiveList=; while(1) / Lable1: / Lable2: ,Lable1: for(E的每个儿子X) if(c(X)U) AddToActiveList(X); Parent(X)=E; if(X是解节点 ,Lable2: while(1) if(ActiveList不再存在需要扩展的活节点) printf(“least cost=”, U); while(ans!=NULL)

10、 printf(ans); ans=PARENT(ans); return; DeleteFromActiveList(E); if(c(E)U) break; ,六、实现时需要考虑的问题,1) 并不存在已知的树T，怎样扩展 2) 怎样设计c(X), u(X) 3) 怎样选择常数e 4) 怎样判断解节点 5) 怎样组织、操作活节点表，以实现不同的BB算法 6) 抽象算法得到的只是节点序列，如何得到解向量 7) 效率问题，参见page194,7.4 0/1背包问题,一、解题的基本思路,问题转换,状态空间设计,定长格式向量，状态空间树的第n+1级节点中包含答案节点,不可行节点,非叶子节点,节点成本

11、估计,设根节点为0级，对状态空间树的第 k 级节点 X ，令：,最小成本上界估计,对状态空间树的第 k 级节点 X ，简单估计：,改进的估计算法：,float UBound(W, P, k) while( kn) if(W+wk)=M) P+=pk; W+=wk; k+; return P; ,二、LC分枝限界解题过程示例,例 已知背包问题n=4, M=15 (p1, p2, p3, p4) =(10,10,12,18) (w1,w2,w3,w4) =(2, 4, 6, 9),解题过程,三、LC分枝限界算法,数据类型和变量,typedef struct ND struct ND * paren

12、t; int level; int tag; float W; float P; float cx; Node; MinHeap *ActiveList; float xN, pN, wN;,LCBB算法,LCBB(float e) / Active 为最小堆 int k=0; float U=-UBound( 0, 0, k) +e; Node *E, *X, *ans; MinHeap Active; Init(Active); E=NewNode(NULL, k, 0); ans=NULL; while( (E!=NULL) ,Node * NewNode(Node *parent, i

13、nt level, int tag) Node *X=GetNodeMemory(Node *); X-parent=parent; X-level=level; X-tag=tag; if( parent !=NULL) X-P=parent-P; X-W=parent-W; else X-P=0; X-W=0; if(X-tag=1) X-P +=plevel-1; X-W +=wlevel-1; X-cx=-LBound(X-W, X-P, X-level); return X; ,void Print(float U, Node * ans) printf(“The maximun p

14、rofit is : %fn”, -U); for(i=n; i=1;i+) if(ans-tag=1) xi-1=1; else xi-1=0; printf(“%dn”, xi-1); ans=ans-parent; ,四、FIFO分枝限界算法,解题过程,FIFOBB(float e) / Q为队列类型 int k=0; float U=-UBound(0,0,k) +e; Node *E, *X, *ans; Queue Q; Init(Q); X=NewNode(NULL, k, 0); AddToQ(X); ans=NULL; while(Q is not empty) E=Dele

15、teFrom(Q); if(E-cx=U) continue; k=E-level; if(k=N) if(-E-PP; ans=E; else X=NewNode(E, k+1,0); / xk=0 if(X-cxW, X-P, k+1)+e); if(M-E-W=wk) / xk=1 X=NewNode(E, k+1,1); if(X-cxW, X-P, k+1)+e); Print(U, ans); ,思考与练习题 怎样设计分枝限界算法，使之能实现最大效益检索，对0/1背包问题，如何实现？,7.5 货郎担问题（TSP）,一、问题描述,有向图：,G的一条周游路线：包含n个节点的有向环,周游

16、路线成本：此路线上所有边的成本和,求：具有最小成本的周游路线,成本邻接矩阵：,二、分枝限界算法,解空间表示,不失一般性，以节点1作为起点和终点，解空间,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,2,3,4,3,4,4,3,2,4,4,2,2,3,3,2,c(X)定义,c(X)定义,规约矩阵,已规约行(列)：至少包含一个零且其余元素非负的行(列),规约矩阵：全部行(列)均为已规约行(列)的矩阵,规约方法：将某行(列)减去同一常数ti (ri),矩阵约数：,考虑一个包含5节点的有向图,图G中各周游路线的成本=,图G的最小成本周游路线的下界=,规约矩阵对应的周游路

17、线成本+矩阵约数,矩阵约数,为了得到C(X)，对每个节点都定义一个规约矩阵；已知节点R的规约矩阵A，求儿子节点S（非叶节点）的规约矩阵的步骤：,1）为了保证这条周游路线采用边，将A中i行j列置为；,2）为了防止这条周游路线采用边，将Aj1置为；,3）对于那些不全为 的行施行规约，得到S的规约矩阵B，设其约数为r, 得：,C(S)=C(R)+Aij+r,对每个叶节点，C(X)= C(X),扩展过程举例,最小成本周游路线： 1，4，2，5，3，1,总成本为：28,实现时需要特别考虑的问题,1）怎样定义节点,2）怎样扩展节点，即怎样选择i的值,3）其它同LCBB算法,本讲小结,最小成本检索,分枝限界

18、算法,0/1背包问题,TSP问题,作业调度问题,课外设计,给定一个带期限的作业排序问题(n=5) ： (p1,p2,p3,p4,p5)=(6,3,4,8,5), (t1, t2, t3, t4, t5)= (2,1,2,1,1), (d1,d2,d3,d4,d5)= (3,1,4,2,4), 应用FIFOBB求使总罚款数最小的可行作业集J, 要求: 1）阐述c(X)和u(X)的设计思路，U的初始化方案; 2）针对解向量变长格式, 画出FIFOBB的生成的部分状态空间树, 按活节点生成顺序给节点编号，在各节点位置标出c(X)和u(X)值，给每条边标记选择的作业编号; 3）阐述当U为纯粹的估值或为找到某答案节点后的估值时，对节点的封杀方案；