第八章 Tree Searching Strategies,骆吉洲 计算机科学与工程系,8.1 Motivation of Tree Searching 8.2 Basic Tree Searching Strategies 8.3 Optimal Tree Searching Strategies 8.4 Personnel Assignment Problem 8.5 Traveling Salesperson Optimization Problem 8.6 0-1 backpacking problem 8.7 The A* Algorithm,提要,参考资料,算法设计与分析 第8章 网站资料 第八章,8.1 Motivation of Tree Searching,很多问题可以表示成为树. 于是, 这些问题可以使用树 搜索算法来求解,问题的定义 输入: n个布尔变量x1, x2, ., xn 关于x1, x2, ., xn的k个析取布尔式 输出: 是否存在一个x1, x2, ., xn的一种赋值 使得所有k个布尔析取式皆为真,布尔表达式可满足性问题,把问题表示为树 通过不断地为赋值集合分类来建立树 (以三个变量(x1, x2, x3)为例),x1=T,x1=F,x2=T,x2=F,x2=T,x2=F,x3=T,x3=T,x3=T,x3=T,x3=F,x3=F,x3=F,x3=F,求解问题 设有布尔式: -x1, x1, x2 x5 , x3, -x2,x1=T,x1=F,问题的定义 输入: 具有8个编号小方块的魔方,8-Puzzle问题,输出: 移动系列, 经过这些移动, 魔方达如下状态,转换为树搜索问题,Hamiltonian环问题,问题定义 输入: 具有n个节点的连通图G=(V, E) 输出: G中是否具有Hamiltonian环,沿着G的n条边经过每个节点一次, 并回到起始节点的环称为G的一个 Hamiltonian环.,1,2,7,4,5,3,6,无Hamiltonian环图:,有Hamiltonian环图:,转换为树搜索问题,1,3,4,5,7,5,6,7,3,2,6,5,2,4,7,4,5,7,4,7,3,7,6,5,3,2,6,2,6,1,1,1,2,3,4,5,4,4,5,3,3,5,8.2 Basic Tree Searching Strategies,Breadth-First Search Depth-First Search,算法 1. 构造由根组成的队列Q； 2. If Q的第一个元素x是目标节点 Then 停止; 3. 从Q中删除x，把x的所有子节点加入Q的末尾; 4. If Q空 Then 失败 Else goto 2.,Breadth-First Search,例: 求解8-Puzzle问题,Depth-First Search,算法 1. 构造一个由根构成的单元素栈S; 2. If Top(S)是目标节点 Then 停止; 3. Pop(S), 把Top(S)的所有子节点压入栈顶; 4. If S空 Then 失败 Else goto 2.,例1. 求解子集合和问题 输入: S=7, 5, 1, 2, 10 输出: 是否存在SS, 使得Sum(S)=9,0,7,8,12,9,10,18,7,5,1,2,2,10,例2. 求解Hamiltonian环问题,1,4,5,2,2,3,5,6,5,3,3,2,2,4,4,4,5,3,6,3,5,6,6,1,7.3 Optimal Tree Searching Strategies,Hill Climbing Best-First Search Strategy Branch-and-Bound Strategy,基本思想 在深度优先搜索过程中, 我们经常遇到多个节点可以扩展的情况, 首先扩展哪个? 爬山策略使用贪心方法确定搜索的方向, 是优化的深度优先搜索策略 爬山策略使用启发式测度来排序节点扩展的顺序,Hill Climbing,用8-Puzzle问题来说明爬山策略的思想 启发式测度函数: f(n)=W(n), W(n)是节点n中处于错误位置的方块数. 例如, 如果节点n如下, 则f(n)=3, 因为方块1、2、8处于错误位置.,3,3,4,4,2,4,1,0,2,f(n) 值,Hill Climbing算法 1. 构造由根组成的单元素栈S; 2. If Top(S)是目标节点 Then 停止; 3. Pop(S); 4. S的子节点按照其启发测度由大到 小的顺序压入S; 5. If S空 Then 失败 Else goto 2.,基本思想 结合深度优先和广度优先的优点 根据一个评价函数, 在目前产生的所有 节点中选择具有最小评价函数值的节 点进行扩展. 具有全局优化观念, 而爬山策略仅具有局部 优化观念.,Best-First Search Sttrategy,BesT-First Search算法 1. 使用评价函数构造一个堆H, 首先构造由根 组成的单元素堆; 2. If H的根r是目标节点 Then 停止; 3. 从H中删除r, 把r的子节点插入H; 4. If H空 Then 失败 Else goto 2. 8-Puzzle问题实例,3,4,4,3,2,4,1,0,2,3,4,基本思想 上述方法很难用于求解优化问题 分支界限策略可以有效地求解组合优化问题 发现优化解的一个界限 缩小解空间, 提高求解的效率 举例说明分支界限策略的原理,Branch-and-Bound Strategy,多阶段图搜索问题 输入: 多阶段图,输出: 从v0到v3的最短路径,1,3,2,5,3,4,3,2,7,4,4,1,1,1,1,v0,v12,v11,v13,v22,v21,v23,v21,v23,v22,v3,v3,v3,v3,v3,v3,问题的树表示,1,3,2,5,3,4,3,2,7,1,1,v0,v12,v11,v22,v21,v23,v21,v23,v22,v3,v3,可能解 上界=5,=65,=75,=65,=95,v13,解,使用爬山策略进行分支界限搜索,分支界限策略的原理 产生分支的机制(使用前面的任意一种策略) 产生一个界限(可以通过发现可能解) 进行分支界限搜索, 即剪除不可能产生优化解的分支.,8.4 Personnel Assignment Problem,问题的定义 转换为树搜索问题 求解问题的分支界限搜索算法,输入 人的集合P=P1, P2, , Pn, P1P2 Pn 工作的集合J=J1, J2, , Jn, J是偏序集合 矩阵Cij, Cij是工作Jj分配到Pi的代价 输出 矩阵Xij, Xij=1表示Pi被分配Jj , i,j CijXij最小 每个人被分配一种工作, 不同人分配不同工作 如果f(Pi)f(Pj), 则Pi Pj,问题的定义,例. 给定P=P1, P2, P3 , J=J1, J2, J3, J1J3, J2J3. P1J1、P2J2、P3J3 是可能的解. P1J1、P2J3、P3J2 不可能是解.,拓朴排序 输入: 偏序集合(S, ) 输出: S的拓朴序列是, 满足: 如果sisj, 则si排在sj的前面. 例,转换为树搜索问题,拓朴排序:,s1,s3,s7,s4,s9,s5,s2,s8,s6,问题的解空间 命题1. P1 Jk1、P2 Jk2、Pn Jkn是一个可能 解, 当且仅当Jk1、Jk2、Jkn必是一个拓朴 排序的序列. 例. P=P1, P2, P3, P4, J=J1, J2, J3, J4, J的偏序如下,则 (J1, J2, J3, J4)、(J1, J2, J4, J3 )、(J1, J3, J2, J4 )、 (J2, J1, J3, J4 )、(J2, J1, J4, J3 )是拓朴排序序列 (J1, J2, J4, J3)对应于P1J1、P2J2、P3 J4、P4 J3,问题的解空间是所有拓朴排序的序列集合， 每个序列对于一个可能的解,问题的树表示(即用树表示所有拓朴排序序列),拓朴序列树的生成算法 输入: 偏序集合S, 树根root. 输出: 由S的所有拓朴排序序列构成的树. 1. 生成树根root; 2. 选择偏序集中没有前序元素的所有元素, 作为 root的子节点; 3. For root的每个字节点v Do 4. S=S-v; 5. 把v作为根, 递归地处理S.,例,0,1,2,2,3,1,3,4,2,3,4,3,4,4,3,4,计算解的代价的下界 命题2. 把代价矩阵某行(列)的各元素减去同一个 数, 不影响优化解的求解. 代价矩阵的每行(列)减去同一个数(该行或列的最小数), 使得每行和每列至少有一个零, 其余各元素非负. 每行(列)减去的数的和即为解的下界.,求解问题的分支界限搜索算法,-12,-26,-3,-10,-3,解代价下界=12+26+3+10+3=54,例.,解空间的加权树表示,分支界限搜索(使用爬山法)算法 1. 建立根节点, 其权值为解代价下界; 2. 使用爬山法, 类似于拓朴排序序列树生成算法 求解问题, 每产生一个节点, 其权值为加工后的 代价矩阵对应元素加其父节点权值; 3. 一旦发现一个可能解, 将其代价作为界限, 循环 地进行分支界限搜索: 剪掉不能导致优化解的 子解, 使用爬山法继续扩展新增节点, 直至发现 优化解.,例,0,1,2,1,3,4,3,4,54,71,58,64,68,70,70,73,分支被 剪掉,P1, P2, P3, P4,8.5 Traveling Salesperson Optimization Problem,问题的定义 转换为树搜索问题 分支界限搜索算法,问题的定义,输入: 无向连通图G=(V, E), 每个节点都没有到自身的边, 每对节点之间都有一条非负加权边. 输出: 一条由任意一个节点开始 经过每个节点一次 最后返回开始节点的路径, 该路径的代价(即权值只和)最小.,所有解集合作为树根, 其权值由代价矩阵 使用上节方法计算; 用爬山法递归地划分解空间, 得到二叉树 划分过程: 如下选择图上满足下列条件的边(i, j) Cost(i, j)=0 (左子树代价增长为0) f(i,j)=min kjCost(i, k)+min kiCost(k, j) (i,j) cost(i,j)=0且f(i,j)达到最大值 使右子树代价下界增加最大 所有包含(i, j)的解集合作为左子树 所有不包含(i, j)的解集合作为右子树 计算出左右子树的代价下界,转换为树搜索问题,分支界限搜索算法,在上述二叉树建立算法中增加如下策略: 发现优化解的上界; 如果一个子节点的代价下界超过, 则终止该 节点的扩展. 下边我们用一个例子来说明算法,构造根节点, 设代价矩阵如下,根节点为所有解的集合 计算根节点的代价下界,- 3 - 4 16 7 25 3 26,-7,-1,-4,变换后的代价矩阵为,得到如下根节点及其代价下界,f(1,2)=6+1=7 f(2,1)=12+0=12 f(3,5)=1+17=18 f(4,6)=32+0=32 f(5,6)=3+0=3 f(6,1)=0+