人工智能基礎(chǔ)與應(yīng)用第四章

第4章搜索搜索是人工智能的一個(gè)基本問題，是推理不可分割的一部分。一個(gè)問題的求解過程就是搜索過程，所以搜索實(shí)際上是求解問題的一種方法。4.1搜索概述4.1.1搜索的基本概念人類的思維過程，可以看作是一個(gè)搜索的過程。我們曾經(jīng)遇到過很多有趣的智力游戲問題，比如傳教士和野人問題：有三傳教士和三個(gè)野人過河，河岸上只有一條能裝下兩個(gè)人的船，在河的任何一方或者船上，如果野人的人數(shù)大于傳教士的人數(shù)，那么傳教士就會有危險(xiǎn)。你能不能找出一種安全的渡河方法呢？如果要作這個(gè)游戲，在每一次渡河之后，都會有幾種渡河方案供你選擇，究竟哪種方案才有利于在滿足題目所規(guī)定的約束條件下順利過河呢？人工智能要解決的問題大多數(shù)是結(jié)構(gòu)不良或者非結(jié)構(gòu)的問題，對這樣的問題一般不存在成熟的求解算法，而只能利用已有的知識一步步地摸索著前進(jìn)。在這個(gè)過程中，存在著如何尋找一條推理路線，使得付出的代價(jià)盡可能地少，而問題又能夠得到解決。我們稱尋找這樣路線的過程為搜索。4.1.2搜索的分類根據(jù)在問題求解過程中是否運(yùn)用啟發(fā)性知識，搜索可分為盲目搜索和啟發(fā)式搜索。盲目搜索是按預(yù)定的控制策略進(jìn)行，在搜索的過程中所獲得的信息不用來改進(jìn)控制策略的一種搜索。由于搜索總是按預(yù)先規(guī)定的路線進(jìn)行，沒有考慮問題本身的特性，這種方法缺乏對問題求解的針對性，需要進(jìn)行全方位的搜索，而沒有選擇最優(yōu)的搜索途徑，因此，這種搜索具有盲目性，效率較低。啟發(fā)式搜索是在搜索中加入了與問題有關(guān)的啟發(fā)式信息，用來指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問題的求解過程，并找到最優(yōu)解。4.2狀態(tài)空間搜索狀態(tài)空間法狀態(tài)空間法的基本思想：用“狀態(tài)”和“操作”來表示或求解問題。問題是用“狀態(tài)”和“操作”來表示，問題求解過程是用“狀態(tài)空間”來表示的。狀態(tài)是表示問題求解過程中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu)，它可形式地表示為：Sk={Sk0,Sk1,……}。在這種狀態(tài)中，當(dāng)對每一個(gè)分量都給予確定的值時(shí)，就得到了一個(gè)具體的狀態(tài)。操作，也稱算符，它是把問題一個(gè)狀態(tài)變換為另一種狀態(tài)的手段。操作可理解為狀態(tài)集合上的一個(gè)函數(shù)，它描述了狀態(tài)之間的關(guān)系。狀態(tài)空間用來描述一個(gè)問題的全部狀態(tài)以及這些狀態(tài)之間的相互關(guān)系。狀態(tài)空間法基本過程：首先為問題選擇適當(dāng)?shù)摹盃顟B(tài)”及“操作”的形式化描述方法；然后從某個(gè)初始狀態(tài)出發(fā)，每次使用一個(gè)“操作”，遞增的建立起操作序列，直到達(dá)到目標(biāo)狀態(tài)為止；此時(shí)，由初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是該問題的一個(gè)解。八數(shù)碼難題在3*3的方格棋盤上，分別放置了標(biāo)有數(shù)字1、2、3、4、5、6、7、8的八張牌，初始狀態(tài)S0,目標(biāo)狀態(tài)為Sg?？梢允褂玫牟僮饔校嚎崭褡笠?、上移、下移、右移狀態(tài)任一時(shí)刻,綜合數(shù)據(jù)庫的情況;237

51486{A，B，C，D} （c,a,b,0,0）狀態(tài)空間狀態(tài)空間所有可能的狀態(tài)的全體.237

51486586

12743124

65783……狀態(tài)轉(zhuǎn)移初始狀態(tài)目標(biāo)狀態(tài)狀態(tài)轉(zhuǎn)移規(guī)則237

51486237

45186搜索(search)路徑狀態(tài)序列搜索尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑;S0Sg搜索問題狀態(tài)空間237

5148612384765搜索不是檢索237

5148612384765搜索與檢索的區(qū)別狀態(tài)是否動態(tài)生成;檢索:靜態(tài);在數(shù)據(jù)庫中檢索某人的紀(jì)錄;搜索:動態(tài)生成;下棋難點(diǎn)237

5148612384765狀態(tài)空間搜索步驟狀態(tài)空間搜索實(shí)際上就是對有向圖的搜索。先把問題的初始狀態(tài)當(dāng)作當(dāng)前擴(kuò)展節(jié)點(diǎn)對其進(jìn)行擴(kuò)展，生成一組子節(jié)點(diǎn)，然后檢查問題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。若出現(xiàn)，則搜索成功，找到了該問題的解；若沒有出現(xiàn)，則按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個(gè)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)。重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或沒有可供擴(kuò)展的節(jié)點(diǎn)為止。狀態(tài)空間搜索算法（準(zhǔn)備）若要討論狀態(tài)空間搜索的一般算法，需要：Open表和Closed表這樣兩個(gè)數(shù)據(jù)結(jié)構(gòu)。其中，Open表用于存放還沒有擴(kuò)展的節(jié)點(diǎn)，因此，Open表稱為未擴(kuò)展的節(jié)點(diǎn)表。

Closed表用于存放已經(jīng)擴(kuò)展或?qū)⒁獢U(kuò)展的節(jié)點(diǎn)，因此，Closed稱為已擴(kuò)展的節(jié)點(diǎn)表。用S0表示問題的初始狀態(tài)，G表示搜索過程所得到的搜索圖，M表示當(dāng)前擴(kuò)展節(jié)點(diǎn)新生成的且不為自己先輩的子節(jié)點(diǎn)集。算法(simpleversion)1．建立一個(gè)只有起始節(jié)點(diǎn)S0組成的圖G,把S0放到OPEN表中；2．建立一個(gè)CLOSED表，置為空；3．While(!NULL(OPEN))a)從OPEN表中取出（并刪除）第一個(gè)節(jié)點(diǎn)n放入

CLOSED表。

b)如果n是目標(biāo)節(jié)點(diǎn)，成功結(jié)束；

c)擴(kuò)展節(jié)點(diǎn)n，把n的后繼加入G中；

d)把n的后繼加入OPEN表中,并建立它們到n的指針；

e)

對OPEN表中的節(jié)點(diǎn)排序；4．返回FAIL；例子SOPENCLOSE{S}{}123{}{S}{1,2,3}{S}{2,1,3}{S}45{1,3}{S,2}{1,3,4,5}{S,2}{3,1,4,5}{S,2}{1,4,5}{S,2,3}6{1,4,5,6}{S,2,3}算法4.1狀態(tài)空間圖的一般搜索算法：1、把初始節(jié)點(diǎn)S0放入Open表中，并建立目前僅包含S0的圖G；2、檢查是否為空，若為空，則問題無解，失敗退出；3、把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表中，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n；4、考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，若是則得到問題的解，成功退出；5、擴(kuò)展節(jié)點(diǎn)n,生成一組子節(jié)點(diǎn)。把這組節(jié)點(diǎn)中不為節(jié)點(diǎn)n先輩的子節(jié)點(diǎn)記入集合M,并把這些節(jié)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)加入G中。6、針對中子節(jié)點(diǎn)的不同情況，分別處理如下（1-3）：對那些沒有在G中出現(xiàn)過的M成員設(shè)置一個(gè)指向其父節(jié)點(diǎn)的指針，并把它放入Open表中。對那些原來已在G中出現(xiàn)過，但還沒有被擴(kuò)展的M成員，確定是否需要修改指向其父節(jié)點(diǎn)的指針。對原來已在G中出現(xiàn)過，并已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。7、按某種策略對Open表中節(jié)點(diǎn)排序。8、轉(zhuǎn)第2步。示例如下：2S1345{1,2,3}{S}{3,1,2}

{S}OPENCLOSE{S}{}{4,5,1,2}

{S,3}67{6,7,5,1,2}

{S,3,4}89{8,9,7,5,1,2}

{S,3,4,6}{10,11,9,7,5,1,2}

{S,3,4,6,8}10111213{13,10,11,9,7,5,2}

{S,3,4,6,8,1,12}14{14,10,11,9,7,5,2}

{S,3,4,6,8,1,12,13}2S13{1,2,3}{S}{3,1,2}

{S}OPENCLOSE{S}{}245{4,5,1,2}

{S,3}67{6,7,5,1,2}

{S,3,4}89{8,9,7,5,1,2}

{S,3,4,6}{10,11,9,7,5,1,2}

{S,3,4,6,8}10111213{13,10,11,9,7,5,2}

{S,3,4,6,8,1,12}14OPEN表中的節(jié)點(diǎn)修改指針2S13{1,2,3}{S}{3,1,2}

{S}OPENCLOSE{S}{}245{4,5,1,2}

{S,3}67{6,7,5,1,2}

{S,3,4}89{8,9,7,5,1,2}

{S,3,4,6}{10,11,9,7,5,1,2}

{S,3,4,6,8}10111213{13,10,11,9,7,5,2}

{S,3,4,6,8,1,12}14{13,10,11,9,7,5}

{S,3,4,6,8,1,12,2}2S13{1,2,3}{S}{3,1,2}

{S}OPENCLOSE{S}{}245{4,5,1,2}

{S,3}67{6,7,5,1,2}

{S,3,4}89{8,9,7,5,1,2}

{S,3,4,6}{10,11,9,7,5,1,2}

{S,3,4,6,8}10111213{13,10,11,9,7,5,2}

{S,3,4,6,8,1,12}14{13,10,11,9,7,5}

{S,3,4,6,8,1,12,2}CLOSED表中的節(jié)點(diǎn)修改指針2S13{1,2,3}{S}{3,1,2}

{S}OPENCLOSE{S}{}245{4,5,1,2}

{S,3}67{6,7,5,1,2}

{S,3,4}89{8,9,7,5,1,2}

{S,3,4,6}{10,11,9,7,5,1,2}

{S,3,4,6,8}10111213{13,10,11,9,7,5,2}

{S,3,4,6,8,1,12}14{13,10,11,9,7,5}

{S,3,4,6,8,1,12,2}CLOSED表中節(jié)點(diǎn)(8)的后裔(10)修改指針?biāo)惴ㄕf明各種搜索策略的主要區(qū)別在于對Open表中節(jié)點(diǎn)排序的不同；一旦被考察的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)時(shí),算法成功結(jié)束;

算法結(jié)束后，將生成一個(gè)圖G，稱為搜索圖。同時(shí)由于每個(gè)節(jié)點(diǎn)都有一個(gè)指針指向父節(jié)點(diǎn)，這些指針指向的節(jié)點(diǎn)構(gòu)成G的一個(gè)支撐樹，稱為搜索樹。

修改指針:找最優(yōu)解；檢查新產(chǎn)生的節(jié)點(diǎn)以前是否產(chǎn)生過，計(jì)算量較大;2S134567891011121314搜索圖2S1324567891011121314搜索樹4.2.1狀態(tài)空間盲目搜索無須重新安排OPEN表的搜索叫做無信息搜索或盲目搜索，它包括寬度優(yōu)先搜索、深度優(yōu)先搜索和等代價(jià)搜索等。盲目搜索只適用于求解比較簡單的問題。一、寬度優(yōu)先搜索寬度優(yōu)先搜索(breadth-firstsearch)又稱為廣度優(yōu)先搜索，是一種盲目搜索策略。其基本思想是，從初始節(jié)點(diǎn)開始，向下逐層對節(jié)點(diǎn)進(jìn)行依次擴(kuò)展，并考察它是否為目標(biāo)節(jié)點(diǎn)，在對下層節(jié)點(diǎn)進(jìn)行擴(kuò)展（或搜索）之前，必須完成對當(dāng)前層的所有節(jié)點(diǎn)的擴(kuò)展。在搜索過程中，未擴(kuò)展節(jié)點(diǎn)表OPEN中的節(jié)點(diǎn)排序準(zhǔn)則是：先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排在后面。二、深度優(yōu)先搜索另一種盲目(無信息)搜索叫做深度優(yōu)先搜索(depth-firstsearch)。在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)。深度相等的節(jié)點(diǎn)可以任意排列。我們定義節(jié)點(diǎn)的深度如下：(1)起始節(jié)點(diǎn)(即根節(jié)點(diǎn))的深度為0。(2)任何其他節(jié)點(diǎn)的深度等于其父輩節(jié)點(diǎn)的深度加1。三、等代價(jià)搜索在等代價(jià)搜索算法中，把從節(jié)點(diǎn)i到其后繼節(jié)點(diǎn)j的連接弧線代價(jià)記為c(i,j)，把從起始節(jié)點(diǎn)s到任一節(jié)點(diǎn)i的路徑代價(jià)記為g(i)。在搜索樹上，假設(shè)g(i)也是從起始節(jié)點(diǎn)s到節(jié)點(diǎn)i的最少代價(jià)路徑上的代價(jià)，因?yàn)樗俏┮坏穆窂?。等代價(jià)搜索方法以g(i)的遞增順序擴(kuò)展其節(jié)點(diǎn)，等代價(jià)搜索方法：

(1)把起始節(jié)點(diǎn)s放到未擴(kuò)展節(jié)點(diǎn)表OPEN中。如果此起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解；否則令g(s)=0。

(2)如果OPEN是個(gè)空表，則沒有解而失敗退出。

(3)從OPEN表中選擇一個(gè)節(jié)點(diǎn)i，使其g(i)為最小。如果有幾個(gè)節(jié)點(diǎn)都合格，那么就要選擇一個(gè)目標(biāo)節(jié)點(diǎn)作為節(jié)點(diǎn)i(要是有目標(biāo)節(jié)點(diǎn)的話)；否則，就從中選一個(gè)作為節(jié)點(diǎn)i。把節(jié)點(diǎn)i從OPEN表移至擴(kuò)展節(jié)點(diǎn)表CLOSED中。

(4)如果節(jié)點(diǎn)i為目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解。

(5)擴(kuò)展節(jié)點(diǎn)i。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向步驟(2)。

(6)對于節(jié)點(diǎn)i的每個(gè)后繼節(jié)點(diǎn)j，計(jì)算g(j)=g(i)+c(i,j)，并把所有后繼節(jié)點(diǎn)j放進(jìn)OPEN表。提供回到節(jié)點(diǎn)i的指針。

(7)轉(zhuǎn)向步驟(2)。4.2.2狀態(tài)空間啟發(fā)式搜索前面我們討論的各種搜索策略的一個(gè)共同的特點(diǎn)就是它們的搜索路線是事先決定好的，沒有利用被求解問題的任何特性信息，在決定要擴(kuò)展的節(jié)點(diǎn)時(shí)，沒有考慮該節(jié)點(diǎn)到底是否可能出現(xiàn)在解的路徑上，也沒有考慮它是否有利于問題的求解以及所求的解是否為最優(yōu)解，這樣的搜索策略具有很大的盲目性。如果能夠找到一種方法用于排列待擴(kuò)展節(jié)點(diǎn)的順序，即選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展，那么，搜索效率將會大為提高。在許多情況下，能夠通過檢測來確定合理的順序。本節(jié)所介紹的搜索方法就是優(yōu)先考慮這類檢測，稱這類搜索為啟發(fā)式搜索(heuristicallysearch)或有信息搜索(informedsearch)。一、啟發(fā)式搜索策略和估價(jià)函數(shù)我們用f(n)表示節(jié)點(diǎn)n的估價(jià)函數(shù)，則f(n)可以為任意函數(shù)。如f(n)可以表示節(jié)點(diǎn)n處于最佳路徑的概率，也可以表示節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的距離。一般來說，估價(jià)一個(gè)節(jié)點(diǎn)價(jià)值必須考慮兩方面的因素：已經(jīng)付出的代價(jià)和將要付出的代價(jià)。二、最佳優(yōu)先搜索最佳優(yōu)先搜索(best-firstsearch)又稱為有序搜索(orderedsearch)，它總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)，而這種最有希望的節(jié)點(diǎn)是按估價(jià)函數(shù)f(n)的值來挑選的，一般估價(jià)函數(shù)的值越小，它的希望程度就越大。根據(jù)習(xí)慣，我們把OPEN表上的節(jié)點(diǎn)按照它們估價(jià)函數(shù)值的遞增順序排列。根據(jù)推測，某個(gè)具有低的估價(jià)值的節(jié)點(diǎn)較有可能處在最佳路徑上。最佳優(yōu)先搜索算法：（1）把起始節(jié)點(diǎn)s放到OPEN表中，計(jì)算其估價(jià)值f(s)。（2）如果OPEN是個(gè)空表，則失敗退出，無解。（3）從OPEN表中選擇一個(gè)f值最小的節(jié)點(diǎn)i。結(jié)果有幾個(gè)節(jié)點(diǎn)合格，當(dāng)其中有一個(gè)為目標(biāo)節(jié)點(diǎn)時(shí)，則選擇此目標(biāo)節(jié)點(diǎn)，否則就選擇其中任一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)i。（4）把節(jié)點(diǎn)i從OPEN表中移出，并把它放入CLOSED表中。（5）如果i是個(gè)目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個(gè)解。（6）擴(kuò)展節(jié)點(diǎn)i，生成其全部后繼節(jié)點(diǎn)。對于i的每一個(gè)后繼節(jié)點(diǎn)j：(a)計(jì)算f(j)。(b)如果j既不在OPEN表中，也不在CLOSED表中，則用估價(jià)函數(shù)f把它添入OPEN表。從j加一指向其父輩節(jié)點(diǎn)i的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑。(c)如果j已在OPEN表或CLOSED表上，則比較剛剛對j計(jì)算過的f值和前面計(jì)算過的該節(jié)點(diǎn)在表中的f值。如果新的f值較小，則(i)以此新值取代舊值。(ii)從j指向i，而不是指向它的父輩節(jié)點(diǎn)。(iii)如果節(jié)點(diǎn)j在CLOSED表中，則把它移回OPEN表。（7）轉(zhuǎn)向（2），即GOTO（2）。三、A*算法g*(n)：從S0到n的最小代價(jià)值值h*(n)：從n到Sg的最小代價(jià)值f*(n)=g*(n)+h*(n)：從S0經(jīng)過n到Sg的最小代價(jià)值值g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計(jì)值對A算法（全局擇優(yōu)）的g(n)、h(n)分別提出如下限制：g(n)是對g*(n)的估計(jì)，且g(n)>0;h(n)是h*(n)的下界，即對任意節(jié)點(diǎn)n均有h(n)≤h*(n)。則稱得到的算法為A*算法。4.3與/或樹搜索與/或樹是不同于狀態(tài)空間法的另外一種用于表示問題及求解過程的形式化方法，通常用于表示比較復(fù)雜的問題求解。與/或樹搜索的目標(biāo)是尋找解樹，從而求得原始問題的解。如果在搜索的某一時(shí)刻，通過可解標(biāo)示過程可確定初始節(jié)點(diǎn)是可解的，則由初始節(jié)點(diǎn)及其下屬的可解節(jié)點(diǎn)就構(gòu)成了解樹。如果在某時(shí)刻被選為擴(kuò)展的解點(diǎn)不可擴(kuò)展，并且它不是終止節(jié)點(diǎn)，則此節(jié)點(diǎn)就是不可解節(jié)點(diǎn)。此時(shí)可應(yīng)用不可解標(biāo)示過程確定初始節(jié)點(diǎn)是否為不可解節(jié)點(diǎn)，如果可以肯定初始節(jié)點(diǎn)是不可解節(jié)點(diǎn)，則搜索失敗，否則繼續(xù)擴(kuò)展節(jié)點(diǎn)。4.3.1與/或樹的盲目搜索對于與/或樹的盲目搜索，通常有寬度優(yōu)先搜索、深度優(yōu)先搜索和有界深度優(yōu)先搜索等。因篇幅所限，我們這里僅介紹與/或樹的寬度優(yōu)先搜索算法。與/或樹的寬度優(yōu)先搜索1、把初始節(jié)點(diǎn)S0放入Open表中；2、把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表中，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n；3、若節(jié)點(diǎn)n可擴(kuò)展，則做下列工作：①擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的尾部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；②考察這些子節(jié)點(diǎn)是否有終止節(jié)點(diǎn)。若有，則標(biāo)記這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn)，并用可解標(biāo)記過程對其父節(jié)點(diǎn)或先輩節(jié)點(diǎn)中可解節(jié)點(diǎn)進(jìn)行標(biāo)記。如初始節(jié)點(diǎn)S0被標(biāo)記為可解節(jié)點(diǎn)，得到解樹，成功退出。如不能確定為S0可解節(jié)點(diǎn)，則從Open表中刪除具有可解先輩的節(jié)點(diǎn)；③轉(zhuǎn)第2步4、如果節(jié)點(diǎn)不可擴(kuò)展，則做下列工作：①標(biāo)記節(jié)點(diǎn)n為不可解節(jié)點(diǎn)；②用不可解標(biāo)記過程對節(jié)點(diǎn)n的先輩節(jié)點(diǎn)中不可解節(jié)點(diǎn)進(jìn)行標(biāo)記。如初始節(jié)點(diǎn)S0被標(biāo)記為不可解節(jié)點(diǎn)，原問題無解而失敗退出。如不能確定S0為不可解節(jié)點(diǎn)，則從Open表中刪除具有不可解先輩的節(jié)點(diǎn)；③轉(zhuǎn)第2步4.3.2與/或樹的啟發(fā)式搜索解樹的代價(jià)希望樹與/或樹的啟發(fā)式搜索解樹的代價(jià)最優(yōu)解樹是指代價(jià)最小的那棵解樹。終止節(jié)點(diǎn)，代價(jià)為0或節(jié)點(diǎn)代價(jià)取其子節(jié)點(diǎn)中的最小值與節(jié)點(diǎn)有和代價(jià)法與節(jié)點(diǎn)代價(jià)最大值法；不可解節(jié)點(diǎn)代價(jià)∝根節(jié)點(diǎn)的代價(jià)為解樹的代價(jià)例子:解樹的代價(jià)(1)n0n1n2n3n4n5n6n7n8代價(jià):9

k(n0,N)=C(n0,n1)+K(n1,N)=1+K(n1,N)=1+C(n1,n3)+K(n3,N)=1+1+K(n3,N)=1+1+2+K(n5,N)+K(n6,N)=1+1+2+1+K(n6,N)+K(n6,N)=1+1+2+1+2+K(n7,N)+K(n8,N)+K(n6,N)=1+1+2+1+2+K(n6,N)=1+1+2+1+2+2+K(n7,N)+K(n8,N)=1+1+2+1+2+2=9n0n1n2n3n4n5n6n7n8代價(jià):8

k(n0,N)=C(n0,n1)+K(n1,N)=1+K(n1,N)=1+C(n1,n3)+K(n3,N)=1+1+K(n3,N)=1+1+2+K(n5,N)+K(n6,N)=1+1+2+2+K(n7,N)+K(n8,N)+K(n6,N)=1+1+2+2+K(n6,N)=1+1+2+2+2+K(n7,N)+K(n8,N)=1+1+2+2+2=8例子:解樹的代價(jià)(2)例子:解樹的代價(jià)(3)代價(jià):7代價(jià):5n0n1n2n3n4n5n6n7n8n0n1n2n3n4n5n6n7n8n0n1n2n3n4n5希望樹從n到N的解樹中，代價(jià)最小的解樹稱為最佳解樹。

為找到最佳解樹，搜索過程的任何時(shí)刻都應(yīng)該選擇那些最有希望成為最佳解樹一部分的節(jié)點(diǎn)進(jìn)行擴(kuò)展。由于這些節(jié)點(diǎn)及其父節(jié)點(diǎn)所構(gòu)成的與/或樹最有可能成為最佳解樹的一部分，因此稱之為希望樹。希望樹主要是針對或節(jié)點(diǎn)而言。希望樹定義初始節(jié)點(diǎn)S0在希望樹T中；如果n是具有子節(jié)點(diǎn)n1,n2,…,nk的或節(jié)點(diǎn)，則n的某個(gè)子節(jié)點(diǎn)ni在希望樹中的充分必要條件是：

h(ni)=min{c(n,ni)+h(ni)}如果n是與節(jié)點(diǎn)，則n的全部子節(jié)點(diǎn)都在希望樹T中。與/或樹的啟發(fā)式搜索與/或樹的啟發(fā)式搜索算法也稱為AO*算法。與/或樹的啟發(fā)式搜索需要不斷地選擇、修正希望樹AO*算法利用h(n)探索求解k(n0,N)=C1+K(n1,N) =1+K(n1,N)k(n0,N)=C2+K(n4,N)+K(n5,N) =2+K(n4,N)+K(n5,N)n0n1n4n5c1c2k(n0,N)=C1+K(n1,N)

1+h(n1)k(n0,N)=C2+K(n4,N)+K(n5,N)

2+h(n4)+h(n5)擴(kuò)展一個(gè)部分解樹后,要重新計(jì)算這個(gè)解樹代價(jià)的估計(jì)值;

n0n1n4n5c1c2c3n3k(n0,N)=C1+K(n1,N)

1+h(n1)k(n0,N)=C1+C3+K(n3,N)

2+h(n3)兩個(gè)過程樹生成過程，即擴(kuò)展節(jié)點(diǎn)計(jì)算解樹代價(jià)的過程特點(diǎn)用標(biāo)記來追蹤解樹把初始節(jié)點(diǎn)S0放入Open表中，計(jì)算

h(S0)；計(jì)算希望樹T；把OPEN表中取出T的端節(jié)點(diǎn)n放入CLOSED表。如節(jié)點(diǎn)n不是終止節(jié)點(diǎn)且可擴(kuò)展，生成n的所有后繼并將所有擴(kuò)展節(jié)點(diǎn)放入Open表中，為每個(gè)后繼設(shè)置指向其父節(jié)點(diǎn)的指針，計(jì)算這些子節(jié)點(diǎn)及其先輩節(jié)點(diǎn)的h值，轉(zhuǎn)2；如節(jié)點(diǎn)n不是終止節(jié)點(diǎn)且不可擴(kuò)展，標(biāo)記n為不可解節(jié)點(diǎn)；在樹T上應(yīng)用不可解標(biāo)記過程，并為n的先輩節(jié)點(diǎn)中所有不可解節(jié)點(diǎn)進(jìn)行標(biāo)記，如果初始節(jié)點(diǎn)可以標(biāo)記為不可解節(jié)點(diǎn)，失敗退出，否則從OPEN表中刪除具有不可解先輩的所有節(jié)點(diǎn)，轉(zhuǎn)2；如節(jié)點(diǎn)n是終止節(jié)點(diǎn)，標(biāo)記n為可解節(jié)點(diǎn)；在樹T上應(yīng)用可解標(biāo)記過程，如果初始節(jié)點(diǎn)可以標(biāo)記為可解節(jié)點(diǎn)，成功退出，否則從OPEN表中刪除具有可解先輩的所有節(jié)點(diǎn)后轉(zhuǎn)2；4.4博弈樹的啟發(fā)式搜索博弈具有“二人零和、全信息、非偶然”的特征。(1)所謂“二人零和”指的是：對壘的MAX、MIN雙方輪流采取行動，博弈的結(jié)果只有