《級(jí)人工智能原理》由會(huì)員分享，可在線閱讀，更多相關(guān)《級(jí)人工智能原理（54頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),,*,*,前面討論的各種搜索方法都沒(méi)有用到問(wèn)題本身的特性信息，只是按照事先設(shè)定的線路進(jìn)行搜索，具有較大的盲目性。事實(shí)上，如果能夠利用搜索過(guò)程所得到的問(wèn)題自身的一些特性信息來(lái)指導(dǎo)搜索過(guò)程，則對(duì)搜索將是十分有益的。這種利用問(wèn)題自身的特性信息來(lái)引導(dǎo)搜索過(guò)程的搜索方法稱為,啟發(fā)式搜索,。由于啟發(fā)式搜索方法具有較強(qiáng)的針對(duì)性，因此，可以縮小搜索范圍，提高搜索效率。,4.5 狀態(tài)空間的啟發(fā)式搜索,,,啟發(fā)式搜索方法所依據(jù)的是問(wèn)題自身的啟發(fā)性信息，而啟發(fā)性信息又是通過(guò),估價(jià)函數(shù),作用到搜索過(guò)程中的。,,1．啟發(fā)性信息,一. 啟

2、發(fā)性信息和估價(jià)函數(shù),,啟發(fā)性信息,是指那種與具體問(wèn)題求解過(guò)程有關(guān)的，并可指導(dǎo)搜索過(guò)程朝著最有希望方向前進(jìn)的控制信息。啟發(fā)性信息一般有以下三種： ① 有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息； ② 有效地幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成； ③ 能決定在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)哪些節(jié)點(diǎn)應(yīng)從搜索樹(shù)上被刪除。 一般來(lái)說(shuō)，搜索過(guò)程所使用的啟發(fā)性信息的啟發(fā)能力越強(qiáng)，擴(kuò)展的無(wú)用節(jié)點(diǎn)就越少。,,,,2．估價(jià)函數(shù),用來(lái)估計(jì)節(jié)點(diǎn)重要性的函數(shù)稱為,估價(jià)函數(shù),。估價(jià)函數(shù)f（n）被定義為從初始節(jié)點(diǎn),S0,出發(fā)，經(jīng)過(guò)節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn),Sg,的所有路徑中最小路徑代價(jià)的估計(jì)值。它的一般形式為,f（n）=

3、g（n）＋h（n）,其中，g（n）是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的實(shí)際代價(jià)；h（n）是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)S0的最優(yōu)路徑的估計(jì)代價(jià)。對(duì)g（n）的值，可以按指向父節(jié)點(diǎn)的指針，從節(jié)點(diǎn)n反向跟蹤到初始節(jié)點(diǎn)S0,得到一條從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的最小代價(jià)路徑，然后把這條路徑上所有有向邊的代價(jià)相加，就得到g（n）的值。對(duì)h（n）的值，則需要根據(jù)問(wèn)題自身的特性來(lái)確定，它體現(xiàn)的是問(wèn)題自身的啟發(fā)性信息，因此也稱h（n）為,啟發(fā)函數(shù),。,n,,,g,(,n,),h,(,n,),,例,： 八數(shù)碼難題。設(shè)問(wèn)題的初始狀態(tài)S0和目標(biāo)狀態(tài) Sg 如前所述，且估價(jià)函數(shù)為: f（n）=d（n）＋W（n）其中，d（n）表

4、示節(jié)點(diǎn) n在搜索樹(shù)中的深度； w（n）表示節(jié)點(diǎn) n中“不在位”的數(shù)碼個(gè)數(shù)。請(qǐng)計(jì)算初始狀態(tài)S0的估價(jià)函數(shù)值f（S0）。 解：在本例的估價(jià)函數(shù)中，取g（n）=d（n），h（n）=W（n）。它說(shuō)明是用從S0到n的路徑上的單位代價(jià)表示實(shí)際代價(jià)，用n中“,不在位,”的數(shù)碼個(gè)數(shù)作為啟發(fā)信息。一般來(lái)說(shuō)，某節(jié)點(diǎn)中的“不在位”的數(shù)碼個(gè)數(shù)越多，說(shuō)明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn)。 對(duì)初始節(jié)點(diǎn) S0，由于 d（S0）= 0， W（S0）= 3，因此有 f（S0）=0＋3=3? 這個(gè)例子僅是為了說(shuō)明估價(jià)函數(shù)的含義及估價(jià)函數(shù)值的計(jì)算。在問(wèn)題搜索過(guò)程中，除了需要計(jì)算初始節(jié)點(diǎn)的估價(jià)函數(shù)之外，更

5、多的是要計(jì)算新生成節(jié)點(diǎn)的估價(jià)函數(shù)值。,,2 8,3,1,4,7 6 5,,,二. A算法,,在圖搜索算法中，如果能在搜索的每一步都利用,估價(jià)函數(shù),f（n）=g（n）＋h（n）對(duì)Open表中的節(jié)點(diǎn)進(jìn)行排序，則該搜索算法為A算法。由于估價(jià)函數(shù)中帶有問(wèn)題自身的啟發(fā)性信息，因此，,A算法,也被稱為,啟發(fā)式搜索算法,。 對(duì)啟發(fā)式搜索算法，又可根據(jù)搜索過(guò)程中選擇擴(kuò)展節(jié)點(diǎn)的范圍，將其分為,全局擇優(yōu)搜索算法,和,局部擇優(yōu)搜索算法,。,,每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí)，總是從Open表的所有節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。其搜索過(guò)程可描述如下：,（1）,把S0放入Open表中，f(s0)=g（

6、So）＋h（So）；,（2）,如果Open表為空，則問(wèn)題無(wú)解，失敗退出；,（3）,把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，記該節(jié)點(diǎn)為n；,（4）,考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則找到了問(wèn)題的解，成功退出；,（5）,若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（2）步；,（6）,擴(kuò)展節(jié)點(diǎn)n，生成其子節(jié)點(diǎn)ni（i=1,2,……），計(jì)算每一個(gè)子節(jié)點(diǎn)的估價(jià)值f(ni) （i=1,2,……），并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后將這些子節(jié)點(diǎn)放入 Open表中；,（7）,根據(jù)各節(jié)點(diǎn)的估價(jià)函數(shù)值，對(duì)Open表中的,全部節(jié)點(diǎn),按從小到大的順序重新進(jìn)行排序；,（8）,轉(zhuǎn)第（2）步。,,1．全局擇優(yōu)搜索,,由于上述

7、算法的第（7）步要對(duì)Open表中的,全部節(jié)點(diǎn),按其估價(jià)函數(shù)值從小到大重新進(jìn)行排序，這樣在算法第（3）步取出的節(jié)點(diǎn)就一定是Open表的所有節(jié)點(diǎn)中估價(jià)函數(shù)值最小的一個(gè)節(jié)點(diǎn)。因此，它是一種全局擇優(yōu)的搜索方式。 對(duì)上述算法進(jìn)一步分析還可以發(fā)現(xiàn)：如果取估價(jià)函數(shù)f(n)=g（n），則它將退化為代價(jià)樹(shù)的廣度優(yōu)先搜索；如果取估價(jià)函數(shù)f(n)=d（n），則它將退化為廣度優(yōu)先搜索?？梢?jiàn)，廣度優(yōu)先搜索和代價(jià)樹(shù)的廣度優(yōu)先搜索是全局擇優(yōu)搜索的兩個(gè)特例。,,例：,八數(shù)碼難題。,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、在局部擇優(yōu)搜索中，每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí)，總是從,剛生成的子節(jié)點(diǎn),中選擇一個(gè)估價(jià)函數(shù)值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。其搜索過(guò)程可描述如下：,（1）,把初始節(jié)點(diǎn)S0放入 Open表中，f(S0)=g(S0)+h(S0) ;,（2）,如果Open表為空，則問(wèn)題無(wú)解，失敗退出；,（3）,把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n；,（4）,考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則找到了問(wèn)題的解，成功退出；,（5）,若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（2）步；,（6）,擴(kuò)展節(jié)點(diǎn)n，生成其子節(jié)點(diǎn)ni(i=1，2，…)，計(jì)算每一個(gè)子節(jié)點(diǎn)的估價(jià)值f（ni） （i=1，2，…），并按估價(jià)值從小到大的順序依次放入Open

10、表的首部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第（2）步。,,2．局部擇優(yōu)搜索(瞎子爬山法),,,由于這一算法的第（6）步僅是把剛生成的子節(jié)點(diǎn)按其估價(jià)函數(shù)值從小到大放入 Open表的首都，這樣在算法第（3）步取出的節(jié)點(diǎn)僅是剛生成的子節(jié)點(diǎn)中估價(jià)函數(shù)值最小的一個(gè)節(jié)點(diǎn)。因此，它是一種局部擇優(yōu)的搜索方式。,對(duì)這一算法進(jìn)一步分析也可以發(fā)現(xiàn)：如果取估價(jià)函數(shù)f（ n）=g（n），則它將退化為代價(jià)樹(shù)的深度優(yōu)先搜索；如果取估價(jià)函數(shù)f（n）=d（n），則它將退化為深度優(yōu)先搜索?？梢?jiàn)，深度優(yōu)先搜索和代價(jià)樹(shù)的深度優(yōu)先搜索是局部擇優(yōu)搜索的兩個(gè)特例。,,三.A,*,算法,前面討,論,論的啟,發(fā),發(fā)式搜,索,索算

11、法,，,，都沒(méi),有,有對(duì)估,價(jià),價(jià)函數(shù)f(n)作任,何,何限制,。,。實(shí)際,上,上，估,價(jià),價(jià)函數(shù),對(duì),對(duì)搜索,過(guò),過(guò)程是,十,十分重,要,要的，,如,如果選,擇,擇不當(dāng),，,，則有,可,可能找,不,不到問(wèn),題,題的解,，,，或者,找,找到的,不,不是問(wèn),題,題的最,優(yōu),優(yōu)解。,為,為此，,需,需要對(duì),估,估價(jià)函,數(shù),數(shù)進(jìn)行,某,某些限,制,制。A* 算,法,法就是對(duì)估價(jià),函,函數(shù)加,上,上一些限制后得到,的,的一種,啟,啟發(fā)式,搜,搜索算,法,法。,,假設(shè)f*(n)為從,初,初始節(jié),點(diǎn),點(diǎn)S0,出,出發(fā)，,約,約束經(jīng),過(guò),過(guò)節(jié)點(diǎn)n到達(dá),目,目標(biāo)節(jié),點(diǎn),點(diǎn)的最,小,小代價(jià),值,值。估,價(jià),價(jià)函

12、數(shù)f(n)是f*(n)的估,計(jì),計(jì)值。,顯,顯然，f*（n）應(yīng),由,由以下,兩,兩部分,所,所組成,：,：一部,分,分是從,初,初始節(jié),點(diǎn),點(diǎn)到節(jié),點(diǎn),點(diǎn)n的最小代價(jià)，,記,記為g*（n,）,）；另,一,一部分,是,是從節(jié),點(diǎn),點(diǎn)n到,目,目標(biāo)節(jié),點(diǎn),點(diǎn)的最小代價(jià)，,記,記為h*（n,）,），當(dāng),問(wèn),問(wèn)題有,多,多個(gè)目,標(biāo),標(biāo)節(jié)點(diǎn),時(shí),時(shí)，應(yīng),取,取其中,代,代價(jià)最,小,小的一,個(gè),個(gè)。因,此,此有,f*（n）＝g*（n）＋h*（n）,把估價(jià),函,函數(shù)f(n),與,與f*(n),相,相比，g（n,）,）是對(duì)g*（n）的,一,一個(gè)估,計(jì),計(jì)，h,（,（n）,是,是對(duì)h*（n,）,）的一,個(gè),個(gè)估

13、計(jì),。,。在這,兩,兩個(gè)估,計(jì),計(jì)中，,盡,盡管g,（,（n）,的,的值容,易,易計(jì)算,，,，但它,不,不一定,就,就是從,初,初始節(jié),點(diǎn),點(diǎn)S0,到,到節(jié)點(diǎn)n的真,正,正最小,代,代價(jià)，,很,很有可,能,能從初,始,始節(jié)點(diǎn)S0到,節(jié),節(jié)點(diǎn)n,的,的真正,最,最小代,價(jià),價(jià)還沒(méi),有,有找到,，,，故有g(shù)（n,）,）≥g*（n,）,）。,有,有了g*（n）和h*（n）的,定,定義，,如,如果對(duì)A算法,（,（全局,擇,擇優(yōu)的,啟,啟發(fā)式,搜,搜索算,法,法）中,的,的g（n）和h（n,）,）分別,提,提出如,下,下限制,：,：,第,第一,，,，g（n）是,對(duì),對(duì)g*,（,（n）,的,的估計(jì),，,，

14、且g,（,（n）,＞,＞0；,第,第二，h（n,）,）是h*（n,）,）的下,界,界，即,對(duì),對(duì)任意,節(jié),節(jié)點(diǎn)n,均,均有,h（n,）,）≤h*（n,）,）。則,稱,稱得到,的,的算法,為,為A*,算,算法,。,。,,A*算,法,法的有,關(guān),關(guān)特性,。,。,1．A*算法,的,的可納,性,性一般來(lái),說(shuō),說(shuō)，對(duì),任,任意一,個(gè),個(gè)狀態(tài),空,空間圖,，,，當(dāng)從,初,初始節(jié),點(diǎn),點(diǎn)到目,標(biāo),標(biāo)節(jié)點(diǎn),有,有路徑,存,存在時(shí),，,，如果,搜,搜索算,法,法能在,有,有限步,內(nèi),內(nèi)找到,一,一條從,初,初始節(jié),點(diǎn),點(diǎn)到目,標(biāo),標(biāo)節(jié)點(diǎn),的,的最佳,路,路徑，,并,并在此,路,路徑上,結(jié),結(jié)束，,則,則稱該,

15、搜,搜索算,法,法是可,采,采納的,。,。A*,算,算法是,可,可采納,的,的。(證明,略,略）。2.A*算法,的,的最優(yōu),性,性A*,算,算法的,搜,搜索效,率,率很大,程,程度上,取,取決于,估,估價(jià)函,數(shù),數(shù)h（n）。,一,一般來(lái),說(shuō),說(shuō)，在,滿,滿足h,（,（n）,≤,≤h*,（,（n）,的,的前提,下,下，h,（,（n）,的,的值越,大,大越好,。,。h（n）的,值,值越大,，,，說(shuō)明,它,它攜帶,的,的啟發(fā),性,性信息,越,越多，A*,算,算法搜,索,索時(shí)擴(kuò),展,展的節(jié),點(diǎn),點(diǎn)就越,少,少，搜,索,索效率,就,就越高,。,。A*,算,算法的,這,這一特,性,性也稱,為,為信息,性,

16、性。(,證,證明略),,A,*,算法應(yīng),用,用舉例,例,例：八數(shù)碼,難,難題。,問(wèn),問(wèn)題的,初,初始狀,態(tài),態(tài)和目,標(biāo),標(biāo)狀態(tài),和,和前例,相,相同。,要,要求用A*,算,算法解,決,決該問(wèn),題,題。解：在上例,中,中，我,們,們?nèi),（,（n）=W（n）。,盡,盡管我,們,們對(duì)h*（n,）,）不能,確,確切知,道,道，但,當(dāng),當(dāng)采用,單,單位代,價(jià),價(jià)時(shí)，,通,通過(guò)對(duì),“,“不在,位,位”數(shù),碼,碼個(gè)數(shù),的,的估計(jì),，,，可以,得,得出至,少,少要移,動(dòng),動(dòng)W（n）步,才,才能到,達(dá),達(dá)目標(biāo),，,，顯然,有,有W（n）≤h*（n）。,因,因此，,前,前例中,所,所定義,的,的h（n）滿,足,

17、足A*,算,算法的,限,限制條,件,件。,這,這,里,里再取,另,另外一,種,種啟發(fā),函,函數(shù)h,（,（n）=P（n），P（n,）,）定義,為,為每一,個(gè),個(gè)數(shù)碼,與,與其目,標(biāo),標(biāo)位置,之,之間距,離,離（不,考,考慮夾,在,在其間,的,的數(shù)碼,）,）的總,和,和，同,樣,樣可以,斷,斷定至,少,少要移,動(dòng),動(dòng)P（n）步,才,才能到,達(dá),達(dá)目標(biāo),，,，因此,有,有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,八數(shù)碼難題h（n）=P（n）的搜索樹(shù),,例：設(shè)有,如,如下結(jié),構(gòu),構(gòu)的移,動(dòng),動(dòng)將牌,游,游戲,,,B代表,黑,黑色牌,，

19、,，W代,表,表白色,牌,牌；E,代,代表該,位,位置為,空,空。玩,法,法：,當(dāng)一個(gè),牌,牌移入,相,相鄰的,空,空位時(shí),，,，費(fèi)用,等,等于挑,過(guò),過(guò)的牌,數(shù),數(shù)加1,。,。,一個(gè)牌,至,至多可,跳,跳過(guò)兩,個(gè),個(gè)牌進(jìn),入,入空位,置,置，其,費(fèi),費(fèi)用等,于,于跳過(guò),的,的牌數(shù),加,加1。,要求把,所,所有的B都移,到,到所有,的,的W的,右,右邊，,設(shè),設(shè)計(jì)h(x),。,。,解：,顯然W,左,左邊的B越少,越,越接近,目,目標(biāo)，,因,因此可,用,用W左,邊,邊B的,個(gè),個(gè)數(shù)作,為,為h(x),h(x)=3*(每,個(gè),個(gè)W左,邊,邊B個(gè),數(shù),數(shù)的總,和,和）,,,h(x)=3*(2+2+3

20、)=21,B,B,B,W,W,W,E,B,B,B,W,W,W,E,,例：傳教士,和,和野人,問(wèn),問(wèn)題。,請(qǐng),請(qǐng)用A*算法,解,解決該,問(wèn),問(wèn)題。解：用m表,示,示左岸,的,的傳道,士,士人數(shù),，,，c表,示,示左岸,的,的野人,數(shù),數(shù)，b,表,表示左,岸,岸的船,數(shù),數(shù)，用,三,三元組,（,（m，c，b,）,）表示,問(wèn),問(wèn)題的,狀,狀態(tài)。,對(duì),對(duì)A*算法,，,，首先,需,需要確,定,定估價(jià),函,函數(shù)。,設(shè),設(shè)g（n,）,）=d,（,（n）,，,，h（n）=m＋c,－,－2b,，,，,則,則,有,有f,（,（n）=g（n）＋h（n,）,）=d,（,（n）,＋,＋m＋c－2b其,中,中，d,（,

21、（n）,為,為節(jié)點(diǎn),的,的深度,。,。通過(guò),分,分析可,知,知h（n）＜h*(n)，,滿,滿足A*算法,的,的限制,條,條件。M-C,問(wèn),問(wèn)題,的,的搜索,過(guò),過(guò)程如,下,下頁(yè)圖,所,所示。,在,在該圖,中,中，每,個(gè),個(gè)節(jié)點(diǎn),旁,旁邊還,標(biāo),標(biāo)出了,該,該節(jié)點(diǎn),的,的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,傳教士和野人問(wèn)題的搜索圖,(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 與/或樹(shù)的盲,目,目搜索,,概念:,直接可解的,簡(jiǎn),簡(jiǎn)單問(wèn)題稱,為,為本原問(wèn)題,，,，本原問(wèn),題,題對(duì)應(yīng)的節(jié),點(diǎn),點(diǎn)稱為終止,節(jié),節(jié)點(diǎn)，在與,或,或圖（樹(shù)）,中,中無(wú)子節(jié)點(diǎn),的,的節(jié)點(diǎn)稱為,端,端節(jié)點(diǎn)，,一,一個(gè)節(jié)點(diǎn)的,子,子節(jié)點(diǎn)如果,是,是“與”關(guān),系,系，則該節(jié),點(diǎn),點(diǎn)便稱為與,節(jié),節(jié)點(diǎn)，一個(gè),節(jié),節(jié)點(diǎn)的子節(jié),點(diǎn),點(diǎn)如果是“,或,或”關(guān)系，,則,則該節(jié)點(diǎn)

23、便,稱,稱為或節(jié)點(diǎn),。,。注意，終,止,止節(jié)點(diǎn)一定,是,是端節(jié)點(diǎn)，,但,但端節(jié)點(diǎn)不,一,一定是終止,節(jié),節(jié)點(diǎn)。,可解性判別,(1)一個(gè),節(jié),節(jié)點(diǎn)是可解,，,，則節(jié)點(diǎn)須,滿,滿足下列條,件,件之一:,①終止節(jié)點(diǎn),是,是可解節(jié)點(diǎn),；,；,②一個(gè)與節(jié),點(diǎn),點(diǎn)可解，當(dāng),且,且僅當(dāng)其子,節(jié),節(jié)點(diǎn)全都可,解,解；,③一個(gè)或節(jié),點(diǎn),點(diǎn)可解，只,要,要其子節(jié)點(diǎn),至,至少有一個(gè),可,可解。,(2)一個(gè),節(jié),節(jié)點(diǎn)是不可,解,解，則節(jié)點(diǎn),須,須滿足下列,條,條件之一:,①非終止節(jié),點(diǎn),點(diǎn)的端節(jié)點(diǎn),是,是不可解節(jié),點(diǎn),點(diǎn)；,②一個(gè)與節(jié),點(diǎn),點(diǎn)不可解，,只,只要其子節(jié),點(diǎn),點(diǎn)至少有一,個(gè),個(gè)不可解；,③一個(gè)或節(jié),點(diǎn),點(diǎn)

24、不可解，,當(dāng),當(dāng)且僅當(dāng)其,子,子節(jié)點(diǎn)全都,不,不可解。,,一. 與/,或,或樹(shù)的一般,搜,搜索,與/或樹(shù)的,搜,搜索過(guò)程實(shí),際,際上是一個(gè),不,不斷尋找解樹(shù)的過(guò)程。其,一,一般搜索過(guò),程,程如下：（1）把原始問(wèn)題,作,作為初始節(jié),點(diǎn),點(diǎn)S0，并,把,把它作為當(dāng),前,前節(jié)點(diǎn)；（2）應(yīng)用分解或等價(jià)變換操作對(duì)當(dāng)前,節(jié),節(jié)點(diǎn)進(jìn)行擴(kuò),展,展；（3）為每個(gè)子節(jié),點(diǎn),點(diǎn)設(shè)置指向,父,父節(jié)點(diǎn)的指,針,針；（4）選擇合適的,子,子節(jié)點(diǎn)作為,當(dāng),當(dāng)前節(jié)點(diǎn)，,反,反復(fù)執(zhí)行第,（,（2）步和,第,第（3）步,，,，在此期間,需,需要多次調(diào),用,用可解標(biāo)記過(guò),程,程或不可解標(biāo)記,過(guò),過(guò)程，直到初始,節(jié),節(jié)點(diǎn)被標(biāo)記,為,

25、為可解節(jié)點(diǎn)或,不,不可解節(jié)點(diǎn)為止。,上,上述,搜,搜索過(guò)程將,形,形成一棵與/或樹(shù)，這,種,種由搜索過(guò),程,程形成的與/或樹(shù)稱為搜索樹(shù)。當(dāng)搜索成,功,功時(shí)，經(jīng)可,解,解標(biāo)記過(guò)程,標(biāo),標(biāo)識(shí)的由初,始,始節(jié)點(diǎn)及其,下,下屬的可解,節(jié),節(jié)點(diǎn)構(gòu)成的,子,子樹(shù)稱為解樹(shù)。,用與/或樹(shù),法,法表示的問(wèn),題,題求解過(guò)程,與,與狀態(tài)空間,法,法類似，也,是,是通過(guò)搜索,來(lái),來(lái)實(shí)現(xiàn)對(duì)問(wèn),題,題求解的。,與,與/或樹(shù)的,搜,搜索策略也,分,分為盲目搜索和啟發(fā)式搜索兩大類。,,搜索過(guò)程中,的,的可解標(biāo)記過(guò),程,程與不可解,標(biāo),標(biāo)記過(guò)程都是自下而,上,上進(jìn)行的，,即,即由子節(jié)點(diǎn),的,的可解性確,定,定父節(jié)點(diǎn)、,祖,祖父

26、節(jié)點(diǎn)的,可,可解性；由,子,子節(jié)點(diǎn)的不,可,可解性確定,父,父節(jié)點(diǎn)、祖,父,父節(jié)點(diǎn)的不,可,可解性。在,與,與/或樹(shù)中,，,，除端節(jié)點(diǎn),和,和終止節(jié)點(diǎn),外,外，一個(gè)節(jié),點(diǎn),點(diǎn)的可解性,完,完全是由其,子,子節(jié)點(diǎn)來(lái)決,定,定的。對(duì)與,節(jié),節(jié)點(diǎn)，只有,其,其所有子節(jié),點(diǎn),點(diǎn)都為可解,時(shí),時(shí)它才為可,解,解，只要有,一,一個(gè)子節(jié)點(diǎn),不,不可解它就,是,是不可解的,；,；對(duì)或節(jié)點(diǎn),，,，只要有一,個(gè),個(gè)子節(jié)點(diǎn)可,解,解它就是可,解,解的，僅當(dāng),所,所有子節(jié)點(diǎn),都,都是不可解,時(shí),時(shí)它才為不,可,可解。這種,由,由可解子節(jié),點(diǎn),點(diǎn)來(lái)確定其,父,父節(jié)點(diǎn)、祖,父,父節(jié)點(diǎn)為可,解,解節(jié)點(diǎn)的過(guò),程,程稱為可解標(biāo)

27、記過(guò),程,程；由不可解,子,子節(jié)點(diǎn)來(lái)確,定,定其父節(jié)點(diǎn),、,、祖父節(jié)點(diǎn),為,為不可解節(jié),點(diǎn),點(diǎn)的過(guò)程稱,為,為不可解標(biāo)記,過(guò),過(guò)程。,由,由于與/或,樹(shù),樹(shù)搜索的目,標(biāo),標(biāo)是尋找解樹(shù)，因此，如,果,果搜索過(guò)程,確,確定某個(gè)節(jié),點(diǎn),點(diǎn)為可解節(jié),點(diǎn),點(diǎn)，則其,不,不可解的后,裔,裔節(jié)點(diǎn)就可,從,從搜索樹(shù)中,刪,刪去；同樣,，,，如果搜索,過(guò),過(guò)程能確定,某,某個(gè)節(jié)點(diǎn)為,不,不可解節(jié)點(diǎn),，,，則其后裔,節(jié),節(jié)點(diǎn)也可從,搜,搜索樹(shù)中刪,去,去。,,與狀態(tài)空間,的,的廣度優(yōu)先,搜,搜索類似，,只,只是在搜索,過(guò),過(guò)程中需要,多,多次調(diào)用可,解,解標(biāo)記過(guò)程,或,或不可解標(biāo),記,記過(guò)程，其,搜,搜索算法如,

28、下,下：（1）把初始節(jié)點(diǎn)S0 放人Open表,中,中；（2）把Open,表,表的第一個(gè),節(jié),節(jié)點(diǎn)取出放,入,入Closed表，并,記,記該節(jié)點(diǎn)為n；（3）如果節(jié)點(diǎn)n,可,可擴(kuò)展，則,做,做下列工作,：,：①擴(kuò)展節(jié)點(diǎn)n,，,，將其子節(jié),點(diǎn),點(diǎn)放入Open表的尾,部,部，并為每,一,一個(gè)子節(jié)點(diǎn),設(shè),設(shè)置指向父,節(jié),節(jié)點(diǎn)的指針,；,；②考察這些子,節(jié),節(jié)點(diǎn)中是否,有,有終止節(jié)點(diǎn),。,。若有，則,標(biāo),標(biāo)記這些終,止,止節(jié)點(diǎn)為可,解,解節(jié)點(diǎn)，并,用,用可解標(biāo)記,過(guò),過(guò)程對(duì)其父,節(jié),節(jié)點(diǎn)及先輩,節(jié),節(jié)點(diǎn)中的可,解,解節(jié)點(diǎn)進(jìn)行,標(biāo),標(biāo)記。如果,初,初始解節(jié)點(diǎn)S0能夠被,標(biāo),標(biāo)記為可解,節(jié),節(jié)點(diǎn)，就得,到,到

29、了解樹(shù)，,搜,搜索成功，,退,退出搜索過(guò),程,程；如果不,能,能確定S0,為,為可解節(jié)點(diǎn),，,，則從Open表中刪,去,去具有可解,先,先輩的節(jié)點(diǎn),；,；③轉(zhuǎn)第（2）,步,步。,二. 與/,或,或樹(shù)的廣度,優(yōu),優(yōu)先搜索,,（4）如果節(jié)點(diǎn)n,不,不可擴(kuò)展，,則,則做下列工,作,作：①標(biāo)記節(jié)點(diǎn)n,為,為不可解節(jié),點(diǎn),點(diǎn)；②應(yīng)用不可解,標(biāo),標(biāo)記過(guò)程對(duì),節(jié),節(jié)點(diǎn)n的先,輩,輩中不可解,的,的節(jié)點(diǎn)進(jìn)行,標(biāo),標(biāo)記。如果,初,初始解節(jié)點(diǎn)S0也被標(biāo),記,記為不可解,節(jié),節(jié)點(diǎn)，則搜,索,索失敗，表,明,明原始問(wèn)題,無(wú),無(wú)解，退出,搜,搜索過(guò)程；,如,如果不能確,定,定S0為不,可,可解節(jié)點(diǎn)，,則,則從Open表

30、中刪去,具,具有不可解,先,先輩的節(jié)點(diǎn),；,；③轉(zhuǎn)第（2）,步,步。,,例 ：,設(shè)有如下圖,所,所示的與/,或,或樹(shù)，節(jié)點(diǎn),按,按圖中所標(biāo),注,注的順序號(hào),進(jìn),進(jìn)行擴(kuò)展，,其,其中標(biāo)有t1、t2、t3的節(jié)點(diǎn),是,是終止節(jié)點(diǎn),，,，A 、B 、 C,為,為不可解的,端,端節(jié)點(diǎn)。,,與/或樹(shù)的廣度優(yōu)先搜索,1,2,3,A,4,t1,t3,C,B,t2,5,搜索過(guò)程為,：,（ 1）先擴(kuò)展1號(hào)節(jié)點(diǎn),，,，生成2號(hào)節(jié)點(diǎn)和3號(hào)節(jié)點(diǎn),，,，由 于這,兩,兩個(gè)子節(jié)點(diǎn),都,都不是終止,節(jié),節(jié)點(diǎn)，因此,接,接著擴(kuò)展2,號(hào),號(hào)節(jié)點(diǎn)。,（2）擴(kuò)展2號(hào)節(jié),點(diǎn),點(diǎn)，生成A,節(jié),節(jié)點(diǎn)和4號(hào),節(jié),節(jié)點(diǎn)。由于,這,這兩個(gè)子節(jié),

31、點(diǎn),點(diǎn)均不是終,止,止節(jié)點(diǎn)，因,此,此接著擴(kuò)展3號(hào)節(jié)點(diǎn),。,（3）擴(kuò)展3號(hào)節(jié),點(diǎn),點(diǎn)，生成t1節(jié)點(diǎn)和5,號(hào),號(hào)節(jié)點(diǎn)。由,于,于t1為終,止,止節(jié)點(diǎn)，則,標(biāo),標(biāo)記它為可,解,解節(jié)點(diǎn)，并,應(yīng),應(yīng)用可解標(biāo),記,記過(guò)程，對(duì),其,其先輩中的,可,可解節(jié)點(diǎn)進(jìn),行,行標(biāo)記，由,于,于t1的父,節(jié),節(jié)點(diǎn)是一個(gè),與,與節(jié)點(diǎn)，因,此,此不能確定3號(hào)節(jié)點(diǎn),是,是否可解。,（4）擴(kuò)展節(jié)點(diǎn)A,，,，由于A是,端,端節(jié)點(diǎn)，調(diào),用,用不可解標(biāo),記,記過(guò)程，由,于,于2號(hào)節(jié)點(diǎn),是,是或節(jié)點(diǎn)，,因,因此不能確,定,定2號(hào)節(jié)點(diǎn),是,是不可解節(jié),點(diǎn),點(diǎn)。,（5）擴(kuò)展4號(hào)節(jié),點(diǎn),點(diǎn)，生成t2節(jié)點(diǎn)和B,節(jié),節(jié)點(diǎn)。由于t2為終止,節(jié),節(jié)

32、點(diǎn)，則標(biāo),記,記它為可解,節(jié),節(jié)點(diǎn)，并應(yīng),用,用可解標(biāo)記,過(guò),過(guò)程，標(biāo)記4號(hào)節(jié)點(diǎn)為,可,可解節(jié)點(diǎn)，,標(biāo),標(biāo)記2號(hào)節(jié),點(diǎn),點(diǎn)為可解節(jié),點(diǎn),點(diǎn)，但不能,標(biāo),標(biāo)記1號(hào)節(jié),點(diǎn),點(diǎn)為可解節(jié),點(diǎn),點(diǎn)。,（6）擴(kuò)展5號(hào),節(jié),節(jié)點(diǎn)，生,成,成t3節(jié),點(diǎn),點(diǎn)和C節(jié),點(diǎn),點(diǎn)。由于t3為終,止,止節(jié)點(diǎn)，,標(biāo),標(biāo)記它為,可,可解節(jié)點(diǎn),，,，并應(yīng)用,可,可解標(biāo)記,過(guò),過(guò)程，標(biāo),記,記5號(hào)節(jié),點(diǎn),點(diǎn)為可解,節(jié),節(jié)點(diǎn)，標(biāo),記,記3號(hào)節(jié),點(diǎn),點(diǎn)為可解,節(jié),節(jié)點(diǎn)。標(biāo),記,記1號(hào)節(jié),點(diǎn),點(diǎn)為可解,節(jié),節(jié)點(diǎn)。,（7）搜索成功，得到由1、2、3、4、5號(hào)節(jié)點(diǎn),及,及t1、t2、t3節(jié)點(diǎn)構(gòu),成,成的解樹(shù),。,。該解樹(shù),如,如上圖中,的

33、,的粗線所,示,示。,,,,,,可以帶有,深,深度限制dm，其,搜,搜索算法,如,如下：（1）把初始節(jié),點(diǎn),點(diǎn)S0放,入,入 Open表,中,中；（2）把Open表的第,一,一個(gè)節(jié)點(diǎn),取,取出放入Closed表，,并,并記該節(jié),點(diǎn),點(diǎn)為n；（3）如果節(jié)點(diǎn)n的深度,等,等于dm,，,，則轉(zhuǎn)第,（,（5）步,的,的第①點(diǎn),；,；（4）如果節(jié)點(diǎn)n可擴(kuò)展,，,，則做下,列,列工作：①擴(kuò)展節(jié)點(diǎn)n，將,其,其子節(jié)點(diǎn),放,放入 Open表,的,的首部，,并,并為每一,個(gè),個(gè)子節(jié)點(diǎn),設(shè),設(shè)置指向,父,父節(jié)點(diǎn)的,指,指針；②考察這些,子,子節(jié)點(diǎn)中,是,是否有終,止,止節(jié)點(diǎn)。,若,若有，則,標(biāo),標(biāo)記這些,終,終

34、止節(jié)點(diǎn),為,為可解節(jié),點(diǎn),點(diǎn)，并用,可,可解標(biāo)記,過(guò),過(guò)程對(duì)其,父,父節(jié)點(diǎn)及,先,先輩節(jié)點(diǎn),中,中的可解,節(jié),節(jié)點(diǎn)進(jìn)行,標(biāo),標(biāo)記。如,果,果初始節(jié),點(diǎn),點(diǎn)S0能,夠,夠被標(biāo)記,為,為可解節(jié),點(diǎn),點(diǎn)，就得,到,到了解樹(shù),，,，搜索成,功,功，退出,搜,搜索過(guò)程,；,；如果不,能,能確定S0為可解,節(jié),節(jié)點(diǎn)，則,從,從Open表中刪,去,去具有可,解,解先輩的,節(jié),節(jié)點(diǎn)；③轉(zhuǎn)第（2,）,）步。,三. 與/或樹(shù)的,深,深度優(yōu)先,搜,搜索,,（5）如果節(jié)點(diǎn)n不可擴(kuò),展,展，則做,下,下列工作,：,：①標(biāo)記節(jié)點(diǎn)n為不可,解,解節(jié)點(diǎn)；②應(yīng)用不可,解,解標(biāo)記過(guò),程,程對(duì)節(jié)點(diǎn)n的先輩,中,中不可解,的,的節(jié)點(diǎn)

35、進(jìn),行,行標(biāo)記。,如,如果初始,節(jié),節(jié)點(diǎn)S0,也,也被標(biāo)記,為,為不可解,節(jié),節(jié)點(diǎn)，則,搜,搜索失敗,，,，表明原,始,始問(wèn)題無(wú),解,解，退出,搜,搜索過(guò)程,；,；如果不,能,能確定為,不,不可解節(jié),點(diǎn),點(diǎn)，則從Open表中,刪,刪去具有,不,不可解先,輩,輩的節(jié)點(diǎn),；,；③轉(zhuǎn)第（2,）,）步。,,與/或樹(shù)的深度優(yōu)先搜索,1,2,3,A,4,t1,t3,C,B,t2,5,例如，對(duì),上,上例所給,出,出的與／,或,或樹(shù)，若,按,按有界深,度,度優(yōu)先搜,索,索，且給,定,定dm=4，則其,擴(kuò),擴(kuò)展節(jié)點(diǎn),的,的順序?yàn)?：,：1,，,，3，5,，,，2，4,其,其解樹(shù),與,與上例相,同,同。,,與/或

36、樹(shù),的,的盲目搜,索,索是按確,定,定路線進(jìn),行,行的，當(dāng),要,要選擇一,個(gè),個(gè)節(jié)點(diǎn)進(jìn),行,行擴(kuò)展時(shí),，,，只是根,據(jù),據(jù)節(jié)點(diǎn)在,與,與/或樹(shù),中,中所處的,位,位置，而,沒(méi),沒(méi)有考慮,要,要付出的,代,代價(jià)，因,而,而求得的,解,解樹(shù)不一,定,定是代價(jià),最,最小的解,樹(shù),樹(shù)，即不,一,一定是最,優(yōu),優(yōu)解樹(shù)。,因,因此，需,要,要考慮與/或樹(shù)的,啟,啟發(fā)式搜,索,索。在討,論,論與／或,樹(shù),樹(shù)的啟發(fā),式,式搜索過(guò),程,程之前，,需,需要先討,論,論幾個(gè)有,關(guān),關(guān)的概念,。,。,一. 解,樹(shù),樹(shù)的代價(jià),與,與希望樹(shù),與／或樹(shù),的,的啟發(fā)式,搜,搜索過(guò)程,是,是一種利,用,用搜索過(guò),程,程所得到,

37、的,的啟發(fā)性,信,信息尋找,最,最優(yōu)解樹(shù),的,的過(guò)程。,對(duì),對(duì)搜索的,每,每一步，,算,算法都試,圖,圖找到一,個(gè),個(gè)最有希,望,望成為最,優(yōu),優(yōu)解樹(shù)的,子,子樹(shù)。最,優(yōu),優(yōu)解樹(shù)是,指,指代價(jià)最,小,小的那棵,解,解樹(shù)。,4.5,與,與/,或,或,樹(shù),樹(shù),的,的,啟,啟,發(fā),發(fā),式,式,搜,搜,索,索,,1,．,．,解,解,樹(shù),樹(shù),的,的,代,代,價(jià),價(jià)在,與,與/,或,或,樹(shù),樹(shù),的,的,啟,啟,發(fā),發(fā),式,式,搜,搜,索,索,過(guò),過(guò),程,程,中,中,，,，,解,解,樹(shù),樹(shù),的,的,代,代,價(jià),價(jià),可,可,按,按,如,如,下,下,規(guī),規(guī),則,則,計(jì),計(jì),算,算,：,：（1,）,）若n,為,為

38、,終,終,止,止,節(jié),節(jié),點(diǎn),點(diǎn),，,，,則,則,其,其,代,代,價(jià),價(jià)h,（,（n,）,）=0,。,。（2,）,）若n,為,為,或,或,節(jié),節(jié),點(diǎn),點(diǎn),，,，,且,且,子,子,節(jié),節(jié),點(diǎn),點(diǎn),為,為n1,，,，n2,，,，,…,…,，,，nk,，,，,則,則n,的,的,代,代,價(jià),價(jià),為,為h,（,（n,）,）=min{c,（,（n,，,，ni,）,）,＋,＋h,（,（ni,）,）}(1,≤,≤i,≤,≤k),其,中,中,，,，c,（,（n,，,，ni,）,）,是,是,節(jié),節(jié),點(diǎn),點(diǎn)n,到,到,其,其,子,子,節(jié),節(jié),點(diǎn),點(diǎn)ni,的,的,邊,邊,代,代,價(jià),價(jià),。,。,（3,）,）若n,為,

39、為,與,與,節(jié),節(jié),點(diǎn),點(diǎn),，,，,且,且,子,子,節(jié),節(jié),點(diǎn),點(diǎn),為,為n1,，,，n2,，,，,…,…,，,，nk,，,，,則,則n,的,的,代,代,價(jià),價(jià),可,可,用,用,和,和,代,代,價(jià),價(jià),法,法,或,或,最,最,大,大,代,代,價(jià),價(jià),法,法,。,。,若,若,用,用,和,和,代,代,價(jià),價(jià),法,法,，,，,則,則,其,其,計(jì),計(jì),算,算,公,公,式,式,為,為,：,：,h,（,（n,）,）=,Σ,Σ((c(n,，,，ni),＋,＋h(ni))i=1,2,,…,…,…,…,k,若,若,用,用,最,最,大,大,代,代,價(jià),價(jià),法,法,，,，,則,則,其,其,計(jì),計(jì),算,算,公,公,式

40、,式,為,為,：,：h,（,（n,）,）=max,｛,｛c,（,（n,，,，ni,）,）,＋,＋h,（,（ni,）,）,｝,｝(1,≤,≤i,≤,≤k)（4,）,）若n,是,是,端,端,節(jié),節(jié),點(diǎn),點(diǎn),，,，,但,但,又,又,不,不,是,是,終,終,止,止,節(jié),節(jié),點(diǎn),點(diǎn),，,，,則,則n,不,不,可,可,擴(kuò),擴(kuò),展,展,，,，,其,其,代,代,價(jià),價(jià),定,定,義,義,為,為h,（,（n,）,）=,∞,∞（5,）,）根,節(jié),節(jié),點(diǎn),點(diǎn),的,的,代,代,價(jià),價(jià),即,即,為,為,解,解,樹(shù),樹(shù),的,的,代,代,價(jià),價(jià),。,。,,例,：,：設(shè),右,右,圖,圖,是,是,一,一,棵,棵,與,與/,或,或

41、,樹(shù),樹(shù),，,，,其,其,中,中,包,包,括,括,兩,兩,棵,棵,解,解,樹(shù),樹(shù),，,，,左,左,邊,邊,的,的,解,解,樹(shù),樹(shù),由,由S0,、,、A,、,、t1,、,、C,及,及t3,組,組,成,成,；,；,右,右,邊,邊,的,的,解,解,樹(shù),樹(shù),由,由S0,、,、B,、,、t2,、,、D,及,及t4,組,組,成,成,。,。,在,在,此,此,與,與/,或,或,樹(shù),樹(shù),中,中,，,，t1,、,、t2,、,、t3,、,、t4,為,為,終,終,止,止,節(jié),節(jié),點(diǎn),點(diǎn),；,；E,、,、F,是,是,端,端,節(jié),節(jié),點(diǎn),點(diǎn),；,；,邊,邊,上,上,的,的,數(shù),數(shù),字,字,是,是,該,該,邊,邊,的,的,

42、代,代,價(jià),價(jià),。,。,請(qǐng),請(qǐng),計(jì),計(jì),算,算,解,解,樹(shù),樹(shù),的,的,代,代,價(jià),價(jià),。,。,S0,A,B,t1,C,t3,E,t2,D,t4,F,與／或樹(shù)的代價(jià),2,2,4,6,3,5,2,1,解：先計(jì)算左,邊,邊的解樹(shù),按,按和代,價(jià),價(jià)：h（S0）=2＋4＋6＋2=14,按,按最大代,價(jià),價(jià)：h（S0）=8＋2=10,再,再,計(jì),計(jì)算右邊的,解,解樹(shù),按,按和代價(jià)：h（S0,）,）= 1＋5＋ 3,＋,＋ 2=11,按,按最大代價(jià),：,：h（S0,）,）=6＋2=8,在,在本例,中,中，無(wú)論按,和,和代價(jià)還是,最,最大代價(jià)，,右,右邊的解樹(shù),都,都是最優(yōu)解,樹(shù),樹(shù)。但在有,些,些情況下

43、，,當(dāng),當(dāng)采用的代,價(jià),價(jià)法不同時(shí),，,，找到的最,優(yōu),優(yōu)解樹(shù)有可,能,能不同。,,2．希望樹(shù)為了找到最,優(yōu),優(yōu)解樹(shù)，搜,索,索過(guò)程的任,何,何時(shí)刻都應(yīng),該,該選擇那些,最,最有希望成,為,為最優(yōu)解樹(shù),一,一部分的節(jié),點(diǎn),點(diǎn)進(jìn)行擴(kuò)展,。,。由于這些,節(jié),節(jié)點(diǎn)及其父,節(jié),節(jié)點(diǎn)所構(gòu)成,的,的與/或樹(shù),最,最有可能成,為,為最優(yōu)解樹(shù),的,的一部分，,因,因此稱它為,希,希望解樹(shù)，,也,也簡(jiǎn)稱為希望樹(shù)。需要注意,，,，希望解樹(shù),是,是會(huì)隨搜索,過(guò),過(guò)程而不斷,變,變化的。,定義：希望解樹(shù)T,（,（1）初始,節(jié),節(jié)點(diǎn)S0在,希,希望樹(shù)T中,；,；,（,（2）如,果,果n是具有,子,子節(jié)點(diǎn)n1,，,，n2

44、，…,，,，nk的或節(jié)點(diǎn)，則n的某,個(gè),個(gè)子節(jié)點(diǎn)ni在希望樹(shù)T中的充分,必,必要條件是h,（,（n）=min {c（n，ni）＋ h,（,（ni）}1≤i≤k（3）如果n是與節(jié)點(diǎn)，則n的全,部,部子節(jié)點(diǎn)都,在,在希望樹(shù)T,中,中。,,與／或樹(shù)的,啟,啟發(fā)式搜索,需,需要不斷地,選,選擇、修正,希,希望樹(shù)，其,搜,搜索過(guò)程如,下,下：（1）把初始節(jié)點(diǎn)S0放入Open表中,，,，計(jì)算h（S0）；（2）計(jì)算希望樹(shù)T；（3）依次在Open表中取,出,出T的端節(jié),點(diǎn),點(diǎn)放入Closed表,，,，記節(jié)點(diǎn)為n；（4）如果節(jié)點(diǎn)n,為,為終止節(jié)點(diǎn),，,，則做下列,工,工作：①標(biāo)記節(jié)點(diǎn)n,為,為可解節(jié)點(diǎn),；,；②

45、在T上應(yīng)用,可,可解標(biāo)記過(guò),程,程，對(duì)n的,先,先輩節(jié)點(diǎn)中,的,的所有可解,節(jié),節(jié)點(diǎn)進(jìn)行標(biāo),記,記；③如果初始節(jié),點(diǎn),點(diǎn)S0能夠,被,被標(biāo)記為可,解,解節(jié)點(diǎn)，則T就是最優(yōu),解,解樹(shù)，成功,退,退出；④否則，從Open表中,刪,刪去具有可,解,解先輩的所,有,有節(jié)點(diǎn)；⑤轉(zhuǎn)第（2）,步,步。,二. 與/,或,或樹(shù)的啟發(fā),式,式搜索過(guò)程,,（5）如果節(jié)點(diǎn)n,不,不是終止節(jié),點(diǎn),點(diǎn)，但可擴(kuò),展,展，則做下,列,列工作：①擴(kuò)展節(jié)點(diǎn)n,，,，生成n的,所,所有子節(jié)點(diǎn),；,；②把這些子節(jié),點(diǎn),點(diǎn)都放入Open表,中,中，并為每,一,一個(gè)子節(jié)點(diǎn),設(shè),設(shè)置指向父,節(jié),節(jié)點(diǎn) n的,指,指針；③計(jì)算這些子,節(jié),節(jié)點(diǎn)

46、及其先,輩,輩節(jié)點(diǎn)的h,值,值；④轉(zhuǎn)第（2）,步,步。（6）如果節(jié)點(diǎn)n,不,不是終止節(jié),點(diǎn),點(diǎn)，且不可,擴(kuò),擴(kuò)展，則做,下,下列工作：①標(biāo)記節(jié)點(diǎn)n,為,為不可解節(jié),點(diǎn),點(diǎn)；②在T上應(yīng)用,不,不可解標(biāo)記,過(guò),過(guò)程，對(duì)n,的,的先輩節(jié)點(diǎn),中,中的所有不,可,可解節(jié)點(diǎn)進(jìn),行,行標(biāo)記；③如果初始節(jié),點(diǎn),點(diǎn)S0能夠,被,被標(biāo)記為不,可,可解節(jié)點(diǎn)，,則,則問(wèn)題無(wú)解,，,，失敗退出,；,；④否則，從Open,表,表中刪去具,有,有不可解先,輩,輩的所有節(jié),點(diǎn),點(diǎn)；⑤轉(zhuǎn)第,（,（2,）,）步,。,。,,例，,搜,搜索,過(guò),過(guò)程,每,每次,擴(kuò),擴(kuò)展,節(jié),節(jié)點(diǎn),時(shí),時(shí),都,都同,時(shí),時(shí)擴(kuò),展,展兩,層,層，,且,

47、且按,一,一層,或,或節(jié),點(diǎn),點(diǎn)、,一,一層,與,與節(jié),點(diǎn),點(diǎn)的,間,間隔,方,方式,進(jìn),進(jìn)行,擴(kuò),擴(kuò)展,。,。,設(shè)初,始,始節(jié),點(diǎn),點(diǎn)為S0,，,，對(duì)S0,擴(kuò),擴(kuò)展,后,后得,到,到的,與,與/,或,或樹(shù),如,如下,圖,圖所,示,示。,其,其中,，,，端,節(jié),節(jié)點(diǎn)B、C、E、F下,面,面的,數(shù),數(shù)字,是,是用,啟,啟發(fā),函,函數(shù),估,估算,出,出的h值,，,，節(jié),點(diǎn),點(diǎn)A,、,、D,旁,旁邊,的,的數(shù),字,字是,按,按和,代,代價(jià),法,法計(jì),算,算出,來(lái),來(lái)的,節(jié),節(jié)點(diǎn),代,代價(jià),。,。此,時(shí),時(shí)，S0,的,的右,子,子樹(shù),是,是當(dāng),前,前的,希,希望,樹(shù),樹(shù)，,下,下面,對(duì),對(duì)其,端,端節(jié)

48、,點(diǎn),點(diǎn)進(jìn),行,行擴(kuò),展,展。,S0,A,D,B,C,E,F,8,7,3,3,3,2,擴(kuò)展S0,后,后的,與,與／,或,或樹(shù),8,,擴(kuò)展,節(jié),節(jié)點(diǎn)E,，,，由,右,右子,樹(shù),樹(shù)求,出,出的h（S0,）,）=12,，,，而,由,由左,子,子樹(shù),求,求出,的,的h,（,（S0）=9,。,。故,當(dāng),當(dāng)前,的,的希,望,望樹(shù),應(yīng),應(yīng)改,為,為左,子,子樹(shù),。,。,對(duì)B,擴(kuò),擴(kuò)展,兩,兩層,。,。由,于,于H,和,和I,是,是可,解,解節(jié),點(diǎn),點(diǎn)，,調(diào),調(diào)用,可,可解,標(biāo),標(biāo)記,過(guò),過(guò)程,，,，得,節(jié),節(jié)點(diǎn)G、B也,為,為可,解,解節(jié),點(diǎn),點(diǎn)，,但,但不,能,能標(biāo),記,記S0為,可,可解,節(jié),節(jié)點(diǎn),，,

49、，須,繼,繼續(xù),擴(kuò),擴(kuò)展,。,。當(dāng),前,前的,希,希望,樹(shù),樹(shù)仍,然,然是,左,左子,樹(shù),樹(shù)。,對(duì),對(duì)C,擴(kuò),擴(kuò)展,。,。擴(kuò),展,展兩,層,層后,得,得到,的,的與,／,／或,樹(shù),樹(shù)如,圖,圖3,所,所示,。,。,S0,A,D,B,C,E,F,8,3,3,2,,,,,,,3,2,2,2,7,7,6,11,9,圖1,擴(kuò),擴(kuò)展E后,的,的與,／,／或,樹(shù),樹(shù),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,擴(kuò),擴(kuò),展,展B,后,后的,與,與／,或,或樹(shù),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 擴(kuò)展C后的與／或樹(shù),9,由于N和P是,可,可解,節(jié),節(jié)點(diǎn),，,，調(diào),用,用可,解,解標(biāo),記,記過(guò),程,程，,得,得節(jié),點(diǎn),點(diǎn)M,、,、C,、,、A,也,也為,可,可解,節(jié),節(jié)點(diǎn),，,，進(jìn),而,而S0為,可,可解,節(jié),節(jié)點(diǎn),。,。求,出,出了,代,代價(jià),最,最小,的,的解,樹(shù),樹(shù)，,即,即最,優(yōu),優(yōu)解,樹(shù),樹(shù)，,如,如圖,中,中粗,線,線所,示,示。,按,按和,代,代價(jià),法,法，,該,該最,優(yōu),優(yōu)解,樹(shù),樹(shù)的,代,代價(jià),為,為9,。,。,,博弈是一,類

51、,類富,有,有智,能,能行,為,為的,競(jìng),競(jìng)爭(zhēng),活,活動(dòng),，,，如,下,下棋,、,、打,牌,牌、,戰(zhàn),戰(zhàn)爭(zhēng),等,等。,博,博弈,可,可分,為,為雙人,完,完備,信,信息,博,博弈和機(jī)遇,性,性博,弈,弈。所,謂,謂雙人,完,完備,信,信息,博,博弈，就,是,是兩,位,位選,手,手對(duì),壘,壘，,輪,輪流,走,走步,，,，每,一,一方,不,不僅,知,知道,對(duì),對(duì)方,已,已經(jīng),走,走過(guò),的,的棋,步,步，,而,而且,還,還能,估,估計(jì),出,出對(duì),方,方未,來(lái),來(lái)的,走,走步,。,。對(duì),弈,弈的,結(jié),結(jié)果,是,是一,方,方贏,，,，另,一,一方,輸,輸；,或,或者,雙,雙方,和,和局,。,。所,謂,謂

52、機(jī)遇,性,性博,弈,弈，是,指,指存,在,在不,可,可預(yù),測(cè),測(cè)性,的,的博,弈,弈，,例,例如,擲,擲幣,等,等。,對(duì),對(duì)機(jī),遇,遇性,博,博弈,，,，由,于,于不,具,具備,完,完備,信,信息,，,，因,此,此不,作,作討,論,論。,假設(shè),博,博弈,的,的一,方,方為MAX，另,一,一方,為,為MIN。在,博,博弈,過(guò),過(guò)程,的,的每,一,一步,，,，可,供,供MAX,和,和MIN,選,選擇,的,的行,動(dòng),動(dòng)方,案,案都,可,可能,有,有多,種,種。,從,從MAX,方,方的,觀,觀點(diǎn),看,看，,可,可供,自,自己,選,選擇,的,的那,些,些行,動(dòng),動(dòng)方,案,案之,間,間是,“,“或”的,關(guān)

53、,關(guān)系,，,，選,擇,擇哪,個(gè),個(gè)方,案,案完,全,全是,由,由自,己,己決,定,定的,；,；而,對(duì),對(duì)那,些,些可,供,供MIN,選,選擇,的,的行,動(dòng),動(dòng)方,案,案之,間,間則,是,是“與”的,關(guān),關(guān)系,，,，主,動(dòng),動(dòng)權(quán),掌,掌握,在,在MIN,的,的手,里,里，,任,任何,一,一個(gè),方,方案,都,都有,可,可能,被,被MIN,選,選中,，,，MAX,必,必須,防,防止,那,那種,對(duì),對(duì)自,己,己最,為,為不,利,利的,情,情況,的,的發(fā),生,生。,4.6,博,博弈,樹(shù),樹(shù)的,啟,啟發(fā),式,式搜,索,索,一.,概,概,述,述,,若把,雙,雙人,完,完備,信,信息,博,博弈,過(guò),過(guò)程,用,

54、用圖,表,表示,出,出來(lái),，,，就,可,可得,到,到一,棵,棵與/或,樹(shù),樹(shù)，,這,這種,與,與/,或,或樹(shù),被,被稱,為,為博弈,樹(shù),樹(shù)。在,博,博弈,樹(shù),樹(shù)中,，,，那,些,些下,一,一步,該,該MAX,走,走步,的,的節(jié),點(diǎn),點(diǎn)稱,為,為MAX節(jié),點(diǎn),點(diǎn)，而,下,下一,步,步該MIN走,步,步的,節(jié),節(jié)點(diǎn),稱,稱為MIN節(jié),點(diǎn),點(diǎn)。博,弈,弈樹(shù),具,具有,如,如下,特,特點(diǎn),：,：,（l,）,）博,弈,弈的,初,初始,狀,狀態(tài),是,是初,始,始節(jié),點(diǎn),點(diǎn)；,（2,）,）博,弈,弈樹(shù),中,中的,“,“或,”,”節(jié),點(diǎn),點(diǎn)和,“,“與,”,”節(jié),點(diǎn),點(diǎn)是,逐,逐層,交,交替,出,出現(xiàn),的,的

55、；,（3,）,）整,個(gè),個(gè)博,弈,弈過(guò),程,程始,終,終站,在,在某,一,一方,的,的立,場(chǎng),場(chǎng)上,，,,對(duì)簡(jiǎn),單,單的,博,博弈,問(wèn),問(wèn)題,，,，可,以,以生,成,成整,個(gè),個(gè)博,弈,弈樹(shù),，,，找,到,到必,勝,勝的,策,策略,。,。但,對(duì),對(duì)于,復(fù),復(fù)雜,的,的博,弈,弈，,如,如國(guó),際,際象,棋,棋，,大,大約,有,有10,120,個(gè)節(jié)點(diǎn),，,，要生,成,成整個(gè),搜,搜索樹(shù),是,是不可,能,能的。,一,一種可,行,行的方,法,法是用,當(dāng),當(dāng)前正,在,在考察,的,的節(jié)點(diǎn),生,生成一,棵,棵部分博,弈,弈樹(shù)，由于,該,該博弈,樹(shù),樹(shù)的葉,二.,極,極大極,小,小過(guò)程,為了計(jì),算,算非葉,節(jié)

56、,節(jié)點(diǎn)的,值,值，必,須,須從葉,節(jié),節(jié)點(diǎn)向,上,上倒推,。,。對(duì)于MAX,節(jié),節(jié)點(diǎn)，,由,由于MAX,方,方總是,選,選擇估,值,值最大,的,的走步,，,，因此,，,，MAX節(jié)點(diǎn),的,的倒推,值,值應(yīng)該,取,取其后,繼,繼節(jié)點(diǎn),估,估值的最大值。對(duì)于MIN,節(jié),節(jié)點(diǎn)，,由,由于MIN方,總,總是選,擇,擇使估,值,值最小,的,的走步,，,，因此MIN,節(jié),節(jié)點(diǎn)的,倒,倒推值,應(yīng),應(yīng)取其,后,后繼節(jié),點(diǎn),點(diǎn)估值,的,的最小值。這樣,一,一步一,步,步的計(jì),算,算倒推,值,值，直,至,至求出,初,初始節(jié),點(diǎn),點(diǎn)的倒,推,推值為,止,止。這,一,一過(guò)程,稱,稱為極大極,小,小過(guò)程。,,例：一字棋,

57、游,游戲。,設(shè),設(shè)有一,個(gè),個(gè)三行,三,三列的,棋,棋盤，,如,如下圖,所,所示，,兩,兩個(gè)棋,手,手輪流,走,走步，,每,每個(gè)棋,手,手走步,時(shí),時(shí)往空,格,格上擺,一,一個(gè)自,己,己的棋,子,子，誰(shuí),先,先使自,己,己的棋,子,子成三,子,子一線,為,為贏。,設(shè),設(shè)MAX方的,棋,棋子用×標(biāo)記，MIN,方,一字棋棋盤,若P對(duì)MAX,、,、MIN都是,勝,勝負(fù)未,定,定局，,則,則,e（P,）,）=e（+P）－e（-P）,其,其中，e（+P）表,示,示棋局P上,有,有可能,使,使×成三子,一,一線的,數(shù),數(shù)目；e（-P）表,示,示棋局P上,有,有可能,使,使○成三子,一,一線的,數(shù),數(shù)目。,

58、,例如，,對(duì),對(duì)圖1,所,所示的,棋,棋局有,估,估價(jià)函,數(shù),數(shù)值e（P）＝6-4,＝,＝2,圖1 棋局1,在搜索,過(guò),過(guò)程中,，,，具有,對(duì),對(duì)稱性,的,的棋局,認(rèn),認(rèn)為是,同,同一棋,局,局。例,如,如，圖2所示,的,的棋局,可,可以認(rèn),為,為是同,一,一個(gè)棋,局,局，這,圖2 對(duì)稱棋局的例子,,圖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,招,招數(shù)),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,,對(duì)于一個(gè),或,節(jié)點(diǎn)來(lái)說(shuō)，它取當(dāng)前子節(jié)點(diǎn)中的最大倒推值作為它倒推

61、值的下界，稱該值為,α,,值。,,α-β,剪,剪枝的,方,方法如,下,下：（1）MAX,節(jié),節(jié)點(diǎn)的,α,α值為,當(dāng),當(dāng)前子,節(jié),節(jié)點(diǎn)的,最,最大倒,推,推值；（2）MIN,節(jié),節(jié)點(diǎn),的,的β值,為,為當(dāng)前,子,子節(jié)點(diǎn),的,的最小,倒,倒推值,；,；（3）α-β,剪,剪枝,的,的規(guī)則,如,如下：①任何MAX節(jié),點(diǎn),點(diǎn)n的,α,α值大,于,于或等,于,于它先,輩,輩節(jié)點(diǎn),的,的β值,，,，則n,以,以下的,分,分枝可,停,停止搜,索,索，并,令,令節(jié)點(diǎn)n的倒,推,推值為,α,α。,這,這種剪,枝,枝稱為β剪枝。②任何MIN節(jié),點(diǎn),點(diǎn)n的,β,β值小,于,于或等,于,于它先,輩,輩節(jié)點(diǎn),的,的α值,

62、，,，則n,以,以下的,分,分枝可,停,停止搜,索,索，并,令,令節(jié)點(diǎ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,,,,,,,,,,,＊,＊,＊,＊,＊,＊,跳棋程序,的,的學(xué)習(xí)策,略,略,,?-?,剪枝算法,在極大極,小,小值算法,基,基礎(chǔ)上增,加,加了剪枝,功,功能，即,在,在返回值,基,基礎(chǔ)上增,加,加了判斷,,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,,分析產(chǎn)生,式,式正向推,理,理算法，,可,可以看出,，,，它們只,能,能用于解,決,決邏輯推,理,理性問(wèn)題,。,。若要求,解,解規(guī)劃性,問(wèn),問(wèn)題則還,需,需要：,,(2)若要回溯，則還需保存與每個(gè)動(dòng)態(tài)數(shù)據(jù)庫(kù)狀態(tài)對(duì)應(yīng)的可用規(guī)則集。因?yàn)閯?dòng)態(tài)數(shù)據(jù)庫(kù)狀態(tài)與可用規(guī)則集實(shí)際是一一對(duì)應(yīng)的。,(3)要進(jìn)行樹(shù)式搜索，還需設(shè)置一個(gè)OPEN表，以進(jìn)行新生動(dòng)態(tài)數(shù)據(jù)庫(kù)的狀態(tài)保存和當(dāng)前動(dòng)態(tài)數(shù)據(jù)庫(kù)狀態(tài)的切換。,(4)還要考慮一條規(guī)則是否只允許執(zhí)行一次。若是，則要對(duì)已執(zhí)行了的規(guī)則進(jìn)行標(biāo)記。,成功退出,失敗退出,把初始數(shù)據(jù)放入綜合數(shù)據(jù)庫(kù),綜合數(shù)