资源描述：
《9 分枝-限界法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、计算机算法基础分枝－限界法0预备知识问题状态解状态状态空间答案状态状态空间树活结点E-结点死结点等等……本节主要目的通过对n-皇后问题的分析，学习以上概念，并且了解回溯法n-皇后问题描述将n个皇后放置在一个n×n的棋盘上，要求没有两个皇后可以互相攻击。攻击的定义：两个皇后出现在同一行、或同一列、或者同一条斜线上都视为出现了攻击。8-皇后问题的一个解1234567812345678该解的8元组表示:(4,6,8,2,7,1,3,5)n-皇后问题用n-元组(x1,x2,…,xn)表示棋盘上皇后的位置状态下标表示皇后i(i=1,2,…,n)xi表示放置皇后i所在的列号显式约束条件：每
2、个xi只从集合Si={1,2,…,n}取值满足显式约束的所有元组确定一个可能的解空间解空间由nn个n-元组组成隐式约束条件没有两个xi可以相同，而且没有两个皇后可以在同一条斜线上由前者得，所有解都是n-元组(1,2,…,n)的置换，因此，解空间缩小为n！个元组4-皇后问题解空间的树结构结点按深度优先检索编号叶子结点有4！＝24个解空间树结构的术语树中每个结点确定求解问题的一个问题状态(problemstate)由根结点到其它结点的所有路径确定了这个问题的状态空间(statespace)解状态(solutionstates)是这样一些问题状态S，对于这些问题状态，由根到S的那
3、条路径确定了这解空间中的一个元组（满足显式约束）答案状态(solutionstates)是这样一些解状态S，由根到S的路径确定了问题的一个解（满足隐式约束）解空间的树结构为状态空间树(statespacetree)利用状态空间树解题1设想状态空间树2生成问题状态3确定问题状态中哪些是解状态4哪些解状态是答案状态生成问题状态构造状态空间树状态空间树术语活结点：自己已经生成而其所有的儿子结点还没有全部生成的结点。E-结点（正在扩展的结点）：当前正在生成其儿子结点的活结点。死结点：不再进一步扩展或者其儿子结点已全部生成的生成结点。静态树(statictrees)：树结构与所要解决的
4、问题的实例无关。动态树(dynamictrees)：根据不同的实例而使用不同的树结构。构造状态空间树的两个方法回溯法当前E-结点R，生成一个新的儿子C，则C就变成一个新的E-结点，对子树C完全检测后，R结点再次成为E-结点分枝-限界方法一个E-结点一直保持到变成死结点为止限界函数以上两种方法都使用限界函数杀死还没有全部生成其儿子结点的那些活结点分支限界法的基本思想分支限界法与回溯法（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。（2）搜索方式：回溯法以深度
5、优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。类似于回溯法，分支限界法也是一种在问题的解空间树T上搜索问题解的算法。分支限界法以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。分支限界法解题步骤在问题的边带权的解空间树中进行广度优先搜索找一
6、个叶结点使其对应路径的权最小(最大)当搜索到达一个扩展结点时,一次性扩展它的所有儿子将满足约束条件且最小耗费函数目标函数限界的儿子,插入活结点表中从活结点表中取下一结点同样扩展直到找到所需的解或活动结点表为空为止14分支限界法与回溯法的差别分支限界法不仅通过约束条件,而且可通过目标函数的限界来减少无效搜索.回溯法是深度优先搜索,而分支限界法是广度优先搜索.采用广度优先搜索策略的目的是:尽早发现剪枝点.常见的两种分支限界法（1）队列式(FIFO)分支限界法将活结点表组织成一个队列，按照先进先出（FIFO）原则选取下一个结点为扩展结点。（2）优先队列式分支限界法将活结点表组织成一
7、个优先队列，按照规定的优先级选取优先级最高的结点成为当前扩展结点。算法实现时，通常用极大（小）堆来实现最大（小）优先队列，提取堆中下一个结点为当前扩展结点，体现最大（小）费用优先的原则。极大堆满足一个节点必定不小于其子节点，极小堆正好相反。极大堆中最大的元素必定是其根节点，堆排序算法正是根据这个特性而产生的：对一个序列，将其构造为极大堆，然后将根节点（数组首元素）和数组的尾元素交换，之后对除了尾元素之外的序列继续以上过程，直到排序完成。FIFO分枝－限界法 例9.1（4-皇后问题）4-皇后问
