人工智能第1章盲目搜索

1、第1章 搜索問題 一種在圖中尋找路徑的方法。 2831476581324765八數(shù)碼魔魔方1.1搜索問題題知識的的表示方方法初始節(jié)點點S0目標(biāo)節(jié)點點Sg狀態(tài)空間間表示狀態(tài)（State）的基本本概念狀態(tài)(state)是為描述述某類不不同事物物間的差差別而引引入的一一組最少少變量q0，q1，qn的有序集集合，其其矢量形形式如下下：Q =q0,q1,qnT(1)式中每個個元素qi(i=0,1，n)為集合的的分量，稱為狀狀態(tài)變量量。給定定每個分分量的一一組值就就得到一一個具體體的狀態(tài)態(tài)，如Qk= q0k,q1k,，qnkT(2)例如，八八數(shù)碼魔魔方中，所有初初始節(jié)點點S0構(gòu)成初始始節(jié)點狀狀態(tài)集合合Q；

2、所有目目標(biāo)節(jié)點點Sg構(gòu)成目標(biāo)標(biāo)節(jié)點狀狀態(tài)集合合Q。當(dāng)Q中每個分分量取定定一個值值時，就就得到一一個具體體的狀態(tài)態(tài)集合，如例子子中的就就是是Q0， 而就就是是Qk。2831476581324765問題求解解技術(shù)主主要是兩兩個方面面：問題的表表示求解的方方法問題的狀狀態(tài)空間間(statespace)是一個表表示該問問題全部部可能狀狀態(tài)及其其關(guān)系的的圖，它它包含三三種說明明的集合合，即所所有可能能的問題題初始狀狀態(tài)集合合S、算符集集合F以及目標(biāo)標(biāo)狀態(tài)集集合G。因此，可把狀狀態(tài)空間間記為三三元狀態(tài)態(tài)(S，F(xiàn)，G)。算符：使問題題從一種種狀態(tài)變變化為另另一種狀狀態(tài)的手手段稱為為操作符符或算符符。操作作符

3、可為為走步、過程、規(guī)則、數(shù)學(xué)算算子、運運算符號號或邏輯輯符號等等。例如，例例子中的的八數(shù)碼碼魔方問問題就可可以用三三元狀態(tài)態(tài)空間表表示為（S0，F(xiàn)，Sg）其中，S0代表初始始狀態(tài)，Sg代表目標(biāo)標(biāo)狀態(tài)，而F就是所有有能將初初始狀態(tài)態(tài)變化為為目標(biāo)狀狀態(tài)的算算符集合合。舉例：012x012y迷宮問題題整個迷宮宮問題的的知識表表示是如如書上第第10頁的圖2.3，這是一一種狀態(tài)態(tài)圖知識識表示法法。問題是：機器人人位于迷迷宮入口口(0，0)處，如何何到達(dá)迷迷宮的出出口(2，2)。解：問題題空間的的初始狀狀態(tài)是節(jié)節(jié)點(0,0),而目標(biāo)狀狀態(tài)是節(jié)節(jié)點(2,2)。從圖2.3可見，從從(0,0)到(2,2)需經(jīng)過

4、(U，R，R，U)算符集合合的操作作，因此此本問題題的解用用三元狀狀態(tài)集合合表示為為：(0,0),(U,R,R,U),(2,2)與圖有關(guān)關(guān)的術(shù)語語狀態(tài)空間間圖由節(jié)點(不一定是是有限的的節(jié)點)及連接節(jié)節(jié)點的分分枝的集集合構(gòu)成成。有限節(jié)點點圖節(jié)點數(shù)目目有限的的圖稱為為有限節(jié)節(jié)點圖。有向圖一對節(jié)點點用分枝枝線連接接起來，從一個個節(jié)點指指向另一一個節(jié)點點。這種種圖叫做做有向圖圖。始節(jié)節(jié)點叫父父節(jié)點或或雙親節(jié)節(jié)點，終終節(jié)點叫叫子節(jié)點點。擴展求解父父節(jié)點的的所有子子節(jié)點，叫做擴擴展。路徑在一系系列節(jié)點點n1,n2,nm中，從n1開始，ni總有分枝枝連接ni+1，稱從n1到nm之間的分分枝集合合是路徑徑。路

5、徑徑中不包包含兩個個及以上上相同的的分枝，如果n1和nm是同一個個節(jié)點，則稱這這種路徑徑為閉路路。不構(gòu)構(gòu)成閉路路的稱為為樹。在用狀態(tài)態(tài)空間圖圖來表示示問題時時，對問問題的求求解就是是求出從從初始節(jié)節(jié)點到目目標(biāo)節(jié)點點的路徑徑。1.2圖搜索策策略1.圖搜索的的定義一種計算算機在狀狀態(tài)圖中中尋找路路徑的方方法。2.CLOSED表的引入入編號節(jié)點號父節(jié)點號CLOSED表(記錄擴展展過的節(jié)節(jié)點)OPEN表的引入入節(jié)點號父節(jié)點號OPEN表(記錄待擴擴展的節(jié)節(jié)點)舉例：八八數(shù)碼魔魔方例子子中OPEN表變化過過程節(jié)點號父節(jié)點號S0空AS0BS0CS0DS0EAFACLOSED表變化過過程編號節(jié)點號父節(jié)點號0S

6、0空1AS02BS0圖搜索的的一般過過程(1)建立一個個只含有有起始節(jié)節(jié)點S的搜索圖圖G，把S放到一個個叫做OPEN表的未擴擴展節(jié)點點表中。(2)建立一個個叫做CLOSED的已擴展展節(jié)點表表，其初初始為空空表。(3)LOOP：若OPEN表是空表表，則失失敗退出出。(4)選擇OPEN表上的第第一個節(jié)節(jié)點，把把它從OPEN表移出并并放進CLOSED表中。稱稱此節(jié)點點為節(jié)點點n。(5)若n為一目標(biāo)標(biāo)節(jié)點，則有解解并成功功退出，此解是是追蹤圖圖G中沿著指指針從n到S這條路徑徑而得到到的(指針將在在第7步中設(shè)置置)。圖搜索的的一般過過程(6)擴展節(jié)點點n，同時生成成不是n的祖先的的那些后后繼節(jié)點點的集合

7、合M。把M的這些成成員作為為n的后繼節(jié)節(jié)點添入入圖G中。(7)對那些未未曾在G中出現(xiàn)過過的(既未曾在在OPEN表上或CLOSED表上出現(xiàn)現(xiàn)過的)M成員設(shè)置置一個通通向n的指針。把M的這些成成員加進進OPEN表。對已已經(jīng)在OPEN或CLOSED表上的每每一個M成員，確確定是否否需要更更改通到到n的指針方方向。對對已在CLOSED表上的每每個M成員，確確定是否否需要更更改圖G中通向它它的每個個后裔節(jié)節(jié)點的指指針方向向。(8)按某一任任意方式式或按某某個探試試值，重重排OPEN表。(9)GOLOOP。開始把S放入OPEN表OPEN表為空表表？把第一個節(jié)節(jié)點(n)從OPEN表移至CLOSED表n為目標(biāo)

8、節(jié)節(jié)點嗎？把n的后繼節(jié)節(jié)點放入入OPEN表的末端端，提供供返回節(jié)節(jié)點n的指針修改指針針方向重排OPEN表失敗成功圖搜索一一般過程程的框圖圖是是否否1.3無信息圖圖搜索過過程深度優(yōu)先先搜索（縱向搜搜索）寬度優(yōu)先先搜索（橫向搜搜索）均一代價價搜索1.深度優(yōu)先先搜索定義首先擴展展最新產(chǎn)產(chǎn)生的(即最深的的)節(jié)點。深度相等等的節(jié)點點可以任任意排列列。這種種盲目(無信息)搜索叫做做深度優(yōu)先先搜索或縱向搜索索。 特點擴展最深深的節(jié)點點的結(jié)果果使得搜搜索沿著著狀態(tài)空空間某條條單一的的路徑從從起始節(jié)節(jié)點向下下進行下下去；只只有當(dāng)搜搜索到達(dá)達(dá)一個沒沒有后裔裔的狀態(tài)態(tài)時，它它才考慮慮另一條條替代的的路徑。為了防止止

9、搜索過過程沿著著無益的的路徑擴擴展下去去，往往往給出一一個節(jié)點點擴展的的最大深深度深度界限限。深度優(yōu)先先搜索算法法是一種種“后進進先出”的算法法。開始把S放入OPEN表OPEN表為空表表？把第一個個節(jié)點(n)從OPEN表移至CLOSED表擴展n，把其后裔放入入OPEN表的前頭頭失敗成功深度優(yōu)先先搜索算法法框圖是否是否是否有后后繼節(jié)點點為目標(biāo)節(jié)節(jié)點？S是否為目目標(biāo)節(jié)點點？成功是否八數(shù)碼魔魔方的深度優(yōu)先先搜索樹2.寬度優(yōu)先先搜索定義以接近起起始節(jié)點點的程度度逐層擴擴展節(jié)點點的搜索索方法(breadth-firstsearch)，這種盲盲目(無信息)搜索叫做做寬度優(yōu)優(yōu)先搜索索或橫向向搜索。 特點一種

10、高代代價搜索索，但若若有解存存在，則則必能找找到它。算法這種搜索索是逐層層進行的的；在對對下一層層的任一一節(jié)點進進行搜索索之前，必須搜搜索完本本層的所所有節(jié)點點。寬度優(yōu)先先搜索算法法是一種種“先進進先出”的算法法。開始把S放入OPEN表OPEN表為空表表？把第一個個節(jié)點(n)從OPEN表移至CLOSED表擴展n，把n的后繼節(jié)節(jié)點放入入OPEN表的末端端，提供供返回節(jié)節(jié)點n的指針失敗寬度優(yōu)先先搜索算法框圖圖是否把第一個節(jié)節(jié)點(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)節(jié)點嗎？成功是否舉例：八數(shù)碼魔魔方1238456712384567（目標(biāo)狀狀態(tài)）（初始狀狀態(tài)）12384567123841238

11、45674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345八數(shù)碼魔魔方的寬度優(yōu)先先搜索樹1345612384567123845671238456712384567123845672324252627123678221238456712384567123845671238456712384567123845671238456714151617181920211238456742829303112384567123845671238456712384

12、5673213456123678381238456739擴展26個節(jié)點，共生成46個節(jié)點之之后，才才得到目目標(biāo)3.均一代價價搜索是橫向搜搜索的一一種推廣廣，不是是沿著等等長度路路徑斷層層進行擴擴展，而而是沿著著均一代代價路徑徑斷層進進行擴展展。搜索樹中中每條連連接弧線線上的有有關(guān)代價價,表示時間間、距離離等花費費。若所有連連接弧線線具有相相等代價價，則簡簡化為橫橫向搜索索算法。均一代價價搜索中中的幾個個記號：起始節(jié)點點記為S；從節(jié)點i到它的后后繼節(jié)點點j的連接弧弧線代價價記為c(i，j)；從起始節(jié)節(jié)點S到任一節(jié)節(jié)點i的路徑代代價記為為g(i)。開始把S放入OPEN表OPEN表為空表表？把第一個

13、個節(jié)點(n)從OPEN表移至CLOSED表擴展n，把n的后繼節(jié)節(jié)點放入入OPEN表的末端端，提供供返回節(jié)節(jié)點n的指針失敗均一代價價搜索算算法框圖圖是否把第一個節(jié)節(jié)點(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)節(jié)點嗎？成功是否按g(i)值由小到到大的順順序重排排OPEN表均一代價價搜索法法思路：1、 從A點開始依依次展開開得到AB（7）、AC（3）、AD（10）、AE（15）四個新結(jié)結(jié)點，把把第一層層結(jié)點A標(biāo)記為已已展開，并且每每個新結(jié)結(jié)點要記記錄下其其距離（括號中中的數(shù)字字）；2、 把未未展開過過的AB、AC、AD、AE四個結(jié)點點中距離離最小的的一個展展開，即即展開AC（3）結(jié)點，得得到AC

14、B（8）、ACD（16）、ACE（13）三個結(jié)點點，并把把結(jié)點AC標(biāo)記為已已展開；3、 再從從未展開開的所有有結(jié)點中中找出距距離最小小的一個個展開，即展開開AB（7）結(jié)點，得得到ABC（12）、ABD（20）、ABE（19）三個結(jié)點點，并把把結(jié)點AB標(biāo)記為已已展開；4、 再次次從未展展開的所所有結(jié)點點中找出出距離最最小的一一個展開開，即展展開ACB（8）結(jié)點；5、 每次次展開所所有未展展開的結(jié)結(jié)點中距距離最小小的那個個結(jié)點，直到展展開的新新結(jié)點中中出現(xiàn)目目標(biāo)情況況（結(jié)點點含有5個字母）時，即即得到了了結(jié)果。算法分析析：由上可見見，均一一代價搜搜索法并并沒有象象橫向搜搜索一樣樣展開所所有結(jié)點點，只是是根據(jù)代代價最小小的原則則，每次次展開距距離A點最近的的那個結(jié)結(jié)點，反反復(fù)下去去即可最最終得到到答案。雖然中中途有時時也展開開