第2章问题求解1用

書式設定, 書式設定,第,2,第,3,第,4,第,5,：,*,1,2.2,信息搜索方法,上一,节,介绍了对目前状态到目标状态的步数或者路径代价一无所知的情况下的,几,种搜索策略。如果我们对状态空间有一些了解，那么可以利用这些知识来帮助确定先扩展哪一个节点。,启发性信息的概念,启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。,概念：启发性信息,按用途可分为3种。,（1）用于决定要扩展的下一个节点，以避免像在宽度优先或深度优先搜索中那样盲目地扩展。,（2）在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。,（3）用于决定某些应该从搜索树中抛弃或修剪的节点。,启发性信息的作用,启发信息的启发能力越强，扩展的无用结点越少。,概念：估价函数,一个节点的“希望”有几种不同的定义方法。在状态空间问题中，一种定义是估算,目标节点,到,此节点的距离,；另一种定义是,整条路径（包括被估价过的节点）的长度或难度,。,用符号,f,来标记估价函数，用,f(n),表示节点,n,的估价函数值。,用于评估节点重要性的函数，叫做估价函数,4,有一点很重要，我们所选择的最优节点是相对于估价函数而言的最优。如果估价函数是无所不知的，那么最优节点确实是最优的。但实际上估价函数并不是万能的，因此还是会导致搜索进入错误的方向。,下面我们来看两种最好优先搜索方法，第一种方法试图扩展最接近目标的节点，第二种方法试图扩展路径损耗代价最小的节点。,5,2.2,信息搜索方法,2.2.1,最好优先搜索,通常，我们是通过一个,估价函数（,evaluation function,）,提供的知识来帮助做决定的，这个函数返回一个节点的扩展期望。如果按照具有最优评估结果的节点最先扩展的方式进行排列，我们称这种策略为最好优先搜索。我们可以把它直接应用到路径搜索中去。,6,2.2.1,最好优先搜索,1.,最小化实现一个目标的估计代价：贪婪搜索,一种最简单的最好优先搜索策略就是最小化到达目标的估计代价。也就是说被认为是最接近目标状态的节点总是最先扩展。对于大多数问题来说，从某个状态到目标的代价是可以估计的，但不能精确确定。这种用来计算估计代价的函数称为,启发式函数（,heuristic function,）,，通常用字母,h,表示：,h(n)=,从节点,n,到目标状态的最短路径的代价估计,这种用,h,来选择下一个被扩展节点的最好优先搜索方法称为,贪婪搜索（,greedy search,）,。从形式上说，,h,可以是任何函数，只要满足,n,为目标节点时,h(n)=0,即可。但针对具体问题启发式函数各不相同。我们仍然以从,A,到,B,的路径搜索问题为例，如下图所示,7,2.2.1,最好优先搜索,8,2.2.1,最好优先搜索,9,2.2.1,最好优先搜索,上图所示为用贪婪搜索寻找从,A,到,B,的路径的搜索过程。根据启发式函数，即直线距离，从,A,扩展的第一个节点将是,S,，因为,S,离,B,最近，比,Z,和,T,离,B,都近。接下来扩展的节点是,F,，因为它最近,B,。接着,F,生成,B,，即目标节点。在这个特殊问题中，启发式函数花费了最小的搜索代价：它没有扩展一个不在解路径上的节点。,10,2.2.1,最好优先搜索,ASFB: 140+99+211=450,ASRPB: 140+80+97+101=418,11,2.2.1,最好优先搜索,但它不是最优的，这条路比经过,R,和,P,的路要长,32,公里。这条路之所以没有发现是因为,F,到,B,的直线距离比,R,的要近，因此,F,先被扩展了。这种策略优先从现有的代价中选出具有最大可能到达目标的一个，而不从长期角度来考虑这是否是最好的，因此称为贪婪搜索。贪婪搜索希望快速找到解，但它不一定能找到最优解。,12,2.2.1,最好优先搜索,贪婪搜索对于错误的开端很敏感。假设问题是从,I,到,F,。启发式函数建议先扩展,N,，但这是一个死角。解路径应该是先到,V,从启发函数的角度讲它离目标确实比,I,远,然后到,U,，,B,，,F,。因此这次启发函数造成了不必要的节点被扩展。进而如果不仔细检测状态的循环，将会永远找不到解,搜索永远在,N,和,I,之间反复。,13,2.2.1,最好优先搜索,贪婪搜索和深度优先搜索一样沿着一条通往目标的路一直走下去，如果遇到死角就会返回。因此它也有和深度优先一样的问题,它不是最优的，而且它也不是完备的因为它有可能沿着一条无限的路走下去而永不回头来寻找其它可能性。在贪婪搜索中一个好的启发式函数可以极大地降低时间和空间复杂度，具体降低的量根据问题的不同和所采用的启发式函数,h,的好坏而不同。,14,2.2.1,最好优先搜索,2.,最小化路径总代价：,A,*,算法,贪婪搜索最小化到目标的估计代价,h(x),，从而大大降低了搜索代价。但是它既不是最优的也不是完备的。另一方面，相同代价搜索最小化路径代价，,g(x),。它是最优的同时也是完备的，却非常没有效率。如果能将两者合并起来，就可以同时拥有两者的优点。,g(x),表示从初始节点到节点,x,的路径代价，,h(x),表示从节点,n,到目标节点的最小路径估计代价，则有：,f(x)=,从初始节点经过节点,x,到达目标节点的最小路径估计代价。,16,2.2.1,最好优先搜索,2.,最小化路径总代价：,A,*,算法,因此如果我们希望找到具有最小路径代价的解，首先要找到具有最小的,f,的节点。值得高兴的是只要对,h,函数稍做限制，我们就能证明这种搜索策略是完备的和最优的。,这个限制就是必须选择一个,h,函数，它对到目标节点的估计代价不会超过实际的代价。我们称这种,h,函数为,容许启发式函数（,admissible heuristic,）,，采用,f,作为估价函数且,h,函数是容许启发式函数的最好优先搜索为,A,*,搜索。,17,2.2.1,最好优先搜索,我们仍然以从,A,到,B,的路径搜索为例，取直线距离为启发式函数。因为任意两点间直线距离最短，所以该启发式函数为容许启发式函数。,18,2.2.1,最好优先搜索,19,2.2.1,最好优先搜索,20,2.2.1,最好优先搜索,21,2.,机器感知,3.,A,*,的性能,1),单调性,从刚才的例子中我们发现一个有趣的现象：从根节点出发沿着路径的,f,代价是不减的。这不是偶然的，几乎所有的容许启发函数都是这样的，我们称之为,单调性,(monotonicity),。只要,h,是容许的，,f,从根节点出发沿着任何路径都是非减的。,2.2.1,最好优先搜索,22,2.,机器感知,2.2.1,最好优先搜索,23,2.,机器感知,如果,f,沿着从根节点出发的任何路径都是非减的，我们可以在状态空间概念性地画出等高线。在等高线,400,以内，所有节点的,f,值都小于或等于,400,，以此类推。因为,A,*,算法扩展,f,值最小的叶节点，我们看到,A,*,搜索从起始节点开始，加入随着,f,代价增加而进入等高线中的节点。,2.2.1,最好优先搜索,24,2.,机器感知,启发函数越精确，这些等高线越向目标状态伸展，而且围绕着最优路径越狭窄。如果我们定义,f,*,为最优解路径的代价，则我们说：,A,*,扩展所有,f *f(n),的节点,A,*,有可能扩展一些处在目标等高线上的节点，对于这种情况，在选择目标节点之前，有,f(n)=f,*,2.2.1,最好优先搜索,直觉上我们感到找到的第一个解是最优的，因为所有后继等高线上的点都有更大的,f,代价。同时,A*,也是完备的。随着,f,的增大等高线越多，最终会达到一个等高线，其上的,f,路径代价与目标节点的相同。,25,2.,机器感知,2).,A,*,是最优的,设,G,为一个最优目标状态，路径代价为,f,*,。令,G,2,为一个次优目标状态，即它的路径代价,g(G,2,) ,f,*,。假设,A,*,从序列中选择了,G,2,，因为,G,2,是一个目标状态，搜索将以一个次优解的结果而结束。我们将证明这是不可能的。,2.2.1,最好优先搜索,26,2.,机器感知,考虑节点,n,是到,G,的最优路径上的一个节点，现在,n,是叶节点。因为,h,是容许的，必有：,f *f(n),。进一步，如果在扩展,G,2,之前,n,没有被选择，必有：,f(n) f(G,2,),。两者合并有：,f *,f(G,2,),。但是因为,G,2,是一个目标状态，我们有,h(G,2,),=0,，因此,f(G,2,),=,g(G,2,),。则从假设我们可以证明,f * g(G,2,),，与,G,2,是次优解矛盾。因此,A,*,是最优算法。,2.2.1,最好优先搜索,27,2.,机器感知,3. A,*,是完备的,我们在前面提到过因为,A,*,按照,f,增加的顺序扩展节点，除非存在无限多个,的节点，否则它最终必然会到达一个目标节点。出现无限个节点只能有以下两种情况：要么有一个节点具有无限分支因子，要么存在一条路径，它的路径代价是有限的但包括了无限个节点。,因此正确的说法是只要存在一些正的常数,满足每个操作符的代价最小为,时,A,*,在局部有限图上是完备的。,2.2.1,最好优先搜索,28,2.,机器感知,4.,A,*,复杂度,虽然,A,*,是最优的和完备的，但对于大多数问题来说，位于目标节点等高线内节点的数目仍然与解的长度呈指数关系。计算时间不是,A,*,的主要缺陷，通常,A,*,算法的主要问题是内存耗尽而不是计算时间太久。,2.2.1,最好优先搜索,29,2.,机器感知,8,数码问题是最早采用启发式搜索的问题之一，其典型的解大约为,20,步，这当然要根据初始状态的不同而有所不同。分支因子大约为,3,（当空格单元在中间时分支因子为,4,，在四个角落时为,2,），这意味着一个深度为,20,的完全搜索将有大约,个状态。当然这里面会有大量重复的状态。除去重复状态仍然会有很多状态，因此下一步就是寻找一个好的启发式函数。如果我们希望找到路径最短的解，我们需要一个估计值不会超过到目标的真实步数的启发式函数。这里有两个候选函数：,2.2.2,启发式函数,30,2.,机器感知,2.2.2,启发式函数,h,1,处在错误位置上的单元数。,h,1,是容许启发函数，因为显然不在正确位置上的单元至少要移动一次。,h,2,所有单元离它的目标位置的距离和。由于单元不能沿着对角线移动，因此我们所指的距离是横向距离与纵向距离之和。,h,2,也是容许的，因为单元的每次移动最多只能向目标靠近一步。,2.2.2,启发式函数,31,2.,机器感知,2.2.2,启发式函数,1.,启发式函数的选择,从两者的定义我们可以看出对于任何节点,n,都有,，我们说,h,2,优于,h,1,。这直接影响到效率：平均来看采用,h,2,的,A,*,算法比采用,h,1,的,A,*,算法扩展的节点少。回忆一下我们以前曾经提到过的，所有满足,f(n)f *,的节点都要被扩展。这相当于是说所有满足,h(n),f *-g(n),的节点都将被扩展。因此凡是被采用,h,2,的,A,*,算法扩展的节点都将被采用,h,1,的,A,*,算法扩展，反之则不然。所以说,在启发式函数的估计值不超过真实值的情况下应该尽可能采用估计值高的启发式函数,。,2.2.2,启发式函数,32,2.,机器感知,2.2.2,启发式函数,2.,生成启发式函数,到目前为止我们还不知道怎样来生成一个启发式函数。我们怎样能想到采用,h,2,的呢？对一个问题，当对其操作符限制较少时我们称之为,松弛问题（,relaxed problem,）,。,通常一个松弛问题的确切解的代价是原始问题的一个好的启发式函数。,近年来有一个叫做,ABSOLVER,的软件就是采用“松弛问题”方法以及其它一些技术，可以根据问题的定义自动生成启发式函数。,2.2.2,启发式函数,33,2.,机器感知,2.2.2,启发式函数,2.,生成启发式函数,生成了新的启发式函数往往还带来一个问题：人们很难判断到底哪一个是最好的？例如有一系列启发式函数,，它们中没有一个能优于另一个。有一个简单的方法就是生成一个新的启发式函数,h(n)=max(h,1,(n),h,2,(2).h,m,(n),由于所有启发函数都是容许的，所以,h(n),也是容许的。,2.2.2,启发式函数,34,2.,机器感知,修道士和野人问题。,问题描述,设有三个传教士和三个野人来到河边，打算乘一只船从左度到右岸。该船的负载能力为两人，在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们这样才能用这条船安全地把所有人都渡河过去？,状态图搜索问题求解,35,2.,机器感知,修道士和野人问题。,问题表示：需要考虑两岸的传教士人数和野人人数，船的位置。用三元组,(m, c, b),表示问题的状态。其中,m,表示左岸的修道士人数，,c,表示左岸的野人数，,b,表示左岸的船数，,右岸的状态可由下式确定：,右岸修道士数,m=3-m,右岸野人数,c=3-c,右岸船数,b=1-b,在这种表示方式下，,m,和,c,都可取,0,、,1,、,2,、,3,中之一，,b,可取,0,和,1,中之一。因此，共有,442=32,种状态。,状态图搜索问题求解,状态,m,c,b,状态,m,c,b,状态,m,c,b,状态,m,c,b,S0,3,3,1,S8,1,3,1,S16,3,3,0,S24,1,3,0,S1,3,2,1,S9,1,2,1,S17,3,2,0,S25,1,2,0,S2,3,1,1,S10,1,1,1,S18,3,1,0,S26,1,1,0,S3,3,0,1,S11,1,0,1,S19,3,0,0,S27,1,0,0,S4,2,3,1,S12,0,3,1,S20,2,3,0,S28,0,3,0,S5,2,2,1,S13,0,2,1,S21,2,2,0,S29,0,2,0,S6,2,1,1,S14,0,1,1,S22,2,1,0,S30,0,1,0,S7,2,0,1,S15,0,0,1,S23,2,0,0,S31,0,0,0,值得注意的是按照题目规定的条件，我们应该,划去不合法的状态,，这样可以加快搜索求解的效率。,1,、首先可以划去岸边野人数目超过传教士的情况，即,4,、,S8,、,S9,、,S20,、,S24,、,S25,等,6,种状态是不合法的；,状态,m,c,b,状态,m,c,b,状态,m,c,b,状态,m,c,b,S0,3,3,1,S8,1,3,1,S16,3,3,0,S24,1,3,0,S1,3,2,1,S9,1,2,1,S17,3,2,0,S25,1,2,0,S2,3,1,1,S10,1,1,1,S18,3,1,0,S26,1,1,0,S3,3,0,1,S11,1,0,1,S19,3,0,0,S27,1,0,0,S4,2,3,1,S12,0,3,1,S20,2,3,0,S28,0,3,0,S5,2,2,1,S13,0,2,1,S21,2,2,0,S29,0,2,0,S6,2,1,1,S14,0,1,1,S22,2,1,0,S30,0,1,0,S7,2,0,1,S15,0,0,1,S23,2,0,0,S31,0,0,0,2,、应该划去右岸边野人数目超过修道士的情况，即,S6,、,S7,、,S11,、,S22,、,S23,、,S27,等情况；,状态,m,c,b,状态,m,c,b,状态,m,c,b,状态,m,c,b,S0,3,3,1,S8,1,3,1,S16,3,3,0,S24,1,3,0,S1,3,2,1,S9,1,2,1,S17,3,2,0,S25,1,2,0,S2,3,1,1,S10,1,1,1,S18,3,1,0,S26,1,1,0,S3,3,0,1,S11,1,0,1,S19,3,0,0,S27,1,0,0,S4,2,3,1,S12,0,3,1,S20,2,3,0,S28,0,3,0,S5,2,2,1,S13,0,2,1,S21,2,2,0,S29,0,2,0,S6,2,1,1,S14,0,1,1,S22,2,1,0,S30,0,1,0,S7,2,0,1,S15,0,0,1,S23,2,0,0,S31,0,0,0,状态,m,c,b,状态,m,c,b,状态,m,c,b,状态,m,c,b,S0,3,3,1,S8,1,3,1,S16,3,3,0,S24,1,3,0,S1,3,2,1,S9,1,2,1,S17,3,2,0,S25,1,2,0,S2,3,1,1,S10,1,1,1,S18,3,1,0,S26,1,1,0,S3,3,0,1,S11,1,0,1,S19,3,0,0,S27,1,0,0,S4,2,3,1,S12,0,3,1,S20,2,3,0,S28,0,3,0,S5,2,2,1,S13,0,2,1,S21,2,2,0,S29,0,2,0,S6,2,1,1,S14,0,1,1,S22,2,1,0,S30,0,1,0,S7,2,0,1,S15,0,0,1,S23,2,0,0,S31,0,0,0,40,2.,机器感知,修道士和野人问题。,这,32,种状态并非全有意义，除去不合法状态和修道士被野人吃掉的状态，,有意义的状态只有,16,种：,S,0,=(3, 3, 1) S,1,=(3, 2, 1) S,2,=(3, 1, 1) S,5,=(2, 2, 1),S,10,=(1, 1, 1) S,12,=(0, 3, 1) S,13,=(0, 2, 1) S,14,=(0, 1, 1),S,17,=(3, 2, 0) S,18,=(3, 1, 0) S,19,=(3, 0, 0) S,21,=(2, 2, 0),S,24,=(1, 1,0) S,29,=(0, 2, 0) S,30,=(0, 1, 0) S,31,=(0, 0, 0),状态图搜索问题求解,41,S,31,42,2.,机器感知,修道士和野人问题。,对,A*,算法，首先需要确定估价函数。设,g(n)=d(n),，,h(n)=m+c-2b,，则有,f(n)=g(n)+h(n)=d(n)+m+c-2b,其中，,d(n),为节点的深度。下面我们来证明,h(n),h*(n),，满足,A*,算法的限制条件。,状态图搜索问题求解,43,2.,机器感知,我们分两种情况考虑：,首先考虑船在左岸的情况。如果不考虑限制条件，也就是说，船一次可以将三人从左岸运到右岸，然后再由一个人将船送回来。这样，船一个来回可以运过河,2,人，而船仍然在左岸。而最后剩下的三个人，则可以一次将它们全部从作左岸到右岸。所以，在不考虑限制条件的情况下，也至少需要摆渡,【,（,M+N-3,）,/2】,*,2+1,次。其中分子上的“,-3,”表示剩下三个留待最后一次运过去。除以“,2,”是因为一个来回可以运过去,2,人，需要（,M+N-3,）,/2,来回，而来回数不能是小数，需要向上取整，这个用符号,【】,表示。乘以,2,是应为一个来回相当于两次摆渡。最后的“,+1,”表示将剩下的三个运过去需要一次摆渡。化简有,M+N-2,。,状态图搜索问题求解,44,2.,机器感知,再考虑船在右岸的情况。同样不考虑限制条件。船在右岸，需要一个人将船运到左岸。因此对于状态（,M,N,0,）来说，其所需要的最少摆渡数相当于船在左岸是状态（,M+1,N,1,）或（,M,N+1,1,）所需要的最少摆渡数，再加上第一次将船从右岸送到左岸的一次摆渡数。因此所需要的最少摆渡数为,M+N.,综合船在左岸和右岸两种情况，所需要的最少摆渡次数为,m+c-2b,，,状态图搜索问题求解,45,(3,3,1),h=4 f=4,(3,2,0) (3,1,0) (2,2,0),(3,2,1),(2,1,0) (3,0,0),(2,2,1) (3,1,1),(0,2,0) (1,1,0),(0,3,1),(0,1,0),(0,2,1),（,1,1,1,）,(0,0,0),h=5 f=6,h=3 f=5,h=3 f=6 h=3 f=6,h=2 f=6,h=2 f=7,h=1 f=7,h=1 f=8,h=0 f=8,传教士和野人问题的搜索图,问题状态：,(m,c,b),估价函数：,h(n)=m+c-2b,h=4 f=5,h=4 f=5,h=2 f=6,h=2 f=7,二阶梵塔问题,设有三根宝石杆,在,1,号杆上穿有,A,、,B,两个金盘,A,小于,B, A,位于,B,的上面。用二元组,(,S,A,S,B,),表示问题的状态,S,A,表示金盘,A,所在的杆号,S,B,表示金盘,B,所在的杆号,这样,全部可能的状态有,9,种,可表示如下：,(1, 1), (1, 2), (1, 3),(2, 1), (2, 2), (2, 3),(3, 1), (3, 2), (3, 3),如图,3-10,所示。,状态图搜索问题求解,图,3-10,二阶梵塔的全部状态,状态图搜索问题求解,这里的状态转换规则就是金盘的搬动规则，分别用,A,(,i,j,),及,B,(,i,j,),表示：,A,(,i,j,),表示把,A,盘从第,i,号杆移到第,j,号杆上,;,B,(,i,j,),表示把,B,盘从第,i,号杆移到第,j,号杆上。经分析，共有,12,个操作，它们分别是：,A,(1,2),A,(1,3),A,(2,1),A,(2,3),A,(3,1),A,(3,2),B,(1,2),B,(1,3),B,(2,1),B,(2,3),B,(3,1),B,(3,2),规则的具体形式应是： ,IF,条件,THEN,A,(,i,j,), IF,条件,THEN,B,(,i,j,),状态图搜索问题求解,这样由题意,问题的初始状态为,(1, 1),目标状态为,(3, 3),则二阶梵塔问题可用状态图表示为,(1, 1), ,A,(1, 2),B,(3, 2), (3, 3),由这,9,种可能的状态和,12,种操作,二阶梵塔问题的状态空间图如图,3-11,所示,。,状态图搜索问题求解,图,3-11,二阶梵塔状态空间图,状态图搜索问题求解,