Artificial-Intelligence第三章搜索技術(shù)-《人工智能》課件

第三章搜索技術(shù)一般來說，一個(gè)智能體有多個(gè)評(píng)價(jià)未知的直接選項(xiàng)的時(shí)候，可以首先檢驗(yàn)各個(gè)不同的能導(dǎo)致已知評(píng)價(jià)的狀態(tài)的可能序列，然后選擇最佳序列，上述過程被稱為搜索。搜索算法把問題初始狀態(tài)作為輸入，并以行動(dòng)序列的形式返回問題的解。在搜索過程中，除了問題中提供的定義之外沒有任何關(guān)于狀態(tài)的附加信息，稱為盲目搜索。若在搜索過程中知道一個(gè)非目標(biāo)狀態(tài)是否比其它狀態(tài)“更有希望”接近目標(biāo)的策略被稱為啟發(fā)式搜索。第一節(jié)盲目搜索一、廣度優(yōu)先搜索廣度優(yōu)先搜索是一個(gè)簡(jiǎn)單的搜索策略，首先是擴(kuò)展根節(jié)點(diǎn)，接著擴(kuò)展根節(jié)點(diǎn)的所有后繼，然后再擴(kuò)展它們的后繼，依此類推。一般來講，在下一層的任何節(jié)點(diǎn)擴(kuò)展之前搜索樹上本層深度的所有節(jié)點(diǎn)都已被擴(kuò)展過。1.數(shù)據(jù)結(jié)構(gòu)

OPEN表：一個(gè)先進(jìn)先出的隊(duì)列，用于存儲(chǔ)待擴(kuò)展的節(jié)點(diǎn)。

CLOSED表：一個(gè)用于存儲(chǔ)已被擴(kuò)展過的節(jié)點(diǎn)的線性表。上圖中：1、OPEN=[S];CLOSED=[]2、OPEN=[A1，A2，A3];CLOSED=[S]3、OPEN=[A2，A3，B1，B2];CLOSED=[A1，S]4、OPEN=[A3，B1，B2，B3，B4]，CLOSED=[A2，A1，S]5、OPEN=[B1，B2，B3，B4，B5]，CLOSED=[A3，A2，A1,S]┇┇11、OPEN=[C2，C3，C4，D1]，CLOSED=[C1，B5，B4，B3，B2，B1，A3，A2，A1，S]深度廣度時(shí)間內(nèi)存需求211000.11秒1M字節(jié)4111，10011秒106M字節(jié)619分鐘10G字節(jié)831小時(shí)1T字節(jié)10129天101T字節(jié)1235年10P字節(jié)假設(shè)，每個(gè)節(jié)點(diǎn)的分支數(shù)為10；10000節(jié)點(diǎn)/秒；1000字節(jié)/節(jié)點(diǎn)3.小結(jié)（1）由于該種搜索方法總是在檢查完N層的節(jié)點(diǎn)之后才轉(zhuǎn)向N+1層的檢查，因此，它總能找到最短路徑解。（2）廣度優(yōu)先算法中內(nèi)存的需求是比執(zhí)行時(shí)間消耗更大的問題。（3）時(shí)間的需求仍然是主要因素。二、深度優(yōu)先搜索深度優(yōu)先搜索是另一個(gè)簡(jiǎn)單的搜索策略，它總是擴(kuò)展最新產(chǎn)生的（即最深的）節(jié)點(diǎn)，使得搜索沿著狀態(tài)空間某一條單一的路徑向下進(jìn)行；只有當(dāng)搜索到一個(gè)沒有后繼的狀態(tài)時(shí)，它才考慮另一條替代路徑。節(jié)點(diǎn)的深度定義如下：根節(jié)點(diǎn)的深度為0；其它任何節(jié)點(diǎn)的深度等于其父親節(jié)點(diǎn)的深度+1。1.數(shù)據(jù)結(jié)構(gòu)OPEN表：一個(gè)先進(jìn)后出的堆棧，用于存儲(chǔ)待擴(kuò)展的節(jié)點(diǎn)。

CLOSED表：一個(gè)用于存儲(chǔ)已被擴(kuò)展過的節(jié)點(diǎn)的線性表。

D：深度界限（許多復(fù)雜問題搜索樹的深度可能無限深，為了避免考慮太長的路徑，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度）。2.算法（深度有界搜索）（1）將初始節(jié)點(diǎn)S放入OPEN表中，若S為目標(biāo)節(jié)點(diǎn)，則得到一個(gè)解。（2）若OPEN表為空，則失敗退出。（3）把第一個(gè)節(jié)點(diǎn)（節(jié)點(diǎn)n）從OPEN移到CLOSED表。（4）若節(jié)點(diǎn)n的深度等于D（深度界限），則轉(zhuǎn)（2）。（5）擴(kuò)展節(jié)點(diǎn)n，產(chǎn)生其所有后繼，并將它們放入OPEN表中。若沒有后繼，則轉(zhuǎn)向（2）。（6）如果后繼節(jié)點(diǎn)中有任一為目標(biāo)節(jié)點(diǎn)，則得到一個(gè)解，成功退出；否則，轉(zhuǎn)向（2）SS1S2S3S5S4S6S71、OPEN=[S];CLOSED=[]2、OPEN=[S1，S2，S3];CLOSED=[S]3、OPEN=[S4，S5，S1，S2，S3];CLOSED=[S1，S]4、OPEN=[S6，S5，S1，S2，S3]，CLOSED=[S4，S1，S]5、OPEN=[S7，S5，S1，S2，S3]，CLOSED=[S6，S4，S1，S]3.小結(jié)（1）深度優(yōu)先搜索算法是不完備的。（2）深度優(yōu)先搜索耗費(fèi)的空間量是路徑長度值的線性函數(shù)，OPEN在每一層只保留一個(gè)狀態(tài)的子狀態(tài)，如果圖中每個(gè)狀態(tài)平均有B個(gè)子狀態(tài)，則搜索到圖中第n層時(shí)要求B×n個(gè)狀態(tài)的空間，有大量分支的圖時(shí)會(huì)有相當(dāng)高的效率。（3）深度優(yōu)先搜索可盡快進(jìn)入底層，但會(huì)在深處迷失方向，找不到目標(biāo)的最短路徑或陷入到一個(gè)不通往目標(biāo)的無限長的路徑中。三、代價(jià)一致搜索

當(dāng)所有單步耗散相等的時(shí)候，廣度優(yōu)先搜索是最優(yōu)的，因?yàn)樗偸窍葦U(kuò)展深度最淺的未擴(kuò)展節(jié)點(diǎn)。簡(jiǎn)單的延伸一下，取代擴(kuò)展深度最淺的節(jié)點(diǎn)，代價(jià)一致搜索擴(kuò)展的是路徑消耗最低的節(jié)點(diǎn)n，如果所有單步耗散相等的話，代價(jià)一致搜索算法和廣度悠閑搜索算法是一樣的。第二節(jié)啟發(fā)式搜索一、基本概念

先剖析“啟發(fā)式搜索”這幾個(gè)字：

啟發(fā)（heuristic）：其內(nèi)容包括發(fā)現(xiàn)、發(fā)明規(guī)則及其研究方法。在狀態(tài)空間搜索中，啟發(fā)式被定義成一系列規(guī)則，它從狀態(tài)空間中選擇最有希望到達(dá)問題解的路徑。啟發(fā)式搜索1、在人工智能問題求解中為什么要研究啟發(fā)式策略？①在問題求解中有不確定性問題；例：醫(yī)學(xué)中的一些基本問題；②在問題求解中有模糊性等問題；例：視覺問題③所求解問題可能有確定解，但它有組合爆炸等問題存在，最終還是達(dá)不到問題求解的目的。④在問題求解中有定性描述過程存在，但對(duì)此類問題只能借助經(jīng)驗(yàn)給予定量幫助描述。2、利用啟發(fā)式搜索策略有何優(yōu)勢(shì)？①可以幫助我們解決問題求解過程中存在的不確定性、模糊性；②可以降低問題求解的復(fù)雜性；③可以幫助我們簡(jiǎn)化問題；3、啟發(fā)式搜索的構(gòu)成及目的①啟發(fā)式搜索由啟發(fā)式方法和啟發(fā)式搜索算法兩部分構(gòu)成。②啟發(fā)式搜索的目的是：利用啟發(fā)式搜索可能得到一個(gè)次最佳解，也可能一無所獲。這也是啟發(fā)式搜索固有的局限性。二、啟發(fā)式搜索的估價(jià)函數(shù)確定方法眾所周知，在智能活動(dòng)中，使用最多的方法不是完備性方法，而是不一定完備的啟發(fā)式方法。其原因是：

1、大多數(shù)智能系統(tǒng)不知道與實(shí)際問題有關(guān)的全部信息，因此，在具體求解問題時(shí)只能借助部分信息加上經(jīng)驗(yàn)去處理；2、理論值與工程中的關(guān)系；3、有些智能行為無法用現(xiàn)有的工具推導(dǎo)表示，只能用經(jīng)驗(yàn)關(guān)系表示：由此可見，無論在理論方面還是在應(yīng)用方面都需要啟發(fā)式方法。我們知道在問題求解的搜索圖中，從節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系來看有：過去節(jié)點(diǎn)、當(dāng)前節(jié)點(diǎn)、將來節(jié)點(diǎn)三種類型，即過去節(jié)點(diǎn)當(dāng)前節(jié)點(diǎn)將來節(jié)點(diǎn)我們把這三種類型節(jié)點(diǎn)的關(guān)系用一個(gè)評(píng)估函數(shù)表示為：f(n)=g(n)+h(n)………………（2）其中：g(n)表示從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的代價(jià)；h(n)表示從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。在f(n)=g(n)+h(n)，中，若有g(shù)(n)>>h(n)，則有f(n)=g(n)…………（3）若有g(shù)(n)<<h(n),則有f(n)=h(n)…………（4）（3）式可以保證f(n)的完備性，但搜索效率較差。（4）式有利于搜索效率的提高分析：前面講的廣度優(yōu)先：f1(n)=MnM，n>2……（5）深度優(yōu)先：f2(n)=M?nM，n>2……（6）有界深度：f3(n)=Mn+Kk≠0M，n>2……（7）在（2）式中：當(dāng)g(n)>h(n)時(shí)：

f(n)→f1(n)…………（8）在（2）式中，當(dāng)h(n)>g(n)時(shí)

f(n)→f2(n)…………（9）三、啟發(fā)式搜索算法1.局部優(yōu)先搜索法（瞎子爬山法）瞎子爬山法只考慮當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的關(guān)系，即啟發(fā)式估價(jià)函數(shù)為：f(n)=h(n)瞎子爬山法只選擇鄰居狀態(tài)中狀態(tài)最好的一個(gè)，而不事先考慮下一步向哪個(gè)方向走。該方法能很快地朝著解的方向進(jìn)展，但常常會(huì)只找到局部最大值。狀態(tài)空間山肩全局最大值局部最大值從不同初始狀態(tài)爬山，到達(dá)的“峰頂”是不同的。[例]用瞎子爬山法求下列九宮問題：f(n)=h(n)其中：h(n)表示格子中的數(shù)字和目標(biāo)數(shù)字錯(cuò)位個(gè)數(shù)之和。（1）（2）2831647512384765283164752831476528316475283164752318476528314765231847652318476583214765123847651238476535533243102.最好優(yōu)先搜索法（有序搜索法）

最好優(yōu)先搜索法也使用兩張表來記錄節(jié)點(diǎn)信息，在open表中保留所有已生成而未考察的節(jié)點(diǎn)；在Closed表中記錄已訪問過的節(jié)點(diǎn)。算法中有一步是根據(jù)某些啟發(fā)信息，按節(jié)點(diǎn)距離目標(biāo)狀態(tài)的長度大小重排open表中的節(jié)點(diǎn)，這樣，循環(huán)中的每一步只考慮open表中狀態(tài)最好的節(jié)點(diǎn)，這就是最好優(yōu)先搜索算法，又稱有序搜索法。即：原始節(jié)點(diǎn)狀態(tài)：open=[A1，A3，A2…An…Am]

↓重排之后

重排后狀態(tài)節(jié)點(diǎn)：open=[A1，A2，A3…Am…An]*最好優(yōu)先搜索算法描述和分析：最好優(yōu)先搜索算法總是從open表中選取最“好”的狀態(tài)進(jìn)行擴(kuò)展。但是，由于啟發(fā)信息有時(shí)可能出錯(cuò)，故算法并不丟棄其他的狀態(tài)而把它們保留在open表中，當(dāng)某一個(gè)啟發(fā)信息將搜索導(dǎo)向錯(cuò)誤路徑時(shí)，算法可以從open表中檢索先前產(chǎn)生的“次最好”狀態(tài)，并且考慮方向轉(zhuǎn)向空間的另一部份。A1A3A2A4A5A6A7A8A9A20A19A18A17A16A15A14A13A12A11A10如圖以

包圍的區(qū)域出錯(cuò)，則返回到未包圍的區(qū)域*啟發(fā)式搜索技術(shù)小結(jié)

f(n)=g(n)+h(n)中：g(n)保證了寬度優(yōu)先搜索的性質(zhì)，h(n)保證了有最好的路徑，因此，最好優(yōu)先搜索方法為我們提供了啟發(fā)式搜索的一般原則，總結(jié)起來有：a、根據(jù)產(chǎn)生式規(guī)則和一些其他的操作，生成當(dāng)前考察結(jié)點(diǎn)的子狀態(tài)；b、檢查每個(gè)子狀態(tài)以前是否已經(jīng)考察過（已在open表或Closed表中），以防止循環(huán)；c、每個(gè)狀態(tài)都以f(n)值為依據(jù)進(jìn)行搜索；d、open表中的狀態(tài)按f(n)值排序；e、通過設(shè)計(jì)open表和Closed表的存儲(chǔ)方式，可以提高算法的效率。四、啟發(fā)式搜索過程的基本性質(zhì)

1、找最短路徑：只要有解存在，用