第5章搜索策略

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

5.1

搜索的概念

5.2

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

5.3

盲目的圖搜索策略

5.4

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

已知解空間未知解空間搜索的概念問(wèn)題求解：解空間搜索

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

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

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

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

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

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

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

（1）二人零和：對(duì)壘的MAX、MIN雙方輪流采取行動(dòng)，博弈的結(jié)果只有三種情況：MAX方勝，MIN?。籑IN方勝，MAX方?。缓途?。

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

博弈樹(shù)搜索策略博弈樹(shù)的搜索過(guò)程如果站在某一方（如MAX方，即MAX要取勝)，把上述博弈過(guò)程用圖表示出來(lái)，則得到的是一棵“與／或樹(shù)”。描述博弈過(guò)程的與或樹(shù)稱為博弈樹(shù)。 （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)。博弈樹(shù)搜索策略極大極小分析法極大極小分析法的基本思想是： （1）設(shè)博弈的雙方中一方為A，另一方為B。極大極小分析法是為其中的一方（例如A方）尋找一個(gè)最優(yōu)行動(dòng)方案的方法。 （2）為了找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對(duì)各個(gè)方案可能產(chǎn)生的后果進(jìn)行比較。 （3）為了計(jì)算得分，需要根據(jù)問(wèn)題的特性信息定義一個(gè)估價(jià)函數(shù)，用來(lái)估算當(dāng)前博弈樹(shù)端節(jié)點(diǎn)的得分，稱為靜態(tài)估值。 （4）當(dāng)端節(jié)點(diǎn)的估值計(jì)算出來(lái)后，再推算出父節(jié)點(diǎn)的得分。 （5）如果一個(gè)行動(dòng)方案能獲得較大的倒推值，則它就是當(dāng)前最好的行動(dòng)方案。

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

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

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

(i=1,2,…,n)

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

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

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

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

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

博弈樹(shù)搜索策略-剪枝

（1）對(duì)于一個(gè)與節(jié)點(diǎn)MIN，若能估計(jì)出其倒推值的上