算法分析与 及设计[分枝限界法].pptVIP

第七章 分枝-限界法;上章知识回顾;n-皇后问题描述;8-皇后问题的一个解;n-皇后问题;利用状态空间树解题;状态空间树术语;构造状态空间树的两个方法;4-皇后问题的限界函数;4-皇后问题回溯法vs状态空间树;4-皇后问题—回溯期间的生成树;分枝－限界法;FIFO分枝－限界法例7.1（4-皇后问题）;4-皇后问题—回溯 vs FIFO分枝-限界;LC-检索（Least Cost）;分枝-限界策略的种类;LC-检索（结点成本的两个标准）;LC-检索（结点成本函数）;LC-检索（成本估计函数）;LC分枝-限界检索;例：15-谜问题;例：15-谜问题;例：15-谜问题; 对于任意一种状态，设LESS (i)是使牌j 小于牌i ，且使POSITION(j) POSITION(i)的数目。 例如，对于图7.2(a)所示的状态，有LESS (1)=0， LESS (4)=1和LESS (12)=6。 在初始状态下，如果空格在图7.2?的阴影位置中的某一格处，则令X=1；否则X=0。 于是有定理7.1： 当且仅当∑LESS (i)+X（1 ≤i≤16)是偶数时，图7.2(b)所示的目标状态可由此初始状态到达。 可以用定理7.1来判定目标状态是否在初始状态的状态空间中。若在，就可以着手确定导致目标状态的一系列移动。; 为了实现这一检索，可以将此状态空间构造成一棵树。在这棵树中，每一个结点的儿子表示由状态X通过一次合法的移动可到达的状态。 不难看出，移动牌与移动空格实质上是等效的，而且在作实际移动时，因此以后都将父状态到子状态的一次转换看成是空格的一次合法移动。 ;15-谜问题(宽度优先);15-谜问题(宽度优先前十步);例：15-谜问题;例：15-谜问题;15-谜问题（使用^C (X)的LC-检索）;例：15-谜问题;分支限界法的基本思想;分支限界法的基本思想;LC-检索的抽象化控制;算法7.1 LC-检索;LC-检索说明;LC-检索的抽象化控制（vs. BFS, D-Search）;LC-检索的特性;LC-检索的特性;LC-检索的特性;算法7.2 找最小成本答案结点的LC-检索;定理7.3 令^C(.)是满足如下条件的函数，在状态空间树T中，对于每一个结点X，有^C(X)≤C(X),而对于T中的每一个答案结点X，有^C(X)=C(X)。如果算法在第5行终止，则所找到的答案结点是具有最成本的答案结点。;分枝-限界算法;分枝-限界算法;实例：带限期的作业排序问题;N=4;(p1,d1,t1)=(5,1,1); (p2,d2,t2)=(10,3,2); (p3,d3,t3)=(6,2,1); (p4,d4,t4)=(3,1,1);;图7.8 大小固定的元组表示对应的状态空间树;实例：带限期的作业排序问题;实例：带限期的作业排序问题;实例：带限期的作业排序问题;实例：带限期的作业排序问题;上界U的确定;找最小成本答案结点的FIFO分枝-限界方法;找最小成本答案结点的FIFO分枝-限界算法;找最小成本结点的LC分枝限界算法;效率分析;定理7.4;定理7.5;定理7.6;定理7.7;定理7.7的证明;7.2 0/1背包问题;上界函数;估价函数^C(X)的定义;7.2.1 LC分枝-限界求解;1;例7.2 [LCBB];例7.2 [LCBB];LCBB求解背包问题分析;状态空间树中结点的结构;如何生成一给定结点的儿子;如何识别答案结点;如何表示活结点表;计算上界和下界的算法;生成一个新结点;背包问题的LC分枝-限界算法;背包问题的LC分枝-限界算法;背包问题的LC分枝-限界算法;7.2.2 FIFO分枝-限界求解;1;背包问题FIFO分枝-限界算法;背包问题FIFO分枝-限界算法;7.3 货郎担问题;货郎担问题的状态空间树;用LC分枝-限界法检索货郎担问题的状态空间树;归约矩阵;矩阵约数;估计函数^C(.)的定义;估计函数^C(.)的定义;估计函数^C(.)的定义;上界函数u(.)的定义;用LC分枝-限界法求解货郎担问题;用LC分枝-限界法求解货郎担问题;用LC分枝-限界法求解货郎担问题