人工智能 AI講稿5(搜索student)

人工智能（ArtificialIntelligence）基本原理福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院陳昭炯1/13/20231精品ppt第六章搜索策略基本概念

狀態(tài)空間的搜索策略

與/或樹的搜索策略

搜索的完備性與效率一般圖的搜索過程廣度優(yōu)先搜索深度優(yōu)先搜索有界深度優(yōu)先搜索代價(jià)樹的廣度優(yōu)先搜索代價(jià)樹的深度優(yōu)先搜索啟發(fā)式搜索A*算法與/或樹的一般搜索過程與/或樹的廣度優(yōu)先搜索與/或樹的深度優(yōu)先搜索與/或樹的有序搜索博弈樹的啟發(fā)式搜索－剪枝技術(shù)搜索的含義狀態(tài)空間表示法與/或樹表示法2精品ppt搜索的含義依問題的實(shí)際情況尋找可利用的知識，構(gòu)造代價(jià)較少的推理路徑從而解決問題的過程離散的問題通常沒有統(tǒng)一的求解方法搜索策略的優(yōu)劣涉及能否找到最好的解、計(jì)算時(shí)間、存儲空間等搜索分為盲目搜索和啟發(fā)式搜索盲目搜索：按預(yù)定的策略進(jìn)行搜索，未用問題相關(guān)的或中間信息改進(jìn)搜索。效率不高，難求解復(fù)雜問題，但不失可用性啟發(fā)式搜索：搜索中加入問題相關(guān)的信息加速問題求解，效率較高，但啟發(fā)式函數(shù)不易構(gòu)造討論的問題有哪些常用的搜索算法?－問題有解時(shí)能否找到解?(完備性)找到的解是最佳的嗎？(最優(yōu)性)－什么情況下可以找到最佳解？求解的效率如何?（時(shí)間、空間復(fù)雜度）基本概念3精品ppt狀態(tài)空間表示法狀態(tài)：描述問題求解中任一時(shí)刻的狀況；變量的有序組合算符：一個(gè)狀態(tài)→另一狀態(tài)的操作狀態(tài)空間：{狀態(tài)，算符}表示,描述形式＋算符問題求解過程：初始狀態(tài)：描述問題求解中的初始狀況算符：一個(gè)狀態(tài)→另一狀態(tài)的操作目標(biāo)測試：確定給定的狀態(tài)是否為目標(biāo)狀態(tài)路徑耗散函數(shù)：設(shè)定每一步算符操作的耗散值問題的解：從初始狀態(tài)到目標(biāo)狀態(tài)的路徑最優(yōu)解：所有解中耗散值最小的解4精品ppt例：二階梵塔問題狀態(tài)描述：（SA,SB）可能狀態(tài)：S0=(1,1),S=(1,2),S=(1,3),S=(2,1),Sg=(2,2),S=(2,3)S=(3,1),S=(3,2),Sg=(3,3)算符：A(i,j)—將A從i軸移至j軸;B(i,j)—將B從i軸移至j軸可能算符：A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2)B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)5精品ppt猴子摘香蕉問題abc6精品ppt操作符：Goto(u):猴子走到u處(w,t,x,y,0)→(u,t,x,y,0)Push(v):猴子推箱到v處(w,t,w,0,0)→(v,t,v,0,0)Climb:猴子爬上箱子(w,t,w,0,0)→(w,t,w,1,0)Grasp:猴子拿到香蕉(a,a,a,1,0)→(a,a,a,1,1)狀態(tài)：(w,t,x,y,z)w:猴子的水平位置{a,b,c}t:天花板上香蕉對應(yīng)的地面位置{a,b,c}x:箱子的水平位置{a,b,c}y:猴子是否在箱子上{0,1}z:猴子是否拿到香蕉{0,1}初始狀態(tài)：(c,a,b,0,0)目標(biāo)狀態(tài)：(a,a,a,1,1)可能狀態(tài)：(b,a,b,0,0)(c,a,c,1,0)(c,a,c,1,1)……7精品ppt例：修道士與野人問題(1968)S0：河左岸有3個(gè)Missionaries和3個(gè)Cannibals,1條boat條件：1）M和C都會(huì)劃船，船一次只能載2人2）在任一岸上，M人數(shù)不得少于C的人數(shù)，否則被吃目標(biāo)：安全抵達(dá)對岸左岸：(m,c,b)：0≤m,c≤3，b∈{0,1}S0：(3,3,1)Sg：(0,0,0)狀態(tài)總數(shù)：4×4×2＝32種，但合法狀態(tài)16種8精品ppt(3,3,1)(3,1,0)(2,2,0)(3,2,0)(3,2,1)(3,0,0)(3,1,1)(1,1,0)(2,2,1)(0,2,0)(0,3,1)(0,1,0)(0,2,1)(0,0,0)0<x+y≤2:(x,y)=(2,0),(0,2),(1,1),(1,0),(0,1)(1,1,1)9精品ppt例：皇后問題初始狀態(tài)：棋盤上無皇后算符：將皇后添加到棋盤上的任一空格目標(biāo)測試：8皇后都在棋盤上，且互相攻擊不到路徑耗散函數(shù)：每一步耗散值1將4個(gè)皇后放到棋盤中，使得彼此不會(huì)攻擊到（不同行、不同列、不同對角線）返回8皇后，92種解找到一般n皇后問題復(fù)雜度為O(n)的算法(1989)QQQQ10精品ppt2831647512384765例：八數(shù)碼游戲8-Puzzle（九宮重排問題）sliding-blockpuzzle初始狀態(tài)：任一狀態(tài)都可為初始狀態(tài)算符：將空位移向四個(gè)方向目標(biāo)測試：確定當(dāng)前狀態(tài)是否為目標(biāo)狀態(tài)路徑耗散函數(shù)：每一步耗散值1其狀態(tài)可以劃分為兩個(gè)不相交的集合。(證明)8數(shù)碼，9！/2＝181440；15數(shù)碼，1.3萬億；24數(shù)碼,1025一般n×n數(shù)碼是NP完全問題（1986）11精品ppt例：TSP問題TravelingSalesmanProblem從某城市出發(fā)遍歷所有n個(gè)城市一遍且僅一遍再回到出發(fā)地，求最短路徑初始狀態(tài)：在某一城市算符：移向下一個(gè)未訪問過的城市目標(biāo)測試：是否處于出發(fā)地且訪問過所有城市一次路徑耗散函數(shù)：路程長度，旅行費(fèi)用等NogeneralmethodofsolutionisknownNP－h(huán)ard(Karp,1972)有效的啟發(fā)式算法（1973）完全多項(xiàng)式近似方案（1998）12精品ppt與/或樹表示法（分解，分治）與樹或樹與或樹13精品ppt例：三階梵塔問題狀態(tài)描述：（SC,SB,SA)(1,1,1)→(3,3,3)(1,2,2,)→(3,2,2)(1,1,1)→(1,2,2)(3,2,2)→(3,3,3)(1,1,1)→(1,1,3)(1,1,3)→(1,2,3)(1,2,3)→(1,2,2)(3,2,2)→(3,2,1)(3,2,1)→(3,3,1)(3,3,1)→(3,3,3)14精品ppt本原問題:不可分解，直接可解的問題端節(jié)點(diǎn)：無子節(jié)點(diǎn)的節(jié)點(diǎn)終止節(jié)點(diǎn)：本原問題對應(yīng)的節(jié)點(diǎn)，可解可解/不可解節(jié)點(diǎn)：端節(jié)點(diǎn)，或節(jié)點(diǎn)，與節(jié)點(diǎn)解樹：始節(jié)點(diǎn)（可解）＋可解節(jié)點(diǎn)15精品ppt若干應(yīng)用實(shí)例尋徑問題：計(jì)算機(jī)網(wǎng)絡(luò)的路由，軍事行動(dòng)的規(guī)劃，飛機(jī)航線旅行規(guī)劃系統(tǒng)，機(jī)器人導(dǎo)航（尋徑問題拓廣）旅行問題：電路板自動(dòng)鉆孔機(jī)的運(yùn)動(dòng)規(guī)劃，倉庫貨物碼放機(jī)的運(yùn)動(dòng)規(guī)劃超大規(guī)模集成電路的布局：在一個(gè)芯片上放置上百萬個(gè)元器件及連線，還要達(dá)到芯片面積最小、電路延遲最小、雜散電容最小和產(chǎn)量最大。單元布局和通道尋徑（1991）自動(dòng)裝配排序：找到一個(gè)裝配物體（電動(dòng)機(jī)）各部件的次序蛋白質(zhì)設(shè)計(jì)：尋找一個(gè)氨基酸序列，當(dāng)該序列疊放在3D的蛋白質(zhì)結(jié)構(gòu)里，可治愈某種疾病因特網(wǎng)搜索：尋找問題的答案、相關(guān)信息等16精品ppt一般圖的搜索過程OPEN表：存放剛生成的節(jié)點(diǎn)CLOSED表：存放當(dāng)前將要擴(kuò)展和前面已擴(kuò)展的節(jié)點(diǎn)擴(kuò)展一個(gè)節(jié)點(diǎn)：生成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)，并給出它們之間的耗散值。狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)編號狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)狀態(tài)空間的搜索策略17精品ppt1）S0→OPEN，S0→G0，2）OPEN=Nil→無解；否則3）OPEN的第一個(gè)節(jié)點(diǎn)→CLOSED，記為n4）節(jié)點(diǎn)n=目標(biāo)→得解；否則5）擴(kuò)展節(jié)點(diǎn)n,M={n擴(kuò)展出的子節(jié)點(diǎn)－n的先輩}；G

n-1∪M→G

n6)處理M，x∈M,考慮①ifx

G

n-1

,x→OPEN;

②ifx∈

G

n-1(已生成過),判斷x的父節(jié)點(diǎn)是否需改變（依代價(jià)）③ifx∈

G

n-1

ANDx∈CLOSED(已擴(kuò)展過),判斷x的后繼節(jié)點(diǎn)的父指針是否需改變7）按某種搜索策略對OPEN表排序①隊(duì)列方式(FIFO)：廣度優(yōu)先;②堆棧方式（LIFO）：深度優(yōu)先8）轉(zhuǎn)2）18精品ppt已擴(kuò)展(∈CLOSED)已生成，未擴(kuò)展(∈OPEN)選中當(dāng)前正擴(kuò)展19精品ppt已擴(kuò)展(∈CLOSED)已生成，未擴(kuò)展(∈OPEN)選中當(dāng)前正擴(kuò)展20精品ppt已擴(kuò)展(∈CLOSED)已生成，未擴(kuò)展(∈OPEN)選中當(dāng)前正擴(kuò)展21精品ppt已擴(kuò)展(∈CLOSED)已生成，未擴(kuò)展(∈OPEN)選中當(dāng)前正擴(kuò)展22精品ppt1）不同的搜索策略只是OPEN表的排序不同，過程類似2）G稱為搜索圖，由節(jié)點(diǎn)及其父指針→搜索樹3）目標(biāo)找到后，其路徑由逐級上行的父指針構(gòu)成4）盲目搜索僅適用于樹結(jié)構(gòu)，不出現(xiàn)圖搜索中6）②③一些基本概念和記號節(jié)點(diǎn)深度： 根節(jié)點(diǎn)深度=0 其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+1012323精品ppt路徑的代價(jià)（耗散值） 一條路徑的代價(jià)（耗散值）等于連接這條路徑各節(jié)點(diǎn)間所有代價(jià)（耗散值）的總和。用C(xi,xj)表示從父節(jié)點(diǎn)xi到子節(jié)點(diǎn)xj的邊代價(jià)（耗散值）。代價(jià)樹：邊上標(biāo)有代價(jià)的樹狀結(jié)構(gòu)圖若干記號：S0－初始態(tài)；Sg－目標(biāo)態(tài)；g(x)－從S0到節(jié)點(diǎn)x的代價(jià)；g(xj)=g(xi)+C(xi,xj)h(x)－x到Sg最優(yōu)路徑的估計(jì)代價(jià)24精品ppt廣度優(yōu)先搜索1,G:=G0(G0=S0),OPEN:=(S0),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→M,Gn-1∪M→Gn;7,IFGOAL(atM)THENEXIT(SUCCESS);8,ADD(M,OPEN),并標(biāo)記M中的節(jié)點(diǎn)到n的指針;9,GOLOOP;ADD(x,y):添加x至y的尾部25精品ppt廣度優(yōu)先搜索23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標(biāo)8234187654生成的新節(jié)點(diǎn)按隊(duì)列方式壓入OPEN表底部（先進(jìn)先出）26精品ppt深度優(yōu)先搜索1,G:=G0(G0=S0),OPEN:=(S0),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→M,Gn-1∪M→Gn;7,IF目標(biāo)在M中THENEXIT(SUCCESS);8,ADD(OPEN,M),并標(biāo)記M中的節(jié)點(diǎn)到n的指針;9,GOLOOP;ADD(x,y):添加x至y的尾部27精品ppt深度優(yōu)先搜索231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標(biāo)28精品ppt廣度優(yōu)先搜索效率分析每個(gè)節(jié)點(diǎn)有b個(gè)后繼節(jié)點(diǎn)；解的深度為d最壞情況已生成的節(jié)點(diǎn)數(shù)＝深度節(jié)點(diǎn)數(shù)時(shí)間內(nèi)存211000.11s1M4111，10011s106M610719m10G(KM)810931h1T(KG)101011129d101T(KG)12101335y10P(KT)1410153523y1E(KP)b=10生成104個(gè)節(jié)點(diǎn)/s占用103bytes/node深度優(yōu)先搜索效率分析存儲的節(jié)點(diǎn)數(shù)＝bd+1；b=10,d=12,存儲空間＝118K；O(bd);百億倍29精品ppt深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí)，可能找不到解（無窮分支）最壞情況時(shí)，搜索空間等同于窮舉時(shí)間效率較低是一個(gè)通用的與問題無關(guān)的方法當(dāng)問題有解時(shí)，一定能找到解是一個(gè)通用的與問題無關(guān)的方法最壞情況時(shí)，搜索空間等同于窮舉時(shí)間、空間效率較低廣度優(yōu)先搜索的性質(zhì)30精品ppt有界深度優(yōu)先搜索（迭代深入）設(shè)定深度界限dm，找不到時(shí)逐漸加深避免搜索陷入某一無窮分支死循環(huán)問題有解一定可以找到解，但不一定最優(yōu)當(dāng)搜索空間很大且解的深度未知時(shí)，首選的盲目搜索法代價(jià)樹廣度優(yōu)先搜索每次擴(kuò)展的子節(jié)點(diǎn)返送回OPEN時(shí)，都對OPEN表所有點(diǎn)按代價(jià)從小到大重新排序代價(jià)樹深度優(yōu)先搜索從剛擴(kuò)展的子節(jié)點(diǎn)中選一個(gè)代價(jià)最小的送入CLOSED表中進(jìn)行擴(kuò)展回溯搜索每次只生成一個(gè)后繼節(jié)點(diǎn)而不是所有的后繼，內(nèi)存O(d)31精品ppt()回溯搜索例：皇后問題皇后問題32精品ppt()Q((1,1))33精品ppt()QQ((1,1))((1,1)(2,3))34精品ppt()Q((1,1))((1,1)(2,3))35精品ppt()QQ((1,1))((1,1)(2,3))((1,1)(2,4))36精品ppt()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))37精品ppt()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))38精品ppt()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))39精品ppt()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))40精品ppt()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))41精品ppt()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))42精品ppt()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))43精品ppt()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))44精品ppt例：找一條從A到E的最短路徑EEBDECEDBCA3334445522代價(jià)樹廣度優(yōu)先搜索是否需遍歷所有路徑才可確定最短？45精品ppt例：找一條從A到E的最短路徑EEBDECEDBCA3334445522代價(jià)樹廣度優(yōu)先搜索是否需遍歷所有路徑才可確定最短？46精品ppt例：找一條從A到E的最短路徑EEBDECEDBCA3334445522代價(jià)樹深度優(yōu)先搜索深度與廣度搜索擴(kuò)展的節(jié)點(diǎn)數(shù)相同47精品ppt啟發(fā)式搜索設(shè)計(jì)一個(gè)與問題相關(guān)的估價(jià)函數(shù)，用于評價(jià)各節(jié)點(diǎn)的重要程度按照節(jié)點(diǎn)的重要性次序，亦即估價(jià)函數(shù)從小到大的順序擴(kuò)展節(jié)點(diǎn)估價(jià)函數(shù)的形式：f(x)=g(x)+h(x)g(x)－從S0到節(jié)點(diǎn)x已付出的代價(jià)；

h(x)－x到Sg最優(yōu)路徑的估計(jì)代價(jià);g(x)比例越大，越傾向廣度優(yōu)先搜索，完備性較好而效率可能受影響；h(x)比例越大，越傾向深度優(yōu)先搜索，效率可能較好；加權(quán)調(diào)整比例,引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。48精品ppt例：B:Black;W:White;E:Empty;將B全移至W右邊；至多移3位；移i位代價(jià)為i，i=1,2,3BBBWWWEh(x)=3×∑{每個(gè)W左邊B的個(gè)數(shù)}；還有？BBBWWWEBBBEWWWBBBWEWWBBBWWEW3+272+271+27BBEWWBW4+21EBBWWBWBEBWWBWBBWEWBWBBWWEBW6+215+215+216+21BWBEWBWBWBWEBW7+188+18EWBBWBWBWEBWBWBWBBWEW10+158+189+18WEBBWBW11+1549精品ppt局部擇優(yōu)搜索（瞎子爬山法）對剛擴(kuò)展的子節(jié)點(diǎn)計(jì)算f(x)，選取其中f(x)最小的一個(gè)節(jié)點(diǎn)→CLOSED表進(jìn)行擴(kuò)展深度優(yōu)先類搜索在此框架下可統(tǒng)一表示為：－深度優(yōu)先：記深度為d(x)，則f(x)=-d(x)－代價(jià)樹深度優(yōu)先：f(x)=C(xi,xj)全局擇優(yōu)搜索每次對OPEN表中所有節(jié)點(diǎn)計(jì)算f(x)，選取其中最小的一個(gè)節(jié)點(diǎn)→CLOSED表進(jìn)行擴(kuò)展廣優(yōu)先類搜索在此框架下可統(tǒng)一表示為：－廣度優(yōu)先：記深度為d(x)，則f(x)=d(x)－代價(jià)樹廣度優(yōu)先：f(x)=g(x)50精品ppt定義評價(jià)函數(shù)1： f1(n)=g(n)+h1(n) g(n)為從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗散值（深度） h1(n)為當(dāng)前節(jié)點(diǎn)“不在位”的將牌數(shù)

2831647512384765例：九宮重排問題 h1(n)=42

831

64751234576851精品ppt2831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目標(biāo)123456全局擇優(yōu)搜索52精品ppt定義評價(jià)函數(shù)2： f2(n)=g(n)+h1(n) g(n)為從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗散值（深度） h2(n)為數(shù)字移到目標(biāo)處的距離總和

2

831

6475h2(n)＝1＋1＋1＋2＝51238476553精品ppt283164752831476528316475283164752318476528314765283147652318476523184765123847651238476512378465s(5)A(7)B(5)C(7)D(7)E(5)F(7)I(5)J(7)K(5)L(5)M(7)目標(biāo)12345全局擇優(yōu)搜索54精品pptA*算法評價(jià)函數(shù)的格式：f(n)=g(n)+h(n) f(n)：評價(jià)函數(shù)；h(n)：啟發(fā)函數(shù)g*(n)：從S0到n的最短路徑的耗散值

h*(n)：從n到Sg的最短路徑的耗散值

f*(n)=g*(n)+h*(n)：從S0經(jīng)過n到Sg的最短路徑的耗散值

g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計(jì)值恒有：g(n)g*(n)且g(n)不增如果滿足可納條件：

h(n)≤h*(n)

則稱為A*算法。九宮問題解1九宮問題解255精品pptA*算法的性質(zhì)A*算法是可納的：對于可解狀態(tài)空間圖，A*算法在有限步內(nèi)終止并找到最優(yōu)解。在h(n)≤h*(n)的條件下，h(n)的值越大，攜帶的啟發(fā)式信息越多，擴(kuò)展的節(jié)點(diǎn)數(shù)越少，搜索效率越高。*若h(n)還滿足如下的單調(diào)性（一致）條件（三角不等式）*：

h(Sg)＝0h(xi)-h(xj)≤C(xi,xj)；xj

是xi

的后繼子節(jié)點(diǎn)則：1）若A*選擇xn進(jìn)行擴(kuò)展,就有：g(xn)=g*(xn)2）由A*擴(kuò)展的節(jié)點(diǎn)序列其f(n)值非遞減3）一般圖的搜索算法可簡化8數(shù)碼的兩種啟發(fā)式算法？56精品pptA*算法的不足與改進(jìn)：大多數(shù)情況節(jié)點(diǎn)數(shù)為解長度的指數(shù)級，存儲量過大，保留了所有生成的節(jié)點(diǎn)，不適用于大規(guī)模問題存儲限制的A*算法啟發(fā)式函數(shù)的精確度問題：解的深度迭代有界深度A*(h1)A*(h2)24681012141618202224101126806384471273644035613203993227539130130567276180943913561218253973113211363676121916418數(shù)碼問題擴(kuò)展的節(jié)點(diǎn)數(shù)57精品ppt與或樹的搜索策略與或樹的一般搜索過程搜索的目的是考察S0是否有解S0→擴(kuò)展（分解或等價(jià)變換）→設(shè)置父指針→選擇節(jié)點(diǎn)節(jié)點(diǎn)可解，其不可解的后裔節(jié)點(diǎn)可刪去節(jié)點(diǎn)不可解，其全部后裔節(jié)點(diǎn)可刪去標(biāo)示過程：1）判斷祖先節(jié)點(diǎn)的可解/不可解性2）刪去無用的后裔節(jié)點(diǎn)：58精品ppt：非終止節(jié)點(diǎn)：終止節(jié)點(diǎn)與或樹的廣度優(yōu)先搜索59精品ppt：非終止節(jié)點(diǎn)：終止節(jié)點(diǎn)與或樹的廣度優(yōu)先搜索60精品ppt：非終止節(jié)點(diǎn)：終止節(jié)點(diǎn)與或樹的廣度優(yōu)先搜索61精品ppt：非終止節(jié)點(diǎn)：終止節(jié)點(diǎn)與或樹的廣度優(yōu)先搜索62精品ppt：非終止節(jié)點(diǎn)：終止節(jié)點(diǎn)：從OPEN中刪去與或樹的廣度優(yōu)先搜索63精品ppt：非終止節(jié)點(diǎn)：終止節(jié)點(diǎn)：在CLOSED中，無需再考慮的節(jié)點(diǎn)與或樹的廣度優(yōu)先搜索64精品ppt：非終止節(jié)點(diǎn)：終止節(jié)點(diǎn)：在CLOSED中，無需再考慮的節(jié)點(diǎn)與或樹的廣度優(yōu)先搜索65精品ppt：非終止節(jié)點(diǎn)：終止節(jié)點(diǎn)：在CLOSED中，無需再考慮的節(jié)點(diǎn)與或樹的廣度優(yōu)先搜索66精品ppt：非終止節(jié)點(diǎn)：終止節(jié)點(diǎn)：在CLOSED中，無需再考慮的節(jié)點(diǎn)與或樹的廣度優(yōu)先搜索67精品ppt：非終止節(jié)點(diǎn)：終止節(jié)點(diǎn)：在CLOSED中，無需再考慮的節(jié)點(diǎn)與或樹的廣度優(yōu)先搜索68精品ppt：非終止節(jié)點(diǎn)：終止節(jié)點(diǎn)：在CLOSED中，無需再考慮的節(jié)點(diǎn)與或樹的廣度優(yōu)先搜索69精品ppt與或樹的有序搜索過程求代價(jià)最小解樹的方法分析節(jié)點(diǎn)被擴(kuò)展的代價(jià)，選擇擴(kuò)展代價(jià)最小的節(jié)點(diǎn)擴(kuò)展解樹的代價(jià)h(S0)計(jì)算準(zhǔn)則倒推，估算，每次刷新希望樹：由最有希望（依代價(jià)）成為最優(yōu)解樹的那一部分節(jié)點(diǎn)及其先輩（含S0）組成70精品ppt

:非終止節(jié)點(diǎn):終止節(jié)點(diǎn):不可解端節(jié)點(diǎn)11311562222211133468∞00000∞和代價(jià)計(jì)算右解樹：h(S0)=8左解樹：h(S0)=1371精品pptS033327邊代價(jià)為1：T樹8每次擴(kuò)展2層72精品pptS033211邊代價(jià)為1：T樹8223267773精品pptS03211邊代價(jià)為1：T樹：從OPEN中刪去82232677200262374精品pptS03211邊代價(jià)為1：T樹：從OPEN中刪去822326770023：在CLOSED中，無需再考慮的節(jié)點(diǎn)75精品pptS0211邊代價(jià)為1：T樹：從OPEN中刪去82232677002330026239：在CLOSED中，無需再考慮的節(jié)點(diǎn)76精品ppt博弈樹的啟發(fā)式搜索博弈過程：二人零和：博弈結(jié)果只有勝、負(fù)、平三種情況全信息：當(dāng)前及過往局勢全開放非偶然：雙方都理智決定行為（選擇最有利于己方的策略）博弈樹構(gòu)成初始格局記為S0“AND”和“OR”逐層交替出現(xiàn)，己方擴(kuò)展的為“OR”，對方為“AND”

使己方獲勝的終局為可解節(jié)點(diǎn)，對方獲勝的為不可解節(jié)點(diǎn)極大極小分析法端節(jié)點(diǎn)用估價(jià)函數(shù)估值，反推上層節(jié)點(diǎn)估值OR(Max),AND(Min)，直至根節(jié)點(diǎn)估值大的方案較好（