人工智能第五章

1、第5章 搜索求解策略5.1基基本本概念一、狀態(tài)態(tài)空間表表示法狀態(tài)空間間表示法法是用“狀態(tài)”和“算算符”（“操作作”）來(lái)來(lái)表示問(wèn)問(wèn)題的一一種方法法?；诮獯鸫鹂臻g的的問(wèn)題表表示和求求解方法法，它是是以狀態(tài)態(tài)和算符符為基礎(chǔ)礎(chǔ)來(lái)表示示和求解解問(wèn)題的的(1)狀狀態(tài)態(tài)（state）：表表示問(wèn)題題解法中中每一步步問(wèn)題狀狀況的數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)；Q=q0，q1，qnTQ表狀態(tài)態(tài)，qi為狀態(tài)分分量(2)算算符符（operator）：把把問(wèn)題從從一種狀狀態(tài)變換換為另一一種狀態(tài)態(tài)的手段段；稱(chēng)為操作作符或算算符。F：f1,f2,狀態(tài)空間間：由狀狀態(tài)變量量和操作作表示的的符號(hào)體體系，包包含了問(wèn)問(wèn)題求解解時(shí)全部可能能狀態(tài)及及

2、其相互互關(guān)系。三元組表表示（S，F(xiàn)，G）例設(shè)有三枚枚錢(qián)幣，其排列列處在“正，正正，反”狀態(tài)，現(xiàn)允許許每次可可翻動(dòng)其其中任意意一個(gè)錢(qián)錢(qián)幣，問(wèn)問(wèn)只允許許操作三三次的情情況下，如何翻翻動(dòng)錢(qián)幣幣使其變變成“正正，正，正”或或“反，反，反反”狀態(tài)態(tài)。狀態(tài)：(q1,q2,q3)“正面”用“1”表示示，“反反面”用用“0”表示初始狀態(tài)態(tài)集合：（1,1,0）目標(biāo)狀態(tài)態(tài)集合：（1，1，1），(0,0,0)操作：f1：翻翻q1，f2：翻q2，f3：翻q3F=f1,f2,f3例：MC問(wèn)題題問(wèn)題：3個(gè)傳教士士(Missionary)，3個(gè)野人(Cannibal)，一條船，可同時(shí)時(shí)乘坐2個(gè)人，要要求在任任何時(shí)刻刻，在河

3、河的兩岸岸，傳教教士人數(shù)數(shù)不能少少于野人人的人數(shù)數(shù)。問(wèn)：如何過(guò)過(guò)河？狀態(tài)：用三元組組(m,c,b)表示示左岸的的傳教士士、野人人和船數(shù)數(shù)。m=0,1,2,3，c=0,1,2,3，b=0,1共44232種種狀態(tài)其中有16種可可行，14種不不可行（危險(xiǎn)），2種種達(dá)不到到。初始狀態(tài)態(tài)：S=（3，3，1）或或S331目標(biāo)狀態(tài)態(tài)：G=（0，0，0）或或S000操作符（規(guī)則）Pij（左右），qij （右左）左右：p01,p10,p11,p02,p20條件：船船在左岸岸右左：q01,q10,q11,q02,q20條件：船船在右岸岸F=p01,p10,p11,p02,p20,q01,q10,q11,q02,q

4、20MC問(wèn)題狀態(tài)空間間圖ppassqquitq11q11q02(210)不合法p11(00 0)(33 0)達(dá)不到二、與/或樹(shù)（圖）表表示法1、分解解：大問(wèn)問(wèn)題分解解為若干干個(gè)易解解子問(wèn)題題，子問(wèn)問(wèn)題解決決了，大大問(wèn)題也也就解決決了。ABC或圖ABCD與圖2、變換換：大問(wèn)問(wèn)題變成成若干個(gè)個(gè)易解子子問(wèn)題，只要有有一個(gè)子子問(wèn)題解解決了，大問(wèn)題題也就解解決了。一些關(guān)于于與或圖圖的術(shù)語(yǔ)語(yǔ)HMBCDEFGAN父節(jié)點(diǎn)與節(jié)點(diǎn)弧線(xiàn)或節(jié)點(diǎn)子節(jié)點(diǎn)端節(jié)點(diǎn)基本概念念本原問(wèn)題題：不能能再分解解或變換換，而且且直接可可解的子子問(wèn)題。終止節(jié)點(diǎn)點(diǎn)：不能能分解或或變換，可直接接求解可解節(jié)點(diǎn)點(diǎn)：終止節(jié)點(diǎn)點(diǎn)“或”節(jié)節(jié)點(diǎn)，其其子節(jié)點(diǎn)

5、點(diǎn)至少有有一個(gè)是是可解節(jié)節(jié)點(diǎn)“與”節(jié)節(jié)點(diǎn)，其其子節(jié)點(diǎn)點(diǎn)均為可可解節(jié)點(diǎn)點(diǎn)不可解節(jié)節(jié)點(diǎn)：可解節(jié)點(diǎn)點(diǎn)的三個(gè)個(gè)條件都都不滿(mǎn)足足的節(jié)點(diǎn)點(diǎn)解樹(shù)：由可解節(jié)節(jié)點(diǎn)構(gòu)成成，并可可推出初初始節(jié)點(diǎn)點(diǎn)為可解解節(jié)點(diǎn)的的子樹(shù)梵塔問(wèn)題題可以分解解為三個(gè)個(gè)子問(wèn)題題：(1)最大盤(pán)以以上由1至2(2)最大盤(pán)由由1至3(3)其余盤(pán)由由2至3問(wèn)題的形形式化表表示：三元組(I,j,k)I -C所在鋼針針號(hào)j -B所在鋼針針號(hào)k-A所在鋼針針號(hào)問(wèn)題：（1，1，1）（3，3，3）ABC123ABC123三階梵塔塔問(wèn)題的的與/或或樹(shù)（113） （123） （111） （113） （123） （122） （111） （333） （122） （3

6、22） （111） （122） （322）（333） （321） （331） （322） （321） （331） （333） 三、搜索索根據(jù)問(wèn)題題的實(shí)際際情況不不斷尋找找可利用用的知識(shí)識(shí)，從而而構(gòu)造一一條代價(jià)價(jià)較少的的推理路路線(xiàn)，使使問(wèn)題得得到圓滿(mǎn)滿(mǎn)解決的的過(guò)程。類(lèi)型：1、問(wèn)題題表示方方式：狀態(tài)空間間搜索與/或樹(shù)樹(shù)搜索2、是否否使用啟啟發(fā)式信信息盲目搜索索：按預(yù)定的的控制策策略進(jìn)行行搜索，在搜索索過(guò)程中中獲得的的中間結(jié)結(jié)果不用用來(lái)改進(jìn)進(jìn)控制策策略。啟發(fā)式搜搜索：搜索過(guò)程程中加入入與問(wèn)題題有關(guān)的的啟發(fā)性性信息。（動(dòng)態(tài)態(tài)地確定定操作規(guī)規(guī)則排序序）5.2狀狀態(tài)態(tài)空間的的搜索策策略基本思想想：初態(tài)作為

7、為當(dāng)前節(jié)節(jié)點(diǎn)進(jìn)行行擴(kuò)展生生成子節(jié)節(jié)點(diǎn)，檢檢查目標(biāo)標(biāo)狀態(tài)是是否出現(xiàn)現(xiàn)，不出出現(xiàn)則按按策略選選一個(gè)子子節(jié)點(diǎn)進(jìn)進(jìn)行擴(kuò)展展直到目目標(biāo)狀態(tài)態(tài)出現(xiàn)或或沒(méi)有可可供擴(kuò)展展的子節(jié)節(jié)點(diǎn)。一、一般般的圖搜搜索過(guò)程程：OPEN表：存存放尚未未被擴(kuò)展展的節(jié)點(diǎn)點(diǎn)CLOSED表表：存放放已被擴(kuò)擴(kuò)展的節(jié)節(jié)點(diǎn)圖搜索算算法：1.把初始節(jié)節(jié)點(diǎn)S放入OPEN表，建立立一個(gè)僅僅包含S的圖G（搜索圖）2.如果OPEN表空，則則以失敗敗退出。3.把OPEN表中的第第一個(gè)節(jié)節(jié)點(diǎn)取出出放入CLOSED表，稱(chēng)此此節(jié)點(diǎn)為為n.4.如果n是目標(biāo)節(jié)節(jié)點(diǎn)，則則成功地地結(jié)束，解路徑徑可通過(guò)過(guò)回溯G中從n到S的指針獲獲得。5.擴(kuò)展節(jié)點(diǎn)點(diǎn)n，產(chǎn)生一組組子節(jié)點(diǎn)

8、點(diǎn)。把不不是n的祖先的那那些子節(jié)節(jié)點(diǎn)記作作集合M，把M的這些成成員作為為n的后繼節(jié)節(jié)點(diǎn)加入入G中。6.對(duì)于M的那些未未曾在G中出現(xiàn)的的成員，建立到到n的指針，并把這這些成員員加到OPEN表中。對(duì)于那些些已在G中出現(xiàn)的的成員，決定是是否要修修改它指指向父節(jié)節(jié)點(diǎn)的指指針。對(duì)于那些些已在G中出現(xiàn)且且已擴(kuò)展展的成員員，決定定是否要要修改其其后繼節(jié)節(jié)點(diǎn)指向向父節(jié)點(diǎn)點(diǎn)的指針針。7.按某種搜搜索策略略重排OPEN表中的節(jié)節(jié)點(diǎn)8.轉(zhuǎn)第2步圖搜索的的一般過(guò)過(guò)程開(kāi)始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點(diǎn)嗎？擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)處理后放入OPEN表，為每個(gè)

9、子節(jié)點(diǎn)配置指向節(jié)點(diǎn)n的指針重排OPEN表失敗成功是是否否節(jié)點(diǎn)n可擴(kuò)展嗎？否是說(shuō)明：這個(gè)一般般的圖搜搜索過(guò)程程，通過(guò)過(guò)不斷循循環(huán)生成成一個(gè)顯顯式表示示的圖G（搜索圖）和一個(gè)個(gè)G的子集T（搜索樹(shù)）樹(shù)T是由（6）中標(biāo)記記的指針針決定的的，除根根節(jié)點(diǎn)s外，G中每個(gè)節(jié)節(jié)點(diǎn)只有有一個(gè)指指針指向向G中的一個(gè)個(gè)父節(jié)點(diǎn)點(diǎn)OPEN表中的節(jié)節(jié)點(diǎn)（未未擴(kuò)展節(jié)節(jié)點(diǎn)）是是搜索樹(shù)樹(shù)的端節(jié)節(jié)點(diǎn)，即即尚未被被選作為為擴(kuò)展的的節(jié)點(diǎn)；CLOSED表中的節(jié)節(jié)點(diǎn)（已已擴(kuò)展節(jié)節(jié)點(diǎn)），可以是是已被擴(kuò)擴(kuò)展而不不能生成成后繼節(jié)節(jié)點(diǎn)的那那些端節(jié)節(jié)點(diǎn)，也也可以是是樹(shù)中的的非端節(jié)節(jié)點(diǎn)（7）中對(duì)OPEN表上的節(jié)節(jié)點(diǎn)進(jìn)行行排序是是為了在在（3）中能選選

10、出一個(gè)個(gè)“最好好”的節(jié)節(jié)點(diǎn)優(yōu)先先擴(kuò)展，不同的的排序方方法可構(gòu)構(gòu)成形式式多樣的的專(zhuān)門(mén)搜搜索算法法如果隱含含圖是一一棵樹(shù)，不會(huì)（6）中討論論的特殊殊節(jié)點(diǎn)，否則可可能這些些節(jié)點(diǎn)*上上述算法法的關(guān)鍵鍵一步是是（7），對(duì)OPEN表的排序序，即決決定節(jié)點(diǎn)點(diǎn)的擴(kuò)展展順序，典型的的有兩種種節(jié)點(diǎn)擴(kuò)擴(kuò)展順序序，得到到兩種搜搜索算法法（廣度度優(yōu)先搜搜索、深深度優(yōu)先先搜索）二、寬度度優(yōu)先（廣度優(yōu)優(yōu)先）基本思想想是：從節(jié)點(diǎn)S0開(kāi)始，逐逐層地對(duì)對(duì)節(jié)點(diǎn)進(jìn)進(jìn)行擴(kuò)展展，并考考察它是是否為目目標(biāo)節(jié)點(diǎn)點(diǎn)，在第第n層節(jié)點(diǎn)沒(méi)沒(méi)有全部部考察完完之前，不對(duì)第第n+1層的節(jié)點(diǎn)點(diǎn)進(jìn)行擴(kuò)擴(kuò)展。OPEN表：按“先進(jìn)先先出”排排特點(diǎn)：一種高代代價(jià)搜

11、索索，但若若有解存存在，則則必能找找到它。例子八數(shù)碼難難題（8-puzzleproblem）1238456712384567（目標(biāo)狀態(tài)）（初始狀狀態(tài)）規(guī)定：將牌移入入空格的的順序?yàn)闉椋簭目湛崭褡筮呥呴_(kāi)始順順時(shí)針旋旋轉(zhuǎn)。不不許斜向向移動(dòng)，也不返返回先輩輩節(jié)點(diǎn)。從圖可見(jiàn)見(jiàn)，要擴(kuò)擴(kuò)展26個(gè)節(jié)點(diǎn)，共生成成46個(gè)節(jié)點(diǎn)之之后才求求得解（目標(biāo)節(jié)節(jié)點(diǎn)）。1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345圖八八數(shù)碼難難題的

12、寬寬度優(yōu)先先搜索樹(shù)樹(shù)13456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567三、深度度優(yōu)先搜搜索首先擴(kuò)展展最新產(chǎn)產(chǎn)生的(即最深深的)節(jié)節(jié)點(diǎn)。深深度相等等的節(jié)點(diǎn)點(diǎn)可以任任意排列列。與寬度優(yōu)優(yōu)先搜索索算法最最根本的的不同在在于：將將擴(kuò)展的的后繼節(jié)節(jié)點(diǎn)放在在OPEN表的的前端。（先進(jìn)進(jìn)后出）問(wèn)題不一定能能找到解解找到的解解不一定定是最佳佳解為了對(duì)深深度優(yōu)先先搜索作作改進(jìn),要

13、解決兩兩個(gè)問(wèn)題題：回溯問(wèn)題題;有圈造成成死循環(huán)環(huán)問(wèn)題。四、有界界深度優(yōu)優(yōu)先搜索索如果問(wèn)題題有解且且路徑長(zhǎng)長(zhǎng)度dm,則一定定可求得得解；否否則得不不到解。問(wèn)題：dm不易確定定這種方法法不一定定能找到到解路徑徑（如果果解路徑徑的深度度超出了了限制深深度）另外它得得到的解解也不一一定是最最優(yōu)解改進(jìn)先定一個(gè)個(gè)較小的的dm，若未找找到解且且closed中有待待擴(kuò)展的的節(jié)點(diǎn)，就將其其送回open表。不不斷改進(jìn)進(jìn)dm。最優(yōu)解：增設(shè)一一表R，每找到到一個(gè)解解就將其其放入R的前面面。最后后求得的的解一定定最優(yōu)五、代價(jià)價(jià)樹(shù)的廣廣度優(yōu)先先搜索分枝界界限法有些問(wèn)題題并不要要求有應(yīng)應(yīng)用算符符序列為為最少的的解，而而是要

14、求求具有某某些特性性的解。搜索樹(shù)樹(shù)中每條條連接弧弧線(xiàn)上的的有關(guān)代代價(jià)以及及隨之而而求得的的具有最最小代價(jià)價(jià)的解答答路徑。代價(jià)樹(shù)：各邊標(biāo)標(biāo)有代價(jià)價(jià)值的樹(shù)樹(shù)-一種種加權(quán)樹(shù)樹(shù)代價(jià)計(jì)算算g(x)-sx代價(jià)g(x2)=g(x1)+c(x1,x2)基本思想想：OPEN表表中的全全部節(jié)點(diǎn)點(diǎn)按代價(jià)價(jià)從小到到大排代價(jià)樹(shù)的的廣度優(yōu)優(yōu)先搜索索開(kāi)始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點(diǎn)嗎？擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)處理后放入OPEN表，為每個(gè)子節(jié)點(diǎn)配置指向節(jié)點(diǎn)n的指針，計(jì)算各節(jié)點(diǎn)代價(jià)。把OPEN表中的全部節(jié)點(diǎn)按代價(jià)從小到大排失敗成功是是否否節(jié)點(diǎn)n可擴(kuò)展嗎？否是例下

15、圖是一一個(gè)交通通圖，設(shè)設(shè)A城市市是出發(fā)發(fā)地，E城市是是目的地地，邊上上的數(shù)字字代表兩兩城市之之間的交交通費(fèi)。試求從從A到E最小費(fèi)費(fèi)用的旅旅行路線(xiàn)線(xiàn)。Ac1d1e28六、代價(jià)價(jià)樹(shù)的深深度優(yōu)先先搜索-爬爬山法基本思想想：將擴(kuò)擴(kuò)展的后后繼節(jié)點(diǎn)點(diǎn)按邊代代價(jià)從小小到大的的順序放放在OPEN表表的前端端。代價(jià)樹(shù)的的廣度優(yōu)優(yōu)先搜索索法是完完備的且且找到的的解一定定是最優(yōu)優(yōu)解代價(jià)樹(shù)的的深度優(yōu)優(yōu)先搜索索法是不不完備的的且找到到的解不不一定是是最優(yōu)解解七、啟發(fā)發(fā)式搜索索問(wèn)題提出出：從理論上上講窮舉舉式搜索索能解決決任何狀狀態(tài)空間間問(wèn)題，但很顯顯然窮舉舉搜索只只能解決決狀態(tài)空空間很小小的簡(jiǎn)單單問(wèn)題，對(duì)于復(fù)復(fù)雜問(wèn)題題

16、會(huì)出現(xiàn)現(xiàn)“組合合爆炸”n階Hanoi塔問(wèn)題題的狀態(tài)態(tài)空間圖圖中有2的n次次方減1個(gè)結(jié)點(diǎn)點(diǎn)；博弈問(wèn)題題中，為為了取勝勝可以將將所有的的算法都都試一下下，然后后選擇最最佳走步步。就所所有可能能的棋局局?jǐn)?shù)來(lái)講講，一字字棋是9！=3.6*109，國(guó)國(guó)際象棋棋是10120，圍圍棋是10761。假設(shè)每每步可以以選擇一一種棋局局，用極極限并行行速度（10-104秒/步）計(jì)計(jì)算，國(guó)國(guó)際象棋棋的算法法得用1016年即即1億億億年才可可以算完完。解決：利用問(wèn)題題的啟發(fā)發(fā)性信息息來(lái)引導(dǎo)導(dǎo)搜索減少搜索索范圍降低問(wèn)題題復(fù)雜度度啟發(fā)信息息：進(jìn)行行搜索技技術(shù)一般般需要某某些有關(guān)關(guān)具體問(wèn)問(wèn)題領(lǐng)域域的特性性的信息息，把此此種信

17、息息叫做啟啟發(fā)信息息。把利利用啟發(fā)發(fā)信息的的搜索方方法叫做做啟發(fā)性性搜索方方法。啟發(fā)性信信息類(lèi)型型1）用于于擴(kuò)展節(jié)點(diǎn)點(diǎn)的選擇擇即決定下下一個(gè)擴(kuò)擴(kuò)展節(jié)點(diǎn)點(diǎn),以免免象在廣廣度優(yōu)先先和深度度優(yōu)先搜搜索中那那樣盲目目地?cái)U(kuò)展展2）用于于生成節(jié)節(jié)點(diǎn)的選選擇即用于決決定生成成哪個(gè)或或哪幾個(gè)個(gè)后繼節(jié)節(jié)點(diǎn),而而不是生生成所有有的節(jié)點(diǎn)點(diǎn)3）用于于刪除節(jié)節(jié)點(diǎn)的選選擇即決定用用于從搜搜索樹(shù)中中拋棄或或修剪的的節(jié)點(diǎn)我們討論論的主要要是基于于“擴(kuò)展展節(jié)點(diǎn)的的選擇”的啟發(fā)發(fā)式搜索索，這種種搜索總總是選擇擇“最有有希望”的節(jié)點(diǎn)點(diǎn)作為下下一個(gè)被被擴(kuò)展的的節(jié)點(diǎn)。這種搜搜索叫做做有序搜搜索(ordered search)。1、估價(jià)

18、價(jià)函數(shù)-評(píng)評(píng)估節(jié)點(diǎn)點(diǎn)的方法法用來(lái)估算算節(jié)點(diǎn)希希望程度度的量度度，叫做做估價(jià)函函數(shù)f(x)=g(x)+h(x)其中:f(x):從初始節(jié)節(jié)點(diǎn)S0到目標(biāo)節(jié)節(jié)點(diǎn)Sg的最優(yōu)路徑徑的代價(jià)價(jià)估計(jì)值值g(x)為從初始始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的實(shí)際代價(jià)價(jià)值。h(x)為啟發(fā)函函數(shù),是從節(jié)點(diǎn)點(diǎn)x到目標(biāo)節(jié)節(jié)點(diǎn)Sg的最優(yōu)路路徑的代代價(jià)h*(n)的估計(jì)值值。g(x)、h(x)作用分析析一般地, 在f(n)中,g(n)的比比重越大大,越越傾向于于寬度優(yōu)優(yōu)先搜索索方式; h(n)的的比重越越大,越越傾向向于深度度優(yōu)先搜搜索方式式。保持g(n)項(xiàng)項(xiàng)就保持持了搜索索的寬度度優(yōu)先趨趨勢(shì),這這有利利于搜索索的完備備性,但但影響響搜索的的效

19、率。在特殊情情況下, 如果果只希望望找到達(dá)達(dá)到目標(biāo)標(biāo)結(jié)點(diǎn)的的路徑而而不關(guān)心心已付出出的代價(jià)價(jià),則則g(n)的作作用可以以忽略。h(n) g(n)時(shí)時(shí),也也可以忽忽略g(n), 這時(shí)時(shí)有f(n)=h(n),這這有利于于搜索的的效率, 但影影響搜索索的完備備性。定義h（x）的的原則：節(jié)點(diǎn)x處處在最佳佳路徑上上的摡率率節(jié)點(diǎn)x與與目標(biāo)節(jié)節(jié)點(diǎn)集之之間的距距離度量量或差異異度量根據(jù)格局局或狀態(tài)態(tài)的特點(diǎn)點(diǎn)來(lái)打分分一般來(lái)說(shuō)說(shuō),評(píng)評(píng)價(jià)一個(gè)個(gè)結(jié)點(diǎn)的的價(jià)值, 必須須綜合考考慮兩方方面的因因素:已已經(jīng)付付出的代代價(jià)和將將要付出出的代價(jià)價(jià)。啟發(fā)式算算法通常常由兩部部分組成成:啟發(fā)方法法使用該方方法搜索索狀態(tài)空空間的算算

20、法。啟發(fā)式搜搜索基本本思想：以一般的的圖搜索索算法為為基礎(chǔ)定義啟發(fā)發(fā)函數(shù)h（x）計(jì)算每個(gè)個(gè)待擴(kuò)展展節(jié)點(diǎn)的的啟發(fā)函函數(shù)值每次擴(kuò)展展節(jié)點(diǎn)后后以節(jié)點(diǎn)點(diǎn)的啟發(fā)發(fā)函數(shù)值值為依據(jù)據(jù)對(duì)待擴(kuò)擴(kuò)展節(jié)點(diǎn)點(diǎn)排序?qū)嵸|(zhì)：選選擇OPEN表表上具有有最小f值的節(jié)節(jié)點(diǎn)作為為下一個(gè)個(gè)要擴(kuò)展展的節(jié)點(diǎn)點(diǎn)。開(kāi)始把S放入OPEN表，計(jì)算算估價(jià)函函數(shù)f (s)OPEN表為空表表？選取OPEN表中f值最小的的節(jié)點(diǎn)i放入CLOSED表i為目標(biāo)節(jié)節(jié)點(diǎn)嗎？擴(kuò)展i，得后繼節(jié)節(jié)點(diǎn)j，計(jì)算f(j)，提供返回回節(jié)點(diǎn)i的指針，利用f(j)對(duì)OPEN表重新排排序，調(diào)調(diào)整親子子關(guān)系及及指針失敗成功圖有序搜索索算法框框圖是否是否算法例：八數(shù)碼難難題（8-puz

21、zleproblem）f(n) =h(n)+ g(n)=w(n) +d(n)h(n)=w(n), w(n)是將牌不不在位個(gè)個(gè)數(shù),例如,與目標(biāo)狀狀態(tài)相比比,初始狀態(tài)態(tài)w(n)=4,即有4個(gè)將牌(1,2,6,8)不在位。g(n)=d(n), d(n)是搜索的的深度。一般根根節(jié)點(diǎn)(初始狀態(tài)態(tài))的深度是是為0,其他子節(jié)節(jié)點(diǎn)深度度為父結(jié)結(jié)點(diǎn)深度度加1。規(guī)定規(guī)則則為空格格移動(dòng)(走步規(guī)規(guī)則), 規(guī)則則選取順順序?yàn)? 左、上、右右、下?？刂撇卟呗詾? 選取取評(píng)價(jià)函函數(shù)值最最小者進(jìn)進(jìn)行擴(kuò)展展(往下下搜索)。12384567（目標(biāo)狀態(tài)）12384567（初始狀態(tài)）5714563123845671238456712

22、384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712384567（5）（7）1238456712384567（6）（7）12384567（5）8132456712384567（5）（7）圖八八數(shù)碼難難題的有有序搜索索樹(shù)123846（4）7A算法利用評(píng)價(jià)價(jià)函數(shù)f(n) =g(n)+ h(n)來(lái)來(lái)排列列OPEN表節(jié)節(jié)點(diǎn)順序序的圖搜搜索算法法稱(chēng)為A算法。實(shí)現(xiàn)類(lèi)型型：局部部擇優(yōu)搜搜索、全全局擇優(yōu)優(yōu)搜索2、局部部擇優(yōu)搜搜索-類(lèi)類(lèi)似深度度優(yōu)先基本思想想：在當(dāng)當(dāng)前擴(kuò)展展的子節(jié)節(jié)點(diǎn)中選選f(x)值值最小的的子節(jié)點(diǎn)點(diǎn)為下一一個(gè)考察察的節(jié)點(diǎn)點(diǎn)實(shí)現(xiàn)：

23、節(jié)節(jié)點(diǎn)n擴(kuò)擴(kuò)展后的的各子節(jié)節(jié)點(diǎn)計(jì)算算出估價(jià)價(jià)值后，按由小小到大次次序放到到OPEN表的的首部分析：可可把深度度優(yōu)先、代價(jià)樹(shù)樹(shù)的深度度優(yōu)先看看成其特特例。3、全局局擇優(yōu)搜搜索-類(lèi)類(lèi)似廣度度優(yōu)先節(jié)點(diǎn)n擴(kuò)擴(kuò)展后的的各子節(jié)節(jié)點(diǎn)計(jì)算算出估價(jià)價(jià)值后，送入OPEN表，然然后OPEN表表中全部部節(jié)點(diǎn)按按估價(jià)值值由小到到大排4、A*算法(Algorithm A*)幾個(gè)有用用的記號(hào)號(hào)f（x）=g（x）+h（x）f*(x)= g*（x）+h*（x）g*（x）：從節(jié)點(diǎn)點(diǎn)S到節(jié)節(jié)點(diǎn)x的的一條最最佳路徑徑的實(shí)際際代價(jià)h*（x）：從節(jié)點(diǎn)點(diǎn) x到到某目標(biāo)標(biāo)節(jié)點(diǎn)的的一條最最佳路徑徑的代價(jià)價(jià)f*(x)：從S開(kāi)始始約束通通過(guò)節(jié)點(diǎn)點(diǎn)

24、x的一一條最佳佳路徑的的代價(jià)分析：g是g*（x）的的估計(jì)；對(duì)于g（n）來(lái)說(shuō)說(shuō)，一個(gè)個(gè)明顯的的選擇就就是搜索索樹(shù)中從從到n這段路路徑的代代價(jià)，這這一代價(jià)價(jià)可以由由從n到到尋找找指針時(shí)時(shí)，把所所遇到的的各段弧弧線(xiàn)的代代價(jià)加起起來(lái)給出出（這條條路徑就就是到目目前為止止用搜索索算法找找到的從從S到n的最小小代價(jià)路路徑)。這個(gè)定定義包含含了g（x）g*（x） 。h是h*（x）的的估計(jì)；對(duì)于h（n），它依依賴(lài)于有有關(guān)問(wèn)題題的領(lǐng)域域的啟發(fā)發(fā)信息。A*算法法-又稱(chēng)最佳佳圖搜索索算法，由著名名人工智智能學(xué)者者Nilsson提出出。定義：如如果A算算法中使使用的啟啟發(fā)函數(shù)數(shù)h(n)對(duì)任任何節(jié)點(diǎn)點(diǎn)n都有有h(n)h

25、*(n)，則則稱(chēng)其為為A*算算法(AlgorithmA*)。對(duì)于寬度度優(yōu)先搜搜索算法法，h(n)=0，滿(mǎn)滿(mǎn)足h(n)h*(n)。寬度優(yōu)優(yōu)先算法法是A*算法的的特殊情情形。A*算法法的性質(zhì)質(zhì)：（1）可可采納性性如果一個(gè)個(gè)搜索算算法對(duì)于于任何具具有解路路徑的圖圖都能找找到一條條最佳解解路徑。則稱(chēng)此此算法是是可采納納的。結(jié)論：A*算法法是可采采納的證明：對(duì)有限圖圖，A*算法法一定會(huì)會(huì)在有限限步結(jié)束束對(duì)無(wú)限圖圖，只有有從S0到Sg有路徑徑存在，則A*算法也也必然會(huì)會(huì)結(jié)束A*算法法一定會(huì)會(huì)終止在在最優(yōu)路路徑上a)對(duì)有有限圖， A*算法一一定會(huì)在在有限步步結(jié)束證明：因因?yàn)樗阉魉鲌D為有有限圖，所以會(huì)會(huì)出現(xiàn)以

26、以下情況況：算法找到到解，則則成功結(jié)結(jié)束（算算法第4步）算法找不不到解，則必然然會(huì)因OPEN表變空空而結(jié)束束（算法法第2步步）b)對(duì)無(wú)無(wú)限圖，只有從從S0到到Sg有有路徑存存在，則則A*算算法也必必然會(huì)結(jié)結(jié)束證明： （分分2步）第1步證明：A*結(jié)束前, OPEN表中必存存在節(jié)點(diǎn)點(diǎn)n，它是最佳路路徑上的的一個(gè)節(jié)節(jié)點(diǎn)，且且滿(mǎn)足f(n)f*(s)而根據(jù)b)證明明可知：在A*結(jié)束前，OPEN表中中存在最最優(yōu)路徑徑上的節(jié)節(jié)點(diǎn)n, 且有有f(n)f*(s),所所以f(n)f*(s) h1(n),則在搜索索過(guò)程中中，被被A2擴(kuò)展的節(jié)節(jié)點(diǎn)也必必定由A1擴(kuò)展,即A1擴(kuò)展的節(jié)節(jié)點(diǎn)不會(huì)會(huì)比A2擴(kuò)展的節(jié)節(jié)點(diǎn)少，亦即A

27、2擴(kuò)展的節(jié)節(jié)點(diǎn)集是是A1擴(kuò)展的節(jié)節(jié)點(diǎn)集的的子集。證明:使數(shù)學(xué)歸歸納法,對(duì)節(jié)點(diǎn)的的深度應(yīng)應(yīng)用歸納納法。對(duì)深度d(n)=0的節(jié)點(diǎn)(即初始節(jié)節(jié)點(diǎn)s),若s為目標(biāo)節(jié)節(jié)點(diǎn),則A1和A2都不擴(kuò)展展s,否則A1和A2都擴(kuò)展了了s(2)設(shè)深度d(n)k時(shí),對(duì)所有路路徑的端端節(jié)點(diǎn),定理結(jié)論論都成立立。(3)證明d(n)=k+1時(shí),所有路徑徑的端節(jié)節(jié)點(diǎn),結(jié)論成立立。（反證法）設(shè)A2搜索樹(shù)上上有一個(gè)個(gè)節(jié)點(diǎn)n (d(n) =k+ 1)被A2擴(kuò)展了,而對(duì)應(yīng)于于A1搜索樹(shù)上上的這個(gè)個(gè)節(jié)點(diǎn)n,沒(méi)有被A1擴(kuò)展。根據(jù)歸歸納法假假設(shè)條件件, A1擴(kuò)展了n的父節(jié)點(diǎn)點(diǎn), n是在A1搜索樹(shù)上上,因此A1結(jié)束時(shí), n必定保留留在其OPE

28、N表上,n沒(méi)有被A1選擇擴(kuò)展展,有f1(n)f*(s),即g1(n)+ h1(n)f*(s)所以h1(n)f*(s)- g1(n)(1)另一方面面A2擴(kuò)展了n,有f2(n)f*(s),即g2(n)+ h2(n)f*(s)所以h2(n)f*(s)- g2(n)(2)由于d =k時(shí), A2擴(kuò)展的節(jié)節(jié)點(diǎn), A1也一定擴(kuò)擴(kuò)展,故有g(shù)1(n)g2(n)(因A1擴(kuò)展的節(jié)節(jié)點(diǎn)數(shù)可可能較多多)所以h1(n)f*(s)- g1(n)f*(s)- g2(n)(3)比較式(2)、(3)可得:至少在節(jié)節(jié)點(diǎn)n上有h1h2(n),這與定理理的前提提條件矛矛盾,因此存在在節(jié)點(diǎn)n的假設(shè)不不成立。證畢（3）單單調(diào)性-指h(n)

29、的單調(diào)調(diào)限制在A*算法中,每當(dāng)要擴(kuò)擴(kuò)展一個(gè)個(gè)節(jié)點(diǎn)時(shí)時(shí),都要先檢檢查其子子節(jié)點(diǎn)是是否已在在OPEN表或CLOSED表中,有時(shí)還需需要調(diào)整整指向父父節(jié)點(diǎn)的的指針,這就增加加了搜索索的代價(jià)價(jià).如果對(duì)啟發(fā)函函數(shù)h(n)加上單調(diào)調(diào)限制,就可以減減少檢查查及調(diào)整整的工作作量,提高搜索索效率.單調(diào)限制制是指h(n)滿(mǎn)足兩個(gè)個(gè)條件:(1)h(Sg)=0(2)設(shè)nj是節(jié)點(diǎn)ni的任意子子節(jié)點(diǎn),則有:h(ni)-h(nj)c(ni,nj)其中,Sg是目標(biāo)節(jié)節(jié)點(diǎn),c(ni,nj)是節(jié)點(diǎn)ni到其子節(jié)節(jié)點(diǎn)nj的弧代價(jià).將上式改改寫(xiě)成:h(ni)h(nj)+c(ni,nj)可看出:節(jié)點(diǎn)ni到目標(biāo)節(jié)節(jié)點(diǎn)最優(yōu)優(yōu)費(fèi)用的的估價(jià)不不

30、會(huì)超過(guò)過(guò)從節(jié)點(diǎn)點(diǎn)ni到其子節(jié)節(jié)點(diǎn)nj的弧代價(jià)價(jià)加上從從nj到目標(biāo)節(jié)節(jié)點(diǎn)最優(yōu)優(yōu)費(fèi)用的的估價(jià).可以證明明:(1)如果滿(mǎn)足足單調(diào)限限制,則當(dāng)A*選擇節(jié)點(diǎn)點(diǎn)n擴(kuò)展時(shí),就已經(jīng)發(fā)發(fā)現(xiàn)了通通向節(jié)點(diǎn)點(diǎn)n的最佳路路徑.即:g(n)=g*(n)(2)如果A*滿(mǎn)足單調(diào)調(diào)限制,則A*所擴(kuò)展節(jié)節(jié)點(diǎn)序列列的估價(jià)價(jià)函數(shù)值值是單調(diào)調(diào)上升的的.A*算法法的理論論意義A*算法法的理論論意義在在于給出出了求解解最佳解解的條件件h(n) h*(n)。對(duì)給定的的問(wèn)題, 函數(shù)數(shù)h*(n)(n是是變量)在問(wèn)題題有解的的條件下下客觀上上是存在在的。但但在問(wèn)題題求解過(guò)過(guò)程中不不可能都都明確知知道例：八數(shù)數(shù)碼難題題h(n) =w(n)(將牌牌不

31、在位位個(gè)數(shù))，顯然有h(n) =W(n)h*(n)h(n) =p(n)（每一個(gè)將將牌與其其目標(biāo)位位置之間間距離的的總和），顯然有h(n) =p(n)h*(n)h(n)取值分析析：h(n) =0:即啟發(fā)函函數(shù)啟發(fā)發(fā)信息為為0,f(n) =h(n)+ g(n)=g(n)d(n)(搜索深度度),此實(shí)際上上是寬度度優(yōu)先搜搜索。h(n) =W(n):f(n)= h(n)+g(n) =W(n)+ d(n)(搜索深度度) (前面例子子中：初初始狀態(tài)態(tài): W(n)=4,d(n) =0)h(n) =p(n):f(n)= h(n)+g(n) =p(n)+ d(n)(搜索深度度)。(前面例子子中：初初始狀態(tài)態(tài)：p(

32、n) =5,d(n)=0)都是A*算法h(n) =p(n)“”節(jié)節(jié)點(diǎn)為被被擴(kuò)的節(jié)節(jié)點(diǎn)“”節(jié)節(jié)點(diǎn)為生生成的節(jié)節(jié)點(diǎn)d)5.3與或樹(shù)（圖）搜搜索與或圖表表示法特特點(diǎn)與或圖表表示問(wèn)題題特點(diǎn)可分解的的問(wèn)題可變換的的問(wèn)題例：如何何上班問(wèn)問(wèn)題開(kāi)自家車(chē)車(chē)車(chē)況好（自己修修車(chē)，他他人修車(chē)車(chē)）足夠燃料料（車(chē)開(kāi)開(kāi)到加油油站，自自帶燃料料）步行身體狀況況好足夠的時(shí)時(shí)間公交車(chē)步行到車(chē)車(chē)站騎車(chē)到車(chē)車(chē)站上班問(wèn)題開(kāi)自家車(chē)步行乘公交車(chē)車(chē)況好燃料足他人修自己修他人修加油站自帶燃油燃油箱身體好時(shí)間夠步行到車(chē)站騎車(chē)到車(chē)站與或圖的的構(gòu)成與節(jié)點(diǎn)：分解問(wèn)問(wèn)題或節(jié)點(diǎn)：變換問(wèn)問(wèn)題弧:相關(guān)關(guān)節(jié)點(diǎn)的的聯(lián)結(jié)終止節(jié)點(diǎn)點(diǎn)：本原原問(wèn)題與或圖表表示法與節(jié)點(diǎn),

33、或節(jié)點(diǎn)點(diǎn),終止止節(jié)點(diǎn)端節(jié)點(diǎn)可解節(jié)點(diǎn)點(diǎn)不可解節(jié)節(jié)點(diǎn)解圖與或圖例例子1可解節(jié)點(diǎn)23B端節(jié)點(diǎn)（不可擴(kuò)展節(jié)點(diǎn)）54t1At2t3t4終止節(jié)點(diǎn)開(kāi)自家車(chē)步行車(chē)況好燃料足自己修他人修加油站自帶燃油燃油箱身體好時(shí)間夠步行到車(chē)站騎車(chē)到車(chē)站上班問(wèn)題乘公交車(chē)一、與或或樹(shù)搜索索的一般般過(guò)程1、幾個(gè)個(gè)概念可解標(biāo)示示過(guò)程：由可解解子節(jié)點(diǎn)點(diǎn)來(lái)確定定父節(jié)點(diǎn)點(diǎn)，祖父父節(jié)點(diǎn)等等為可解解節(jié)點(diǎn)的的過(guò)程不可解標(biāo)標(biāo)示過(guò)程程：由不可可解子節(jié)節(jié)點(diǎn)來(lái)確確定父節(jié)節(jié)點(diǎn)，祖祖父節(jié)點(diǎn)點(diǎn)等為不不可解節(jié)節(jié)點(diǎn)的過(guò)過(guò)程2、基本本思想：對(duì)與或樹(shù)樹(shù)（圖）標(biāo)記（示）可可解與不不可解的的遞歸過(guò)過(guò)程，通通過(guò)對(duì)終終節(jié)點(diǎn)的的可解與與否最終終確定初初始節(jié)點(diǎn)點(diǎn)是否可可解。擴(kuò)展

34、（自自上而下下）標(biāo)示（自自下而上上）結(jié)束條件件：初始始節(jié)點(diǎn)為為可解或或不可解解搜索過(guò)程程（1）把原始始問(wèn)題作作為初始始節(jié)點(diǎn)S0,并將其作作為當(dāng)前前節(jié)點(diǎn)（2）應(yīng)用分解解或變換換算符過(guò)過(guò)程對(duì)當(dāng)前節(jié)節(jié)點(diǎn)進(jìn)行行擴(kuò)展（3）為每個(gè)個(gè)子節(jié)點(diǎn)點(diǎn)設(shè)置指指向父節(jié)節(jié)點(diǎn)的指指針（4）選擇適適當(dāng)?shù)淖幼庸?jié)點(diǎn)作作為當(dāng)前前節(jié)點(diǎn)，反復(fù)應(yīng)應(yīng)用（2）（3）步，在在此期間間要多次次應(yīng)用可可解標(biāo)示示過(guò)程和和不可解解標(biāo)示過(guò)過(guò)程，直直到初始始節(jié)點(diǎn)被被標(biāo)示為為可解節(jié)節(jié)點(diǎn)或不不可解節(jié)節(jié)點(diǎn)。搜索樹(shù)：搜索過(guò)過(guò)程所形形成的節(jié)節(jié)點(diǎn)和指指針結(jié)構(gòu)構(gòu)解樹(shù)：若已標(biāo)標(biāo)示初始始節(jié)點(diǎn)是是可解的的，則由由初始節(jié)節(jié)點(diǎn)及其其下屬的的可解節(jié)節(jié)點(diǎn)就構(gòu)構(gòu)成了解解樹(shù)節(jié)點(diǎn)的刪刪除

35、可解節(jié)點(diǎn)點(diǎn)的不可可解后裔裔不可解節(jié)節(jié)點(diǎn)的全全部后裔裔二、與或或樹(shù)的廣廣度優(yōu)先先搜索（1）把把初始節(jié)節(jié)點(diǎn)S0放入OPEN表（2）把把OPEN表中中的第一一個(gè)節(jié)點(diǎn)點(diǎn)（n）取出放放入CLOSED表（3）n可擴(kuò)擴(kuò)展OPEN表按“先進(jìn)先出出”排子節(jié)點(diǎn)加加入OPEN表表尾時(shí)要要判斷其其是否為為終止節(jié)節(jié)點(diǎn)。若若是，則則標(biāo)示可可解并調(diào)調(diào)用可解解標(biāo)示過(guò)過(guò)程標(biāo)示示其祖先先節(jié)點(diǎn)。若S0可解則則結(jié)束，否則刪刪去具有有可解祖祖先的子子節(jié)點(diǎn)。（4）n不可可擴(kuò)展標(biāo)示為不不可解節(jié)節(jié)點(diǎn)并調(diào)調(diào)用不可可解標(biāo)示示過(guò)程標(biāo)標(biāo)示其祖祖先節(jié)點(diǎn)點(diǎn)。若S0不可可解則結(jié)結(jié)束，否否則刪去去具有不不可解祖祖先的子子節(jié)點(diǎn)。（5）轉(zhuǎn)轉(zhuǎn)（2）解樹(shù)構(gòu)成成：1

36、,2,3,4,5,t1,t2,t3,t4三、與或或樹(shù)的深深度優(yōu)先先搜索（1）把把初始節(jié)節(jié)點(diǎn)S0放入OPEN表（2）把把OPEN表中中的第一一個(gè)節(jié)點(diǎn)點(diǎn)（n）取出放放入CLOSED表（3）n可擴(kuò)擴(kuò)展OPEN表按“后進(jìn)先先出”排排子節(jié)點(diǎn)加加入OPEN表表首時(shí)要要判斷其其是否為為終止節(jié)節(jié)點(diǎn)。若若是，則則標(biāo)示可可解并調(diào)調(diào)用可解解標(biāo)示過(guò)過(guò)程標(biāo)示示其祖先先節(jié)點(diǎn)。若S0可解則則結(jié)束，否則刪刪去具有有可解祖祖先的子子節(jié)點(diǎn)。（4）n不可可擴(kuò)展（若深度度界限限，當(dāng)不不可擴(kuò)展展處理）標(biāo)示為不不可解節(jié)節(jié)點(diǎn)并調(diào)調(diào)用不可可解標(biāo)示示過(guò)程標(biāo)標(biāo)示其祖祖先節(jié)點(diǎn)點(diǎn)。若S0不可可解則結(jié)結(jié)束，否否則刪去去具有不不可解祖祖先的子子節(jié)點(diǎn)。（

37、5）轉(zhuǎn)轉(zhuǎn)（2）四、與或或樹(shù)的有有序搜索索根據(jù)代價(jià)價(jià)決定搜搜索路線(xiàn)線(xiàn)-求求最優(yōu)解解樹(shù)是與或圖圖啟發(fā)式式搜索的的一種特特例與或圖啟啟發(fā)式搜搜索算法法也稱(chēng)為為AO*算法1、擴(kuò)展展節(jié)點(diǎn)時(shí)時(shí)代價(jià)計(jì)計(jì)算節(jié)點(diǎn)x的的代價(jià)為為h(x)X：終止節(jié)點(diǎn)點(diǎn)h(x) =0端節(jié)點(diǎn)（非終止止）h(x)=或節(jié)點(diǎn)與節(jié)點(diǎn)根節(jié)點(diǎn)的的代價(jià)-解樹(shù)樹(shù)的代價(jià)價(jià)左邊的解解樹(shù)S0,A,t1,C,t3H(s0)=2+4+6+2=14(按和和)H(s0)=8+2=10(按最大大)右邊的解解樹(shù)s0,B,t2,D,t4H(s0)=1+5+3+2=11(按和和)H(s0)=6+2=8(按按最大)無(wú)論按和和代價(jià)還還是最大大代價(jià)，右邊的的解樹(shù)都都是最優(yōu)優(yōu)解樹(shù)

38、問(wèn)題1）由于于h(yi)不不是終止止節(jié)點(diǎn)則則無(wú)法知知道其值值引入啟發(fā)發(fā)函數(shù)計(jì)計(jì)算h(yi)2）每當(dāng)當(dāng)有一代代新節(jié)點(diǎn)點(diǎn)生成時(shí)時(shí)，都要要自下而而上地重重新計(jì)算算其先輩輩節(jié)點(diǎn)的的代價(jià)h3）選出出擴(kuò)展的的節(jié)點(diǎn)應(yīng)應(yīng)是代價(jià)價(jià)最小的的部分解解樹(shù)（圖圖）中的的節(jié)點(diǎn)希望樹(shù)：可能成成為最優(yōu)優(yōu)解樹(shù)的的一部分分2、希望望樹(shù)T在搜索過(guò)過(guò)程中任任一時(shí)刻刻求出的的局部解解圖（樹(shù)樹(shù)）其代代價(jià)都是是最小的的。這個(gè)個(gè)局部解解圖即是是希望圖圖（樹(shù)）1)S0在T中中2)x在在T中若x為“或”接接點(diǎn)，則則滿(mǎn)足minc(x,yi)+h(yi)的的子節(jié)點(diǎn)點(diǎn)yi也也在T中中若x為“與”接接點(diǎn)，則則其所有有子節(jié)點(diǎn)點(diǎn)yi也也在T中中3、與或或樹(shù)

39、的有有序搜索索過(guò)程目標(biāo)：尋尋找最小小代價(jià)的的解樹(shù)，最優(yōu)解解圖(樹(shù)樹(shù))方法：按按解圖生生成的方方法,分分步生成成局部解解圖,重重新計(jì)算算節(jié)點(diǎn)的的耗散值值（代價(jià)價(jià)）,從從中選選擇一個(gè)個(gè)代價(jià)最最小的局局部解圖圖用于擴(kuò)擴(kuò)展，同同時(shí)使用用標(biāo)示過(guò)過(guò)程。與其他搜搜索過(guò)程程的不同同點(diǎn)：從OPEN表中中選希望望樹(shù)T的的端節(jié)點(diǎn)點(diǎn)N作為為當(dāng)前節(jié)節(jié)點(diǎn)送入入CLOSED表擴(kuò)展N時(shí)時(shí)所產(chǎn)生生的子節(jié)節(jié)點(diǎn)均需需計(jì)算自自身及其其先輩節(jié)節(jié)點(diǎn)的h值具體過(guò)程程：（1）把把S0放放入OPEN表表中，計(jì)計(jì)算h(S0)（2）計(jì)計(jì)算希望望樹(shù)T（3）依依次在OPEN表中取取出T的的端節(jié)點(diǎn)點(diǎn)n放入入CLOSED表（4）根根據(jù)n的的三種可可能做以

40、以下工作作：n的三種種可能：“終終止節(jié)點(diǎn)點(diǎn)”、不不是但可可擴(kuò)展、不是且且不可擴(kuò)擴(kuò)展“終止節(jié)節(jié)點(diǎn)”標(biāo)記n為可解解節(jié)點(diǎn)在T上上應(yīng)用可可解標(biāo)記記過(guò)程，對(duì)n的的先輩節(jié)節(jié)點(diǎn)中的的所有可可解節(jié)點(diǎn)點(diǎn)進(jìn)行標(biāo)標(biāo)記如果初初始節(jié)點(diǎn)點(diǎn)S0被被標(biāo)記為為可解，則T就就是最優(yōu)優(yōu)解樹(shù)，成功退退出否則，從OPEN表表中刪去去具有可可解先輩輩的所有有節(jié)點(diǎn)轉(zhuǎn)（2）不是“終終止節(jié)點(diǎn)點(diǎn)”但可可擴(kuò)展擴(kuò)展節(jié)節(jié)點(diǎn)n，生成n的所所有子節(jié)節(jié)點(diǎn)把這些些子節(jié)點(diǎn)點(diǎn)都放入入OPEN表，并為每每一個(gè)子子節(jié)點(diǎn)設(shè)設(shè)置指向向父節(jié)點(diǎn)點(diǎn)n的指指針計(jì)算這這些子節(jié)節(jié)點(diǎn)及其其先輩節(jié)節(jié)點(diǎn)的h值轉(zhuǎn)（2）不是“終終止節(jié)點(diǎn)點(diǎn)”且不不可擴(kuò)展展標(biāo)記n為不可可解節(jié)點(diǎn)點(diǎn)在T上上應(yīng)用不不

41、可解標(biāo)標(biāo)記過(guò)程程，對(duì)n的先輩輩節(jié)點(diǎn)中中的所有有不可解解節(jié)點(diǎn)進(jìn)進(jìn)行標(biāo)記記如果初初始節(jié)點(diǎn)點(diǎn)S0被被標(biāo)記為為不可解解，則問(wèn)問(wèn)題無(wú)解解，失敗敗退出否則，從OPEN表表中刪去去具有不不可解先先輩的所所有節(jié)點(diǎn)點(diǎn)轉(zhuǎn)（2）與或樹(shù)示示例：設(shè)設(shè)：在在搜索過(guò)過(guò)程中每每次擴(kuò)展展兩層且且按一層層或節(jié)點(diǎn)點(diǎn)、一層層與節(jié)點(diǎn)點(diǎn)的間隔隔方式進(jìn)進(jìn)行擴(kuò)展展按和計(jì)計(jì)算。10、S0擴(kuò)擴(kuò)展兩層層判斷：右右子樹(shù)為為當(dāng)前的的T按“和”計(jì)算20、擴(kuò)展E30計(jì)算T右子樹(shù)h(s0)=12左子樹(shù)h(s0)=9所以T應(yīng)應(yīng)改為左左子樹(shù)按“和”計(jì)算40、擴(kuò)展B因 H，I可解解，調(diào)用用可解標(biāo)標(biāo)記過(guò)程程得：G，B可可解計(jì)算T，仍是左左子樹(shù)刪除可解解節(jié)點(diǎn)的的后裔

42、（B的后后裔）50、擴(kuò)展CN，P可可解，調(diào)調(diào)用可解解標(biāo)記過(guò)過(guò)程得：M，C，A可可解，所以推出出S0為為可解節(jié)節(jié)點(diǎn)，結(jié)結(jié)束。五、博弈弈樹(shù)的啟啟發(fā)式搜搜索1、博弈弈樹(shù)諸如下棋棋、打牌牌、競(jìng)技技、戰(zhàn)爭(zhēng)爭(zhēng)等一類(lèi)類(lèi)競(jìng)爭(zhēng)性性智能活活動(dòng)稱(chēng)為為博弈。博弈樹(shù)：以一方方立場(chǎng)（我方）來(lái)看博博弈過(guò)程程用圖表表示出來(lái)來(lái)，得到到的與或或樹(shù)初始節(jié)點(diǎn)點(diǎn)為博弈弈的初始始格局。與或節(jié)點(diǎn)點(diǎn)交替出出現(xiàn)，我我方擴(kuò)展展節(jié)點(diǎn)之之間是“或”的的關(guān)系，敵方為為“與”節(jié)點(diǎn)。使我方獲獲勝的終終局都是是本原問(wèn)問(wèn)題，使使敵方獲獲勝的終終局都是是不可解解節(jié)點(diǎn)博弈的特特點(diǎn)：二二人零和和，全信信息，非非偶然二人零和和：結(jié)果果必有一一方獲勝勝，或平平局。全信息：參與者者都了解解對(duì)手當(dāng)當(dāng)前和過(guò)過(guò)去的走走步，也也可以推推測(cè)出將將要走的的招術(shù)。非偶然:根據(jù)當(dāng)前前情況（一般不不能看到到終局），選取對(duì)自自己最為為有利而而對(duì)對(duì)方方最為不不利的對(duì)對(duì)策如何找到到博弈必必勝的策策略思路：盡盡選擇對(duì)對(duì)自己有有利的方方案，向向前盡量量多看幾幾步基本概念念靜態(tài)估值值：每個(gè)個(gè)結(jié)點(diǎn)的的勢(shì)態(tài)估估計(jì)值。倒推值：由每個(gè)個(gè)結(jié)點(diǎn)的的靜態(tài)估估值倒推推出父結(jié)結(jié)點(diǎn)的估估計(jì)值?；蚬?jié)點(diǎn)(MAX節(jié)點(diǎn))，其倒倒推值選選 取各各分枝中中最大值值。與節(jié)點(diǎn)(MIN節(jié)點(diǎn))，其倒倒推值選選取各分分枝中最最小值。基本思想想(極大大極小法法)。以