人工智能與知識(shí)工程-搜索推理技術(shù)1

3.1圖搜索(sōusuǒ)策略3.2盲目搜索3.3啟發(fā)式搜索3.4博弈樹(shù)搜索3搜索(sōusuǒ)推理技術(shù)1共一百頁(yè)從問(wèn)題表示到問(wèn)題的解決，有一個(gè)求解的過(guò)程。常見(jiàn)的AI問(wèn)題求解技術(shù)有兩種，即“搜索”（Search）和“推理”（Reasoning）方法。搜索是AI研究的一個(gè)重要課題，幾乎所有的AI問(wèn)題都可以被歸結(jié)為搜索問(wèn)題。各種搜索技術(shù)的研究是AI初期（1956－1970）的“熱門(mén)”課題。雖然現(xiàn)在已有不少成熟的搜索技術(shù)出現(xiàn)于AI手冊(cè)和各種AI書(shū)籍中，并在一些知識(shí)系統(tǒng)種得到廣泛應(yīng)用。但搜索效率的提高(tígāo)仍然是現(xiàn)在和今后AI研究者關(guān)心的一個(gè)重要問(wèn)題。問(wèn)題求解的第二種方法是邏輯推理。通過(guò)構(gòu)造一個(gè)邏輯系統(tǒng)，由它可以從已有的斷言（公理）推導(dǎo)出新的斷言。并用邏輯形式語(yǔ)言描述的一組公理來(lái)表達(dá)問(wèn)題域。用這種方法來(lái)解決問(wèn)題就是通過(guò)推理來(lái)積聚越來(lái)越多的斷言，直到獲得問(wèn)題的解答。雖然問(wèn)題求解可通過(guò)搜索方法，也可用邏輯推理，但二者的側(cè)重點(diǎn)是不一樣的。前者著重于尋求問(wèn)題解答的過(guò)程，而后者強(qiáng)調(diào)前提（初始）問(wèn)題空間（公理集合）與問(wèn)題解答間連接的邏輯正確性。或者簡(jiǎn)單地講，搜索著重于發(fā)現(xiàn)（Discovery），而推理強(qiáng)調(diào)證明（Proof）。

2共一百頁(yè)3.1圖搜索(sōusuǒ)策略3.1.1問(wèn)題求解(qiújiě)的過(guò)程3.1.2圖搜索的一般過(guò)程3共一百頁(yè)3.1.1問(wèn)題求解(qiújiě)的過(guò)程1.問(wèn)題的表示:主要采用狀態(tài)空間法(狀態(tài)空間圖)和問(wèn)題歸約法(與或圖)。2.問(wèn)題的求解:通過(guò)(tōngguò)在圖(“狀態(tài)空間圖”或”與或圖”)中進(jìn)行搜索,尋找一條路徑的方法.一般搜索:從初始節(jié)點(diǎn)出發(fā),擴(kuò)展節(jié)點(diǎn),并沿子節(jié)點(diǎn)推進(jìn),繼續(xù)擴(kuò)展選擇的子節(jié)點(diǎn),直到找到通向目標(biāo)結(jié)點(diǎn)的路徑,或找到解樹(shù)為止。肓目搜索:是按預(yù)定的控制策略進(jìn)行搜索,在搜索過(guò)程中獲得的中間信息并不改變控制策略。啟發(fā)式搜索:是在搜索過(guò)程中加入了與問(wèn)題有關(guān)的啟發(fā)性信息,縮小問(wèn)題的搜索范圍，指導(dǎo)搜索朝著最有希望的方向前進(jìn)，以盡快地找到問(wèn)題的（最優(yōu)）解。4共一百頁(yè)3.1.2圖搜索(sōusuǒ)的一般過(guò)程例：從某王姓家族的四代中找王A的后代且其壽命為X的人。

王A：壽命47，有兒子王B1、王B3、王B2

王B1：壽命77，有兒子王C1、王C2

王B3：壽命52，有兒子王D1

王B2：壽命65，有兒子王E1、王E2

王F1：壽命32

王G1：壽命96

王C2：壽命87，有兒子王F1

王D1：壽命77，沒(méi)有兒子

王E1：壽命57，有兒子王G1

王E2：壽命92，有兒子王H1

王C1：壽命27，沒(méi)有兒子

王H1：壽命51

若X=57，如果是一個(gè)N代的家族表中找其壽命為X的人，我們最可能(kěnéng)用的手工方法是從家族表的開(kāi)始往下，例中還要求所找的人是某人的后代，就比較復(fù)雜了。如果用圖來(lái)表示，就很容易了。圖中把姓氏省去，每個(gè)成員的后代按例子中給出名字的先后順序。5共一百頁(yè)3.1.2圖搜索的一般(yībān)過(guò)程(續(xù))圖搜索策略可看作一種在圖中尋找路徑的方法。初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別代表初始數(shù)據(jù)庫(kù)和滿足終止條件的數(shù)據(jù)庫(kù)。求得把一個(gè)數(shù)據(jù)庫(kù)變換為另一數(shù)據(jù)庫(kù)的規(guī)則序列問(wèn)題就等價(jià)于求得圖中的一條路徑問(wèn)題。研究(yánjiū)圖搜索的一般策略，能夠給出圖搜索過(guò)程的一般步驟。6共一百頁(yè)3.1.2圖搜索(sōusuǒ)的一般過(guò)程（續(xù)）數(shù)據(jù)結(jié)構(gòu):OPEN：未擴(kuò)展節(jié)點(diǎn)表CLOSED：已擴(kuò)展節(jié)點(diǎn)表算法過(guò)程(1)建立一個(gè)只含有起始節(jié)點(diǎn)S的搜索圖G,把S放到一個(gè)叫作OPEN的未擴(kuò)展節(jié)點(diǎn)表中;(2)建立一個(gè)叫做CLOSED的已擴(kuò)展節(jié)點(diǎn)表,其初始為空表;(3)LOOP:若OPEN表是空表,則失敗退出(tuìchū);(4)選擇OPEN表上的第一個(gè)節(jié)點(diǎn),把它從OPEN表移出并放進(jìn)CLOSED表中,稱此節(jié)點(diǎn)為節(jié)點(diǎn)n;(5)若n為一目標(biāo)節(jié)點(diǎn),則有解并成功退出,此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針將在第(7)步中設(shè)置);7共一百頁(yè)3.1.2圖搜索(sōusuǒ)的一般過(guò)程（續(xù)）(6)擴(kuò)展節(jié)點(diǎn)n，同時(shí)生成不是n的祖先的那些后繼(hòujì)節(jié)點(diǎn)的集合M，把M的這些成員作為n的后繼(hòujì)節(jié)點(diǎn)添入圖G中；(7)對(duì)那些未曾在G中出現(xiàn)過(guò)的(即未曾在OPEN表上或CLOSED表中出現(xiàn)過(guò)的)M成員設(shè)置一個(gè)通向n的指針,把M的這些成員加進(jìn)OPEN表。對(duì)已經(jīng)在OPEN或CLOSED表上的每一個(gè)M成員，確定是否需要更改通到n的指針?lè)较?。?duì)已在CLOSED表上的每個(gè)M成員，確定是否需要更改圖G中通向它的每個(gè)后裔節(jié)點(diǎn)的指針?lè)较颍?8)按某一任意方式或按某個(gè)探試值,重排OPEN表;(9)GoLoop。8共一百頁(yè)3.1.2圖搜索(sōusuǒ)的一般過(guò)程（續(xù)）圖搜索(sōusuǒ)過(guò)程框圖9共一百頁(yè)3.1.2圖搜索(sōusuǒ)的一般過(guò)程（續(xù)）過(guò)程說(shuō)明:①搜索(sōusuǒ)圖:圖搜索(sōusuǒ)的一般過(guò)程生成一個(gè)明確的圖G,稱為搜索(sōusuǒ)圖。②搜索樹(shù):圖搜索的一般過(guò)程生成G的一個(gè)子集T稱為搜索樹(shù)。由步驟(7)中設(shè)置的指針來(lái)確定。③G中每個(gè)節(jié)點(diǎn)(S除外)都有一個(gè)只指向G中一個(gè)父輩節(jié)點(diǎn)的指針,該父輩節(jié)點(diǎn)就定為樹(shù)中那個(gè)節(jié)點(diǎn)的惟一父輩節(jié)點(diǎn)。④OPEN表上的節(jié)點(diǎn)都是搜索圖上未被擴(kuò)展的端節(jié)點(diǎn),而CLOSED表上的節(jié)點(diǎn),或者是已被擴(kuò)展但沒(méi)有生成后繼節(jié)點(diǎn)的端節(jié)點(diǎn),或者是搜索樹(shù)的非端節(jié)點(diǎn)。10共一百頁(yè)3.1.2圖搜索(sōusuǒ)的一般過(guò)程（續(xù)）⑤步驟(8)對(duì)OPEN表上的節(jié)點(diǎn)進(jìn)行排序,以便選出一個(gè)”最好”的節(jié)點(diǎn)作為步驟(4)擴(kuò)展(kuòzhǎn)使用。 (1)排序可以是任意的即肓目的(盲目搜索) (2)可以用啟發(fā)信息為依據(jù)(啟發(fā)式搜索)⑥當(dāng)擴(kuò)展某個(gè)節(jié)點(diǎn)時(shí),搜索圖已經(jīng)保存了從初始節(jié)點(diǎn)到該節(jié)點(diǎn)的搜索樹(shù)。⑦每當(dāng)被選作擴(kuò)展的節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)時(shí),這一過(guò)程就宣告成功結(jié)束。這時(shí)，從目標(biāo)節(jié)點(diǎn)按指向父節(jié)點(diǎn)的指針不斷回溯,能夠重現(xiàn)從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的成功路徑。⑧當(dāng)搜索樹(shù)不再剩有末被擴(kuò)展的端節(jié)點(diǎn)時(shí)(即OPEN表為空時(shí))，過(guò)程就以失敗告終。從起始節(jié)點(diǎn),達(dá)不到目標(biāo)節(jié)點(diǎn)。11共一百頁(yè)3.1.2圖搜索的一般(yībān)過(guò)程（續(xù)）⑨步驟(6)擴(kuò)展節(jié)點(diǎn)時(shí),生成一個(gè)節(jié)點(diǎn)的所有后繼(hòujì)節(jié)點(diǎn)。⑩步驟(7)的說(shuō)明:特別地用于啟發(fā)式搜索擴(kuò)展節(jié)點(diǎn)1以前的搜索圖擴(kuò)展節(jié)點(diǎn)1以后搜索圖12共一百頁(yè)3.2盲目(mángmù)搜索3.2.1寬度優(yōu)先搜索(sōusuǒ)3.2.1深度優(yōu)先搜索3.2.3等代價(jià)搜索13共一百頁(yè)3.2.1寬度(kuāndù)優(yōu)先搜索寬度優(yōu)先(yōuxiān)搜索：如果搜索是以接近起始節(jié)點(diǎn)的程度來(lái)依次擴(kuò)展節(jié)點(diǎn)，那么這種搜索叫做寬度優(yōu)先搜索(breadth-firstsearch)。特點(diǎn)：這種搜索是逐層進(jìn)行的；在對(duì)下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。14共一百頁(yè)3.2.1寬度優(yōu)先(yōuxiān)搜索（續(xù)）寬度優(yōu)先(yōuxiān)搜索算法:(1)把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn),則求得一個(gè)解答)。(2)如果OPEN是個(gè)空表則沒(méi)有解，失敗退出，否則繼續(xù)。(3)把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。(4)擴(kuò)展節(jié)點(diǎn)n，如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向步驟(2)。(5)把n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到n的指針。(6)如果n的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn),則找到一個(gè)解答，成功退出，否則轉(zhuǎn)向步驟(2)。15共一百頁(yè)3.2.1寬度優(yōu)先(yōuxiān)搜索（續(xù)）寬度優(yōu)先搜索算法說(shuō)明:(1)搜索樹(shù):搜索過(guò)程產(chǎn)生的節(jié)點(diǎn)和指針構(gòu)成一棵隱式定義的狀態(tài)空間圖的子樹(shù),稱為搜索樹(shù)。(2)如果問(wèn)題有解,寬度優(yōu)先算法能夠保證找到一條通向目標(biāo)節(jié)點(diǎn)的最短路徑(即找到最優(yōu)解)。(3)如果問(wèn)題無(wú)解，對(duì)于有限圖，該算法會(huì)失敗退出；對(duì)于無(wú)限圖，則永遠(yuǎn)不會(huì)終止。(4)寬度優(yōu)先搜索是圖搜索一般過(guò)程的特殊情況，將圖搜索一般過(guò)程中的第8步具體化為本算法中的第6步，這實(shí)際(shíjì)是將OPEN表作為“先進(jìn)先出”的隊(duì)列進(jìn)行操作。

16共一百頁(yè)3.2.1寬度(kuāndù)優(yōu)先搜索（續(xù)）17共一百頁(yè)3.2.1寬度(kuāndù)優(yōu)先搜索（續(xù)）例:八數(shù)碼(shùmǎ)難題，在3×3的方格棋盤(pán)上，分別放置了標(biāo)有數(shù)字1,2,3,4,5,6,7,8的八張牌，初始狀態(tài)如圖S0所示，目標(biāo)狀態(tài)如圖Sg所示，要求應(yīng)用寬度優(yōu)先搜索策略尋找從初始狀態(tài)到目標(biāo)狀態(tài)的解路徑。18共一百頁(yè)3.2.1寬度(kuāndù)優(yōu)先搜索（續(xù)）八數(shù)碼難題的寬度(kuāndù)優(yōu)先搜索樹(shù)19共一百頁(yè)3.2.2深度優(yōu)先(yōuxiān)搜索深度優(yōu)先(yōuxiān)搜索：在搜索過(guò)程中，首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)，深度相等的節(jié)點(diǎn)可以任意排列，這種搜索叫做深度優(yōu)先搜索(depth-firstsearch)。特點(diǎn)：首先，擴(kuò)展最深的節(jié)點(diǎn)的結(jié)果使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點(diǎn)向下進(jìn)行下去；只有當(dāng)搜索到達(dá)一個(gè)沒(méi)有后裔的狀態(tài)時(shí)，它才考慮另一條替代的路徑。20共一百頁(yè)3.2.2深度(shēndù)優(yōu)先搜索（續(xù)）節(jié)點(diǎn)深度:(1)起始節(jié)點(diǎn)(即根節(jié)點(diǎn))的深度為0。(2)任何其他節(jié)點(diǎn)的深度等于其父輩節(jié)點(diǎn)的深度加1。深度界限:為了避免考慮太長(zhǎng)的路徑(防止搜索過(guò)程沿著無(wú)益的路徑擴(kuò)展下去),往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度,稱為深度界限。任何節(jié)點(diǎn)如果達(dá)到了深度界限,那么都將把它們作為(zuòwéi)沒(méi)有后繼節(jié)點(diǎn)來(lái)處理。即使應(yīng)用了深度界限,深度優(yōu)先搜索所求得的解答路徑也不一定就是最短路徑。21共一百頁(yè)3.2.2深度(shēndù)優(yōu)先搜索（續(xù)）含有深度界限的深度優(yōu)先搜索算法:(1)把起始節(jié)點(diǎn)S放到未擴(kuò)展節(jié)點(diǎn)OPEN表中。如果此節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn),則得到一個(gè)解。(2)如果OPEN為一空表,則失敗退出。(3)把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移到CLOSED表。(4)如果節(jié)點(diǎn)n的深度等于最大深度,則轉(zhuǎn)向步驟(2)。(5)擴(kuò)展節(jié)點(diǎn)n,產(chǎn)生其全部后裔,并把它們放入OPEN表的前頭(qiántou)。如果沒(méi)有后裔，則轉(zhuǎn)向步驟(2)。(6)如果后繼節(jié)點(diǎn)中有任一個(gè)為目標(biāo)節(jié)點(diǎn),則求得一個(gè)解,成功退出;否則,轉(zhuǎn)向步驟(2)。22共一百頁(yè)23共一百頁(yè)3.2.2深度(shēndù)優(yōu)先搜索（續(xù)）八數(shù)碼難題深度界限為5的深度優(yōu)先(yōuxiān)搜索樹(shù)24共一百頁(yè)3.2.3等代價(jià)(dàijià)搜索寬度優(yōu)先的局限:在寬度優(yōu)先搜索中作了一種假設(shè),認(rèn)為狀態(tài)空間中各邊的代價(jià)都相同,且都為一個(gè)單位量。從而可用路徑的長(zhǎng)度(chángdù)代替路徑的代價(jià)。然而,對(duì)許多問(wèn)題這種假設(shè)是不現(xiàn)實(shí)的,它們的狀態(tài)空間中的各個(gè)邊的代價(jià)不可能完全相同。 例:城市交通問(wèn)題。為此,需要在搜索樹(shù)中給每條邊都標(biāo)上其代價(jià)。代價(jià)樹(shù):在搜索樹(shù)中給每條邊都標(biāo)上其代價(jià)。這種邊上標(biāo)有代價(jià)的樹(shù)稱為代價(jià)樹(shù)。等代價(jià)搜索:尋找從起始狀態(tài)至目標(biāo)狀態(tài)的具有最小代價(jià)的路徑問(wèn)題,叫做等代價(jià)搜索。在等代價(jià)搜索算法中,是沿著等代價(jià)路徑斷層進(jìn)行擴(kuò)展的。25共一百頁(yè)3.2.3等代價(jià)(dàijià)搜索（續(xù)）例:城市交通問(wèn)題.設(shè)有5個(gè)城市,它們之間的交通路線如圖所示,圖中的數(shù)字表示兩個(gè)城市之間的交通費(fèi)用(fèiyong),即代價(jià)。用等代價(jià)搜索,求從A市出發(fā)到E市,費(fèi)用(fèiyong)最小的交通路線。26共一百頁(yè)3.2.3等代價(jià)(dàijià)搜索（續(xù)）解:其代價(jià)(dàijià)搜索樹(shù)如右下圖:最優(yōu)解:A,C,D,E27共一百頁(yè)3.2.3等代價(jià)(dàijià)搜索（續(xù)）記號(hào)(jìhɑo)c(i,j):從節(jié)點(diǎn)I到其后繼節(jié)點(diǎn)j的連接弧線代價(jià)。g(i):從起始節(jié)點(diǎn)S到任一節(jié)點(diǎn)i的路徑代價(jià)(即是從起始節(jié)點(diǎn)S到節(jié)點(diǎn)i的最少代價(jià)路徑上的代價(jià))28共一百頁(yè)3.2.3等代價(jià)(dàijià)搜索（續(xù)）等代價(jià)搜索算法:(1)把起始節(jié)點(diǎn)S放到未擴(kuò)展節(jié)點(diǎn)有OPEN中。如果此起始節(jié)點(diǎn)為一目標(biāo)(mùbiāo)節(jié)點(diǎn),則求得一個(gè)解，否是令g(S)=0。(2)如果OPEN是個(gè)空表,則沒(méi)有解而失敗退出。(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中。29共一百頁(yè)3.2.3等代價(jià)(dàijià)搜索（續(xù)）(4)如果節(jié)點(diǎn)i為目標(biāo)節(jié)點(diǎn),則求得一個(gè)解。(5)擴(kuò)展節(jié)點(diǎn)i。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向步驟(bùzhòu)(2);(6)對(duì)于節(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)。30共一百頁(yè)31共一百頁(yè)3.3啟發(fā)式搜索(sōusuǒ)3.3.1啟發(fā)式搜索(sōusuǒ)策略和估價(jià)函數(shù)3.3.2有序搜索3.3.3A*算法3.3.4圖搜索策略的評(píng)價(jià)32共一百頁(yè)3.3啟發(fā)式搜索(sōusuǒ)（續(xù)）盲目搜索存在的問(wèn)題擴(kuò)展節(jié)點(diǎn)數(shù)目較多。效率低，耗費(fèi)過(guò)多的計(jì)算時(shí)間和空間。分析前面介紹的寬度優(yōu)先、深度優(yōu)先搜索，或等代價(jià)搜索算法,其主要的差別是OPEN表中待擴(kuò)展節(jié)點(diǎn)的順序問(wèn)題。如果找到一種方法用于排列待擴(kuò)展節(jié)點(diǎn)的順序，即選擇(xuǎnzé)最有希望的節(jié)點(diǎn)加以擴(kuò)展，那么，搜索效率將會(huì)大為提高。

33共一百頁(yè)3.3.1啟發(fā)式搜索策略(cèlüè)和估價(jià)函數(shù)啟發(fā)性信息：指那種與具體問(wèn)題求解過(guò)程有關(guān)的，并可指導(dǎo)搜索過(guò)程朝著最有希望方向前進(jìn)的控制信息。三種啟發(fā)性信息：(1)用于決定要擴(kuò)展(kuòzhǎn)的下一個(gè)節(jié)點(diǎn)，以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地?cái)U(kuò)展(kuòzhǎn)。(2)在擴(kuò)展一個(gè)節(jié)點(diǎn)的過(guò)程中，用于決定要生成哪一個(gè)或哪幾個(gè)后繼節(jié)點(diǎn)，以免盲目地同時(shí)生成所有可能的節(jié)點(diǎn)。(3)用于決定某些應(yīng)該從搜索樹(shù)中拋棄或修剪的節(jié)點(diǎn)。啟發(fā)式搜索：利用啟發(fā)信息的搜索方法叫做啟發(fā)式搜索。34共一百頁(yè)3.3.1啟發(fā)式搜索(sōusuǒ)策略和估價(jià)函數(shù)（續(xù)）估價(jià)函數(shù)(evaluationfunction):用于度量節(jié)點(diǎn)的”希望”(此節(jié)點(diǎn)在通向目標(biāo)結(jié)點(diǎn)的最佳路徑上的”希望”)的量度。記號(hào)f(n):表示節(jié)點(diǎn)n的估價(jià)函數(shù)值。用函數(shù)f(n)的值來(lái)排列圖搜索的一般算法(suànfǎ)中的OPEN表中節(jié)點(diǎn)。節(jié)點(diǎn)按遞增順序排列,即優(yōu)先擴(kuò)展具有低估價(jià)值的節(jié)點(diǎn),根據(jù)低估價(jià)值節(jié)點(diǎn)更有可能處在最佳路徑上。35共一百頁(yè)3.3.2有序搜索(sōusuǒ)有序搜索：應(yīng)用某個(gè)算法(例如等代價(jià)法)選擇OPEN表上具有(jùyǒu)最小f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)，這種搜索方法叫做有序搜索或最佳優(yōu)先搜索，其算法就叫做有序搜索算法（orderedsearch）或最佳優(yōu)先算法（best-firstsearch）。有序搜索總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn).36共一百頁(yè)3.3.2有序搜索(sōusuǒ)(續(xù))有序搜索算法:(1)把起始節(jié)點(diǎn)S放到OPEN表中，計(jì)算f(S),并把其值與節(jié)點(diǎn)S聯(lián)系起來(lái)。(2)如果OPEN表是個(gè)空表,則失敗退出，無(wú)解。(3)從OPEN表中選擇一個(gè)f值最小的節(jié)點(diǎn)i，結(jié)果(jiēguǒ)有幾個(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的擴(kuò)展節(jié)點(diǎn)表中。(5)如果i是個(gè)目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個(gè)解，37共一百頁(yè)3.3.2有序搜索(sōusuǒ)(續(xù))(6)擴(kuò)展節(jié)點(diǎn)i，生成其全部后繼節(jié)點(diǎn)。對(duì)于i的每一個(gè)后繼節(jié)點(diǎn)j:a)計(jì)算f(j)。b)如果j既不在OPEN表中，也不在CLOSED表中，則用估價(jià)函數(shù)f把它添入OPEN表，從j加一指向父輩節(jié)點(diǎn)i的指針(以便(yǐbiàn)找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑)。c)如果j已在OPEN表或CLOSED表上，則比較剛剛對(duì)j計(jì)算過(guò)的f值和前面計(jì)算過(guò)的該節(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);38共一百頁(yè)3.3.2有序搜索(sōusuǒ)(續(xù))39共一百頁(yè)3.3.2有序搜索(sōusuǒ)(續(xù))在有序搜索中定義f(i)為節(jié)點(diǎn)i的深度,則退化為寬度優(yōu)先算法搜索。定義f(i)為從起始節(jié)點(diǎn)至節(jié)點(diǎn)i這段路徑的代價(jià),則退化為等代價(jià)搜索。估價(jià)函數(shù)的作用f的選擇直接決定了有序搜索中被擴(kuò)展節(jié)點(diǎn)的數(shù)目,即直接影響了搜索算法的效率。對(duì)搜索結(jié)果具有決定性的作用，如果選擇不合適，有序搜索就可能失去一個(gè)最好的解甚至全部的解。估價(jià)函數(shù)的選擇，如果沒(méi)有適用的準(zhǔn)確的希望量度，那么f的選擇將涉及兩個(gè)方面的內(nèi)容：一方面是時(shí)間和空間之間的折衷方案；另一方面是保證有一個(gè)最優(yōu)的解或任意解。一個(gè)節(jié)點(diǎn)處在最佳路徑上的概率；求出任意一個(gè)節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)集之間的距離度量或差異度量；根據(jù)格局(géjú)（博弈問(wèn)題）或狀態(tài)的特點(diǎn)來(lái)打分。40共一百頁(yè)3.3.2有序搜索(sōusuǒ)(續(xù))例:八數(shù)碼難題.設(shè)問(wèn)題的初始狀態(tài)S0和目標(biāo)狀態(tài)Sg如圖所示,定義估價(jià)函數(shù)為:f(n)=d(n)+W(n) 其中,d(n)表示節(jié)點(diǎn)n在搜索樹(shù)中的深度;

W(n)表示節(jié)點(diǎn)n中”不在位”的數(shù)碼個(gè)數(shù). 請(qǐng)計(jì)算初始狀態(tài)S0的估價(jià)函數(shù)值f(S0). 解:對(duì)初始節(jié)點(diǎn)S0,由于(yóuyú)d(n)=0,W(n)=4,因此有:f(S0)=441共一百頁(yè)八數(shù)碼(shùmǎ)難題有序搜索樹(shù)42共一百頁(yè)3.3.3A*算法(suànfǎ)估價(jià)函數(shù)f(n)的定義:是從起始節(jié)點(diǎn)約束地通過(guò)節(jié)點(diǎn)n而到達(dá)目標(biāo)節(jié)點(diǎn)的最小代價(jià)路徑的代價(jià)的一個(gè)(yīɡè)估計(jì)。估價(jià)函數(shù)的形式:f(n)=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)Sg的最優(yōu)路徑的估計(jì)代價(jià)。43共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）定義3.1在GRAPHSEARCH過(guò)程(guòchéng)中,如果步驟(8)的重排OPEN表是依據(jù)f(n)=g(n)+h(n)進(jìn)行的,則稱該過(guò)程為A算法。說(shuō)明:在圖搜索的一般算法中,在搜索的每一步都利用估價(jià)函數(shù)f(n)=g(n)+h(n)對(duì)Open表中的節(jié)點(diǎn)進(jìn)行排序,找出一個(gè)最有希望的節(jié)點(diǎn)作為下一次擴(kuò)展的節(jié)點(diǎn),則該搜索算法稱為A算法。44共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）例:八數(shù)碼難題。設(shè)問(wèn)題的初始狀態(tài)(zhuàngtài)和目標(biāo)狀態(tài)(zhuàngtài)如圖所示,估價(jià)函數(shù)為:f(n)=d(n)+W(n) 其中,d(n)表示節(jié)點(diǎn)n在搜索樹(shù)中的深度;

W(n)表示節(jié)點(diǎn)n中”不在位”的數(shù)碼個(gè)數(shù)。45共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）記號(hào):k(ni,nj):表示任意兩個(gè)節(jié)點(diǎn)ni和nj之間最小代價(jià)路徑(lùjìng)的實(shí)際代價(jià)(對(duì)于兩節(jié)點(diǎn)間沒(méi)有通路的節(jié)點(diǎn),函數(shù)k沒(méi)有定義).h*(n):表示整個(gè)目標(biāo)節(jié)點(diǎn)集合{ti}上所有k(n,ti)中最小的一個(gè),即從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)最優(yōu)路徑的實(shí)際代價(jià)。g*的定義:g*(n)=k(S,n)f*的定義:f*(n)=g*(n)+h*(n)46共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）估價(jià)函數(shù)f是f*的一個(gè)估計(jì):f(n)=g(n)+h(n) 其中g(shù)(n)是g*(n)的估計(jì),h(n)是h*(n)的估計(jì)。g(n),通常為從S到n這段路徑的實(shí)際代價(jià)則有g(shù)(n)≥g*(n)h(n):是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估計(jì)代價(jià)。它的選擇依賴于有關(guān)問(wèn)題領(lǐng)域的啟發(fā)信息(xìnxī)，叫做啟發(fā)函數(shù)。例如八數(shù)碼中的W(n)。47共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）定義3.2在A算法中,如果對(duì)所有的n存在h(n)≤h*(n),則稱h(n)為h*(n)的下界。定義3.3采用h*(n)的下界h(n)為啟發(fā)函數(shù)的A算法,稱為A*算法.當(dāng)h=0時(shí),A*算法就變?yōu)橛行蛩阉魉惴?。說(shuō)明:當(dāng)定義的啟發(fā)函數(shù)h(n)是h*(n)的下界,即對(duì)任意的節(jié)點(diǎn)(jiédiǎn)n均有h(n)≤h*(n)。那么這時(shí)的A算法就稱為A*算法。48共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）例:八數(shù)碼難題.設(shè)問(wèn)題的初始狀態(tài)和目標(biāo)狀態(tài)如前圖所示,估價(jià)函數(shù)(hánshù)為:f(n)=d(n)+W(n) 其中,d(n)表示節(jié)點(diǎn)n在搜索樹(shù)中的深度;

W(n)表示節(jié)點(diǎn)n中”不在位”的數(shù)碼個(gè)數(shù).d(n)是對(duì)g*(n)的一個(gè)估計(jì)，d(n)≥g*(n)W(n)是對(duì)h*(n)的一個(gè)估計(jì)49共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）算法步驟:(1)把S放入OPEN表,記f=h,令CLOSED為空表。(2)重復(fù)下列過(guò)程,直至找到目標(biāo)節(jié)點(diǎn)為止。若OPEN為空表,則宣告失敗。(3)選取(xuǎnqǔ)OPEN表中未設(shè)置過(guò)的具有最小f值的節(jié)點(diǎn)為最佳節(jié)點(diǎn)BESTNODE,并把它放入CLOSED表。(4)若BESTNODE為一目標(biāo)節(jié)點(diǎn),則成功求得一解。(5)若BESTNODE不是目標(biāo)節(jié)點(diǎn),則擴(kuò)展之,產(chǎn)生后繼節(jié)點(diǎn)SUCCESSOR。50共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）(6)對(duì)每個(gè)SUCCESSOR進(jìn)行下列過(guò)程:a)建立從SUCCESSOR返回BESTNODE的指針。b)計(jì)算g(SUC)=g(BES)+g(BES,SUC)。c)如果SUCCESSOR∈OPEN,則稱此節(jié)點(diǎn)(jiédiǎn)為OLD,并把它添至BESTNODE的后繼節(jié)點(diǎn)(jiédiǎn)表中。d)比較新舊路徑代價(jià).如果g(SUC)<g(OLD),則重新確定OLD的父輩節(jié)點(diǎn)為BESTNODE,記下較小代價(jià)g(OLD),并修正f(OLD)值。51共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）(6)對(duì)每個(gè)SUCCESSOR進(jìn)行下列過(guò)程:e)若至OLD節(jié)點(diǎn)的代價(jià)較低或一樣,則停止擴(kuò)展節(jié)點(diǎn)。f)若SUCCESSOR不在CLOSE表中,則看其是否在CLOSED表中。g)若SUCCESSOR在CLOSE表中,則轉(zhuǎn)向(zhuǎnxiàng)(c);h)若SUCCESSOR既不在OPEN表中,又不在CLOSED表中,則把它放入OPEN表中,并添入BESTNODE后裔表,然后轉(zhuǎn)向(7)。(7)計(jì)算f值。(8)GOLOOP。52共一百頁(yè)A*算法參考(cānkǎo)框圖53共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）例1:八數(shù)碼難題.定義如下兩種估價(jià)函數(shù):構(gòu)成兩個(gè)A*算法A1*和A2*。A1*: h1(n):“不在位”的棋子數(shù) g1(n):實(shí)際走的步數(shù)(節(jié)點(diǎn)深度)A2*: h2(n):所有棋子偏離目標(biāo)位置(wèizhi)的距離總和 g2(n):實(shí)際走的步數(shù)(節(jié)點(diǎn)深度) 則有:h1(n)≤h2(n)54共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）八數(shù)碼難題(nántí)的A1*算法的搜索圖55共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）八數(shù)碼難題的A2*算法(suànfǎ)的搜索圖56共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）A*算法的特點(diǎn):若存在從初始節(jié)點(diǎn)S0到目標(biāo)(mùbiāo)節(jié)點(diǎn)Sg的路徑,則A*算法必能結(jié)束在最佳路徑上。使用啟發(fā)函數(shù)h(n)的A*算法，比不使用h(n)(h(n)≡0)的算法,求得最佳路徑時(shí)擴(kuò)展的節(jié)點(diǎn)數(shù)要少.一般來(lái)說(shuō),在滿足h(n)≤h*(n)的條件下,h(n)的值越大,說(shuō)明它攜帶的啟發(fā)性信息越多,搜索時(shí)擴(kuò)展的節(jié)點(diǎn)就越少,搜索效率就越高,當(dāng)h(n)=h*(n)時(shí),則不會(huì)去擴(kuò)展多余的節(jié)點(diǎn)就可找到解.57共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）例2:迷宮(mígōng)圖從入口到出口有若干條通路，求從入口到出口處最短路徑的走法。下圖為一簡(jiǎn)單迷宮(mígōng)示意圖及其平面坐標(biāo)表示。58共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）問(wèn)題狀態(tài):物體在迷宮中的位置坐標(biāo)(zuòbiāo)(x,y)。則初始狀態(tài):(1,1)目標(biāo)狀態(tài):(4,4)操作規(guī)則（迷宮走法規(guī)定為向上、下、左、右前進(jìn)一步）U:上方無(wú)墻→向上走一步(x,y+1)D:下方無(wú)墻→向下走一步(x,y-1)L:左方無(wú)墻→向左走一步(x-1,y)R:右方無(wú)墻→向右走一步(x+1,y)59共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）取h(n)＝|XG-xn|+|YG-yn|，g(n)＝d(n),f(n)=g(n)+h(n)，顯然可以滿足A*的條件。 其中,(XG,YG)為目標(biāo)點(diǎn)坐標(biāo)，(xn,yn)為節(jié)點(diǎn)(jiédiǎn)n的坐標(biāo)。再設(shè)當(dāng)不同節(jié)點(diǎn)的f值相等時(shí)，以深度優(yōu)先排序。60共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）迷宮(mígōng)問(wèn)題搜索圖61共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）例3:修道士和野人問(wèn)題(M-C問(wèn)題)。狀態(tài):(m,c,b)操作:Pij,Qij證明h(n)＝m+c-2b是滿足A*條件的。 若不考慮限制條件,如果船在左岸,也就是說(shuō)，船一次可以將三人從左岸運(yùn)到右岸，然后再有一個(gè)人將船送回來(lái)。這樣，船一個(gè)來(lái)回可以運(yùn)過(guò)河2人，而船仍然在左岸。而最后剩下的三個(gè)人，則可以一次將他們?nèi)繌淖蟀哆\(yùn)到右岸。則至少(zhìshǎo)擺渡次數(shù)為:62共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）考慮船在右岸的情況。船在右岸，需要一個(gè)人將船運(yùn)到左岸。對(duì)于狀態(tài)(m，c，0)來(lái)說(shuō)，其所需要的最少擺渡(bǎidù)數(shù)，相當(dāng)于船在左岸時(shí)狀態(tài)(m+1，c，1)或(m，c+1，1)所需要的最少擺渡(bǎidù)數(shù)，再加上第一次將船從右岸送到左岸的一次擺渡(bǎidù)數(shù)。因此所需要的最少擺渡(bǎidù)數(shù)為：(m+c+1)-2+1化簡(jiǎn)有：(m+c+1)-2+1=m+c。

綜合船在左岸和船在右岸兩種情況下，所需要的最少擺渡(bǎidù)次數(shù)用一個(gè)式子表示為：m+c-2b。其中b＝1表示船在左岸，b＝0表示船在右岸。

由于該擺渡(bǎidù)次數(shù)是在不考慮限制條件下，推出的最少所需要的擺渡(bǎidù)次數(shù)。因此，當(dāng)有限制條件時(shí)，最優(yōu)的擺渡(bǎidù)次數(shù)只能大于等于該擺渡(bǎidù)次數(shù)。所以該啟發(fā)函數(shù)h是滿足A*條件的。定義估價(jià)函數(shù)f(n)=g(n)+h(n),其中g(shù)(n)=d(n),h(n)=m+c-2b63共一百頁(yè)3.3.3A*算法(suànfǎ)（續(xù)）M-C問(wèn)題(wèntí)的A*算法搜索圖64共一百頁(yè)3.3.4圖搜索(sōusuǒ)策略的評(píng)價(jià)準(zhǔn)則1、完備性：有解時(shí)能否保證找到解2、最優(yōu)性：如果問(wèn)題存在多個(gè)解，那么利用該搜索策略一定能夠找到最優(yōu)解。3、時(shí)間復(fù)雜度：根據(jù)搜索過(guò)程中產(chǎn)生的節(jié)點(diǎn)數(shù)目來(lái)度量4、空間復(fù)雜度：在執(zhí)行搜索的過(guò)程中需要(xūyào)的內(nèi)存，取決于儲(chǔ)存的最大節(jié)點(diǎn)數(shù)。時(shí)間與空間的復(fù)雜度往往要與問(wèn)題難度的某種度量一起考慮65共一百頁(yè)3.3.4圖搜索(sōusuǒ)策略的評(píng)價(jià)（續(xù)）問(wèn)題難度的度量 時(shí)間與空間的復(fù)雜度往往要與問(wèn)題難度的某種度量一起考慮（狀態(tài)空間圖的大?。┢骄种б蜃觔：節(jié)點(diǎn)的后繼節(jié)點(diǎn)的平均個(gè)數(shù)d：最淺的目標(biāo)節(jié)點(diǎn)的深度（解深度）m：狀態(tài)空間中任何(rènhé)路徑的最大深度66共一百頁(yè)3.3.4圖搜索策略(cèlüè)的評(píng)價(jià)（續(xù)）寬度優(yōu)先搜索當(dāng)b有限時(shí)，搜索是完備(wánbèi)的從尋找最短路徑的解（或深度最淺的解）的意義上最優(yōu)時(shí)間復(fù)雜度：O(bd)（b：平均分枝因子，d：解深度）空間復(fù)雜度：O(bd)（b：平均分枝因子，d：解深度）67共一百頁(yè)3.3.4圖搜索策略(cèlüè)的評(píng)價(jià)（續(xù)）深度優(yōu)先搜索不完備(wánbèi)非最優(yōu)時(shí)間復(fù)雜度：O(bm)（b：平均分枝因子，m：狀態(tài)空間的最大深度）空間復(fù)雜度：O(b.m)（b：平均分枝因子，m：狀態(tài)空間的最大深度）68共一百頁(yè)3.3.4圖搜索(sōusuǒ)策略的評(píng)價(jià)（續(xù)）含有(hányǒu)深度界限的深度優(yōu)先搜索當(dāng)l≥d時(shí)完備(l：深度限，d：解深度)非最優(yōu)時(shí)間復(fù)雜度：O(bl)（b：平均分枝因子，l：深度限）空間復(fù)雜度：O(b.l)（b：平均分枝因子，l：深度限）69共一百頁(yè)3.3.4圖搜索(sōusuǒ)策略的評(píng)價(jià)（續(xù)）等代價(jià)搜索完備從尋找到根結(jié)點(diǎn)代價(jià)最小路徑的解的意義上最優(yōu)時(shí)間復(fù)雜度：O(bd)（b：平均分枝(fēnzhī)因子，d：解深度）空間復(fù)雜度：O(bd)（b：平均分枝因子，d：解深度）70共一百頁(yè)3.3.4圖搜索(sōusuǒ)策略的評(píng)價(jià)（續(xù)）有序搜索不完備不優(yōu)化時(shí)間復(fù)雜度：O(bm)（b：平均分枝因子，m：狀態(tài)(zhuàngtài)空間的最大深度）71共一百頁(yè)3.3.4圖搜索(sōusuǒ)策略的評(píng)價(jià)（續(xù)）A*算法完備優(yōu)化時(shí)間復(fù)雜度：O(bd)（b：平均分枝因子，d：解深度）在內(nèi)存空間中保存了所有(suǒyǒu)的節(jié)點(diǎn)A*也稱為最佳圖搜索算法72共一百頁(yè)3.4博弈(bóyì)樹(shù)搜索3.4.1博弈問(wèn)題概述3.4.2極小極大(jídà)分析法3.4.3α-β搜索過(guò)程73共一百頁(yè)3.4.1博弈(bóyì)問(wèn)題概述如下棋、打牌、競(jìng)技、戰(zhàn)爭(zhēng)等一類競(jìng)爭(zhēng)性智能(zhìnénɡ)活動(dòng)稱為博弈。博弈有很多種，我們討論最簡(jiǎn)單的“二人零和、全信息、非偶然”博弈，其特征如下：（1）雙人對(duì)弈，對(duì)壘的雙方輪流走步。（2）信息完備，對(duì)壘雙方所得到的信息是一樣的，不存在一方能看到，而另一方看不到的情況。（3）零和。即對(duì)一方有利的棋，對(duì)另一方肯定是不利的，不存在對(duì)雙方均有利、或均無(wú)利的棋。對(duì)弈的結(jié)果是一方贏，而另一方輸，或者雙方和棋。（4）任何一方在采取行動(dòng)前都要根據(jù)當(dāng)前的實(shí)際情況，進(jìn)行得失分析，選取對(duì)自已為最有利而對(duì)對(duì)方最為不利的對(duì)策，不存在擲骰子之類的"碰運(yùn)氣"因素。即雙方都是很理智地決定自己的行動(dòng)。74共一百頁(yè)3.4.1博弈問(wèn)題(wèntí)概述(續(xù))博弈樹(shù)搜索與狀態(tài)空間搜索的區(qū)別由機(jī)器完全控制結(jié)點(diǎn)的擴(kuò)展，到由博弈雙方分別控制每一步操作后的結(jié)果不可預(yù)測(cè) 由于對(duì)手的操作帶來(lái)不確定性：機(jī)器無(wú)從知道對(duì)方將會(huì)如何操作 對(duì)手總是試圖給對(duì)方帶來(lái)不便在實(shí)際使用中的一些其它問(wèn)題 特別(tèbié)大的狀態(tài)空間 國(guó)際象棋：

平均分枝因子：35

每盤(pán)棋每方平均走棋：50步

狀態(tài)空間大小：35100（1040不同的合法的狀態(tài)） 每一次搜索均有時(shí)間的限制 對(duì)搜索的結(jié)果要求更高75共一百頁(yè)3.4.1博弈(bóyì)問(wèn)題概述(續(xù))博弈問(wèn)題的知識(shí)表示 在博弈過(guò)程中，任何一方都希望自己取得勝利。因此，當(dāng)某一方當(dāng)前有多個(gè)行動(dòng)方案可供選擇時(shí)，他總是挑選對(duì)自己最為有利而對(duì)對(duì)方最為不利的那個(gè)行動(dòng)方案。 如果我們站在MAX方的立場(chǎng)上，則可供MAX方選擇的若干行動(dòng)方案之間是“或”關(guān)系，因?yàn)橹鲃?dòng)權(quán)操在MAX方手里，他或者選擇這個(gè)行動(dòng)方案，或者選擇另一個(gè)行動(dòng)方案，完全(wánquán)由MAX方自已決定。 當(dāng)MAX方選取任一方案走了一步后，MIN方也有若干個(gè)可供選擇的行動(dòng)方案，此時(shí)這些行動(dòng)方案對(duì)MAX方來(lái)說(shuō)它們之間則是"與"關(guān)系，因?yàn)檫@時(shí)主動(dòng)權(quán)操在MIN方手里，這些可供選擇的行動(dòng)方案中的任何一個(gè)都可能被MIN方選中，MAX方必須應(yīng)付每一種情況的發(fā)生。

這樣，如果站在某一方(如MAX方，即MAX要取勝)，把上述博弈過(guò)程用圖表示出來(lái)，則得到的是一棵"與或樹(shù)"。描述博弈過(guò)程的與或樹(shù)稱為博弈樹(shù)76共一百頁(yè)3.4.1博弈問(wèn)題(wèntí)概述(續(xù))博弈樹(shù)的特點(diǎn) (1)博弈的初始格局是初始節(jié)點(diǎn)。

(2)在博弈樹(shù)中，"或"節(jié)點(diǎn)和"與"節(jié)點(diǎn)是逐層交替出現(xiàn)的。自己一方擴(kuò)展的節(jié)點(diǎn)之間是"或"關(guān)系，對(duì)方擴(kuò)展的節(jié)點(diǎn)之間是"與"關(guān)系。雙方輪流地?cái)U(kuò)展節(jié)點(diǎn)。

(3)所有自己一方獲勝的終局都是本原問(wèn)題，相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對(duì)方獲勝的終局都認(rèn)為是不可解節(jié)點(diǎn)。

假定MAX先走，處于奇數(shù)深度級(jí)的節(jié)點(diǎn)都對(duì)應(yīng)(duìyìng)下一步由MAX走，這些節(jié)點(diǎn)稱為MAX節(jié)點(diǎn)，相應(yīng)地偶數(shù)級(jí)為MIN節(jié)點(diǎn)。

77共一百頁(yè)3.4.1博弈問(wèn)題(wèntí)概述(續(xù))問(wèn)題空間模型化 四元組：（初始狀態(tài)，操作集合，終止(zhōngzhǐ)測(cè)試（非目標(biāo)測(cè)試），判定函數(shù)） 以下棋為例：初始狀態(tài)：棋的開(kāi)局操作集合：下棋的規(guī)則終止測(cè)試：如果以輸、贏、和局為下棋的終止，終止測(cè)試代表對(duì)輸、贏、和局的判定判定函數(shù)：通過(guò)它可以估計(jì)每一種狀態(tài)下輸、贏、和局的可能大?。ū热纾嚎梢?1表示輸，0表示和局，1表示贏）78共一百頁(yè)3.4.1博弈問(wèn)題(wèntí)概述(續(xù))例：分錢(qián)幣問(wèn)題 有一堆數(shù)目為N的錢(qián)幣，由兩位選手(MAX,MIN)輪流進(jìn)行分堆，要求每個(gè)選手每次只把其中某一堆分成數(shù)目不等的兩小堆。例如選手甲把N分成兩堆后，輪到選手乙就可以挑其中一堆來(lái)分，如此進(jìn)行下去直到有一位選手先無(wú)法把錢(qián)幣再分成不相等的兩堆時(shí)就得認(rèn)輸(rènshū)。用無(wú)序數(shù)字序列x1，x2，…，xn表示n堆錢(qián)幣不同的個(gè)數(shù)，再用兩個(gè)說(shuō)明符號(hào)代表選手，無(wú)序數(shù)列和符號(hào)M組合（x1，x2，…，xn，M）就代表由某個(gè)選手走步的狀態(tài)。初始狀態(tài)：（7，MIN）規(guī)則：if（x1，…，xn，M）∧（xi＝y(tǒng)+z，y≠z）

then（x1，…，xi-1，y，z，xi+1，…，xn，M）79共一百頁(yè)3.4.1博弈(bóyì)問(wèn)題概述(續(xù))分錢(qián)幣問(wèn)題狀態(tài)空間圖 圖中所有終節(jié)點(diǎn)均表示該選手必輸?shù)那闆r，取勝(qǔshèng)方的目標(biāo)是設(shè)法使棋局發(fā)展為結(jié)束在對(duì)方走步時(shí)的終節(jié)點(diǎn)上，因此節(jié)點(diǎn)A是MAX的搜索目標(biāo)，而節(jié)點(diǎn)B，C則為MIN的搜索目標(biāo)。80共一百頁(yè)3.4.1博弈問(wèn)題(wèntí)概述(續(xù))分錢(qián)幣問(wèn)題 尋找MAX的取勝策略便和求與或圖的解圖一致起來(lái)，即MAX要取勝，必須對(duì)所有與節(jié)點(diǎn)取勝，但只需對(duì)一個(gè)或節(jié)點(diǎn)取勝，這就是(jiùshì)一個(gè)解圖。因此實(shí)現(xiàn)一種取勝的策略就是(jiùshì)搜索一個(gè)解圖的問(wèn)題，解圖就代表一種完整的博弈策略。

81共一百頁(yè)3.4.1博弈問(wèn)題(wèntí)概述(續(xù))對(duì)于分錢(qián)幣問(wèn)題這種較簡(jiǎn)單的博弈，或者復(fù)雜博弈的殘局，可以用類似于與或圖的搜索技術(shù)求出解圖，解圖代表了從開(kāi)局到終局任何階段上的弈法。但是這對(duì)許多博弈問(wèn)題是不可能實(shí)現(xiàn)的。完全取勝策略（或和局）必須丟棄(diūqì)，而應(yīng)當(dāng)把目標(biāo)確定為尋找一步好棋，等對(duì)手回敬后再考慮尋找另一步好棋這種實(shí)際可行的實(shí)用策略。這種情況下每一步結(jié)束條件可根據(jù)時(shí)間限制、存儲(chǔ)空間限制或深度限制等因素加以確定。搜索策略可采用寬度、深度或啟發(fā)式方法，一個(gè)階段搜索結(jié)束后，要從搜索樹(shù)中提取一個(gè)優(yōu)先考慮的"最好的"走步，這就是實(shí)用策略的基本點(diǎn)。82共一百頁(yè)3.4.2極小(jíxiǎo)極大分析法基本思想首先假定，有一個(gè)評(píng)價(jià)函數(shù)可以對(duì)所有的棋局進(jìn)行評(píng)估。當(dāng)評(píng)價(jià)函數(shù)值大于0時(shí)，表示棋局對(duì)我方有利，對(duì)對(duì)方不利。當(dāng)評(píng)價(jià)函數(shù)小于0時(shí)，表示棋局對(duì)我方不利，對(duì)對(duì)方有利。而評(píng)價(jià)函數(shù)值越大，表示對(duì)我方越有利。當(dāng)評(píng)價(jià)函數(shù)值等于正無(wú)窮大時(shí)，表示我方必勝。評(píng)價(jià)函數(shù)值越小，表示對(duì)我方越不利。當(dāng)評(píng)價(jià)函數(shù)值等于負(fù)無(wú)窮大時(shí)，表示對(duì)方必勝。假設(shè)雙方都是對(duì)弈高手(gāoshǒu)，在只看一步棋的情況下，我方一定走評(píng)價(jià)函數(shù)值最大的一步棋，而對(duì)方一定走評(píng)價(jià)函數(shù)值最小的一步棋。83共一百頁(yè)3.4.2極小(jíxiǎo)極大分析法（續(xù)）極小極大搜索方法 當(dāng)輪到我方走棋時(shí)，首先按照一定的搜索深度生成出給定深度d以內(nèi)的所有狀態(tài)，計(jì)算所有葉節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值。然后從d-1層節(jié)點(diǎn)開(kāi)始逆向計(jì)算：對(duì)于我方要走的節(jié)點(diǎn)（用MAX標(biāo)記，稱為(chēnɡwéi)極大節(jié)點(diǎn)）取其子節(jié)點(diǎn)中的最大值為該節(jié)點(diǎn)的值（因?yàn)槲曳娇偸沁x擇對(duì)我方有利的棋）；對(duì)于對(duì)方要走的節(jié)點(diǎn)（用MIN標(biāo)記，稱為(chēnɡwéi)極小節(jié)點(diǎn)）取其子節(jié)點(diǎn)中的最小值為該節(jié)點(diǎn)的值（對(duì)方總是選擇對(duì)我方不利的棋）。一直到計(jì)算出根節(jié)點(diǎn)的值為止。獲得根節(jié)點(diǎn)取值的那一分枝，即為所選擇的最佳走步。84共一百頁(yè)3.4.2極小(jíxiǎo)極大分析法（續(xù)）算法框架整個(gè)算法分為四個(gè)步驟：1、以當(dāng)前狀態(tài)為根結(jié)點(diǎn)產(chǎn)生一個(gè)博弈(bóyì)樹(shù)。2、對(duì)博弈樹(shù)的每一個(gè)葉結(jié)點(diǎn)，利用判定函數(shù)給出它的判定值。3、從葉結(jié)點(diǎn)開(kāi)始，一層一層地回溯。在回溯過(guò)程中，利用最大/最小判定為每一個(gè)結(jié)點(diǎn)給出其判定值。4、MAX方選擇下一層中判定值最大的結(jié)點(diǎn)，作為它的下一狀態(tài)。85共一百頁(yè)3.4.2極小(jíxiǎo)極大分析法（續(xù)）例86共一百頁(yè)3.4.2極小(jíxiǎo)極大分析法（續(xù)）例一字棋游戲設(shè)有九個(gè)空格(kōnɡɡé)，由MAX，MIN二人對(duì)弈，輪到誰(shuí)走棋誰(shuí)就往空格(kōnɡɡé)上放一只自己的棋子，誰(shuí)先使自己的棋子構(gòu)成“三子成一線”(同一行或列或?qū)蔷€全是某人的棋子)，誰(shuí)就取得了勝利。設(shè)程序方MAX的棋子用（×）表示，對(duì)手MIN的棋子用（○）表示，MAX先走。87共一百頁(yè)3.4.2極小(jíxiǎo)極大分析法（續(xù)）靜態(tài)估計(jì)函數(shù)f（p）規(guī)定如下：若p對(duì)任何一方來(lái)說(shuō)都不是獲勝(huòshènɡ)的格局， 則f（p）＝（所有空格都放上MAX的棋子之后，MAX的三子成線（行、列、對(duì)角）的總數(shù)－（所有空格都放上MIN的棋子之后，MIN的三子成線（行、列、對(duì)角）的總數(shù)）若p是MAX獲勝的格局，則f（p）＝∞；若p是MIN獲勝的格局，則f（p）＝－∞。當(dāng)p的格局如圖時(shí)，則可得f（p）＝6－4＝2；假定具有對(duì)稱性的兩個(gè)棋局算作一個(gè)棋局88共一百頁(yè)3.4.2極小(jíxiǎo)極大分析法（續(xù)）第一階段搜索樹(shù)89共一百頁(yè)3.4.2極小(jíxiǎo)極大分析法（續(xù)）第二階段搜索樹(shù)90共一百頁(yè)3.4.2極小(jíxiǎo)極大分析法（續(xù)）第三階段搜索樹(shù)91共一百頁(yè)3.4.3α-β搜索(sōusuǒ)過(guò)程在極小極大搜索方法中，由于