级人工智能原理

《级人工智能原理》由会员分享，可在线阅读，更多相关《级人工智能原理（54页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,*,*,前面讨论的各种搜索方法都没有用到问题本身的特性信息，只是按照事先设定的线路进行搜索，具有较大的盲目性。事实上，如果能够利用搜索过程所得到的问题自身的一些特性信息来指导搜索过程，则对搜索将是十分有益的。这种利用问题自身的特性信息来引导搜索过程的搜索方法称为,启发式搜索,。由于启发式搜索方法具有较强的针对性，因此，可以缩小搜索范围，提高搜索效率。,4.5 状态空间的启发式搜索,,,启发式搜索方法所依据的是问题自身的启发性信息，而启发性信息又是通过,估价函数,作用到搜索过程中的。,,1．启发性信息,一. 启

2、发性信息和估价函数,,启发性信息,是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。启发性信息一般有以下三种： ① 有效地帮助确定扩展节点的信息； ② 有效地帮助决定哪些后继节点应被生成； ③ 能决定在扩展一个节点时哪些节点应从搜索树上被删除。 一般来说，搜索过程所使用的启发性信息的启发能力越强，扩展的无用节点就越少。,,,,2．估价函数,用来估计节点重要性的函数称为,估价函数,。估价函数f（n）被定义为从初始节点,S0,出发，经过节点n到达目标节点,Sg,的所有路径中最小路径代价的估计值。它的一般形式为,f（n）=

3、g（n）＋h（n）,其中，g（n）是从初始节点S0到节点n的实际代价；h（n）是从节点n到目标节点S0的最优路径的估计代价。对g（n）的值，可以按指向父节点的指针，从节点n反向跟踪到初始节点S0,得到一条从初始节点S0到节点n的最小代价路径，然后把这条路径上所有有向边的代价相加，就得到g（n）的值。对h（n）的值，则需要根据问题自身的特性来确定，它体现的是问题自身的启发性信息，因此也称h（n）为,启发函数,。,n,,,g,(,n,),h,(,n,),,例,： 八数码难题。设问题的初始状态S0和目标状态 Sg 如前所述，且估价函数为: f（n）=d（n）＋W（n）其中，d（n）表

4、示节点 n在搜索树中的深度； w（n）表示节点 n中“不在位”的数码个数。请计算初始状态S0的估价函数值f（S0）。 解：在本例的估价函数中，取g（n）=d（n），h（n）=W（n）。它说明是用从S0到n的路径上的单位代价表示实际代价，用n中“,不在位,”的数码个数作为启发信息。一般来说，某节点中的“不在位”的数码个数越多，说明它离目标节点越远。 对初始节点 S0，由于 d（S0）= 0， W（S0）= 3，因此有 f（S0）=0＋3=3  这个例子仅是为了说明估价函数的含义及估价函数值的计算。在问题搜索过程中，除了需要计算初始节点的估价函数之外，更

5、多的是要计算新生成节点的估价函数值。,,2 8,3,1,4,7 6 5,,,二. A算法,,在图搜索算法中，如果能在搜索的每一步都利用,估价函数,f（n）=g（n）＋h（n）对Open表中的节点进行排序，则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息，因此，,A算法,也被称为,启发式搜索算法,。 对启发式搜索算法，又可根据搜索过程中选择扩展节点的范围，将其分为,全局择优搜索算法,和,局部择优搜索算法,。,,每当需要扩展节点时，总是从Open表的所有节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：,（1）,把S0放入Open表中，f(s0)=g（

6、So）＋h（So）；,（2）,如果Open表为空，则问题无解，失败退出；,（3）,把Open表的第一个节点取出放入Closed表，记该节点为n；,（4）,考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；,（5）,若节点n不可扩展，则转第（2）步；,（6）,扩展节点n，生成其子节点ni（i=1,2,……），计算每一个子节点的估价值f(ni) （i=1,2,……），并为每一个子节点设置指向父节点的指针，然后将这些子节点放入 Open表中；,（7）,根据各节点的估价函数值，对Open表中的,全部节点,按从小到大的顺序重新进行排序；,（8）,转第（2）步。,,1．全局择优搜索,,由于上述

7、算法的第（7）步要对Open表中的,全部节点,按其估价函数值从小到大重新进行排序，这样在算法第（3）步取出的节点就一定是Open表的所有节点中估价函数值最小的一个节点。因此，它是一种全局择优的搜索方式。 对上述算法进一步分析还可以发现：如果取估价函数f(n)=g（n），则它将退化为代价树的广度优先搜索；如果取估价函数f(n)=d（n），则它将退化为广度优先搜索。可见，广度优先搜索和代价树的广度优先搜索是全局择优搜索的两个特例。,,例：,八数码难题。,2 8 3,4,7 6 5,S0,2 8 3,1 4,7 6 5,2 3,8 4,7

8、 6 5,2 8 3,4,7 6 5,2 8 3,6 4,7 5,,8 3,2 1 4,7 6 5,2 8 3,7 1 4,6 5,,2 3,8 4,7 6 5,2 3,8 4,7 6 5,,S9,,4,1 2 3,8 4,7 6 5,1 2 3,8 4,7 6 5,1 2 3 7 8 4,6 5,S5,,5,S6,6,,S8,,6,,S7,,4,Sg,S10,,4,S11,,6,S1,,4,S2,,4,,S3,,5,S4,,5,,

9、在局部择优搜索中，每当需要扩展节点时，总是从,刚生成的子节点,中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：,（1）,把初始节点S0放入 Open表中，f(S0)=g(S0)+h(S0) ;,（2）,如果Open表为空，则问题无解，失败退出；,（3）,把Open表的第一个节点取出放入Closed表，并记该节点为n；,（4）,考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；,（5）,若节点n不可扩展，则转第（2）步；,（6）,扩展节点n，生成其子节点ni(i=1，2，…)，计算每一个子节点的估价值f（ni） （i=1，2，…），并按估价值从小到大的顺序依次放入Open

10、表的首部，并为每一个子节点设置指向父节点的指针，然后转第（2）步。,,2．局部择优搜索(瞎子爬山法),,,由于这一算法的第（6）步仅是把刚生成的子节点按其估价函数值从小到大放入 Open表的首都，这样在算法第（3）步取出的节点仅是刚生成的子节点中估价函数值最小的一个节点。因此，它是一种局部择优的搜索方式。,对这一算法进一步分析也可以发现：如果取估价函数f（ n）=g（n），则它将退化为代价树的深度优先搜索；如果取估价函数f（n）=d（n），则它将退化为深度优先搜索。可见，深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例。,,三.A,*,算法,前面讨,论,论的启,发,发式搜,索,索算

11、法,，,，都没,有,有对估,价,价函数f(n)作任,何,何限制,。,。实际,上,上，估,价,价函数,对,对搜索,过,过程是,十,十分重,要,要的，,如,如果选,择,择不当,，,，则有,可,可能找,不,不到问,题,题的解,，,，或者,找,找到的,不,不是问,题,题的最,优,优解。,为,为此，,需,需要对,估,估价函,数,数进行,某,某些限,制,制。A* 算,法,法就是对估价,函,函数加,上,上一些限制后得到,的,的一种,启,启发式,搜,搜索算,法,法。,,假设f*(n)为从,初,初始节,点,点S0,出,出发，,约,约束经,过,过节点n到达,目,目标节,点,点的最,小,小代价,值,值。估,价,价函

12、数f(n)是f*(n)的估,计,计值。,显,显然，f*（n）应,由,由以下,两,两部分,所,所组成,：,：一部,分,分是从,初,初始节,点,点到节,点,点n的最小代价，,记,记为g*（n,）,）；另,一,一部分,是,是从节,点,点n到,目,目标节,点,点的最小代价，,记,记为h*（n,）,），当,问,问题有,多,多个目,标,标节点,时,时，应,取,取其中,代,代价最,小,小的一,个,个。因,此,此有,f*（n）＝g*（n）＋h*（n）,把估价,函,函数f(n),与,与f*(n),相,相比，g（n,）,）是对g*（n）的,一,一个估,计,计，h,（,（n）,是,是对h*（n,）,）的一,个,个估

13、计,。,。在这,两,两个估,计,计中，,尽,尽管g,（,（n）,的,的值容,易,易计算,，,，但它,不,不一定,就,就是从,初,初始节,点,点S0,到,到节点n的真,正,正最小,代,代价，,很,很有可,能,能从初,始,始节点S0到,节,节点n,的,的真正,最,最小代,价,价还没,有,有找到,，,，故有g（n,）,）≥g*（n,）,）。,有,有了g*（n）和h*（n）的,定,定义，,如,如果对A算法,（,（全局,择,择优的,启,启发式,搜,搜索算,法,法）中,的,的g（n）和h（n,）,）分别,提,提出如,下,下限制,：,：,第,第一,，,，g（n）是,对,对g*,（,（n）,的,的估计,，,，

14、且g,（,（n）,＞,＞0；,第,第二，h（n,）,）是h*（n,）,）的下,界,界，即,对,对任意,节,节点n,均,均有,h（n,）,）≤h*（n,）,）。则,称,称得到,的,的算法,为,为A*,算,算法,。,。,,A*算,法,法的有,关,关特性,。,。,1．A*算法,的,的可纳,性,性一般来,说,说，对,任,任意一,个,个状态,空,空间图,，,，当从,初,初始节,点,点到目,标,标节点,有,有路径,存,存在时,，,，如果,搜,搜索算,法,法能在,有,有限步,内,内找到,一,一条从,初,初始节,点,点到目,标,标节点,的,的最佳,路,路径，,并,并在此,路,路径上,结,结束，,则,则称该,

15、搜,搜索算,法,法是可,采,采纳的,。,。A*,算,算法是,可,可采纳,的,的。(证明,略,略）。2.A*算法,的,的最优,性,性A*,算,算法的,搜,搜索效,率,率很大,程,程度上,取,取决于,估,估价函,数,数h（n）。,一,一般来,说,说，在,满,满足h,（,（n）,≤,≤h*,（,（n）,的,的前提,下,下，h,（,（n）,的,的值越,大,大越好,。,。h（n）的,值,值越大,，,，说明,它,它携带,的,的启发,性,性信息,越,越多，A*,算,算法搜,索,索时扩,展,展的节,点,点就越,少,少，搜,索,索效率,就,就越高,。,。A*,算,算法的,这,这一特,性,性也称,为,为信息,性,

16、性。(,证,证明略),,A,*,算法应,用,用举例,例,例：八数码,难,难题。,问,问题的,初,初始状,态,态和目,标,标状态,和,和前例,相,相同。,要,要求用A*,算,算法解,决,决该问,题,题。解：在上例,中,中，我,们,们取h,（,（n）=W（n）。,尽,尽管我,们,们对h*（n,）,）不能,确,确切知,道,道，但,当,当采用,单,单位代,价,价时，,通,通过对,“,“不在,位,位”数,码,码个数,的,的估计,，,，可以,得,得出至,少,少要移,动,动W（n）步,才,才能到,达,达目标,，,，显然,有,有W（n）≤h*（n）。,因,因此，,前,前例中,所,所定义,的,的h（n）满,足,

17、足A*,算,算法的,限,限制条,件,件。,这,这,里,里再取,另,另外一,种,种启发,函,函数h,（,（n）=P（n），P（n,）,）定义,为,为每一,个,个数码,与,与其目,标,标位置,之,之间距,离,离（不,考,考虑夹,在,在其间,的,的数码,）,）的总,和,和，同,样,样可以,断,断定至,少,少要移,动,动P（n）步,才,才能到,达,达目标,，,，因此,有,有P（n）≤h*（n），,即,即满足A*算,法,法的限,制,制条件,。,。,23,84,765,523,84,761,,2 8,3,1,4,7 6 5,h*=4, f=4,S0,2,3,1,,8,4,7 6 5,2 8,3,1 6,4

18、,7 5,2 8,3,,,1,4,7 6 5,2 8,3,1 4,7 6 5,g*=1,,2,3,1,8,4,7 6 5,2,3,1,8,4,7 6 5,g*=2,1,,2,3,8,4,7 6 5,1,,2,3,7,8,4,6 5,Sg,g*=4,h*=5, f=6,h*=5, f=6,h*=3, f=4,h*=5, f=6,h*=2, f=4,h*=4, f=6,1,,2,3,8,4,7 6 5,g*=3,h*=1, f=4,h*=0, f=4,h*=1, f=6,八数码难题h（n）=P（n）的搜索树,,例：设有,如,如下结,构,构的移,动,动将牌,游,游戏,,,B代表,黑,黑色牌,，

19、,，W代,表,表白色,牌,牌；E,代,代表该,位,位置为,空,空。玩,法,法：,当一个,牌,牌移入,相,相邻的,空,空位时,，,，费用,等,等于挑,过,过的牌,数,数加1,。,。,一个牌,至,至多可,跳,跳过两,个,个牌进,入,入空位,置,置，其,费,费用等,于,于跳过,的,的牌数,加,加1。,要求把,所,所有的B都移,到,到所有,的,的W的,右,右边，,设,设计h(x),。,。,解：,显然W,左,左边的B越少,越,越接近,目,目标，,因,因此可,用,用W左,边,边B的,个,个数作,为,为h(x),h(x)=3*(每,个,个W左,边,边B个,数,数的总,和,和）,,,h(x)=3*(2+2+3

20、)=21,B,B,B,W,W,W,E,B,B,B,W,W,W,E,,例：传教士,和,和野人,问,问题。,请,请用A*算法,解,解决该,问,问题。解：用m表,示,示左岸,的,的传道,士,士人数,，,，c表,示,示左岸,的,的野人,数,数，b,表,表示左,岸,岸的船,数,数，用,三,三元组,（,（m，c，b,）,）表示,问,问题的,状,状态。,对,对A*算法,，,，首先,需,需要确,定,定估价,函,函数。,设,设g（n,）,）=d,（,（n）,，,，h（n）=m＋c,－,－2b,，,，,则,则,有,有f,（,（n）=g（n）＋h（n,）,）=d,（,（n）,＋,＋m＋c－2b其,中,中，d,（,

21、（n）,为,为节点,的,的深度,。,。通过,分,分析可,知,知h（n）＜h*(n)，,满,满足A*算法,的,的限制,条,条件。M-C,问,问题,的,的搜索,过,过程如,下,下页图,所,所示。,在,在该图,中,中，每,个,个节点,旁,旁边还,标,标出了,该,该节点,的,的h值,和,和f值,。,。,,(3,2,0),(3,1,0),(2,2,0),(3,3,1),h=4,f=4,f(n)=d(n)+,m+c-2b,h,h=5,f=6,h=4,f=5,h=4,f=5,(3,2,1),h=3,f=5,(2,1,0),(3,0,0),h=3,f=6,h=3,f=6,(2,2,1),(3,1,1),h=2

22、,f=6,h=2,f=6,h=2,f=7,h=2,f=7,传教士和野人问题的搜索图,(0,0,0),(0,3,1),h=1,f=7,(0,1,0),h=1,f=8,(0,2,1),h=0,f=8,(0,2,0),(1,1,0),,,4.4 与/或树的盲,目,目搜索,,概念:,直接可解的,简,简单问题称,为,为本原问题,，,，本原问,题,题对应的节,点,点称为终止,节,节点，在与,或,或图（树）,中,中无子节点,的,的节点称为,端,端节点，,一,一个节点的,子,子节点如果,是,是“与”关,系,系，则该节,点,点便称为与,节,节点，一个,节,节点的子节,点,点如果是“,或,或”关系，,则,则该节点

23、便,称,称为或节点,。,。注意，终,止,止节点一定,是,是端节点，,但,但端节点不,一,一定是终止,节,节点。,可解性判别,(1)一个,节,节点是可解,，,，则节点须,满,满足下列条,件,件之一:,①终止节点,是,是可解节点,；,；,②一个与节,点,点可解，当,且,且仅当其子,节,节点全都可,解,解；,③一个或节,点,点可解，只,要,要其子节点,至,至少有一个,可,可解。,(2)一个,节,节点是不可,解,解，则节点,须,须满足下列,条,条件之一:,①非终止节,点,点的端节点,是,是不可解节,点,点；,②一个与节,点,点不可解，,只,只要其子节,点,点至少有一,个,个不可解；,③一个或节,点,点

24、不可解，,当,当且仅当其,子,子节点全都,不,不可解。,,一. 与/,或,或树的一般,搜,搜索,与/或树的,搜,搜索过程实,际,际上是一个,不,不断寻找解树的过程。其,一,一般搜索过,程,程如下：（1）把原始问题,作,作为初始节,点,点S0，并,把,把它作为当,前,前节点；（2）应用分解或等价变换操作对当前,节,节点进行扩,展,展；（3）为每个子节,点,点设置指向,父,父节点的指,针,针；（4）选择合适的,子,子节点作为,当,当前节点，,反,反复执行第,（,（2）步和,第,第（3）步,，,，在此期间,需,需要多次调,用,用可解标记过,程,程或不可解标记,过,过程，直到初始,节,节点被标记,为,

25、为可解节点或,不,不可解节点为止。,上,上述,搜,搜索过程将,形,形成一棵与/或树，这,种,种由搜索过,程,程形成的与/或树称为搜索树。当搜索成,功,功时，经可,解,解标记过程,标,标识的由初,始,始节点及其,下,下属的可解,节,节点构成的,子,子树称为解树。,用与/或树,法,法表示的问,题,题求解过程,与,与状态空间,法,法类似，也,是,是通过搜索,来,来实现对问,题,题求解的。,与,与/或树的,搜,搜索策略也,分,分为盲目搜索和启发式搜索两大类。,,搜索过程中,的,的可解标记过,程,程与不可解,标,标记过程都是自下而,上,上进行的，,即,即由子节点,的,的可解性确,定,定父节点、,祖,祖父

26、节点的,可,可解性；由,子,子节点的不,可,可解性确定,父,父节点、祖,父,父节点的不,可,可解性。在,与,与/或树中,，,，除端节点,和,和终止节点,外,外，一个节,点,点的可解性,完,完全是由其,子,子节点来决,定,定的。对与,节,节点，只有,其,其所有子节,点,点都为可解,时,时它才为可,解,解，只要有,一,一个子节点,不,不可解它就,是,是不可解的,；,；对或节点,，,，只要有一,个,个子节点可,解,解它就是可,解,解的，仅当,所,所有子节点,都,都是不可解,时,时它才为不,可,可解。这种,由,由可解子节,点,点来确定其,父,父节点、祖,父,父节点为可,解,解节点的过,程,程称为可解标

27、记过,程,程；由不可解,子,子节点来确,定,定其父节点,、,、祖父节点,为,为不可解节,点,点的过程称,为,为不可解标记,过,过程。,由,由于与/或,树,树搜索的目,标,标是寻找解树，因此，如,果,果搜索过程,确,确定某个节,点,点为可解节,点,点，则其,不,不可解的后,裔,裔节点就可,从,从搜索树中,删,删去；同样,，,，如果搜索,过,过程能确定,某,某个节点为,不,不可解节点,，,，则其后裔,节,节点也可从,搜,搜索树中删,去,去。,,与状态空间,的,的广度优先,搜,搜索类似，,只,只是在搜索,过,过程中需要,多,多次调用可,解,解标记过程,或,或不可解标,记,记过程，其,搜,搜索算法如,

28、下,下：（1）把初始节点S0 放人Open表,中,中；（2）把Open,表,表的第一个,节,节点取出放,入,入Closed表，并,记,记该节点为n；（3）如果节点n,可,可扩展，则,做,做下列工作,：,：①扩展节点n,，,，将其子节,点,点放入Open表的尾,部,部，并为每,一,一个子节点,设,设置指向父,节,节点的指针,；,；②考察这些子,节,节点中是否,有,有终止节点,。,。若有，则,标,标记这些终,止,止节点为可,解,解节点，并,用,用可解标记,过,过程对其父,节,节点及先辈,节,节点中的可,解,解节点进行,标,标记。如果,初,初始解节点S0能够被,标,标记为可解,节,节点，就得,到,到

29、了解树，,搜,搜索成功，,退,退出搜索过,程,程；如果不,能,能确定S0,为,为可解节点,，,，则从Open表中删,去,去具有可解,先,先辈的节点,；,；③转第（2）,步,步。,二. 与/,或,或树的广度,优,优先搜索,,（4）如果节点n,不,不可扩展，,则,则做下列工,作,作：①标记节点n,为,为不可解节,点,点；②应用不可解,标,标记过程对,节,节点n的先,辈,辈中不可解,的,的节点进行,标,标记。如果,初,初始解节点S0也被标,记,记为不可解,节,节点，则搜,索,索失败，表,明,明原始问题,无,无解，退出,搜,搜索过程；,如,如果不能确,定,定S0为不,可,可解节点，,则,则从Open表

30、中删去,具,具有不可解,先,先辈的节点,；,；③转第（2）,步,步。,,例 ：,设有如下图,所,所示的与/,或,或树，节点,按,按图中所标,注,注的顺序号,进,进行扩展，,其,其中标有t1、t2、t3的节点,是,是终止节点,，,，A 、B 、 C,为,为不可解的,端,端节点。,,与/或树的广度优先搜索,1,2,3,A,4,t1,t3,C,B,t2,5,搜索过程为,：,（ 1）先扩展1号节点,，,，生成2号节点和3号节点,，,，由 于这,两,两个子节点,都,都不是终止,节,节点，因此,接,接着扩展2,号,号节点。,（2）扩展2号节,点,点，生成A,节,节点和4号,节,节点。由于,这,这两个子节,

31、点,点均不是终,止,止节点，因,此,此接着扩展3号节点,。,（3）扩展3号节,点,点，生成t1节点和5,号,号节点。由,于,于t1为终,止,止节点，则,标,标记它为可,解,解节点，并,应,应用可解标,记,记过程，对,其,其先辈中的,可,可解节点进,行,行标记，由,于,于t1的父,节,节点是一个,与,与节点，因,此,此不能确定3号节点,是,是否可解。,（4）扩展节点A,，,，由于A是,端,端节点，调,用,用不可解标,记,记过程，由,于,于2号节点,是,是或节点，,因,因此不能确,定,定2号节点,是,是不可解节,点,点。,（5）扩展4号节,点,点，生成t2节点和B,节,节点。由于t2为终止,节,节

32、点，则标,记,记它为可解,节,节点，并应,用,用可解标记,过,过程，标记4号节点为,可,可解节点，,标,标记2号节,点,点为可解节,点,点，但不能,标,标记1号节,点,点为可解节,点,点。,（6）扩展5号,节,节点，生,成,成t3节,点,点和C节,点,点。由于t3为终,止,止节点，,标,标记它为,可,可解节点,，,，并应用,可,可解标记,过,过程，标,记,记5号节,点,点为可解,节,节点，标,记,记3号节,点,点为可解,节,节点。标,记,记1号节,点,点为可解,节,节点。,（7）搜索成功，得到由1、2、3、4、5号节点,及,及t1、t2、t3节点构,成,成的解树,。,。该解树,如,如上图中,的

33、,的粗线所,示,示。,,,,,,可以带有,深,深度限制dm，其,搜,搜索算法,如,如下：（1）把初始节,点,点S0放,入,入 Open表,中,中；（2）把Open表的第,一,一个节点,取,取出放入Closed表，,并,并记该节,点,点为n；（3）如果节点n的深度,等,等于dm,，,，则转第,（,（5）步,的,的第①点,；,；（4）如果节点n可扩展,，,，则做下,列,列工作：①扩展节点n，将,其,其子节点,放,放入 Open表,的,的首部，,并,并为每一,个,个子节点,设,设置指向,父,父节点的,指,指针；②考察这些,子,子节点中,是,是否有终,止,止节点。,若,若有，则,标,标记这些,终,终

34、止节点,为,为可解节,点,点，并用,可,可解标记,过,过程对其,父,父节点及,先,先辈节点,中,中的可解,节,节点进行,标,标记。如,果,果初始节,点,点S0能,够,够被标记,为,为可解节,点,点，就得,到,到了解树,，,，搜索成,功,功，退出,搜,搜索过程,；,；如果不,能,能确定S0为可解,节,节点，则,从,从Open表中删,去,去具有可,解,解先辈的,节,节点；③转第（2,）,）步。,三. 与/或树的,深,深度优先,搜,搜索,,（5）如果节点n不可扩,展,展，则做,下,下列工作,：,：①标记节点n为不可,解,解节点；②应用不可,解,解标记过,程,程对节点n的先辈,中,中不可解,的,的节点

35、进,行,行标记。,如,如果初始,节,节点S0,也,也被标记,为,为不可解,节,节点，则,搜,搜索失败,，,，表明原,始,始问题无,解,解，退出,搜,搜索过程,；,；如果不,能,能确定为,不,不可解节,点,点，则从Open表中,删,删去具有,不,不可解先,辈,辈的节点,；,；③转第（2,）,）步。,,与/或树的深度优先搜索,1,2,3,A,4,t1,t3,C,B,t2,5,例如，对,上,上例所给,出,出的与／,或,或树，若,按,按有界深,度,度优先搜,索,索，且给,定,定dm=4，则其,扩,扩展节点,的,的顺序为,：,：1,，,，3，5,，,，2，4,其,其解树,与,与上例相,同,同。,,与/或

36、树,的,的盲目搜,索,索是按确,定,定路线进,行,行的，当,要,要选择一,个,个节点进,行,行扩展时,，,，只是根,据,据节点在,与,与/或树,中,中所处的,位,位置，而,没,没有考虑,要,要付出的,代,代价，因,而,而求得的,解,解树不一,定,定是代价,最,最小的解,树,树，即不,一,一定是最,优,优解树。,因,因此，需,要,要考虑与/或树的,启,启发式搜,索,索。在讨,论,论与／或,树,树的启发,式,式搜索过,程,程之前，,需,需要先讨,论,论几个有,关,关的概念,。,。,一. 解,树,树的代价,与,与希望树,与／或树,的,的启发式,搜,搜索过程,是,是一种利,用,用搜索过,程,程所得到,

37、的,的启发性,信,信息寻找,最,最优解树,的,的过程。,对,对搜索的,每,每一步，,算,算法都试,图,图找到一,个,个最有希,望,望成为最,优,优解树的,子,子树。最,优,优解树是,指,指代价最,小,小的那棵,解,解树。,4.5,与,与/,或,或,树,树,的,的,启,启,发,发,式,式,搜,搜,索,索,,1,．,．,解,解,树,树,的,的,代,代,价,价在,与,与/,或,或,树,树,的,的,启,启,发,发,式,式,搜,搜,索,索,过,过,程,程,中,中,，,，,解,解,树,树,的,的,代,代,价,价,可,可,按,按,如,如,下,下,规,规,则,则,计,计,算,算,：,：（1,）,）若n,为,为

38、,终,终,止,止,节,节,点,点,，,，,则,则,其,其,代,代,价,价h,（,（n,）,）=0,。,。（2,）,）若n,为,为,或,或,节,节,点,点,，,，,且,且,子,子,节,节,点,点,为,为n1,，,，n2,，,，,…,…,，,，nk,，,，,则,则n,的,的,代,代,价,价,为,为h,（,（n,）,）=min{c,（,（n,，,，ni,）,）,＋,＋h,（,（ni,）,）}(1,≤,≤i,≤,≤k),其,中,中,，,，c,（,（n,，,，ni,）,）,是,是,节,节,点,点n,到,到,其,其,子,子,节,节,点,点ni,的,的,边,边,代,代,价,价,。,。,（3,）,）若n,为,

39、为,与,与,节,节,点,点,，,，,且,且,子,子,节,节,点,点,为,为n1,，,，n2,，,，,…,…,，,，nk,，,，,则,则n,的,的,代,代,价,价,可,可,用,用,和,和,代,代,价,价,法,法,或,或,最,最,大,大,代,代,价,价,法,法,。,。,若,若,用,用,和,和,代,代,价,价,法,法,，,，,则,则,其,其,计,计,算,算,公,公,式,式,为,为,：,：,h,（,（n,）,）=,Σ,Σ((c(n,，,，ni),＋,＋h(ni))i=1,2,,…,…,…,…,k,若,若,用,用,最,最,大,大,代,代,价,价,法,法,，,，,则,则,其,其,计,计,算,算,公,公,式

40、,式,为,为,：,：h,（,（n,）,）=max,｛,｛c,（,（n,，,，ni,）,）,＋,＋h,（,（ni,）,）,｝,｝(1,≤,≤i,≤,≤k)（4,）,）若n,是,是,端,端,节,节,点,点,，,，,但,但,又,又,不,不,是,是,终,终,止,止,节,节,点,点,，,，,则,则n,不,不,可,可,扩,扩,展,展,，,，,其,其,代,代,价,价,定,定,义,义,为,为h,（,（n,）,）=,∞,∞（5,）,）根,节,节,点,点,的,的,代,代,价,价,即,即,为,为,解,解,树,树,的,的,代,代,价,价,。,。,,例,：,：设,右,右,图,图,是,是,一,一,棵,棵,与,与/,或,或

41、,树,树,，,，,其,其,中,中,包,包,括,括,两,两,棵,棵,解,解,树,树,，,，,左,左,边,边,的,的,解,解,树,树,由,由S0,、,、A,、,、t1,、,、C,及,及t3,组,组,成,成,；,；,右,右,边,边,的,的,解,解,树,树,由,由S0,、,、B,、,、t2,、,、D,及,及t4,组,组,成,成,。,。,在,在,此,此,与,与/,或,或,树,树,中,中,，,，t1,、,、t2,、,、t3,、,、t4,为,为,终,终,止,止,节,节,点,点,；,；E,、,、F,是,是,端,端,节,节,点,点,；,；,边,边,上,上,的,的,数,数,字,字,是,是,该,该,边,边,的,的,

42、代,代,价,价,。,。,请,请,计,计,算,算,解,解,树,树,的,的,代,代,价,价,。,。,S0,A,B,t1,C,t3,E,t2,D,t4,F,与／或树的代价,2,2,4,6,3,5,2,1,解：先计算左,边,边的解树,按,按和代,价,价：h（S0）=2＋4＋6＋2=14,按,按最大代,价,价：h（S0）=8＋2=10,再,再,计,计算右边的,解,解树,按,按和代价：h（S0,）,）= 1＋5＋ 3,＋,＋ 2=11,按,按最大代价,：,：h（S0,）,）=6＋2=8,在,在本例,中,中，无论按,和,和代价还是,最,最大代价，,右,右边的解树,都,都是最优解,树,树。但在有,些,些情况下

43、，,当,当采用的代,价,价法不同时,，,，找到的最,优,优解树有可,能,能不同。,,2．希望树为了找到最,优,优解树，搜,索,索过程的任,何,何时刻都应,该,该选择那些,最,最有希望成,为,为最优解树,一,一部分的节,点,点进行扩展,。,。由于这些,节,节点及其父,节,节点所构成,的,的与/或树,最,最有可能成,为,为最优解树,的,的一部分，,因,因此称它为,希,希望解树，,也,也简称为希望树。需要注意,，,，希望解树,是,是会随搜索,过,过程而不断,变,变化的。,定义：希望解树T,（,（1）初始,节,节点S0在,希,希望树T中,；,；,（,（2）如,果,果n是具有,子,子节点n1,，,，n2

44、，…,，,，nk的或节点，则n的某,个,个子节点ni在希望树T中的充分,必,必要条件是h,（,（n）=min {c（n，ni）＋ h,（,（ni）}1≤i≤k（3）如果n是与节点，则n的全,部,部子节点都,在,在希望树T,中,中。,,与／或树的,启,启发式搜索,需,需要不断地,选,选择、修正,希,希望树，其,搜,搜索过程如,下,下：（1）把初始节点S0放入Open表中,，,，计算h（S0）；（2）计算希望树T；（3）依次在Open表中取,出,出T的端节,点,点放入Closed表,，,，记节点为n；（4）如果节点n,为,为终止节点,，,，则做下列,工,工作：①标记节点n,为,为可解节点,；,；②

45、在T上应用,可,可解标记过,程,程，对n的,先,先辈节点中,的,的所有可解,节,节点进行标,记,记；③如果初始节,点,点S0能够,被,被标记为可,解,解节点，则T就是最优,解,解树，成功,退,退出；④否则，从Open表中,删,删去具有可,解,解先辈的所,有,有节点；⑤转第（2）,步,步。,二. 与/,或,或树的启发,式,式搜索过程,,（5）如果节点n,不,不是终止节,点,点，但可扩,展,展，则做下,列,列工作：①扩展节点n,，,，生成n的,所,所有子节点,；,；②把这些子节,点,点都放入Open表,中,中，并为每,一,一个子节点,设,设置指向父,节,节点 n的,指,指针；③计算这些子,节,节点

46、及其先,辈,辈节点的h,值,值；④转第（2）,步,步。（6）如果节点n,不,不是终止节,点,点，且不可,扩,扩展，则做,下,下列工作：①标记节点n,为,为不可解节,点,点；②在T上应用,不,不可解标记,过,过程，对n,的,的先辈节点,中,中的所有不,可,可解节点进,行,行标记；③如果初始节,点,点S0能够,被,被标记为不,可,可解节点，,则,则问题无解,，,，失败退出,；,；④否则，从Open,表,表中删去具,有,有不可解先,辈,辈的所有节,点,点；⑤转第,（,（2,）,）步,。,。,,例，,搜,搜索,过,过程,每,每次,扩,扩展,节,节点,时,时,都,都同,时,时扩,展,展两,层,层，,且,

47、且按,一,一层,或,或节,点,点、,一,一层,与,与节,点,点的,间,间隔,方,方式,进,进行,扩,扩展,。,。,设初,始,始节,点,点为S0,，,，对S0,扩,扩展,后,后得,到,到的,与,与/,或,或树,如,如下,图,图所,示,示。,其,其中,，,，端,节,节点B、C、E、F下,面,面的,数,数字,是,是用,启,启发,函,函数,估,估算,出,出的h值,，,，节,点,点A,、,、D,旁,旁边,的,的数,字,字是,按,按和,代,代价,法,法计,算,算出,来,来的,节,节点,代,代价,。,。此,时,时，S0,的,的右,子,子树,是,是当,前,前的,希,希望,树,树，,下,下面,对,对其,端,端节

48、,点,点进,行,行扩,展,展。,S0,A,D,B,C,E,F,8,7,3,3,3,2,扩展S0,后,后的,与,与／,或,或树,8,,扩展,节,节点E,，,，由,右,右子,树,树求,出,出的h（S0,）,）=12,，,，而,由,由左,子,子树,求,求出,的,的h,（,（S0）=9,。,。故,当,当前,的,的希,望,望树,应,应改,为,为左,子,子树,。,。,对B,扩,扩展,两,两层,。,。由,于,于H,和,和I,是,是可,解,解节,点,点，,调,调用,可,可解,标,标记,过,过程,，,，得,节,节点G、B也,为,为可,解,解节,点,点，,但,但不,能,能标,记,记S0为,可,可解,节,节点,，,

49、，须,继,继续,扩,扩展,。,。当,前,前的,希,希望,树,树仍,然,然是,左,左子,树,树。,对,对C,扩,扩展,。,。扩,展,展两,层,层后,得,得到,的,的与,／,／或,树,树如,图,图3,所,所示,。,。,S0,A,D,B,C,E,F,8,3,3,2,,,,,,,3,2,2,2,7,7,6,11,9,图1,扩,扩展E后,的,的与,／,／或,树,树,S0,A,D,B,C,E,F,8,3,3,2,,,,,,,3,2,2,2,7,7,6,11,9,G,K,H,I,L,J,0,0,2,2,2,6,图2,扩,扩,展,展B,后,后的,与,与／,或,或树,S0,D,E,F,A,B,C,8,3,3,2

50、,,,,,,,3,2,2,2,7,7,6,11,9,I,G,K,H,L,J,0,0,2,2,2,6,M,N,P,0,0,5,2,2,9,图3 扩展C后的与／或树,9,由于N和P是,可,可解,节,节点,，,，调,用,用可,解,解标,记,记过,程,程，,得,得节,点,点M,、,、C,、,、A,也,也为,可,可解,节,节点,，,，进,而,而S0为,可,可解,节,节点,。,。求,出,出了,代,代价,最,最小,的,的解,树,树，,即,即最,优,优解,树,树，,如,如图,中,中粗,线,线所,示,示。,按,按和,代,代价,法,法，,该,该最,优,优解,树,树的,代,代价,为,为9,。,。,,博弈是一,类

51、,类富,有,有智,能,能行,为,为的,竞,竞争,活,活动,，,，如,下,下棋,、,、打,牌,牌、,战,战争,等,等。,博,博弈,可,可分,为,为双人,完,完备,信,信息,博,博弈和机遇,性,性博,弈,弈。所,谓,谓双人,完,完备,信,信息,博,博弈，就,是,是两,位,位选,手,手对,垒,垒，,轮,轮流,走,走步,，,，每,一,一方,不,不仅,知,知道,对,对方,已,已经,走,走过,的,的棋,步,步，,而,而且,还,还能,估,估计,出,出对,方,方未,来,来的,走,走步,。,。对,弈,弈的,结,结果,是,是一,方,方赢,，,，另,一,一方,输,输；,或,或者,双,双方,和,和局,。,。所,谓,谓

52、机遇,性,性博,弈,弈，是,指,指存,在,在不,可,可预,测,测性,的,的博,弈,弈，,例,例如,掷,掷币,等,等。,对,对机,遇,遇性,博,博弈,，,，由,于,于不,具,具备,完,完备,信,信息,，,，因,此,此不,作,作讨,论,论。,假设,博,博弈,的,的一,方,方为MAX，另,一,一方,为,为MIN。在,博,博弈,过,过程,的,的每,一,一步,，,，可,供,供MAX,和,和MIN,选,选择,的,的行,动,动方,案,案都,可,可能,有,有多,种,种。,从,从MAX,方,方的,观,观点,看,看，,可,可供,自,自己,选,选择,的,的那,些,些行,动,动方,案,案之,间,间是,“,“或”的,关

53、,关系,，,，选,择,择哪,个,个方,案,案完,全,全是,由,由自,己,己决,定,定的,；,；而,对,对那,些,些可,供,供MIN,选,选择,的,的行,动,动方,案,案之,间,间则,是,是“与”的,关,关系,，,，主,动,动权,掌,掌握,在,在MIN,的,的手,里,里，,任,任何,一,一个,方,方案,都,都有,可,可能,被,被MIN,选,选中,，,，MAX,必,必须,防,防止,那,那种,对,对自,己,己最,为,为不,利,利的,情,情况,的,的发,生,生。,4.6,博,博弈,树,树的,启,启发,式,式搜,索,索,一.,概,概,述,述,,若把,双,双人,完,完备,信,信息,博,博弈,过,过程,用,

54、用图,表,表示,出,出来,，,，就,可,可得,到,到一,棵,棵与/或,树,树，,这,这种,与,与/,或,或树,被,被称,为,为博弈,树,树。在,博,博弈,树,树中,，,，那,些,些下,一,一步,该,该MAX,走,走步,的,的节,点,点称,为,为MAX节,点,点，而,下,下一,步,步该MIN走,步,步的,节,节点,称,称为MIN节,点,点。博,弈,弈树,具,具有,如,如下,特,特点,：,：,（l,）,）博,弈,弈的,初,初始,状,状态,是,是初,始,始节,点,点；,（2,）,）博,弈,弈树,中,中的,“,“或,”,”节,点,点和,“,“与,”,”节,点,点是,逐,逐层,交,交替,出,出现,的,的

55、；,（3,）,）整,个,个博,弈,弈过,程,程始,终,终站,在,在某,一,一方,的,的立,场,场上,，,,对简,单,单的,博,博弈,问,问题,，,，可,以,以生,成,成整,个,个博,弈,弈树,，,，找,到,到必,胜,胜的,策,策略,。,。但,对,对于,复,复杂,的,的博,弈,弈，,如,如国,际,际象,棋,棋，,大,大约,有,有10,120,个节点,，,，要生,成,成整个,搜,搜索树,是,是不可,能,能的。,一,一种可,行,行的方,法,法是用,当,当前正,在,在考察,的,的节点,生,生成一,棵,棵部分博,弈,弈树，由于,该,该博弈,树,树的叶,二.,极,极大极,小,小过程,为了计,算,算非叶,节

56、,节点的,值,值，必,须,须从叶,节,节点向,上,上倒推,。,。对于MAX,节,节点，,由,由于MAX,方,方总是,选,选择估,值,值最大,的,的走步,，,，因此,，,，MAX节点,的,的倒推,值,值应该,取,取其后,继,继节点,估,估值的最大值。对于MIN,节,节点，,由,由于MIN方,总,总是选,择,择使估,值,值最小,的,的走步,，,，因此MIN,节,节点的,倒,倒推值,应,应取其,后,后继节,点,点估值,的,的最小值。这样,一,一步一,步,步的计,算,算倒推,值,值，直,至,至求出,初,初始节,点,点的倒,推,推值为,止,止。这,一,一过程,称,称为极大极,小,小过程。,,例：一字棋,

57、游,游戏。,设,设有一,个,个三行,三,三列的,棋,棋盘，,如,如下图,所,所示，,两,两个棋,手,手轮流,走,走步，,每,每个棋,手,手走步,时,时往空,格,格上摆,一,一个自,己,己的棋,子,子，谁,先,先使自,己,己的棋,子,子成三,子,子一线,为,为赢。,设,设MAX方的,棋,棋子用×标记，MIN,方,一字棋棋盘,若P对MAX,、,、MIN都是,胜,胜负未,定,定局，,则,则,e（P,）,）=e（+P）－e（-P）,其,其中，e（+P）表,示,示棋局P上,有,有可能,使,使×成三子,一,一线的,数,数目；e（-P）表,示,示棋局P上,有,有可能,使,使○成三子,一,一线的,数,数目。,

58、,例如，,对,对图1,所,所示的,棋,棋局有,估,估价函,数,数值e（P）＝6-4,＝,＝2,图1 棋局1,在搜索,过,过程中,，,，具有,对,对称性,的,的棋局,认,认为是,同,同一棋,局,局。例,如,如，图2所示,的,的棋局,可,可以认,为,为是同,一,一个棋,局,局，这,图2 对称棋局的例子,,图3,一,一子,棋,棋的极,大,大极小,搜,搜索,S0,S1,S2,S3,S4,S5,-1,1,-2,6-5=1,5-5=0,6-5=1,5-5=0,4-5=,-,1,5-6=,-,1,5-5=0,6-6=0,5-6=,-,1,4-6=,-,2,5-4=1,6-4=2,,极大极,小,小值算,法

59、,法,FunctionMAX-MIN-DECISION(,state,) returns,anaction,inputs:,state,(currentstateingame),v←MAX-VALUE(state),returnthe,action,inSUCCESSORS(,state,) withvaluev,FunctionMAX-VALUE(,state,) returns,a utilityvalue,ifTERMINAL-TEST(state)then returnUTILITY(,state,),v←-∞,for,a,s,inSUCCESSORS(,state,) do v,←,

60、← MAX(v,MIN-VALUE(,s,)),returnv(a=action,招,招数),FunctionMIN-VALUE(,state,) returns,a utilityvalue,ifTERMINAL-TEST(,state,) thenreturn UTILITY(,state,),v←+∞,for,a,s,inSUCCESSORS(,state,) do v,←,← MIN(v,MAX-VALUE(,s,)),returnv,,三.,α,α-β,剪,剪枝,<=2,3,S0,D,E,F,A,B,C,5,3,3,2,,对于一个,或,节点来说，它取当前子节点中的最大倒推值作为它倒推

61、值的下界，称该值为,α,,值。,,α-β,剪,剪枝的,方,方法如,下,下：（1）MAX,节,节点的,α,α值为,当,当前子,节,节点的,最,最大倒,推,推值；（2）MIN,节,节点,的,的β值,为,为当前,子,子节点,的,的最小,倒,倒推值,；,；（3）α-β,剪,剪枝,的,的规则,如,如下：①任何MAX节,点,点n的,α,α值大,于,于或等,于,于它先,辈,辈节点,的,的β值,，,，则n,以,以下的,分,分枝可,停,停止搜,索,索，并,令,令节点n的倒,推,推值为,α,α。,这,这种剪,枝,枝称为β剪枝。②任何MIN节,点,点n的,β,β值小,于,于或等,于,于它先,辈,辈节点,的,的α值,

62、，,，则n,以,以下的,分,分枝可,停,停止搜,索,索，并,令,令节点n的倒,推,推值为,β,β。这,种,种剪枝,称,称为α剪枝。,三.,α,α-β,剪,剪枝,≥ α,min,≤,≤ β,max,≥,≥,α,α,,S0,A,B,C,D,F,G,H,E,I,J,K,L,M,N,P,Q,R,S,,,,,,,,4,8,6,1,5,8,0,-6,4,≥4,≤1,≤4,＝4,5,≥5,＝4,≥4,≥0,＝0,≤-6,＝0,≤0,＝4,＊,＊,＊,＊,＊,α-β剪,枝,枝的例子,T,4,,S0,,,,,,,,,,,0,-3,3,0,0,3,1,6,,,,,,,,5,3,-3,2,2,-3,-2,5,4,-

63、3,0,8,9,-3,,,,,,,,,,,,S0,,,,,,,,,,,0,-3,3,0,0,3,1,6,,,,,,,,5,3,-3,2,2,-3,-2,5,4,-3,0,8,9,-3,,,,,,,,,,,＊,＊,＊,＊,＊,＊,跳棋程序,的,的学习策,略,略,,-,剪枝算法,在极大极,小,小值算法,基,基础上增,加,加了剪枝,功,功能，即,在,在返回值,基,基础上增,加,加了判断,,FunctionALPHA-BETA-SEARCH(,state,) returns anaction,inputs:,state,(currentstate in game),v← MAX-VALUE(,st

64、ate,,,-,∞, +,∞,∞),return the,action,in SUCCESSORS(,state,) with value,v,,,-,剪枝算法,FunctionMAX-VALUE(,state,,, ,) returns,a utility value,inputs:,state,,, the valueof the bestalternativeforMAXalong the path to,state,,, the valueof the bestalternativeforMINalong the path to,state,if TERMINAL-TEST

65、(,state,) then return UTILITY(,state,),v←,-,∞,for,a, s,in SUCCESSORS(,state,) do,v← MAX(v, MIN-VALUE(,s,,, ,)),if v,≥,,thenreturnv,,← MAX(,,, v),return v,,-,剪枝算法,FunctionMIN-VALUE(,state,,, ,) returns,a utility value,inputs:,state,,,thevalue ofthebest alternative for MAX alongthepathto,sta

66、te,,thevalue ofthebest alternative for MIN alongthepathto,state,if TERMINAL-TEST(,state,) then return UTILITY(,state,),v← +,∞,∞,for,a, s,in SUCCESSORS(,state,) do,v← MIN(v, MAX-VALUE(,s,,, ,)),ifv,≤,,thenreturnv,,← MIN(,,, v),return v,,分析产生,式,式正向推,理,理算法，,可,可以看出,，,，它们只,能,能用于解,决,决逻辑推,理,理性问题,。,。若要求,解,解规划性,问,问题则还,需,需要：,,(2)若要回溯，则还需保存与每个动态数据库状态对应的可用规则集。因为动态数据库状态与可用规则集实际是一一对应的。,(3)要进行树式搜索，还需设置一个OPEN表，以进行新生动态数据库的状态保存和当前动态数据库状态的切换。,(4)还要考虑一条规则是否只允许执行一次。若是，则要对已执行了的规则进行标记。,成功退出,失败退出,把初始数据放入综合数据库,综合数