学习]算法设计与分析ch7Treesearchingstrateg.ppt

第七章,Tree Searching Strategies,问题的定义,输入,:,n,个布尔变量,x,1,x,2,.,x,n,关于,x,1,x,2,.,x,n,的,k,个析取布尔式,输出,:,是否存在一个,x,1,x,2,.,x,n,的一种赋值,使得所有,k,个布尔析取式皆为真,布尔表达式可满足性问题,把问题表示为树,通过不断地为赋值集合分类来建立树,(,以三个变量,(,x,1,x,2,x,3,),为例,),x,1,=T,x,1,=F,x,2,=T,x,2,=F,x,2,=T,x,2,=F,x,3,=T,x,3,=T,x,3,=T,x,3,=T,x,3,=F,x,3,=F,x,3,=F,x,3,=F,求解问题,设有布尔式,:,-x,1,x,1,x,2,x,5,x,3,-x,2,x,1,=T,x,1,=F,问题的定义,输入,:,具有,8,个编号小方块的魔方,8-Puzzle,问题,2,3,5,1,4,7,8,6,输出,:,移动系列,经过这些移动,魔方达如下状态,1,2,8,4,5,6,7,3,转换为树搜索问题,2,3,5,1,4,7,8,6,2,5,1,4,7,8,6,3,2,3,5,1,7,8,6,4,Hamiltonian,环问题,问题定义,输入,:,具有,n,个节点的连通图,G,=(,V,E,),输出,:G,中是否具有,Hamiltonian,环,沿着,G,的,n,条边经过每个节点一次,并回到起始节点的环称为,G,的一个,Hamiltonian,环,.,1,2,7,4,5,3,6,1,2,4,3,5,无,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,7,4,5,3,6,1,2,3,4,5,4,4,5,3,3,5,1,2,4,3,5,7.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,问题,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,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,输出,:,是否存在,S,S,使得,Sum,(,S,)=9,0,7,8,12,9,10,18,7,5,1,2,2,10,例,2.,求解,Hamiltonian,环问题,1,2,5,4,3,6,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,处于错误位置,.,8,2,1,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,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,问题实例,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,3,4,4,2,1,8,4,5,6,7,3,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,1,8,4,5,6,7,3,2,4,1,0,2,2,1,8,4,5,6,7,3,3,2,1,8,4,5,6,7,3,4,基本思想,上述方法很难用于求解优化问题,分支界限策略可以有效地求解组合优化问题,发现优化解的一个界限,缩小解空间,提,高求解的效率,举例说明分支界限策略的原理,Branch-and-Bound Strategy,多阶段图搜索问题,输入,:,多阶段图,输出,:,从,v,0,到,v,3,的最短路径,v,0,v,11,v,12,v,13,v,21,v,22,v,23,v,3,1,3,2,2,3,5,3,4,7,4,1,1,v,0,v,11,v,12,v,13,v,21,v,22,v,23,v,3,1,3,2,2,3,5,3,4,7,4,1,1,1,3,2,5,3,4,3,2,7,4,4,1,1,1,1,v,0,v,12,v,11,v,13,v,22,v,21,v,23,v,21,v,23,v,22,v,3,v,3,v,3,v,3,v,3,v,3,问题的树表示,v,0,v,11,v,12,v,13,v,21,v,22,v,23,v,3,1,3,2,2,3,5,3,4,7,4,1,1,1,3,2,5,3,4,3,2,7,1,1,v,0,v,12,v,11,v,22,v,21,v,23,v,21,v,23,v,22,v,3,v,3,可能解,上界,=5,=65,=75,=65,=95,v,13,解,使用爬山策略进行分支界限搜索,分支界限策略的原理,产生分支的机制,(,使用前面的任意一种策略,),产生一个界限,(,可以通过发现可能解,),进行分支界限搜索,即剪除不可能产生优化解的分支,.,7.4,Personnel Assignment Problem,问题的定义,转换为树搜索问题,求解问题的分支界限搜索算法,输入,人的集合,P=,P,1,P,2,P,n,P,1,P,2,P,n,工作的集合,J=,J,1,J,2,J,n,J,是偏序集合,矩阵,C,ij,C,ij,是工作,J,j,分配到,P,i,的代价,输出,矩阵,X,ij,X,ij,=,1,表示,P,i,被分配,J,j,i,j,C,ij,X,ij,最小,每个人被分配一种工作,不同人分配不同工作,如果,f(P,i,),f(P,j,),则,P,i,P,j,问题的定义,例,.,给定,P=,P,1,P,2,P,3,J,=,J,1,J,2,J,3,J,1,J,3,J,2,J,3,.,P,1,J,1,、,P,2,J,2,、,P,3,J,3,是可能的解,.,P,1,J,1,、,P,2,J,3,、,P,3,J,2,不可能是解,.,拓朴排序,输入,:,偏序集合,(,S,),输出,:,S,的拓朴序列是,满足,:,如果,s,i,s,j,则,s,i,排,在,s,j,的前面,.,例,转换为树搜索问题,s,6,s,5,s,4,s,3,s,2,s,1,s,9,s,8,s,7,拓朴排序,:,s,1,s,3,s,7,s,4,s,9,s,5,s,2,s,8,s,6,问题的解空间,命题,1.,P,1,J,k1,、,P,2,J,k2,、,、,P,n,J,kn,是一个可能,解,当且仅当,J,k1,、,J,k2,、,、,J,kn,必是一个拓朴,排序的序列,.,例,.,P,=,P,1,P,2,P,3,P,4,J,=,J,1,J,2,J,3,J,4,J,的偏序如下,J,1,J,2,J,3,J,4,则,(,J,1,J,2,J,3,J,4,),、,(J,1,J,2,J,4,J,3,),、,(,J,1,J,3,J,2,J,4,),、,(J,2,J,1,J,3,J,4,),、,(J,2,J,1,J,4,J,3,),是拓朴排序序列,(,J,1,J,2,J,4,J,3,),对应于,P,1,J,1,、,P,2,J,2,、,P,3,J,4,、,P,4,J,3,问题的解空间是所有拓朴排序的序列集合，,每个序列对于一个可能的解,问题的树表示,(,即用树表示所有拓朴排序序列,),0,1,2,2,3,1,3,4,2,4,3,3,4,4,4,3,拓朴序列树的生成算法,输入,:,偏序集合,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,J,1,J,2,J,3,J,4,J,2,J,3,J,4,J,1,J,3,J,4,J,3,J,4,J,2,J,4,J,3,J,4,J,4,J,3,J,4,J,3,J,4,计算解的代价的下界,命题,2.,把代价矩阵某行,(,列,),的各元素减去同一个,数,不影响优化解的求解,.,代价矩阵的每行,(,列,),减去同一个数,(,该行或列的最小数,),使得每行和每列至少有一个零,其余各元素非负,.,每行,(,列,),减去的数的和即为解的下界,.,求解问题的分支界限搜索算法,-12,-26,-3,-10,-3,解代价下界,=12+26+3+10+3=54,J,1,J,2,J,3,J,4,P,1,P,2,P,3,P,4,例,.,0,1,2,2,3,1,3,4,2,3,4,3,4,4,3,4,54,71,72,71,86,91,76,78,78,81,58,64,68,70,70,73,被分配到的人,1,2,3,4,解空间的加权树表示,分支界限搜索,(,使用爬山法,),算法,1.,建立根,节点,其权值为解代价下界,;,2.,使用爬山法,类似于拓朴排序序列树生成算法,求解问题,每产生一个节点,其权值为加工后的,代价矩阵对应元素加其父节点权值,;,3.,一旦发现一个可能解,将其代价作为界限,循环,地进行分支界限搜索,:,剪掉不能导致优化解的,子解,使用爬山法继续扩展新增节点,直至发现,优化解,.,例,0,1,2,1,3,4,3,4,54,71,58,64,68,70,70,73,被分配到的人,1,2,3,4,分支被,剪掉,J,1,J,2,J,3,J,4,P,1,P,2,P,3,P,4,7.5,Traveling Salesperson Optimization Problem,问题的定义,转换为树搜索问题,分支界限搜索算法,问题的定义,输入,:,无向连通图,G=(V,E),每个节点都没有到自身的边,每对节点之间都有一条非负加权边,.,输出,:,一条由任意一个节点开始,经过每个节点一次,最后返回开始节点的路径,该路径的代价,(,即权值只和,),最小,.,所有解集合作为树根,其权值由代价矩阵,使用上节方法计算,;,用爬山法,递归地,划分解空间,得到二叉树,划分过程,:,如下选择图上满足下列条件的边,(,i,j,),Cost(,i,1,)=maxCost(,k,1,)|,kV,Cost(,i,j,)=0,使右子树代价下界增加最大,所有包含,(,i,j,),的解集合作为左子树,所有不包含,(,i,j,),的解集合作为右子树,计算出左右子树的代价下界,转换为树搜索问题,分支界限搜索算法,在上述二叉树建立算法中增加如下策略,:,发现优化解的上界,;,如果一个子节点的代价下界超过,则终止该,节点的扩展,.,下边我们用一个例子来说明算法,构造根节点,设代价矩阵如下,j=1 2 3 4 5,6 7,i=1,2,3,4,5,6,7,根节点为所有解的集合,计算根节点的代价下界,-3,-4,16,7,25,3,26,-7,-1,-4,所有解的集合,L.B=96,变换后的代价矩阵为,j=1 2 3 4 5,6 7,i=1,2,3,4,5,6,7,得到如下根节点及其代价下界,构造根节点的两个子节点,选择使子节点代价下界,增加最大的划分边,(4,6),建立根节点的子节点,:,左子节点为包括边,(4,6),的所有解集合,左子节点为不包括边,(4,6),的所有解集合,所有解的集合,L.B=96,包括边,(4,6),的,所有解集合,不包括边,(4,6),的所有解集合,计算左右子节点的代价下界,(4,6),的代价为,0,所以左节点代价下界仍为,96,.,我们来计算右节点的代价下界,:,如果一个解不包含,(4,6),它必包含一条从,4,出发,的边和 进入节点,6,的边,.,由变换后的代价矩阵可知,具有最小代价由,4,出发的边为,(4,1),代价为,32.,由变换后的代价矩阵可知,具有最小代价进入,6,的边为,(5,6),代价为,0,.,于是,右节点代价下界为,:,96+32+0=128,.,目前的树为,所有解的集合,L.B=96,包括边,(4,6),的,所有解集合,不包括边,(4,6),的所有解集合,L.B=96,L.B=128,左子树,右子树,递归地构造左右子树,构造左子树根对应的代价矩阵,左子节点为包括边,(4,6),的所有解集合,所以矩阵的第,4,行和第,6,列应该被删除,由于边,(4,6),被使用,边,(6,4),不能再使用,所以代价矩阵的元素,C,6,4,应该设置为,.,结果矩阵如下,j=1 2 3 4 5 6 7,i=1,2,3,4,5,6,7,计算左子树根的代价下界,矩阵的第,5,行不包含,0,第,5,行元素减,3,左子树根代价下界为,:,96+3=99,结果矩阵如下,j=1 2 3 4 5 6 7,i=1,2,3,4,5,6,7,构造右子树根对应的代价矩阵,右子节点为不包括边,(4,6),的所有解集合,只需要把,C,4,6,设置为,结果矩阵如下,j=1 2 3 4 5,6 7,i=1,2,3,4,5,6,7,计算右子树根的代价下界,矩阵的第,4,行不包含,0,第,4,行元素减,32,右子树根代价下界为,:,128+32=160,结果矩阵如下,j=1 2 3 4 5,6 7,i=1,2,3,4,5,6,7,目前的树为,所有解的集合,L.B=96,包括边,(4,6),的,所有解集合,不包括边,(4,6),的所有解集合,L.B=99,L.B=160,左子树,右子树,使用爬山策略扩展左子树根,选择边使子节点代价下界增加最大的,划分边,(3,5),左子节点为包括边,(3,5),的所有解集合,右子节点为不包括边,(3,5),的所有解集合,计算左、右子节点的代价下界,:99,和,117,目前树扩展为,:,L.B=96,所有解集合,包括边,(4,6),不包括边,(4,6),L.B=99,L.B=160,包括边,(3,5),不包括边,(3,5),L.B=99,L.B=117,包括边,(2,1),不包括边,(2,1),L.B=112,L.B=125,包括边,(1,4),不包括边,(1,4),L.B=126,L.B=153,包括边,(6,7),不包括边,(6,7),L.B=126,L.B=134,包括边,(5,2),不包括边,(5,2),L.B=126,空集合,包括边,(7,3),不包括边,(7,3),L.B=126,空集合,解,:,1-4-6-7-3-5-2-1,代价,:126,由于右子树代价,下界,=160126,停止扩展,优化解代价的上界,i,1,i,m,j,1,j,n,X,注 意,如果,i,1,-i,2,-i,m,和,j,1,-j,2,-j,m,已被包含在一个正在构造的路径中,(,i,m,j,1,),被加入,则必须避免,j,n,到,i,1,的路径被加入,.,否则出现环,.,7.6,The A*Algorithm,A*,算法的基本思想,A*,算法的规则,应用,A*,算法求解最短路径问题,A*,算法的基本思想,A*,算法与分支界限策略的比较,分支界限策略是为了剪掉不能达到优化解的分支,分支界限策略的关键是,“,界限,”,A*,算法的核心是告诉我们在某些情况下,我们得,到的解一定是优化解,于是算法可以停止,A*,算法试图尽早地发现优化解,A*,算法经常使用,Best-first,策略求解优化问题,A*,算法关键,代价函数,对于任意节点,n,g(n),从树根到,n,的代价,h*(n),从,n,到目标节点的优化路径的代价,f*(n),g(n)+h*(n),是节点,n,的代价,What is the value of,h*(n),?,不知道！,于是,f*(n),也不知道,估计,h*(n),使用任何方法去估计,h*(n),用,h(n),表示,h*(n),的估计,h(n),h*(n),总为真,f(n),=,g(n)+h(n),g(n)+h*(n),=,f*(n),定义为,n,的代价,输出,:,发现一个从,S,到,T,的最短路径,例,1.,最短路径问题,:,输入,:,S,V,3,V,2,V,1,V,4,V,5,T,2,3,4,3,2,2,2,2,3,5,1,V,3,V,2,V,1,2,3,4,S,g(V,1,)=2,g(V,2,)=3,g(V,3,)=4,h*(V,1,)=5,f*(V,1,)=g(V,1,)+h*(V,1,)=7,估计,h*(n),从,V,1,出发有两种可能,:,代价为,2,代价为,3,最小者为,2,h*(V,1,),2,选择,h(n),=2,为,h*(V,1,),的估计值,f(V,1,),=,g(v,1,),+,h(V,1,),=4,为,V,1,的代价,求解树的第一阶段,S,V,3,V,2,V,1,V,4,V,5,T,2,3,4,3,2,2,2,2,3,5,1,A*,算法本质,已经发现的解是优化解,定理,1,.,使用,Best-first,策略搜索树,如果,A*,选择的节点是,目标节点,则该节点表示的解是优化解,.,证明,.,令,n,是任意扩展到的节点,t,是选中目标节点,.,往证,f(t)=g(t),是优化解代价,.,(1).A*,算法使用,Best-first,策略,f(t),f(n),.,(2).,A*,算法使用,h(n),h*(n),估计规则,f(t),f(n),f*(n).,(3).,f*(n),中必有一个为优化解的代价,令其为,f*(s).,我们有,f(t),f*(s).,(4).,t,是目标节点,h(t)=0,所以,f(t)=g(t)+h(t)=g(t),f*(s).,(5).,f(t)=g(t),是一个可能解,g(t),f*(s),f(t)=g(t),=,f*(s).,A*,算法的规则,(1).,使用,Best-first,策略搜索树,;,(2).,节点,n,的代价函数为,f(n)=g(n)+h(n),g(n),是,从根到,n,的路径代价,h(n),是从,n,到某个目,标节点的优化路径代价,;,(3).,对于所有,n,h(n),h*(n),;,(4).,当选择到的节点是目标节点时,算法停止,返回一个优化解,.,应用,A*,算法求解最短路径问题,问题的输入,:,A*,算法的执行全过程,S,V,3,V,2,V,1,V,4,V,5,T,2,3,4,3,2,2,2,2,3,5,1,S,V,3,V,2,V,1,V,4,V,5,T,2,3,4,3,2,2,2,2,3,5,Step 1,S,V,1,V,3,V,2,2,4,3,g(V,1,)=,2,g(V,3,)=,4,g(V,2,)=,3,h(V,1,)=min,2,3,=,2,h(V,3,)=min,2,=,2,h(V,2,)=min,2,2,=,2,f(V,1,)=,2+2,=,4,f(V,3,)=,4+2,=,6,f(V,2,)=,2+2,=,5,4,6,5,1,S,V,3,V,2,V,1,V,4,V,5,T,2,3,4,3,2,2,2,2,3,5,Step 2.,扩展,V,1,g(V,4,)=,2+2=4,g(V,2,)=,2+3=5,h(V,4,)=min,3,1,=,1,h(V,2,)=min,2,2,=,2,f(V,4,)=,4+1,=,5,f(V,2,)=,5+2,=,7,S,V,3,V,2,2,4,3,4,6,5,V,4,V,2,V,1,2,3,1,5,7,S,V,3,V,2,V,1,V,4,V,5,T,2,3,4,3,2,2,2,2,3,5,Step 3.,扩展,V,2,g(V,4,)=,3+2=5,g(V,5,)=,3+2=5,h(V,4,)=min,3,1,=,1,h(V,5,)=min,5,=,5,f(V,4,)=,5+1,=,6,f(V,2,)=,5+5,=,10,S,V,3,2,4,3,4,6,5,V,4,V,2,V,1,2,3,1,5,7,V,4,V,5,2,2,V,2,6,10,S,V,3,V,2,V,1,V,4,V,5,T,2,3,4,3,2,2,2,2,3,5,Step 4.,扩展,V,4,g(V,5,)=,2+2+1=5,g(T)=,2+2+3=7,h(V,5,)=min,5,=,5,h(T)=0,f(V,5,)=,5+5,=,10,f(V,2,)=,7+0,=,7,S,V,3,2,4,3,4,6,5,V,2,V,1,2,3,1,5,7,V,4,V,5,2,2,V,2,6,10,V,5,T,1,3,V,4,7,10,S,V,3,V,2,V,1,V,4,V,5,T,2,3,4,3,2,2,2,2,3,5,Step 5.,扩展,V,3,g(V,5,)=,4+2=6,h(V,5,)=min,5,=,5,f(V,5,)=,6+5,=,11,S,V,3,2,4,3,6,5,1,V,4,V,5,2,2,V,2,6,10,4,V,2,V,1,2,3,5,7,V,5,T,1,3,V,4,7,10,V,5,2,11,S,V,3,V,2,V,1,V,4,V,5,T,2,3,4,3,2,2,2,2,3,5,Step 6.,扩展,V,4,g(V,5,)=,3+2+1=6,g(T)=,3+2+3=8,h(V,5,)=min,5,=,5,h(T)=0,f(V,5,)=,6+5,=,11,f(T)=,8+0,=,8,S,V,3,2,4,3,6,5,1,4,V,2,V,1,2,3,5,7,V,5,T,1,3,V,4,7,10,V,5,2,11,V,5,T,1,V,4,V,5,2,2,V,2,6,10,3,11,8,S,V,3,V,2,V,1,V,4,V,5,T,2,3,4,3,2,2,2,2,3,5,Step 7.,扩展,T,因为,T,是目标节点,所以我们得到解,:,S,V,1,V,4,T,S,V,3,2,4,3,6,5,1,4,V,2,V,1,2,3,5,7,V,5,T,1,3,V,4,7,10,V,5,2,11,V,5,T,1,V,4,V,5,2,2,V,2,6,10,3,11,8,