第九章-分支限界法课件

算法分析与设计主讲:徐晓蓉

计算机科学与技术学院算法分析与设计主讲:徐晓蓉1第九章分枝限界法主要内容一般方法分枝限界法的基本思想分枝限界法的算法框架分枝限界法的分类应用举例数码问题0/1背包旅行商问题第九章分枝限界法主要内容29.1 一般方法1.分支限界法与回溯法的不同（1）概念:

深度优先生成状态空间树中的结点,并使用剪枝函数的的求解方法称为回溯法;

广度优先生成状态空间树中的结点，并使用剪枝函数的求解方法称为分枝限界法.（2）求解目标：

回溯法的求解目标是找出解空间树中满足约束条件的所有解或最优解;

分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

（3）搜索方式的不同：

回溯法以深度优先的方式搜索解空间树;

分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。9.1 一般方法1.分支限界法与回溯法的不同39.1 一般方法2.分支限界法基本思想在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。9.1 一般方法2.分支限界法基本思想49.1 一般方法3.常见的三种分支限界法（1）FIFO分支限界法

活结点表是先进先出队列,按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）LIFO分支限界法

活结点表是堆栈,按照栈后进先出（LIFO）原则选取下一个节点为扩展节点。（3）LC(优先队列式)分支限界法

活结点表是优先权队列，按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。9.1 一般方法3.常见的三种分支限界法5例9-1(4-皇后问题)用FIFO分支限界法求解4-皇后问题9.1 一般方法例9-1(4-皇后问题)用FIFO分支限界法求解4-皇后问题69.1一般方法template<classT>voidBranchBound(Node<T>*t)//t是指向状态空间树的根结点指针{LiveList<Node<T>*>lst(mSize);//lst为活结点表，表中元素为指针类型

Node<T>*x,*E=t; //E指向根结点t

do

{//为方便起见，以下描述中不区分指针与其所指示的结点，用指针代表所指示的结点

for(对结点E的每个不受限的孩子)

{x=newNode;x->parent=E; //构造E的孩子结点x

if(x是一个答案结点)

{ 输出从x到t的一条路径；return;//输出一个解后算法终止}lst.Append(x); //指向活结点的指针x进活结点表

}if(lst.IsEmpty()){cout<<"没有答案结点"；return； //搜索失败终止}lst.Serve(E); //从lst输出一个活结点为E-结点}while（1）；}template<classT>structNode{Tcost;Node*parent;

//状态空间树采用树的双亲表示法，parent是指向其双亲的指针};4.算法控制流程Lst可以是FIFO队列,堆栈或优先权队列9.1一般方法tem79.1 一般方法

回溯法,FIFO分支限界法和LIFO分支限界法选择活结点作为新的扩展结点的方法是盲目的，只是机械的按照FIFO或LIFO原则选取下一个活结点.而LC分支限界法可根据活结点的优先权选择活结点作为扩展结点.9.1 一般方法回溯法,FIFO分支限界法和LIF89.1 一般方法5.LC分支限界法LC分枝限界法:可根据活结点的优先权选择结点作为扩展结点用途:1,求解问题的一个可行解2,求解最优化问题的最优解

采用LC分枝限界法时，为了去掉盲目性，尽快搜索到一个答案结点，可对活结点表使用一个”有智力”的评价函数作为优先权来选择下一个扩展结点，该评价函数通过衡量一个活结点的搜索代价，来确定哪个活结点能够引导尽快到达一个答案结点.9.1 一般方法5.LC分支限界法99.1 一般方法(1)代价函数c(.)C(X)=从根到X的代价X是答案结点无穷X不是答案结点,且X的子树不含答案结点子树X上具有最小搜索代价的答案结点的代价X不是答案结点,但X子树上含答案结点

一个答案结点X的搜索代价cost(X)定义为:从根结点开始，直到搜索到X为止所耗费的搜索时间.假设T1中有三个答案结点，A,B,C其中A的代价最小，B次之，C最大,则C(T)=C(X)=C(Y)=C(A)=cost(A)C(Z)=C(B)=cost(B)C(W)=C(Q)=C(C)=cost(C)C(U)=C(V)=无穷9.1 一般方法(1)代价函数c(.)C(X)=从根到X的代109.1 一般方法(2)相对代价函数g(.)衡量一个结点X的相对代价一般有两种标准:(1),在生成一个答案结点之前，子树X上需要生成的结点数目(2),在子树X上，离X最近的答案结点到X的路径长度

一个答案结点X的搜索代价cost(X)定义为:从根结点开始，直到搜索到X为止所耗费的搜索时间.假设T2中有三个答案结点，A,B,C采用标准(1),g(X)=4,g(Y)=3,g(Z)=2先找到答案结点C采用标准(2),g(X)=1,g(Y)=g(Z)=2先找到答案结点A9.1 一般方法(2)相对代价函数g(.)衡量一个结点X的相11(4)代价估计函数作为g(X)的估计值，用于估计结点X的相对代价，它是由X到达一个答案结点所需代价的估计函数,一般的满足如下性质:如果Y是X的孩子，则有9.1 一般方法(3)相对代价估计函数由两部分组成，从根到X的代价f(X)和从X到答案结点的估计代价:即一般而言，可令f(X)等于X在树中的层次LC-检索及LC分枝限界法

以代价估计函数作为选择下一个扩展结点的评价函数，即总是选取值最小的活结点为下一个E-结点.这种搜索策略称为最小成本检索,简称LC-检索采用LC检索并伴之有限界函数的方法，称为LC分枝限界法

(4)代价估计函数作为g(X)的估计值，用于129.1 一般方法

15数码问题描述如下:在一个4*4的方形棋盘上放置了15块编了号的牌，还剩下一个空格,棋盘上的号牌的一次合法移动是指将位于空格四周(上下左右)的一块号牌移入空格位置的四种移动方式.问题要求对于任意给定的一种初始排列，通过一系列的合法移动，将给定的初始排列转换成所给定的目标排列，初始排列和目标排列是15数码问题的初始状态和目标状态.用LC分枝限界法求解数码问题

若从某一个状态出发，经过一系列合法的移动能够到达另一个状态，则称后者可由前者到达.9.1 一般方法15数码问题描述如下:在一个4139.1 一般方法15数码问题的解空间大小:16!=20.9*10^12

对于任意给定的初始状态，它可以到达的其他状态只有其中的一半.假定棋盘上16个方格所在位置的编号如图9-3所示的目标状态的牌号相同,设Less(i)为满足下列情况的号牌的数目:这些号牌的牌号小于i,但当前被放置在号牌i的位置之后.定理9-1,对给定的初始状态,当且仅当为偶数时,可以由此初始状态到达目标状态,其中i和j分别是空格在棋盘上的行和列的下标.用LC分枝限界法求解数码问题15数码问题的状态空间树是以给定的初始状态为根结点的树.9.1 一般方法15数码问题的解空间大小:16!=20.9*14分析:1.状态结点为棋盘的某一状态2,状态结点X的孩子是从状态X通过一个合法的移动可以到达的状态.3,代价函数为初始状态到目标状态所需移动数字块的次数最小代价估计函数可定义为:9.1 一般方法12346758从根到X所移动的次数+不在其位的非空白牌的数目实际耗费的代价还未到位的数字,表示至少还要移动的次数12345678初始状态目标状态分析:9.1 一般方法12346758从根到X所移动的次数+159.1 一般方法12345678从根到X所移动的次数+不在其位的非空白牌的数目初始状态目标状态123467581234567812345678134267581234675812346758上下左右右思考1：

还有没有其他的定义方法？如:X状态与目标状态相同的号牌之间的位置差之和思考2：当目标状态非i号牌放在i处时，less(i)该如何定义？如:Less(i)定义为:这些号牌在i号牌之前，但当前被放置在i号牌之后1+1=21+3=41+3=41+3=49.1 一般方法12345678从根到X所移动的次数+不在其169.1 一般方法123847658321476523184765初始状态目标状态283147652318476523184765283164752831476528314765上下左右右Less(i)定义为:这些号牌在i号牌之前，但当前被放置在i号牌之后123847652837146512384765左上下下右1+3=41+4=51+3=41+4=52+4=62+2=42+3=52+4=63+1=44+0=49.1 一般方法1238476583214765231847179.2 求最优解的分枝限界法9.2.1上下界函数

当分枝限界法用于求最优解时,为了进一步压缩所需生成的状态空间树的结点数目，需要使用上下界函数作为限界函数,剪去不含最优解的分枝.定义9-1(代价函数)

状态空间树上一个结点X的代价函数C(X)定义为:

C(X)=X所代表的可行解的目标函数值X是答案结点

无穷X非可行结点子树X上具有最小代价的结点代价X代表部分向量定义9-2(上下界函数)

函数u(X)和分别是代价函数C(X)的上界和下界函数.对所有结点X,总有对于许多问题虽然不能确切求得C(X),但却能得到和u(X).9.2 求最优解的分枝限界法9.2.1上下界函数当18如：当目标函数取最小值时为最优解时,(1).算法需要一个上界变量设为U,保存到目前为止已知的关于最小代价的上界值,即最小代价答案结点的代价值不会超过U,(2).任意结点X,若则X子树可剪去.在搜索到一个答案结点之后，所有满足的子树X都可以剪去.

注意：在搜索到一个答案结点之前以作为剪枝条件，会将最小答案结点误剪除掉，为了既能运用作为剪枝条件，又不至于误剪去包含最小答案结点的子树，可对所有结点X，使用u(X)+ε作为该子树的最小代价上界值，ε是一个小量9.2 求最优解的分枝限界法9.2 求最优解的分枝限界法199.2 求最优解的分枝限界法基于上下界函数的分枝限界法的限界方法:

算法要求U的初值大于最优解的代价，并在搜索状态空间树的过程中不断修正U的值，对于某个结点X,U的值可按如下原则修正:(1)若X是答案结点,cost(X)是X所代表的可行解的目标函数值，U(X)是该子树上最小代价答案结点代价的上界值，则U=min(cost(X),U(X)+ε,U)(2)如果Ｘ代表部分向量，则U=min(U(X)+ε,U)9.2 求最优解的分枝限界法基于上下界函数的分枝限界法的限界209.4 0/1背包9.4.1问题描述

形式化描述:给定C>0,wi>0，pi>0，要求X=(x0,x1…xn-1)使得且9.4 0/1背包9.4.1问题描述给定C>0,219.4 0/1背包(1)目标函数:(求最大值)(2)代价函数:(3)上下界函数:LBB(X),UBB(X)C(X)=cost(X)X是答案结点负无穷X是叶结点但非答案结点Max{c(rchild(X)),c(lchild(X))}X代表部分向量9.4.2分枝限界法求解

对0/1背包问题的解的结构，约束条件,目标函数和状态空间树的分析与回溯法时相同.求解0/1背包问题的一个关键问题是设计上下界函数.9.4 0/1背包(1)目标函数:22由此，可得0/1背包问题的代价函数和上下界函数:(1)代价函数:(2)下界函数:(3)上界函数:9.4 0/1背包9.4.2分枝限界法求解

X是状态空间树上的结点，从根到X的部分向量为(x0,x1…xk-1),背包的剩余载重为cu,以X为根的子树可以看成背包载重为cu,由剩余物品组成物品集的0/1背包的状态空间树:设Z代表子树X上一般背包问题的最优解(zk,zk+1,…zn-1),ans代表0/1背包的最优解(xk,xk+1,…xn-1),Y代表0/1背包的任一可行解(yk,yk+1,…yn-1),则必有:这是X子树上最大代价答案结点代价的下界估计值这是X子树上最大代价答案结点代价的上界估计值由此，可得0/1背包问题的代价函数和上下界函数:9.4 0239.4 0/1背包9.4.2分枝限界法求解求解0/1背包问题的分枝限界法:

(1)定义一个下界变量L,记录当前为止最大代价答案结点代价的下界值(2)生成根结点,计算根结点的上下界值UBB和LBB(3)令L=LBB-ε(4)若X是答案结点，且该答案结点的收益prof大于L,则记录该答案结点，并令L=prof,(5)若X不是答案结点，若左儿子结点可行，即(cu>w[k]),则生成左儿子结点(UBB不变),否则，计算右孩子的上下界，若右孩子的上界大于L,则生成右孩子结点，若右孩子的下界-ε大于L,则令L=LBB-ε;(6)当活结点(优先权队列)为空时或当扩展结点的上界<=L时，结束例:9-2.M=16,n=4W=(2,4,6,9),P=(10,10,12,18)9.4 0/1背包9.4.2分枝限界法求解例:9-2.249.4 0/1背包9.4.2分枝限界法求解求解0/1背包问题的分枝限界法:例:9-2.M=16,n=4W=(2,4,6,9),P=(10,10,12,18)123435756385639.4 0/1背包9.4.2分枝限界法求解例:9-2.259.5旅行商问题9.5.1.问题描述

某售货员要到n个城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。9.5.2.分枝限界法求解

设带权有向图G=(V,E)|V|=n,表示连接n个城市的道路交通图,边上的权值为两个城市之间的路程,c[n][n]是该图的邻接矩阵(代价矩阵)1)解的结构可表示为(x0,x1…xn-1,xn),x0=xn0≤xi≤n-1xi≠xj,i≠j且i,j≠0或n;<xi,xi+1>∈E,0≤i<n-1

目标函数是路径长度9.5旅行商问题9.5.1.问题描述9.5.2.分枝限269.5旅行商问题2)上下界函数的设计定义9-3,如果矩阵的一行(列)中至少包含一个零且其余元素非负，则称此行(或列)已归约定义9-4,如果一个矩阵的所有行和列均已归约,则称此矩阵为归约矩阵归约的方法:对矩阵的一行(列)进行归约，可通过将该行(列)中的每个元素减去该行(列)的最小数进行,此最小数称为该行(列)的约数归约矩阵:可通过逐行逐列归约一个代价矩阵而得到矩阵约数:所有行和所有列的约数之和称为矩阵约数例:矩阵归约的过程可以理解为:对原图象进行某种处理，使得边上权值变小，但图的结构不变9.5旅行商问题2)上下界函数的设计279.5旅行商问题2)上下界函数的设计根的下界函数∵归约矩阵非负∴归约代价矩阵所代表的周游路径长度非负，故矩阵约数L的长度≤原图的任意一条周游路径长度∴可将L作为旅行商问题状态空间树根R的下界函数值非叶状态的下界函数状态空间树中，若状态P是状态X的双亲,边<P,X>代表周游路线中的一条边<i,j>.设P和X状态的归约矩阵为A和B,X是非叶状态由A计算B的过程分为如下两步:(1)将矩阵A的第i行和第j列的所有元素及元素A[j][0]都置成∞得到A’;(2)对A’实施归约得到BX状态的下界函数值为9.5旅行商问题2)上下界函数的设计289.5旅行商问题2)上下界函数的设计叶状态的下界函数若S是叶状态结点,由于一个叶状态唯一确定一条周游路径,可用此周游路径作为结点S的代价值,即上界函数:对于树中任何状态结点X,令上界函数值u(X)=∞3)lc分支限界法求解该问题的过程(1)生成状态空间树的根结点，作为扩展结点E,并令u=∞（2）若该结点为答案结点，则计算其代价,修改u,否则,进第（3）步（3）生成扩展节点E的孩子结点，并分别计算他们的下界函数值，作为优先权，进优先权队列，选择优先级（即下界函数值最小）最高的结点继续扩展，重复（2）（3）（4）若优先权队列中的所有结点都下界函数值都大于u，则结束。9.5旅行商问题2)上下界函数的设计299.5旅行商问题9.5旅行商问题30（1）分枝限界法:广度优先生成树中结点并使用剪枝函数的方法.（2）适合求解的问题:求一个可行解的问题和最优化问题（3）分枝限界法的分类:FIFO分支限界法LIFO分支限界法LC分支限界法（4）分枝限界法的基本思想

在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

总结与作业总结：（1）分枝限界法:广度优先生成树中结点并使用剪枝函数的方法.31总结与作业作业：P224：9-8,9-9总结与作业作业：P224：9-8,9-9329.2 求最优解的分枝限界法9.2.2FIFO分枝限界法Node<T>*FIFOBB(Node<T>*t,T&U){//t是指向状态树根指针,U的初值应大于最优解值,U返回最优解值,函数返回答案结点指针ansLiveList<Node<T>*>lst(mSize); //lst为FIFO队列Node<T>*ans=NULL,*x,*E=t; //ans指向答案结点，E为扩展结点do{ for(对结点E的每个孩子) //所有满足约束条件的孩子{x=newNode;x->parent=E; //构造E的孩子结点xif((x)<U) //未被限界函数剪枝的子树根x{lst.Append(x); //x进队列if(x是一个答案结点&&cost(x)<U) //x为答案结点时修正Uif(u(x)+<cost(x))U=u(x)+;else{U=cost(x);ans=x;}elseif(u(x)+<U)U=u(x)+; //x为非答案结点时修正U}}do{if(lst.IsEmpty())returnans;//若队列为空，则返回指针anslst.Serve(E); //从队列中取出活结点}while((E)≥U); //当(E)<U时，E成为扩展结点}while（1）；}只有当活结点表为空时，算法才结束.9.2 求最优解的分枝限界法9.2.2FIFO分枝限界法N339.2 求最优解的分枝限界法9.2.3LC分枝限界法Node<T>*LCBB(Node<T>*t,T&U){LiveList<Node<T>*>lst(mSize); //lst为优先权队列Node<T>*ans=NULL,*x,E=*t;do{for(对结点E的每个孩子) //所有满足约束函数的孩子{x=newNode;x->parent=E; //构造E的孩子结点xif((x)<U) //x子树未被限界函数剪枝{lst.Append(x);if(x是一个答案结点&&cost(x)<U) //x为答案结点时修正Uif(u(x)+<cost(x))U=u(x)+;else{U=coxt(x);ans=x;}elseif(u(x)+<U)U=u(x)+; //x为非答案结点时修正U}}if(!lst.IsEmpty()){lst.Serve(E); //从队列中取出活结点Eif((E)≥U)returnans; //若(E)≥U，则算法结束}elsereturnans; //若队列为空，则算法结束}while（1）；}以优先权队列为空或C(X)>=U为算法终止条件.9.2 求最优解的分枝限界法9.2.3LC分枝限界法Nod34算法分析与设计主讲:徐晓蓉

计算机科学与技术学院算法分析与设计主讲:徐晓蓉35第九章分枝限界法主要内容一般方法分枝限界法的基本思想分枝限界法的算法框架分枝限界法的分类应用举例数码问题0/1背包旅行商问题第九章分枝限界法主要内容369.1 一般方法1.分支限界法与回溯法的不同（1）概念:

深度优先生成状态空间树中的结点,并使用剪枝函数的的求解方法称为回溯法;

广度优先生成状态空间树中的结点，并使用剪枝函数的求解方法称为分枝限界法.（2）求解目标：

回溯法的求解目标是找出解空间树中满足约束条件的所有解或最优解;

分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

（3）搜索方式的不同：

回溯法以深度优先的方式搜索解空间树;

分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。9.1 一般方法1.分支限界法与回溯法的不同379.1 一般方法2.分支限界法基本思想在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。9.1 一般方法2.分支限界法基本思想389.1 一般方法3.常见的三种分支限界法（1）FIFO分支限界法

活结点表是先进先出队列,按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）LIFO分支限界法

活结点表是堆栈,按照栈后进先出（LIFO）原则选取下一个节点为扩展节点。（3）LC(优先队列式)分支限界法

活结点表是优先权队列，按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。9.1 一般方法3.常见的三种分支限界法39例9-1(4-皇后问题)用FIFO分支限界法求解4-皇后问题9.1 一般方法例9-1(4-皇后问题)用FIFO分支限界法求解4-皇后问题409.1一般方法template<classT>voidBranchBound(Node<T>*t)//t是指向状态空间树的根结点指针{LiveList<Node<T>*>lst(mSize);//lst为活结点表，表中元素为指针类型

Node<T>*x,*E=t; //E指向根结点t

do

{//为方便起见，以下描述中不区分指针与其所指示的结点，用指针代表所指示的结点

for(对结点E的每个不受限的孩子)

{x=newNode;x->parent=E; //构造E的孩子结点x

if(x是一个答案结点)

{ 输出从x到t的一条路径；return;//输出一个解后算法终止}lst.Append(x); //指向活结点的指针x进活结点表

}if(lst.IsEmpty()){cout<<"没有答案结点"；return； //搜索失败终止}lst.Serve(E); //从lst输出一个活结点为E-结点}while（1）；}template<classT>structNode{Tcost;Node*parent;

//状态空间树采用树的双亲表示法，parent是指向其双亲的指针};4.算法控制流程Lst可以是FIFO队列,堆栈或优先权队列9.1一般方法tem419.1 一般方法

回溯法,FIFO分支限界法和LIFO分支限界法选择活结点作为新的扩展结点的方法是盲目的，只是机械的按照FIFO或LIFO原则选取下一个活结点.而LC分支限界法可根据活结点的优先权选择活结点作为扩展结点.9.1 一般方法回溯法,FIFO分支限界法和LIF429.1 一般方法5.LC分支限界法LC分枝限界法:可根据活结点的优先权选择结点作为扩展结点用途:1,求解问题的一个可行解2,求解最优化问题的最优解

采用LC分枝限界法时，为了去掉盲目性，尽快搜索到一个答案结点，可对活结点表使用一个”有智力”的评价函数作为优先权来选择下一个扩展结点，该评价函数通过衡量一个活结点的搜索代价，来确定哪个活结点能够引导尽快到达一个答案结点.9.1 一般方法5.LC分支限界法439.1 一般方法(1)代价函数c(.)C(X)=从根到X的代价X是答案结点无穷X不是答案结点,且X的子树不含答案结点子树X上具有最小搜索代价的答案结点的代价X不是答案结点,但X子树上含答案结点

一个答案结点X的搜索代价cost(X)定义为:从根结点开始，直到搜索到X为止所耗费的搜索时间.假设T1中有三个答案结点，A,B,C其中A的代价最小，B次之，C最大,则C(T)=C(X)=C(Y)=C(A)=cost(A)C(Z)=C(B)=cost(B)C(W)=C(Q)=C(C)=cost(C)C(U)=C(V)=无穷9.1 一般方法(1)代价函数c(.)C(X)=从根到X的代449.1 一般方法(2)相对代价函数g(.)衡量一个结点X的相对代价一般有两种标准:(1),在生成一个答案结点之前，子树X上需要生成的结点数目(2),在子树X上，离X最近的答案结点到X的路径长度

一个答案结点X的搜索代价cost(X)定义为:从根结点开始，直到搜索到X为止所耗费的搜索时间.假设T2中有三个答案结点，A,B,C采用标准(1),g(X)=4,g(Y)=3,g(Z)=2先找到答案结点C采用标准(2),g(X)=1,g(Y)=g(Z)=2先找到答案结点A9.1 一般方法(2)相对代价函数g(.)衡量一个结点X的相45(4)代价估计函数作为g(X)的估计值，用于估计结点X的相对代价，它是由X到达一个答案结点所需代价的估计函数,一般的满足如下性质:如果Y是X的孩子，则有9.1 一般方法(3)相对代价估计函数由两部分组成，从根到X的代价f(X)和从X到答案结点的估计代价:即一般而言，可令f(X)等于X在树中的层次LC-检索及LC分枝限界法

以代价估计函数作为选择下一个扩展结点的评价函数，即总是选取值最小的活结点为下一个E-结点.这种搜索策略称为最小成本检索,简称LC-检索采用LC检索并伴之有限界函数的方法，称为LC分枝限界法

(4)代价估计函数作为g(X)的估计值，用于469.1 一般方法

15数码问题描述如下:在一个4*4的方形棋盘上放置了15块编了号的牌，还剩下一个空格,棋盘上的号牌的一次合法移动是指将位于空格四周(上下左右)的一块号牌移入空格位置的四种移动方式.问题要求对于任意给定的一种初始排列，通过一系列的合法移动，将给定的初始排列转换成所给定的目标排列，初始排列和目标排列是15数码问题的初始状态和目标状态.用LC分枝限界法求解数码问题

若从某一个状态出发，经过一系列合法的移动能够到达另一个状态，则称后者可由前者到达.9.1 一般方法15数码问题描述如下:在一个4479.1 一般方法15数码问题的解空间大小:16!=20.9*10^12

对于任意给定的初始状态，它可以到达的其他状态只有其中的一半.假定棋盘上16个方格所在位置的编号如图9-3所示的目标状态的牌号相同,设Less(i)为满足下列情况的号牌的数目:这些号牌的牌号小于i,但当前被放置在号牌i的位置之后.定理9-1,对给定的初始状态,当且仅当为偶数时,可以由此初始状态到达目标状态,其中i和j分别是空格在棋盘上的行和列的下标.用LC分枝限界法求解数码问题15数码问题的状态空间树是以给定的初始状态为根结点的树.9.1 一般方法15数码问题的解空间大小:16!=20.9*48分析:1.状态结点为棋盘的某一状态2,状态结点X的孩子是从状态X通过一个合法的移动可以到达的状态.3,代价函数为初始状态到目标状态所需移动数字块的次数最小代价估计函数可定义为:9.1 一般方法12346758从根到X所移动的次数+不在其位的非空白牌的数目实际耗费的代价还未到位的数字,表示至少还要移动的次数12345678初始状态目标状态分析:9.1 一般方法12346758从根到X所移动的次数+499.1 一般方法12345678从根到X所移动的次数+不在其位的非空白牌的数目初始状态目标状态123467581234567812345678134267581234675812346758上下左右右思考1：

还有没有其他的定义方法？如:X状态与目标状态相同的号牌之间的位置差之和思考2：当目标状态非i号牌放在i处时，less(i)该如何定义？如:Less(i)定义为:这些号牌在i号牌之前，但当前被放置在i号牌之后1+1=21+3=41+3=41+3=49.1 一般方法12345678从根到X所移动的次数+不在其509.1 一般方法123847658321476523184765初始状态目标状态283147652318476523184765283164752831476528314765上下左右右Less(i)定义为:这些号牌在i号牌之前，但当前被放置在i号牌之后123847652837146512384765左上下下右1+3=41+4=51+3=41+4=52+4=62+2=42+3=52+4=63+1=44+0=49.1 一般方法1238476583214765231847519.2 求最优解的分枝限界法9.2.1上下界函数

当分枝限界法用于求最优解时,为了进一步压缩所需生成的状态空间树的结点数目，需要使用上下界函数作为限界函数,剪去不含最优解的分枝.定义9-1(代价函数)

状态空间树上一个结点X的代价函数C(X)定义为:

C(X)=X所代表的可行解的目标函数值X是答案结点

无穷X非可行结点子树X上具有最小代价的结点代价X代表部分向量定义9-2(上下界函数)

函数u(X)和分别是代价函数C(X)的上界和下界函数.对所有结点X,总有对于许多问题虽然不能确切求得C(X),但却能得到和u(X).9.2 求最优解的分枝限界法9.2.1上下界函数当52如：当目标函数取最小值时为最优解时,(1).算法需要一个上界变量设为U,保存到目前为止已知的关于最小代价的上界值,即最小代价答案结点的代价值不会超过U,(2).任意结点X,若则X子树可剪去.在搜索到一个答案结点之后，所有满足的子树X都可以剪去.

注意：在搜索到一个答案结点之前以作为剪枝条件，会将最小答案结点误剪除掉，为了既能运用作为剪枝条件，又不至于误剪去包含最小答案结点的子树，可对所有结点X，使用u(X)+ε作为该子树的最小代价上界值，ε是一个小量9.2 求最优解的分枝限界法9.2 求最优解的分枝限界法539.2 求最优解的分枝限界法基于上下界函数的分枝限界法的限界方法:

算法要求U的初值大于最优解的代价，并在搜索状态空间树的过程中不断修正U的值，对于某个结点X,U的值可按如下原则修正:(1)若X是答案结点,cost(X)是X所代表的可行解的目标函数值，U(X)是该子树上最小代价答案结点代价的上界值，则U=min(cost(X),U(X)+ε,U)(2)如果Ｘ代表部分向量，则U=min(U(X)+ε,U)9.2 求最优解的分枝限界法基于上下界函数的分枝限界法的限界549.4 0/1背包9.4.1问题描述

形式化描述:给定C>0,wi>0，pi>0，要求X=(x0,x1…xn-1)使得且9.4 0/1背包9.4.1问题描述给定C>0,559.4 0/1背包(1)目标函数:(求最大值)(2)代价函数:(3)上下界函数:LBB(X),UBB(X)C(X)=cost(X)X是答案结点负无穷X是叶结点但非答案结点Max{c(rchild(X)),c(lchild(X))}X代表部分向量9.4.2分枝限界法求解

对0/1背包问题的解的结构，约束条件,目标函数和状态空间树的分析与回溯法时相同.求解0/1背包问题的一个关键问题是设计上下界函数.9.4 0/1背包(1)目标函数:56由此，可得0/1背包问题的代价函数和上下界函数:(1)代价函数:(2)下界函数:(3)上界函数:9.4 0/1背包9.4.2分枝限界法求解

X是状态空间树上的结点，从根到X的部分向量为(x0,x1…xk-1),背包的剩余载重为cu,以X为根的子树可以看成背包载重为cu,由剩余物品组成物品集的0/1背包的状态空间树:设Z代表子树X上一般背包问题的最优解(zk,zk+1,…zn-1),ans代表0/1背包的最优解(xk,xk+1,…xn-1),Y代表0/1背包的任一可行解(yk,yk+1,…yn-1),则必有:这是X子树上最大代价答案结点代价的下界估计值这是X子树上最大代价答案结点代价的上界估计值由此，可得0/1背包问题的代价函数和上下界函数:9.4 0579.4 0/1背包9.4.2分枝限界法求解求解0/1背包问题的分枝限界法:

(1)定义一个下界变量L,记录当前为止最大代价答案结点代价的下界值(2)生成根结点,计算根结点的上下界值UBB和LBB(3)令L=LBB-ε(4)若X是答案结点，且该答案结点的收益prof大于L,则记录该答案结点，并令L=prof,(5)若X不是答案结点，若左儿子结点可行，即(cu>w[k]),则生成左儿子结点(UBB不变),否则，计算右孩子的上下界，若右孩子的上界大于L,则生成右孩子结点，若右孩子的下界-ε大于L,则令L=LBB-ε;(6)当活结点(优先权队列)为空时或当扩展结点的上界<=L时，结束例:9-2.M=16,n=4W=(2,4,6,9),P=(10,10,12,18)9.4 0/1背包9.4.2分枝限界法求解例:9-2.589.4 0/1背包9.4.2分枝限界法求解求解0/1背包问题的分枝限界法:例:9-2.M=16,n=4W=(2,4,6,9),P=(10,10,12,18)123435756385639.4 0/1背包9.4.2分枝限界法求解例:9-2.599.5旅行商问题9.5.1.问题描述

某售货员要到n个城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。9.5.2.分枝限界法求解

设带权有向图G=(V,E)|V|=n,表示连接n个城市的道路交通图,边上的权值为两个城市之间的路程,c[n][n]是该图的邻接矩阵(代价矩阵)1)解的结构可表示为(x0,x1…xn-1,xn),x0=xn0≤xi≤n-1xi≠xj,i≠j且i,j≠0或n;<xi,xi+1>∈E,0≤i<n-1

目标函数是路径长度9.5旅行商问题9.5.1.问题描述9.5.2.分枝限609.5旅行商问题2)上下界函数的设计定义9-3,如果矩阵的一行(列)中至少包含一个零且其余元素非负，则称此行(或列)已归约定义9-4,如果一个矩阵的所有行和列均已归约,则称此矩阵为归约矩阵归约的方法:对矩阵的一行(列)进行归约，可通过将该行(列)中的每个元素减去该行(列)的最小数进行,此最小数称为该行(列)的约数归约矩阵:可通过逐行逐列归约一个代价矩阵而得到矩阵约数:所有行和所有列的约数之和称为矩阵约数例:矩阵归约的过程可以理解为:对原图象进行某种处理，使得边上权值变小，但图的结构不变9.5旅行商问题2)上下界函数的设计619.5旅行商问题2)上下界函数的设计根的下界函数∵归约矩阵非负∴归约代价矩阵所代表的周游路径长度非负，故矩阵约数L的长度≤原图的任意一条周游路径长度∴可将L作为旅行商问题状态空间树根R的下界函数值非叶状态的下界函数状态空间树中，若状态P是状态X的双亲,边<P,X>代表周游路线中的一条边<i,j>.设P和X状态的归约矩阵为A和B,X是非叶状态由A计算B的过程分为如下两步:(1)将矩阵A的第i行和第j列的所有元素及元素A[j][0]都置成∞得到A’;(2)对A’实施归约得到BX状态的下界函数值为9.5旅行商问题2)上下界函数的设计629.5旅行商问题2)上下界函数的设计叶状态的下界函数若S是叶状态结点,由于一个叶状态唯一确定一条周游路径,可用此周游路径作为结点S的代价值,即上界函数:对于树中任何状态结点X,令上界函数值u(X)=∞3)lc分支限界法求解该问题的过程(1)生成状态空间树的根结点，作为扩展结点E,并令u=∞（2）若该结点为答案结点，则计算其代价,修改u,否则,进第（3）步（3）生成扩展节点E的孩子结点，并分别计算他们的下界函数值，作为优先权，进优先权队列，选择优先级（即下界函数值最小）最高的结点继续扩展，重复（2）（3）（4）若优先权队列中的所有结点都下界函数值都大于u，则结束。9.5旅行商问题2)上下界函数的设计639.5旅行商问题9.5旅行商问题64（1）分枝限界法:广度优先生成树中结点并使用剪枝函数的方法.（2）适合求解的问题:求一个可行解的问题和最优化问题（3）分枝限界