1、Ai人工智能第三章 搜索策略 前 言人工智能的核心問題就是求解問題。對于給定的問題，智能系統(tǒng)的行為一般是找到能夠達(dá)到所希望目標(biāo)的動作序列并使其所付出的代價最小、性能最好。搜索就是找到智能系統(tǒng)的動作序列的過程。搜素方式盲目搜索(非啟發(fā)式)盲目性，效率較低，容易出現(xiàn)“組合爆炸”問題。有深度優(yōu)先搜索和寬度優(yōu)先搜索啟發(fā)式捜索A算法，A*算法 前 言搜索策略可以通過下面4個準(zhǔn)則來評價：完備性：如果存在一個解答，該策略是否保證能夠找到。時間復(fù)雜性：需要多長時間可以找到解答。空間復(fù)雜性：執(zhí)行搜索需要多少存儲空間。最優(yōu)性：如果存在不同的幾個解答，該策略是否可以發(fā)現(xiàn)最高質(zhì)量的解答目 錄CONTENTS01基于狀

2、態(tài)空間圖的搜索技術(shù)02盲目搜索03啟發(fā)式搜索04問題規(guī)約05與或圖啟發(fā)式搜索06博弈基于狀態(tài)空間圖的搜索技術(shù)0101基于狀態(tài)空間圖的搜索技術(shù)栗子(錢幣翻轉(zhuǎn)問題)只允許每次翻轉(zhuǎn)一個錢幣，連翻3次，問能否達(dá)到目標(biāo)狀態(tài)。反、正、反正、正、正反、反、反狀態(tài)空間搜索1. 什么是狀態(tài)空間圖01基于狀態(tài)空間圖的搜索技術(shù)01基于狀態(tài)空間圖的搜索技術(shù)01基于狀態(tài)空間圖的搜索技術(shù)(2)操作(operator)操作也稱為運算符或算符，它引起狀態(tài)中的某些分量發(fā)生改變，從而使問題由一個具體狀態(tài)改變到另一個具體狀態(tài)。操作可以是一個機械的步驟、過程、規(guī)則或算子,指出了狀態(tài)之間的關(guān)系。操作用于反映過程性知識。.狀態(tài)有向弧節(jié)點

3、 狀態(tài)有向弧 狀態(tài)的變遷弧上的表情 導(dǎo)致狀態(tài)變遷的操作算子操作算子01基于狀態(tài)空間圖的搜索技術(shù)01基于狀態(tài)空間圖的搜索技術(shù)這種描述問題的有向圖稱為狀態(tài)空間圖，簡稱狀態(tài)圖。邊表示兩節(jié)點之間的某種聯(lián)系，如它可以是某種操作、規(guī)則、變換、算子或關(guān)系等。在狀態(tài)圖中，從初始節(jié)點到目標(biāo)節(jié)點的一條路徑，或者所找的目標(biāo)節(jié)點，就是相應(yīng)問題的一個解。0表示硬幣為正面1表示硬幣為反面01基于狀態(tài)空間圖的搜索技術(shù)1. 顯式圖與隱式圖為求解問題，需要把有關(guān)的知識存儲在計算機的知識庫中，包括以下兩種存儲方式(1)顯式存儲把與問題有關(guān)的全部狀態(tài)空間圖。(2)隱式存儲只存儲與問題求解有關(guān)的部分知識(即部分狀態(tài)空間)。這種存儲方

4、式稱為隱式存儲。 圖搜索的基本概念01基于狀態(tài)空間圖的搜索技術(shù)2. 圖搜索的基本思想圖搜索就是一種在圖中尋找路徑的方法。 從初始節(jié)點到目標(biāo)節(jié)點。方法是先把問題的初始狀態(tài)作為當(dāng)前狀態(tài)，選擇適用的算符對其進(jìn)行操作，生成一組子狀態(tài)，檢查目標(biāo)狀態(tài)是否在其中出現(xiàn)。 若出現(xiàn)，則搜索成功，找到了問題的解；若不出現(xiàn)，則按某種搜索策略從已生成的狀態(tài)中再選一個狀態(tài)作為當(dāng)前狀態(tài)。重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)或者不再有可供操作的狀態(tài)及算符時為止。產(chǎn)生式系統(tǒng)的初始數(shù)據(jù)庫滿足終止條件的數(shù)據(jù)庫01基于狀態(tài)空間圖的搜索技術(shù)關(guān)于經(jīng)典的“傳教士和野人問題”設(shè)N個傳教士帶領(lǐng)N個野人劃船渡河，且為安全起見過河需遵從三個約束:船上人

5、數(shù)不得超過載重限量，設(shè)為K個人;為預(yù)防野人攻擊，任何時刻(包括兩岸、船上)野人數(shù)目不得超過傳教士;允許在河的某一岸或者在船上只有野人而沒有傳教士。為便于理解狀態(tài)空間表示方法，將該問題簡化為一個特例：N=3，K=2；并以變量m表示傳教士在左岸的實際人數(shù)變量c表示野人在左岸的實際人數(shù)，變量b表示船是否在左岸(值1指示船在左岸，否則為0)。在船上時m+c=c01基于狀態(tài)空間圖的搜索技術(shù)狀態(tài)設(shè)初始狀態(tài)下傳教士、野人和船都在左岸，目標(biāo)狀態(tài)下這三者均在右岸，問題狀態(tài)以三元組(m, c, b)表示，則問題求解任務(wù)可摘述為：(3,3,1)-(0,0,0)操作算子可以定義兩類:L(m,c) 表示從左岸到右岸的劃

6、船操作R(m,c) 表示從右岸到右岸的劃船操作01基于狀態(tài)空間圖的搜索技術(shù)由此例可以看出:用狀態(tài)空間方法表示問題時，需要專注于狀態(tài)和操作。問題的求解過程是一個不斷把操作作用于狀態(tài)的過程。一個狀態(tài)，可能存在多個操作，也就有多個待搜索的解答路徑。狀態(tài)空間搜索的基本思想狀態(tài)空間表示法就是用來表示問題及其搜索過程的一種方法。通過搜索引擎尋找一個操作算子的調(diào)用序列，使問題從初始狀態(tài)變遷到目標(biāo)狀態(tài)之一，而變遷過程中的狀態(tài)序列或相應(yīng)的操作算子調(diào)用序列稱為從初始狀態(tài)到目標(biāo)狀態(tài)的解答路徑。01基于狀態(tài)空間圖的搜索技術(shù)描述狀態(tài)空間的一般都很大，無法直觀地畫，只能將其視為隱含圖，在搜索解答路徑的過程中只畫出搜索時直接涉及的節(jié)點和弧線，構(gòu)成所謂的搜索圖。下面再看一個智力游戲八數(shù)碼問題（用圖搜索算法解）：01基于狀態(tài)空間圖的搜索技術(shù)一般圖的搜索算法01基于狀態(tài)空間圖的搜索技術(shù)01基于狀態(tài)空間圖的搜索技術(shù)01基于狀態(tài)空間圖的搜索技術(shù)上述過程生成一個顯式圖G(稱為捜索圖)。由返回指針確定G的子圖T(稱為搜索樹)，OPEN表中的節(jié)點是