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

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

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

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

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

王C1：壽命27，沒有兒子

王H1：壽命51

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

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

33共一百頁3.3.1啟發(fā)式搜索策略(cèlüè)和估價函數(shù)啟發(fā)性信息：指那種與具體問題求解過程有關(guān)的，并可指導(dǎo)搜索過程朝著最有希望方向前進的控制信息。三種啟發(fā)性信息：(1)用于決定要擴展(kuòzhǎn)的下一個節(jié)點，以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地擴展(kuòzhǎn)。(2)在擴展一個節(jié)點的過程中，用于決定要生成哪一個或哪幾個后繼節(jié)點，以免盲目地同時生成所有可能的節(jié)點。(3)用于決定某些應(yīng)該從搜索樹中拋棄或修剪的節(jié)點。啟發(fā)式搜索：利用啟發(fā)信息的搜索方法叫做啟發(fā)式搜索。34共一百頁3.3.1啟發(fā)式搜索(sōusuǒ)策略和估價函數(shù)（續(xù)）估價函數(shù)(evaluationfunction):用于度量節(jié)點的”希望”(此節(jié)點在通向目標(biāo)結(jié)點的最佳路徑上的”希望”)的量度。記號f(n):表示節(jié)點n的估價函數(shù)值。用函數(shù)f(n)的值來排列圖搜索的一般算法(suànfǎ)中的OPEN表中節(jié)點。節(jié)點按遞增順序排列,即優(yōu)先擴展具有低估價值的節(jié)點,根據(jù)低估價值節(jié)點更有可能處在最佳路徑上。35共一百頁3.3.2有序搜索(sōusuǒ)有序搜索：應(yīng)用某個算法(例如等代價法)選擇OPEN表上具有(jùyǒu)最小f值的節(jié)點作為下一個要擴展的節(jié)點，這種搜索方法叫做有序搜索或最佳優(yōu)先搜索，其算法就叫做有序搜索算法（orderedsearch）或最佳優(yōu)先算法（best-firstsearch）。有序搜索總是選擇最有希望的節(jié)點作為下一個要擴展的節(jié)點.36共一百頁3.3.2有序搜索(sōusuǒ)(續(xù))有序搜索算法:(1)把起始節(jié)點S放到OPEN表中，計算f(S),并把其值與節(jié)點S聯(lián)系起來。(2)如果OPEN表是個空表,則失敗退出，無解。(3)從OPEN表中選擇一個f值最小的節(jié)點i，結(jié)果(jiēguǒ)有幾個節(jié)點合格,當(dāng)其中有一個為目標(biāo)節(jié)點時，則選擇此目標(biāo)節(jié)點,否則就選擇其中任一個節(jié)點作為節(jié)點i。(4)把節(jié)點i從OPEN表中移出，并把它放入CLOSED的擴展節(jié)點表中。(5)如果i是個目標(biāo)節(jié)點，則成功退出，求得一個解，37共一百頁3.3.2有序搜索(sōusuǒ)(續(xù))(6)擴展節(jié)點i，生成其全部后繼節(jié)點。對于i的每一個后繼節(jié)點j:a)計算f(j)。b)如果j既不在OPEN表中，也不在CLOSED表中，則用估價函數(shù)f把它添入OPEN表，從j加一指向父輩節(jié)點i的指針(以便(yǐbiàn)找到目標(biāo)節(jié)點時記住一個解答路徑)。c)如果j已在OPEN表或CLOSED表上，則比較剛剛對j計算過的f值和前面計算過的該節(jié)點在表中的f值.如果新的f值較小，則

I.以此新值取代舊值。 II.從j指向i,而不是指向它的父輩節(jié)點。 III.如果節(jié)點j在CLOSED表中,則把它移回OPEN表。(7)轉(zhuǎn)向(2),即GOTO(2);38共一百頁3.3.2有序搜索(sōusuǒ)(續(xù))39共一百頁3.3.2有序搜索(sōusuǒ)(續(xù))在有序搜索中定義f(i)為節(jié)點i的深度,則退化為寬度優(yōu)先算法搜索。定義f(i)為從起始節(jié)點至節(jié)點i這段路徑的代價,則退化為等代價搜索。估價函數(shù)的作用f的選擇直接決定了有序搜索中被擴展節(jié)點的數(shù)目,即直接影響了搜索算法的效率。對搜索結(jié)果具有決定性的作用，如果選擇不合適，有序搜索就可能失去一個最好的解甚至全部的解。估價函數(shù)的選擇，如果沒有適用的準(zhǔn)確的希望量度，那么f的選擇將涉及兩個方面的內(nèi)容：一方面是時間和空間之間的折衷方案；另一方面是保證有一個最優(yōu)的解或任意解。一個節(jié)點處在最佳路徑上的概率；求出任意一個節(jié)點與目標(biāo)節(jié)點集之間的距離度量或差異度量；根據(jù)格局(géjú)（博弈問題）或狀態(tài)的特點來打分。40共一百頁3.3.2有序搜索(sōusuǒ)(續(xù))例:八數(shù)碼難題.設(shè)問題的初始狀態(tài)S0和目標(biāo)狀態(tài)Sg如圖所示,定義估價函數(shù)為:f(n)=d(n)+W(n) 其中,d(n)表示節(jié)點n在搜索樹中的深度;

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

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

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

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

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

平均分枝因子：35

每盤棋每方平均走棋：50步

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

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

(2)在博弈樹中，"或"節(jié)點和"與"節(jié)點是逐層交替出現(xiàn)的。自己一方擴展的節(jié)點之間是"或"關(guān)系，對方擴展的節(jié)點之間是"與"關(guān)系。雙方輪流地擴展節(jié)點。

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

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

77共一百頁3.4.1博弈問題(wèntí)概述(續(xù))問題空間模型化 四元組：（初始狀態(tài)，操作集合，終止(zhōngzhǐ)測試（非目標(biāo)測試），判定函數(shù)） 以下棋為例：初始狀態(tài)：棋的開局操作集合：下棋的規(guī)則終止測試：如果以輸、贏、和局為下棋的終止，終止測試代表對輸、贏、和局的判定判定函數(shù)：通過它可以估計每一種狀態(tài)下輸、贏、和局的可能大小（比如：可以-1表示輸，0表示和局，1表示贏）78共一百頁3.4.1博弈問題(wèntí)概述(續(xù))例：分錢幣問題 有一堆數(shù)目為N的錢幣，由兩位選手(MAX,MIN)輪流進行分堆，要求每個選手每次只把其中某一堆分成數(shù)目不等的兩小堆。例如選手甲把N分成兩堆后，輪到選手乙就可以挑其中一堆來分，如此進行下去直到有一位選手先無法把錢幣再分成不相等的兩堆時就得認(rèn)輸(rènshū)。用無序數(shù)字序列x1，x2，…，xn表示n堆錢幣不同的個數(shù)，再用兩個說明符號代表選手，無序數(shù)列和符號M組合（x1，x2，…，xn，M）就代表由某個選手走步的狀態(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共一百頁3.4.1博弈(bóyì)問題概述(續(xù))分錢幣問題狀態(tài)空間圖 圖中所有終節(jié)點均表示該選手必輸?shù)那闆r，取勝(qǔshèng)方的目標(biāo)是設(shè)法使棋局發(fā)展為結(jié)束在對方走步時的終節(jié)點上，因此節(jié)點A是MAX的搜索目標(biāo)，而節(jié)點B，C則為MIN的搜索目標(biāo)。80共一百頁3.4.1博弈問題(wèntí)概述(續(xù))分錢幣問題 尋找MAX的取勝策略便和求與或圖的解圖一致起來，即MAX要取勝，必須對所有與節(jié)點取勝，但只需對一個或節(jié)點取勝，這就是(jiùshì)一個解圖。因此實現(xiàn)一種取勝的策略就是(jiùshì)搜索一個解圖的問題，解圖就代表一種完整的博弈策略。

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