《算法分析与设计-第09章》由会员分享，可在线阅读，更多相关《算法分析与设计-第09章（66页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析算法设计与分析Design and Analysis of Algorithms In C+Design and Analysis of Algorithms In C+主讲主讲 王海艳王海艳 计算机学院计算机学院 第第9 9章章 分枝限界法分枝限界法基本要求：了解分枝限界法可用于求解可行解或最优解 。理解分枝限界法的剪枝搜索策略，理解使用分 枝限界法求最优化问题时为状态空间树的每个结 点定义上下界函数的作用，掌握分枝限界法的算 法框架并会用分枝限界法的设计策略求解问题的 最优解 。 学习要点： 理解分枝限界法的剪枝搜索策略。 分枝限界法与回溯法的异同。 掌握几种常见的分枝限界法
2、思想： （1）FIFO(先进先出)分枝限界法 （2）LIFO(堆栈,即D-检索)分枝限界法 （3）LC(优先权队列)分枝限界法 分枝限界法的算法框架。 通过应用范例学习分枝限界法的设计策略。 （1）15谜问题 （2）带时限的作业排序 （3）旅行商问题9 9.1 .1 一般方法一般方法9.2 9.2 求最优解的分枝限界法求最优解的分枝限界法9.3 9.3 带时限的作业排序带时限的作业排序9.5 9.5 旅行商问题旅行商问题9.1 一般方法相关概念 (P54)未访问状态：结点尚未访问的状态；x未检测状态：x已访问但其后继未访问；x已检测状态：x已访问且其后继已访问；扩展结点(E-结点)：算法正从x
3、出发，访问 x的某个后继结点y；x被称为扩展结点。活结点：未检测结点；死结点：已检测结点；活结点表：保存活结点的数据结构；D-检索：以栈为活结点表按BFS的算法。9.1.1 分枝限界法概述l采用广度优先产生状态空间树中的结点，并使用剪枝函数的方法称为分枝限界法。l采用深度优先产生状态空间树中的结点，并使用剪枝函数的方法称为回溯法。l分枝限界法的基本做法是：l以广度优先的方式搜索问题的状态空间树。每一个 活结点只有一次机会成为E-结点。l按照广度优先原则，活结点一旦成为E-结点R后，就依次生成它的所有孩子结点。在这些孩子结点中， 导致不可行解或导致非最优解的孩子结点被舍弃，其 余孩子结点被一一加
4、入活结点表中。 l然后R自身成为死结点，从活结点表中取下一结点 成为当前E-结点，重复上述结点扩展过程, 直到找到所需的解或活结点表为空时为止。 分枝限界法分类按活结点表的结构FIFO分枝限界法活结结点表是队队列；按队列的FIFO原则选取 下一个结点为当前扩展结点；LIFO分枝限界法（D-检索）活结点表是栈；按栈的LIFO原则选取下一 个结点为当前扩展结点；LC分枝限界法活结点表是优先权队列优先权队列；按优先权队列中 规定的结点优先级选取优先级最高的下一个 结点为当前扩展结点。例9-1 FIFO分枝限界法求解4-皇后问题03113212389112B13161415312BBBB0321819
5、242B2932303102ansBB031343540 B45383613BB021505156B61545212B595702B B12图9-1 FIFO分枝限界法求第一个解对于n-皇后问题, FIFO分枝限界法并不占优, 它 搜索了31个结点, 而回溯法只搜索了16个结点。181 x0=02312930192483131415911x0=1x1=1x1=3x1=2x2=1x2=3x2=2x3=2x2=016x1=1x1=3x1=2x2=1x3=2图8-6 回溯法实际生成的状态空间树的部分BBBBBBBans程序9-1 分枝限界算法框架 Template void BranchBound(
6、Node *t) /t指向空间状态树的根 LiveList * lst(mSize);Node *x, *E=t; /lst为活结点表,表中元素为指针类型 do for (对结点E的每个不受限的孩子) x=new Node; x-parent=E; /构造E的孩子结点x if (x是一个答案节点) 输出从x到t的一条路经; return; /算法终止 lst.Append(x); 程序9-1 分枝限界算法框架（续）if (lst.IsEmpty()/搜索失败终止. cout Node *FIFOBB(Node *t, T /FIFO队列Node *ans=NULL, *x, *E=t;do f
7、or(对结点E的每个孩子) x=new Node; x-parent=E; if(c(x) Node *LCBB(Node *t, T /优先权队列Node *ans=NULL, *x, *E=t;do for(对结点E的每个孩子) x=new Node; x-parent=E; if(c(X)U=14 故X=4被剪枝c=15同理，X=5被剪枝用程序9-2的 FIFOBB搜索图9-7 可变大小元组状态空间树x0=0126712138143910154115c=8x0=3x0=1x0=2U=24 c=0x1=3x1=1x1=2x2=3x2=2 x2=3x2=3x1=3x1=3x1=2u=19 c
8、=0u=14 c=5c=15c=21 u=9 c=0c=8 c=5c=15 c=11c=10(p0,d0,t0)=(5,1,1) (p1,d1,t1)=(10,3,2) (p2,d2,t2)=(6,2,1) (p3,d3,t3)=(3,1,1) u=18u=21U=14X=2出队，成 为E-结点。由于 U=9 故X=7被剪枝c=10同理，X=8被剪枝X=3出队，成 为E-结点。由于 struct qNode qNode()qNode(T p, T los, int sd, int k, Node *pt) prof=p; loss=los; d=sd; ptr=pt; j=k; /当前结点X的
9、下界函数c(X)=lossT prof, loss; /上界函数u(X)=24-profint j, d; /活结点所代表分量xj=j, d是迄今为止的时间Node *ptr; /指向状态空间树中相应的结点 ;活结点表中的 活结点结构prof loss j d ptr程序9-4 带时限作业排序算法(续)template class JS public:JS(T *prof, int *de, int *time, int size);T JSFIFOBB();void GenerateAns(int *x, int private: /p为收益数组T *p, total; /total初始为n
10、个作业收益之和int *t, *d, n;Node *ans,*root; ;JS类程序9-4 带时限作业排序算法(续)template T JS:JSFIFOBB() Node *E,*child;SeqQueue q(mSize); /生成队列E=root=new Node(NULL,-1); /构造根结点qNode ep(0,0,0,-1,root); /ep为扩展结点qNode ec; T U=total; /U是上界变量JSFIFOBB()函数的实现程序9-4 带时限作业排序算法(续)while(1) /loss为已造成的损失, prof为已获收益 T loss=ep.loss, p
11、rof=ep.prof; E=ep.ptr; for(int j=ep.j+1; j=U); JSFIFOBB()函数的实现(续)程序9-4生成的状态空间树结构1 -1 -1NodeNum parent jans2 1 03 1 17 2 28 2 39 3 211 4 34 1 25 1 3(x0, x1)=(2, 3)(p0,d0,t0)=(5,1,1) (p1,d1,t1)=(10,3,2) (p2,d2,t2)=(6,2,1) (p3,d3,t3)=(3,1,1) (p0,d0,t0)=(5,1,1) (p1,d1,t1)=(3,1,1) (p2,d2,t2)=(6,2,1) (p3,d3,t3)=(10,3,2) 作业按时限的非 减次序排列。9.5 旅行商问题9.5.1. 问题描述旅行商问题：一个旅行商准备到n个村庄售货，他从 A村出发经过其他n-1个村庄，又回到出发地，要求 一条最短路径，使得每个村庄都经过且仅经过一次
