人工智能原理及應(yīng)用第5章搜索求解策略PrinciplesandApplicationsofArtificialIntelligence第5章搜索求解策略

5.1

搜索的概念

5.2

狀態(tài)空間表示法

5.3

盲目的圖搜索策略

5.4

啟發(fā)式圖搜索策略搜索的概念問題求解：解空間搜索

已知解空間未知解空間搜索的概念問題求解：解空間搜索

連續(xù)搜索空間搜索的概念問題求解：解空間搜索

連續(xù)搜索空間離散搜索空間旅行商問題、背包問題、作業(yè)流水線調(diào)度問題…圍棋對弈、象棋對弈、投資博弈…機器人路徑規(guī)劃、災(zāi)難逃生規(guī)劃、戰(zhàn)場火力配置規(guī)劃…搜索的概念問題求解：解空間搜索

解的表示形式搜索的策略窮舉搜索啟發(fā)式搜索搜索的概念搜索：從問題初始狀態(tài)到目標(biāo)狀態(tài)的一條路線正向搜索:從初始狀態(tài)出發(fā)逆向搜索:從目標(biāo)狀態(tài)出發(fā)

選擇應(yīng)用操作算子初始狀態(tài)新狀態(tài)目標(biāo)狀態(tài)？終止YN搜索的概念搜索：從問題初始狀態(tài)到目標(biāo)狀態(tài)的一條路線盲目搜索:按固定步驟進行搜索啟發(fā)式搜索:運用領(lǐng)域知識指導(dǎo)搜索過程

選擇應(yīng)用操作算子初始狀態(tài)新狀態(tài)目標(biāo)狀態(tài)？終止YN搜索的概念搜索：從問題初始狀態(tài)到目標(biāo)狀態(tài)的一條路線是否一定能找到一個解？是否能找到最優(yōu)解？搜索是否會終止？搜索所需的時間和空間復(fù)雜性？

選擇應(yīng)用操作算子初始狀態(tài)新狀態(tài)目標(biāo)狀態(tài)？終止YN狀態(tài)空間表示法基本定義狀態(tài)(State):描述問題在任一時刻所處狀況的一種數(shù)據(jù)結(jié)構(gòu)初始狀態(tài)S0/目標(biāo)狀態(tài)集G操作(Operator):狀態(tài)之間的轉(zhuǎn)換函數(shù)狀態(tài)空間(StateSpace):四元組<S,O,S0,G>

狀態(tài)空間表示法（例）八數(shù)碼問題問題描述:33的棋盤上，放有1~8的數(shù)字，另有一格為空?？崭裆舷伦笥业臄?shù)字可移動到空格。問從某個狀態(tài)出發(fā)，如何確定移動序列，最終到達圖示的目標(biāo)狀態(tài)。狀態(tài)結(jié)構(gòu):長度為9的向量（數(shù)組）S0=[2,3,1,5,0,8,4,6,7]G={[1,2,3,8,0,4,7,6,5]}操作Left:A[p0]A[p01] (p0%3>0)Right:A[p0]A[p0+1] (p0%3<2)Up:A[p0]A[p03] (p03)Down:A[p0]

A[p0+3] (p0<6)2315846712384765初始狀態(tài)目標(biāo)狀態(tài)狀態(tài)空間表示法（例）修道士與野人問題問題描述:河的左岸有3個修道士、3個野人和一條船。修道士和野人都會劃船，船上每次最多只能坐兩個人；任何岸邊只要野人的數(shù)目多于修道士數(shù)目，修道士就會被野人吃掉。安排一個安全的方案將修道士和野人都渡到河的右岸。狀態(tài)結(jié)構(gòu):?操作:?狀態(tài)空間表示法（例）修道士與野人問題問題描述:河的左岸有3個修道士、3個野人和一條船。修道士和野人都會劃船，船上每次最多只能坐兩個人；任何岸邊只要野人的數(shù)目多于修道士數(shù)目，修道士就會被野人吃掉。安排一個安全的方案將修道士和野人都渡到河的右岸。狀態(tài)結(jié)構(gòu):三元組<m,c,b>S0=[3,3,1]G={[0,0,0]}操作:Lij,RijL01L10L11L02L20R01R10R11R02R20狀態(tài)空間表示法（例）修道士與野人問題問題描述:河的左岸有3個修道士、3個野人和一條船。修道士和野人都會劃船，船上每次最多只能坐兩個人；任何岸邊只要野人的數(shù)目多于修道士數(shù)目，修道士就會被野人吃掉。安排一個安全的方案將修道士和野人都渡到河的右岸。狀態(tài)空間表示法狀態(tài)空間的圖描述結(jié)點：狀態(tài)邊：狀態(tài)轉(zhuǎn)換操作求解過程：尋找圖中從初始狀態(tài)到目標(biāo)狀態(tài)的一條路徑（操作序列）搜索算法：操作序列的選擇方法狀態(tài)空間表示法（例）旅行商問題問題描述:尋找從網(wǎng)絡(luò)圖中的一個結(jié)點出發(fā)、歷經(jīng)其它結(jié)點并最終回到原結(jié)點的一條最短路徑。狀態(tài)結(jié)構(gòu):?操作:?狀態(tài)空間表示法（例）最短路徑問題問題描述:尋找從網(wǎng)絡(luò)圖中的兩個結(jié)點之間的一條最短路徑。狀態(tài)結(jié)構(gòu):?操作:?狀態(tài)空間表示法（例）最短路徑問題問題描述:尋找從網(wǎng)絡(luò)圖中的兩個結(jié)點之間的一條最短路徑。SP(a,e)SP(b,e)SP(c,e)SP(d,e)181028SP(c,e)SP(d,e)2433(b,e)15狀態(tài)空間表示法與/或樹（問題歸約法）將復(fù)雜問題分解（歸約）為一系列較簡單的問題，通過對簡單問題的求解來實現(xiàn)對原問題的求解。與樹:從所有子問題的解可得出原問題的解或樹:從任一子問題的解可得出原問題的解狀態(tài)空間表示法與/或樹（問題歸約法）盲目的圖搜索策略盲目搜索:按預(yù)定方向進行搜索Open:待展開的結(jié)點列表Closed:已展開過的結(jié)點列表初始化:將S0狀態(tài)放入Open表達到目標(biāo)狀態(tài)？搜索成功YNOpen表為空?搜索失敗從Open表中取出一個當(dāng)前結(jié)點擴展當(dāng)前結(jié)點,將未出現(xiàn)的子結(jié)點加入Open表YN盲目的圖搜索策略盲目搜索:按預(yù)定方向進行搜索寬度優(yōu)先搜索:Open表先進先出初始化:將S0狀態(tài)放入Open表達到目標(biāo)狀態(tài)？搜索成功YNOpen表為空?搜索失敗從Open表中取出一個當(dāng)前結(jié)點擴展當(dāng)前結(jié)點,將未出現(xiàn)的子結(jié)點加入Open表YN盲目的圖搜索策略盲目搜索:按預(yù)定方向進行搜索寬度優(yōu)先搜索:Open表先進先出深度優(yōu)先搜索:Open表先進后出初始化:將S0狀態(tài)放入Open表達到目標(biāo)狀態(tài)？搜索成功YNOpen表為空?搜索失敗從Open表中取出一個當(dāng)前結(jié)點擴展當(dāng)前結(jié)點,將未出現(xiàn)的子結(jié)點加入Open表YN啟發(fā)式圖搜索策略啟發(fā)式搜索:利用問題領(lǐng)域知識指導(dǎo)搜索過程代價優(yōu)先搜索:Open表按結(jié)點代價函數(shù)排列初始化:將S0狀態(tài)放入Open表達到目標(biāo)狀態(tài)？搜索成功YNOpen表為空?搜索失敗從Open表中取出一個當(dāng)前結(jié)點擴展當(dāng)前結(jié)點,將未出現(xiàn)的子結(jié)點加入Open表YN啟發(fā)式圖搜索策略啟發(fā)式搜索:利用問題領(lǐng)域知識指導(dǎo)搜索過程代價優(yōu)先搜索:Open表按結(jié)點代價函數(shù)排列abcd181028啟發(fā)式圖搜索策略啟發(fā)式搜索:利用問題領(lǐng)域知識指導(dǎo)搜索過程代價優(yōu)先搜索:Open表按結(jié)點代價函數(shù)排列abcd181028d20b24啟發(fā)式圖搜索策略啟發(fā)式搜索:利用問題領(lǐng)域知識指導(dǎo)搜索過程代價優(yōu)先搜索:Open表按結(jié)點代價函數(shù)排列abcd181028e15cd2416d20啟發(fā)式圖搜索策略啟發(fā)式搜索:利用問題領(lǐng)域知識指導(dǎo)搜索過程代價優(yōu)先搜索:Open表按結(jié)點代價函數(shù)排列abcd181028e15e12bc1620d20啟發(fā)式圖搜索策略A搜索算法代價優(yōu)先搜索:Open表按結(jié)點代價函數(shù)排列估價函數(shù):f(n)=g(n)+h(n)初始化:將S0狀態(tài)放入Open表達到目標(biāo)狀態(tài)？搜索成功YNOpen表為空?搜索失敗從Open表中取出一個當(dāng)前結(jié)點擴展當(dāng)前結(jié)點未出現(xiàn)的子結(jié)點:加入Open表已在Open表中但代價更小:更新Open表已在Closed表中但代價更小:移入Open表YN啟發(fā)式圖搜索策略A*搜索算法代價優(yōu)先搜索:Open表按結(jié)點代價函數(shù)排列估價函數(shù):f(n)=g(n)+h(n)滿足h(n)h*(n),其中h*(n)為狀態(tài)n到目標(biāo)狀態(tài)的最優(yōu)路徑代價啟發(fā)式圖搜索策略A*搜索算法可采納:存在最短求解路徑時，必能找到它單調(diào)性:h(c)h(p)

cost(p,c),h(G)=0啟發(fā)性:h(n)越大，啟發(fā)性越好啟發(fā)式圖搜索策略其它啟發(fā)策略局部最優(yōu):擴展當(dāng)前節(jié)點時，選擇估價最小的一個后繼節(jié)點作為下一個考察節(jié)點分支限界:如代價函數(shù)單調(diào)增長，設(shè)已找到的最優(yōu)解代價為c*，則剪去所有代價已超過c*的結(jié)點abcd181028ed1520b24cd2416與／或樹搜索策略可解標(biāo)示:由可解子節(jié)點來確定父節(jié)點為可解節(jié)點不可解標(biāo)示:由不可解子節(jié)點來確定父節(jié)點為不可解節(jié)點將初始問題放入Open表當(dāng)前問題為葉結(jié)點？可解性標(biāo)示YNOpen表為空?搜索失敗從Open表中取出一個當(dāng)前結(jié)點分解當(dāng)前問題,將未出現(xiàn)的子結(jié)點加入Open表YN搜索成功YN確定S0可解性?與／或樹搜索策略深度優(yōu)先廣度優(yōu)先代價優(yōu)先博弈樹搜索策略博弈樹的搜索過程博弈具有“二人零和、全信息、非偶然”的特征。

（1）二人零和：對壘的MAX、MIN雙方輪流采取行動，博弈的結(jié)果只有三種情況：MAX方勝，MIN??；MIN方勝，MAX方敗；和局。

（2）全信息：在對壘過程中，任何一方都了解當(dāng)前的格局及過去的歷史。 （3）非偶然：任何一方在采取行動前都要根據(jù)當(dāng)前的實際情況，進行得失分忻，選取對自己最為有利而對對方最為不利的對策，不存在擲骰子之類的“碰運氣”因素。即雙方都是理智地決定自己的行動。

博弈樹搜索策略博弈樹的搜索過程如果站在某一方（如MAX方，即MAX要取勝)，把上述博弈過程用圖表示出來，則得到的是一棵“與／或樹”。描述博弈過程的與或樹稱為博弈樹。 （1）博弈的初始格局是初始節(jié)點。 （2）在博弈樹中，“或”節(jié)點和“與”節(jié)點是逐層交替出現(xiàn)的。自己一方擴展的節(jié)點之間是“或”關(guān)系，對方擴展的節(jié)點之間是“與”關(guān)系。雙方輪流地擴展節(jié)點。 （3）所有自己一方獲勝的終局都是本原問題，相應(yīng)的節(jié)點是可解節(jié)點；所有使對方獲勝的終局都認為是不可解節(jié)點。博弈樹搜索策略極大極小分析法極大極小分析法的基本思想是： （1）設(shè)博弈的雙方中一方為A，另一方為B。極大極小分析法是為其中的一方（例如A方）尋找一個最優(yōu)行動方案的方法。 （2）為了找到當(dāng)前的最優(yōu)行動方案，需要對各個方案可能產(chǎn)生的后果進行比較。 （3）為了計算得分，需要根據(jù)問題的特性信息定義一個估價函數(shù)，用來估算當(dāng)前博弈樹端節(jié)點的得分，稱為靜態(tài)估值。 （4）當(dāng)端節(jié)點的估值計算出來后，再推算出父節(jié)點的得分。 （5）如果一個行動方案能獲得較大的倒推值，則它就是當(dāng)前最好的行動方案。

博弈樹搜索策略極大極小分析法博弈樹的啟發(fā)式搜索算法：

（1）k=1，初始棋局Sk=S1;

（2）如果棋局Sk是終止節(jié)點棋局，則算法成功終止；否則，由棋局Sk生成A方所有可能的或關(guān)系子節(jié)點Si(i=1,2,…,n)。（3）對每一個或關(guān)系子節(jié)點Si，生成其B方所有可能的與關(guān)系子節(jié)點Sj

(i=1,2,…,n)

。生成節(jié)點數(shù)為n×m+1的部分博弈樹。（4）計算每個與關(guān)系子節(jié)點Si的啟發(fā)函數(shù)值Sj。博弈樹搜索策略極大極小分析法（5）分別由m個與關(guān)系子節(jié)點倒推計算其父節(jié)點（與節(jié)點）的啟發(fā)函數(shù)值:

（6）由n個或關(guān)系子節(jié)點倒推計算其父節(jié)點Sk（或節(jié)點）的啟發(fā)函數(shù)值：（7）A方從Sk的n個或關(guān)系子節(jié)點中選擇節(jié)點i作為最優(yōu)行動方案，獲得棋局Si。 （8）B方從Si的m個與關(guān)系子節(jié)點中選擇節(jié)點j作為最優(yōu)行動方案，獲得棋局Sj。（9）若節(jié)點j是端節(jié)點，則算法終止；否則令k=j，轉(zhuǎn)步驟（2）。博弈樹搜索策略極大極小分析法一字棋游戲。設(shè)有一個三行三列的棋盤，如圖5-27所示，兩個棋手輪流走步，每個棋手走步時往空格上擺一個自己的棋子，誰先使自己的棋子成三子一線為贏。設(shè)A方的棋子用×標(biāo)記，B方的棋子用○標(biāo)記，并規(guī)定A方先走步。

博弈樹搜索策略極大極小分析法【解】（1）啟發(fā)函數(shù)定義

A方的啟發(fā)函數(shù)定義為

B方的啟發(fā)函數(shù)定義為 其中，ea(Si)為形成棋局Si時，A方棋子×可能占滿行、列和對角線的數(shù)目；eb(Si)為形成棋局Si時，B方棋子○可能占滿行、列和對角線的數(shù)目。博弈樹搜索策略極大極小分析法（2）A方第一回合博弈樹

博弈樹搜索策略-剪枝

（1）對于一個與節(jié)點MIN，若能估計出其倒推值的上