圖搜索-圖搜索策略

1第三章搜索推理技術(shù)3.1圖搜索策略3.2盲目搜索3.3啟發(fā)式搜索問(wèn)題：知識(shí)表示有那些方法？知識(shí)表示的目的是什么？構(gòu)建智能系統(tǒng)的關(guān)鍵是什么？23.1圖搜索策略思考：狀態(tài)空間法的基本特點(diǎn)？基本推理方法？其求解結(jié)果是什么？簡(jiǎn)單回顧實(shí)例：猴子與香蕉。3用一個(gè)四元表列（W，x，Y，z）表示這個(gè)問(wèn)題狀態(tài)W猴子的水平位置x當(dāng)猴子在箱子頂上時(shí)取x=1；否則取x=0Y箱子的水平位置z 當(dāng)猴子摘到香蕉時(shí)取z=1；否則取z=0算符：

Goto（U），（W，0，Y，z）goto（U）（U，0，Y，z）

Pushbox（V），（W，0，W，z）pushbox（V）（V，0，V，z）Climbbox，（W，0，W，z）climbbox（W，1，W，z）Grasp，（c，1，c，0）grasp（c，1，c，1）3.1圖搜索策略4(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0）（c，1，c，1）（a，0，b，0）U=b，climbbox猴子和香蕉問(wèn)題的狀態(tài)空間圖提問(wèn)：人工搜索求解的解答？目標(biāo)狀態(tài)goto（U）goto（U）goto（U）U=b,pushbox（V）pushbox（V）goto（U）V≠c，climbboxV=c，climbbox3.1圖搜索策略5猴子和香蕉問(wèn)題自動(dòng)演示：

猴子香蕉箱子

猴子香蕉箱子

Ha!Ha!3.1圖搜索策略思考：計(jì)算機(jī)的搜索策略？6圖搜索控制策略:一種在圖中尋找路徑的方法。圖中每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)狀態(tài);每條連線對(duì)應(yīng)一個(gè)操作符。用產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫(kù)和規(guī)則來(lái)標(biāo)記：初始節(jié)點(diǎn)————初始數(shù)據(jù)庫(kù)；目標(biāo)節(jié)點(diǎn)————目標(biāo)數(shù)據(jù)庫(kù)；狀態(tài)圖的一條路徑問(wèn)題————求得把一個(gè)數(shù)據(jù)庫(kù)變換為另一數(shù)據(jù)庫(kù)的規(guī)則序列問(wèn)題。圖搜索過(guò)程（GraphSearch）3.1圖搜索策略7圖搜索的一般過(guò)程如下：1）建立一個(gè)只含有起始節(jié)點(diǎn)S的搜索圖G，把S放到一個(gè)叫做OPEN的未擴(kuò)展節(jié)點(diǎn)表中。2）建立一個(gè)叫做CLOSED的已擴(kuò)展節(jié)點(diǎn)表，其初始為空表.3）LOOP：若OPEN表是空表，則失敗退出。4）選擇OPEN表上的第一個(gè)節(jié)點(diǎn)，把它從OPEN表移出并放進(jìn)CLOSED表中。稱此節(jié)點(diǎn)為節(jié)點(diǎn)n5）若n為一目標(biāo)節(jié)點(diǎn)，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針將在第7步中設(shè)置)。3.1圖搜索策略86）擴(kuò)展節(jié)點(diǎn)n，同時(shí)生成不是n的祖先的那些后繼節(jié)點(diǎn)的集合M。把M的這些成員作為n的后繼節(jié)點(diǎn)添入圖G中。7）對(duì)那些未曾在G中出現(xiàn)過(guò)的M成員設(shè)置一個(gè)通向n的指針。把M的這些成員加進(jìn)OPEN表。對(duì)已經(jīng)在OPEN或CLOSED表上的每一個(gè)M成員，確定是否需更改通到n的指針?lè)较?。?duì)已在CLOSED表上的每個(gè)M成員，確定是否需要更改圖G中通向它的每個(gè)后裔節(jié)點(diǎn)的指針?lè)较颉?）按某一任意方式或按某個(gè)探試值，重排OPEN表。9）GOLOOP。3.1圖搜索策略9開(kāi)始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點(diǎn)嗎？把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針修改指針?lè)较蛑嘏臤PEN表失敗成功圖3.1

圖搜索過(guò)程框圖是是否否3.1圖搜索策略(1)(3)(4)(5)(6)(7)(7)(8)(9)OPENCLOSED(1)(2)寬度優(yōu)先10圖搜索的生成結(jié)果：搜索圖（G）搜索樹(shù)（T）修正算法：一次只生成一個(gè)后繼節(jié)點(diǎn)；思考：（1）結(jié)果路徑的形成中，為什么其節(jié)點(diǎn)順序是明確的？（2）OPEN表中的節(jié)點(diǎn)具有什么特點(diǎn)？（3）CLOSED表中的節(jié)點(diǎn)具有什么特點(diǎn)？（4）對(duì)OPEN表節(jié)點(diǎn)的排序有何意義？提出：盲目搜索與啟發(fā)式搜索。3.1圖搜索策略113.2盲目搜索盲目搜索又叫做無(wú)信息搜索，一般只適用于求解比較簡(jiǎn)單的問(wèn)題。特點(diǎn)：不需重排OPEN表；種類：寬度優(yōu)先、深度優(yōu)先、等代價(jià)搜索等。3.2.1寬度優(yōu)先搜索（Breadth-first）

定義：

以接近起始節(jié)點(diǎn)的程度逐層擴(kuò)展節(jié)點(diǎn)的搜索方法。特點(diǎn)：一種高代價(jià)搜索，但若有解存在，則必能找到它。12SLOMFPQNFFF寬度優(yōu)先搜索示意圖131）把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解答)。2）如果OPEN是個(gè)空表，則沒(méi)有解，失敗退出；否則繼續(xù)。3）把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。4）擴(kuò)展節(jié)點(diǎn)n。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第(2)步。5）把n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到n的指針。6）如果n的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出；否則轉(zhuǎn)向第(2)步。寬度優(yōu)先搜索算法：3.2盲目搜索14開(kāi)始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表是否有后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？擴(kuò)展n，把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針失敗成功圖3.2寬度優(yōu)先算法框圖是否是否3.2盲目搜索思考：與原始算法比較異同，寬度優(yōu)先的體現(xiàn)？15

例子

八數(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)，要擴(kuò)展26個(gè)節(jié)點(diǎn)，共生成46個(gè)節(jié)點(diǎn)之后才求得解（目標(biāo)節(jié)點(diǎn)）。3.2盲目搜索163.2盲目搜索173.2.2

深度優(yōu)先搜索(Dephth-first)

定義：

首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)。

特點(diǎn)：

防止搜索過(guò)程沿著無(wú)益的路徑擴(kuò)展下去，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度——深度界限。與寬度優(yōu)先搜索算法最根本的不同在于：將擴(kuò)展的后繼節(jié)點(diǎn)放在OPEN表的前端。3.2盲目搜索18深度優(yōu)先搜索示意圖SLOMFPQNFFF3.2盲目搜索19開(kāi)始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表是否有后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？擴(kuò)展n，把n的后繼節(jié)點(diǎn)放入OPEN表的前端，提供返回節(jié)點(diǎn)n的指針失敗成功圖3.6深度優(yōu)先算法框圖是否是否3.2盲目搜索節(jié)點(diǎn)n的深度等于最大深度？否20示范：有界深度(4)優(yōu)先的八數(shù)碼問(wèn)題深度優(yōu)先搜索樹(shù)？3.2盲目搜索1238456712384567（目標(biāo)狀態(tài)）（初始狀態(tài)）213.2盲目搜索223.2.3

等代價(jià)搜索

定義

是寬度優(yōu)先搜索的一種推廣，不是沿著等長(zhǎng)度路徑斷層進(jìn)行擴(kuò)展，而是沿著等代價(jià)路徑斷層進(jìn)行擴(kuò)展。搜索樹(shù)中每條連接弧線上的有關(guān)代價(jià),表示時(shí)間、距離等花費(fèi)。

算法

在等價(jià)搜索算法中，把從節(jié)點(diǎn)i到其后續(xù)節(jié)點(diǎn)j的連接弧線記為c(I,j),把從起始節(jié)點(diǎn)S到任一節(jié)點(diǎn)I的路徑代價(jià)記為g(i)。在搜索樹(shù)上，假設(shè)g(i)也是從起始節(jié)點(diǎn)S到節(jié)點(diǎn)的最少代價(jià)路徑上的代價(jià)。3.2盲目搜索思考：如何動(dòng)態(tài)計(jì)算g(i)?23開(kāi)始把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節(jié)點(diǎn)i從OPEN表移至CLOSED表是否有后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？失敗成功圖3.8等代價(jià)搜索算法框圖是否是否令g(s)=0S是否目標(biāo)節(jié)點(diǎn)？是成功否3.2盲目搜索擴(kuò)展i，計(jì)算其后繼節(jié)點(diǎn)j的g(j)，并把后繼節(jié)點(diǎn)放入OPEN表243.3啟發(fā)式搜索啟發(fā)式信息：用來(lái)加速搜索過(guò)程的問(wèn)題領(lǐng)域信息，一般與有關(guān)問(wèn)題具體領(lǐng)域背景有關(guān)，不一定具有通用性。啟發(fā)式搜索：利用啟發(fā)式信息的搜索方法特點(diǎn)：重排OPEN表，選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展種類：有序搜索、A*算法等基本步驟：初始化，判斷OPEN表是否為空，選擇節(jié)點(diǎn)n，判斷n是否目標(biāo)節(jié)點(diǎn)，擴(kuò)展節(jié)點(diǎn)n，重排OPEN表、調(diào)整指針，循環(huán)。各自特點(diǎn)：重排OPEN表的依據(jù)不同。盲目搜索可能帶來(lái)組合爆炸。思考：（1）圖搜索方法的基本步驟？（2）寬度優(yōu)先、深度優(yōu)先、等代價(jià)方法的特點(diǎn)？

（3）盲目搜索的缺點(diǎn)？253.3.1啟發(fā)式搜索策略和估價(jià)函數(shù)有序搜索（OrderedSearch）總是選擇“最有希望”的節(jié)點(diǎn)作為下一被擴(kuò)展節(jié)點(diǎn)估價(jià)函數(shù)（EvaluationFunction）為獲得某些節(jié)點(diǎn)“希望”的啟發(fā)信息，提供一個(gè)評(píng)定侯選擴(kuò)展節(jié)點(diǎn)的方法，以便確定哪個(gè)節(jié)點(diǎn)最有可能在通向目標(biāo)的最佳路徑上。

f(n)——表示節(jié)點(diǎn)n的估價(jià)函數(shù)值

應(yīng)用節(jié)點(diǎn)“希望”程度（估價(jià)函數(shù)值）重排OPEN表；有序搜索也稱為最佳優(yōu)先搜索；估價(jià)函數(shù)舉例：（1）棋局的得分；（2）距離目標(biāo)狀態(tài)的距離量度；（3）TSP問(wèn)題中的路徑；思考：f函數(shù)的計(jì)算，重排序的方法？3.3啟發(fā)式搜索263.3.2

有序搜索（OrderedSearch；Best－firstSearch）實(shí)質(zhì)：選擇OPEN表上具有最小f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。3.3啟發(fā)式搜索Nilsson（尼爾遜）方法：一個(gè)節(jié)點(diǎn)的“希望”越大，則其f值越小。被選擇的節(jié)點(diǎn)是估價(jià)函數(shù)最小的節(jié)點(diǎn)。思考：如果把寬度優(yōu)先、深度優(yōu)先、等代價(jià)搜索方法作為有序搜索的特例，那么它們的f

函數(shù)如何計(jì)算？ 舉例示范。27開(kāi)始把S放入OPEN表，計(jì)算估價(jià)函數(shù)

f(s)OPEN表為空表？選取OPEN表中f值最小的節(jié)點(diǎn)i放入CLOSED表i為目標(biāo)節(jié)點(diǎn)嗎？擴(kuò)展i，得后繼節(jié)點(diǎn)j，計(jì)算f(j)，提供返回節(jié)點(diǎn)i的指針，利用f(j)對(duì)OPEN表重新排序，調(diào)整親子關(guān)系及指針失敗成功圖3.9有序搜索算法框圖是否是否3.3啟發(fā)式搜索算法28八數(shù)碼難題（2）如下的八數(shù)碼難題（8-puzzleproblem）12384567（目標(biāo)狀態(tài)）12384567（初始狀態(tài)）（3）八數(shù)碼難題的有序搜索樹(shù)見(jiàn)下圖：3.3啟發(fā)式搜索（1）估價(jià)函數(shù)設(shè)置：

f(n)=d(n)+W(n)

d(n):節(jié)點(diǎn)n的深度；W(n):錯(cuò)放的棋子數(shù)

293.3啟發(fā)式搜索30f

函數(shù)的重要性有序搜索的有效性直接取決于f,是提高搜索效率的關(guān)鍵；如果f

不準(zhǔn)確，可能失去最佳解，也可能失去全部解；f

一般選擇策略搜索時(shí)間與空間的折衷；保證有解或有最佳解；f

選擇的三種典型情況：（1）最優(yōu)解答：狀態(tài)空間中有多條解答路徑，求解最優(yōu)解答，如A*算法；（2）搜索代價(jià)與解答質(zhì)量的綜合：?jiǎn)栴}類似于（1），但搜索過(guò)程可能超出時(shí)間與空間的界限。在適當(dāng)?shù)乃阉鲗?shí)驗(yàn)中找到滿意解答，并限制滿意解答與最優(yōu)解答的差異程度；如：TSP問(wèn)題；（3）最小搜索代價(jià)：不考慮解答的最優(yōu)化（只有一個(gè)解答或多個(gè)解答間無(wú)差異），盡量使搜索代價(jià)最??；如：定理證明。思考：（1）f不能識(shí)別某些節(jié)點(diǎn)的真實(shí)“希望”值會(huì)怎么樣？（2）f過(guò)多估計(jì)了全部節(jié)點(diǎn)又會(huì)怎么樣？3.3啟發(fā)式搜索313.3.3A*算法思考：經(jīng)過(guò)節(jié)點(diǎn)n的最佳路徑，怎么表示？怎么求解最優(yōu)解答路徑。估價(jià)函數(shù)f*：對(duì)節(jié)點(diǎn)n定義f*(n)=g*(n)+h*(n),表示從S開(kāi)始通過(guò)節(jié)點(diǎn)n的一條最佳路徑的代價(jià)。其中g(shù)*(n)表示從起始節(jié)點(diǎn)S到n的最佳路徑，h*(n)表示從n到某目標(biāo)節(jié)點(diǎn)的最佳路徑。估價(jià)函數(shù)f

：f(n)=g(n)+h(n)；其中g(shù)是g*的估計(jì)，h是h*的估計(jì)；g的一個(gè)選擇就是搜索樹(shù)中從S到n的這段路徑的代價(jià)；顯然有g(shù)(n)≥g*(n)；h

的依賴于領(lǐng)域的啟發(fā)信息，比如八數(shù)碼問(wèn)題中的W(n),h

稱為啟發(fā)式函數(shù)；3.3啟發(fā)式搜索32A*算法：

定義1

在GRAPHSEARCH過(guò)程中，如果第8步的重排OPEN表是依據(jù)f(x)=g(x)+h(x)進(jìn)行的，則稱該過(guò)程為A算法。定義2

在A算法中，如果對(duì)所有的x存在h(x)≤h*(x),則稱h(x)為h*(x)的下界，它表示某種偏于保守的估計(jì)。定義3

采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為