计算机算法基础(第七章).ppt

《计算机算法基础(第七章).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

2、表示放置皇后i所在的列号显式约束条件：每个xi只从集合Si={1,2,…,n}取值满足显式约束的所有元组确定一个可能的解空间解空间由nn个n-元组组成隐式约束条件没有两个xi可以相同，而且没有两个皇后可以在同一条斜线上由前者得，所有解都是n-元组(1,2,…,n)的置换，因此，解空间缩小为n！个元组4-皇后问题解空间的树结构结点按深度优先检索编号叶子结点有4！＝24个解空间树结构的术语树中每个结点确定求解问题的一个问题状态(problemstate)由根结点到其它结点的所有路径确定了这个问题的状态空间(statespace)解状态(so

3、lutionstates)是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组（满足显式约束）答案状态(solutionstates)是这样一些解状态S，由根到S的路径确定了问题的一个解（满足隐式约束）解空间的树结构为状态空间树(statespacetree)利用状态空间树解题1设想状态空间树2生成问题状态3确定问题状态中哪些是解状态4哪些解状态是答案状态生成问题状态构造状态空间树状态空间树术语活结点：自己已经生成而其所有的儿子结点还没有全部生成的结点。E-结点（正在扩展的结点）：当前正在生成其儿子结点的活

4、结点。死结点：不再进一步扩展或者其儿子结点已全部生成的生成结点。静态树(statictrees)：树结构与所要解决的问题的实例无关。动态树(dynamictrees)：根据不同的实例而使用不同的树结构。构造状态空间树的两个方法回溯法当前E-结点R，生成一个新的儿子C，则C就变成一个新的E-结点，对子树C完全检测后，R结点再次成为E-结点分枝-限界方法一个E-结点一直保持到变成死结点为止限界函数以上两种方法都使用限界函数杀死还没有全部生成其儿子结点的那些活结点4-皇后问题的限界函数如果(x1,x2,…,xi)是到当前E-结点的路径，那么具有父

5、-子标记xi+1的所有儿子结点是一些这样的结点，它们使得(x1,x2,…,xi+1)表示没有两个皇后正在互相攻击的一种棋盘格局。4-皇后问题-回溯解123412344-皇后问题回溯法vs状态空间树结点按深度优先检索编号叶子结点有4！＝24个4-皇后问题—回溯期间的生成树分枝－限界法在生成当前E-结点全部儿子之后再生成其它活结点的儿子并且，用限界函数帮助避免生成不包含答案结点子树的状态空间FIFO检索：活结点表采用队LIFO检索：活结点表采用栈FIFO分枝－限界法例7.1（4-皇后问题）4-皇后问题—回溯vsFIFO分枝-限界回溯Win！

6、LC-检索（LeastCost）分枝-限界失败的原因对下一个E-结点的选择规则过于死板如何解决？排序，让答案结点排在前面！寻找一种“有智力”的排序函数C(·)，该函数能够让答案结点尽早生成排序的标准下一个E-结点应当是生成答案结点花费成本最小的结点，因此C(·)又称作结点成本函数。LC：LeastCostLC-检索（结点成本）一：在生成一个答案结点之前，子树X需要生成的结点数。二：在子树X中离X最近的那个答案结点到X的路径长度。以图7.1为例节点1、18、34、29、35、30、38可计算其他结点可得到一个范围生成结点（1>2183450>

7、192429>3032>31）LC-检索（结点成本函数）C(·)定义如果X是答案结点，则C(X)是由状态空间树的根结点到X的成本（即花费的代价，可以是级数、计算复杂度等）如果X不是答案结点且子树X不包含任何答案结点，则C(X)＝∞如果X不是答案结点但子树X包含答案结点，则C(X)等于子树X中具有最小成本的答案结点的成本LC-检索（成本估计函数）从前面的两个成本度量标准看，计算C(·)的工作量与原问题的解具有相同复杂度。因此需要成本估计函数g^(X)出现的新问题仅利用g^(X)会导致算法偏向纵深检查，无法有效处理下面这种情况：即g^(W)

8、^(Z)，但Z比W更接近答案结点LC分枝-限界检索c^(X)＝f(h(X))+g^(X)h(X)为根结点到结点X的成本LC-限界检索：选择c^(·)值最小的活结点作为下一个E-结