第三章搜索策略-PracticalReaso

1、Artificial IntelligenceSearching: 1 Graduate University , Chinese academy of Sciences. 人工智能人工智能Artificial IntelligenceArtificial IntelligenceSearching: 2 Graduate University , Chinese academy of Sciences. 搜索策略搜索策略 Artificial IntelligenceSearching: 3 Graduate University , Chinese academy of Sciences.

2、 主要內(nèi)容主要內(nèi)容 概述概述 狀態(tài)空間搜索狀態(tài)空間搜索狀態(tài)空間的一般搜索過程狀態(tài)空間的一般搜索過程廣度優(yōu)先搜索廣度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索啟發(fā)式搜索啟發(fā)式搜索A*算法算法問題規(guī)約搜索問題規(guī)約搜索博弈博弈Artificial IntelligenceSearching: 4 Graduate University , Chinese academy of Sciences. 概述概述(1) 問題求解問題求解 AI中每個研究領(lǐng)域都有其各自的特點和規(guī)律中每個研究領(lǐng)域都有其各自的特點和規(guī)律,但就求解但就求解問題問題的過程看的過程看,都可抽象為一個問題求解過程都可抽象為一個問題求解過程。 問題求

3、解過程實際上是一個搜索問題求解過程實際上是一個搜索,廣義地說廣義地說,它包含了全部計它包含了全部計算機科學。算機科學。 任何問題求解技術(shù)都包括兩個重要的方面任何問題求解技術(shù)都包括兩個重要的方面:表示和搜索表示和搜索 表示是基本的表示是基本的,搜索必須要在表示的基礎(chǔ)上進行。表示關(guān)系搜索必須要在表示的基礎(chǔ)上進行。表示關(guān)系到搜索的效率。到搜索的效率。 本章討論的表示主要包括本章討論的表示主要包括: 狀態(tài)空間表示狀態(tài)空間表示 問題空間表示問題空間表示Artificial IntelligenceSearching: 5 Graduate University , Chinese academy of

4、Sciences. 概述概述(2)q 1974年，年，Nilsson歸納出的歸納出的AI研究的基本研究的基本問題問題 知識的模型化和表示知識的模型化和表示 常識性推理、演繹和問題解決常識性推理、演繹和問題解決 啟發(fā)式搜索 人工智能系統(tǒng)和語言人工智能系統(tǒng)和語言q 搜索是人工智能中的一個基本問題搜索是人工智能中的一個基本問題,是推理不可分割的一部分是推理不可分割的一部分,直接關(guān)系到智能系統(tǒng)的性能和運行效率直接關(guān)系到智能系統(tǒng)的性能和運行效率q AI為什么要研究為什么要研究search? 問題沒有直接的解法問題沒有直接的解法; 需要探索地求解需要探索地求解;Artificial Intelligenc

5、eSearching: 6 Graduate University , Chinese academy of Sciences. 搜索搜索(3) 什么是搜索什么是搜索 根據(jù)問題的實際情況不斷尋找可利用的知識根據(jù)問題的實際情況不斷尋找可利用的知識,構(gòu)造構(gòu)造出一條代價較少的推理路線出一條代價較少的推理路線,使問題得到圓滿解決使問題得到圓滿解決的過程稱為的過程稱為搜索 包括兩個方面： - 找到從初始事實到問題最終答案的一條推理路徑 - 找到的這條路徑在時間和空間上復(fù)雜度最小Artificial IntelligenceSearching: 7 Graduate University , Chines

6、e academy of Sciences. 搜索搜索(4) 盲目搜索:也稱為無信息搜索，即只按預(yù)定的控制策也稱為無信息搜索，即只按預(yù)定的控制策略進行搜索略進行搜索,在搜索過程中獲得的中間信息不用來改在搜索過程中獲得的中間信息不用來改進控制策略進控制策略 啟發(fā)式搜索: 在搜索中加入了與問題有關(guān)的啟發(fā)性信在搜索中加入了與問題有關(guān)的啟發(fā)性信息息,用于指導搜索朝著最有希望的方向進行用于指導搜索朝著最有希望的方向進行,加速問題加速問題的求解過程并找到最優(yōu)解的求解過程并找到最優(yōu)解Artificial IntelligenceSearching: 8 Graduate University , Chine

7、se academy of Sciences. 狀態(tài)空間表示法狀態(tài)空間表示法(1)q 狀態(tài)空間表示法：用來表示問題及其搜索過程的一種方法狀態(tài)空間表示法：用來表示問題及其搜索過程的一種方法q 狀態(tài)狀態(tài) 狀態(tài)是描述問題求解過程中任一時刻狀況的數(shù)據(jù)結(jié)構(gòu)狀態(tài)是描述問題求解過程中任一時刻狀況的數(shù)據(jù)結(jié)構(gòu).23751486A，B，C，D（2, 3,7 ,0 , 5, 2, 4, 8, 6）Artificial IntelligenceSearching: 9 Graduate University , Chinese academy of Sciences. 狀態(tài)空間表示法狀態(tài)空間表示法(2)q 狀態(tài)空間:

8、由問題的全部狀態(tài)及一切可用算符所構(gòu)成的集合稱為問題的狀態(tài)由問題的全部狀態(tài)及一切可用算符所構(gòu)成的集合稱為問題的狀態(tài)空間空間.一般表示為一般表示為: (S, F, G)S:問題所有的初始狀態(tài)集合問題所有的初始狀態(tài)集合; F:算符集合算符集合; G:目標狀態(tài)集合目標狀態(tài)集合q 算符: 引起狀態(tài)中某些分量發(fā)生變化引起狀態(tài)中某些分量發(fā)生變化, 從而使問題由一個狀從而使問題由一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作稱為算符態(tài)變?yōu)榱硪粋€狀態(tài)的操作稱為算符.q 狀態(tài)空間表示法是用狀態(tài)空間表示法是用“狀態(tài)狀態(tài)”和和“算符算符”表示問題的一種表示問題的一種方法方法q 狀態(tài)空間圖:狀態(tài)空間的圖式表示狀態(tài)空間的圖式表示,稱為狀態(tài)

9、空間圖稱為狀態(tài)空間圖.其中節(jié)其中節(jié)點表示狀態(tài)點表示狀態(tài),有向邊有向邊(弧弧)表示算符表示算符.Artificial IntelligenceSearching: 10 Graduate University , Chinese academy of Sciences. 狀態(tài)空間表示法狀態(tài)空間表示法(3) 路徑路徑 狀態(tài)序列狀態(tài)序列 搜索搜索 尋找從初始狀態(tài)到目標狀態(tài)的路徑尋找從初始狀態(tài)到目標狀態(tài)的路徑;S0SgArtificial IntelligenceSearching: 11 Graduate University , Chinese academy of Sciences. 狀態(tài)空間表

10、示法（狀態(tài)空間表示法（4）例一例一:二階梵塔問題二階梵塔問題 設(shè)有三個鋼針設(shè)有三個鋼針,在一號鋼針上穿有在一號鋼針上穿有A,B兩個金片兩個金片,A小于小于B,A位于位于B的上面的上面.要求把這兩要求把這兩個金片全部移到另一個鋼針上個金片全部移到另一個鋼針上,而且規(guī)定每次只能移動一片而且規(guī)定每次只能移動一片,任何時刻都不能使任何時刻都不能使B位于位于A的上面的上面設(shè)用設(shè)用Sk=(Sk0,Sk1)表示問題的狀態(tài)表示問題的狀態(tài),SK0表示金片表示金片A所在的鋼針號所在的鋼針號,SK1表示金片表示金片B所在的所在的鋼針號鋼針號,全部可能的狀態(tài)為全部可能的狀態(tài)為:S0=(1,1), S1=(1,2),

11、S3=(1,3)S4=(2,1), S5=(2,2), S6=(2,3)S7=(3,1), S8=(3,2), S9=(3,3)問題初始狀態(tài)集合問題初始狀態(tài)集合S=S0,目標狀態(tài)集合目標狀態(tài)集合G=S4,S8.算符算符:A( i,j):表示把金片表示把金片A從第從第i號針移到第號針移到第j號針上號針上B(i,j):表示把表示把B從第從第i號針移到第號針移到第j號針上號針上共共12個算符個算符:A(1,2), A(1,3), A(2,1) ,A(2,3), A(3,1),A(3,2)B(1,2), B(1,3), B(2,1), B(2,3), B(3,1), B(3,2)Artificial

12、IntelligenceSearching: 12 Graduate University , Chinese academy of Sciences. 狀態(tài)空間表示法（狀態(tài)空間表示法（5）用狀態(tài)空間表示用狀態(tài)空間表示,首先必須定義狀態(tài)的描述形式首先必須定義狀態(tài)的描述形式,把問題的一切狀態(tài)都表把問題的一切狀態(tài)都表示出來示出來,其次定義算符其次定義算符,完成狀態(tài)的轉(zhuǎn)換完成狀態(tài)的轉(zhuǎn)換問題的求解過程就是一個把算符不斷地作用于狀態(tài)的過程問題的求解過程就是一個把算符不斷地作用于狀態(tài)的過程.如果在使用如果在使用某個算符后得到的狀態(tài)就是目標狀態(tài)某個算符后得到的狀態(tài)就是目標狀態(tài),就得到了問題的解就得到了問題的

13、解.這個解就是從這個解就是從初始狀態(tài)到目標狀態(tài)所用算符構(gòu)成的序列初始狀態(tài)到目標狀態(tài)所用算符構(gòu)成的序列.算符的一次使用算符的一次使用,就使問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)就使問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài).可能有多個算可能有多個算符序列都可使問題從初始狀態(tài)變到目標狀態(tài)符序列都可使問題從初始狀態(tài)變到目標狀態(tài),這就得到了多個解這就得到了多個解.對任何一個狀態(tài)對任何一個狀態(tài),可使用的算符可能不止一個可使用的算符可能不止一個,這樣由一個狀態(tài)所生成的這樣由一個狀態(tài)所生成的后繼狀態(tài)可能有多個后繼狀態(tài)可能有多個.如何選擇下一步的操作如何選擇下一步的操作,由搜索策略決定由搜索策略決定.Artificial Int

14、elligenceSearching: 13 Graduate University , Chinese academy of Sciences. 搜索控制策略（搜索控制策略（1）q 搜索控制策略搜索控制策略 不可撤回的控制策略不可撤回的控制策略; 試探性控制策略試探性控制策略 回溯型回溯型 圖搜索圖搜索Artificial IntelligenceSearching: 14 Graduate University , Chinese academy of Sciences. 搜索控制策略（搜索控制策略（2） 不可撤回的控制策略不可撤回的控制策略 例：八數(shù)碼問題例：八數(shù)碼問題 評價函數(shù)評價函數(shù)

15、:f： （規(guī)定規(guī)定: 評價函數(shù)非增）評價函數(shù)非增）2831647512384765與的差異為4Artificial IntelligenceSearching: 15 Graduate University , Chinese academy of Sciences. 搜索控制策略（搜索控制策略（3） 不可撤回的控制策略不可撤回的控制策略283164752831476523184765123847651238476523184765f=4f=3f=3f=0f=1f=21Artificial IntelligenceSearching: 16 Graduate University , Chin

16、ese academy of Sciences. 搜索控制策略（搜索控制策略（4） 不可撤回的控制策略不可撤回的控制策略283147652831476583214765813247658132476583214765f=3f=3f=3f=3f=3f=313824765f=213824765f=12Artificial IntelligenceSearching: 17 Graduate University , Chinese academy of Sciences. 搜索控制策略（搜索控制策略（5） 不可撤回的控制策略不可撤回的控制策略可能無解1258476312384765目標f=2Art

17、ificial IntelligenceSearching: 18 Graduate University , Chinese academy of Sciences. 搜索控制策略（搜索控制策略（6） 回溯策略回溯策略 例：四皇后問題例：四皇后問題QQQQArtificial IntelligenceSearching: 19 Graduate University , Chinese academy of Sciences. ()Artificial IntelligenceSearching: 20 Graduate University , Chinese academy of Sci

18、ences. ()Q(1,1)Artificial IntelligenceSearching: 21 Graduate University , Chinese academy of Sciences. ()QQ(1,1)(1,1)(2,3)Artificial IntelligenceSearching: 22 Graduate University , Chinese academy of Sciences. ()Q(1,1)(1,1)(2,3)Artificial IntelligenceSearching: 23 Graduate University , Chinese acade

19、my of Sciences. ()QQ(1,1)(1,1)(2,3)(1,1)(2,4)Artificial IntelligenceSearching: 24 Graduate University , Chinese academy of Sciences. ()QQ(1,1)(1,1)(2,3)(1,1)(2,4)Q(1,1)(2,4)(3.2)Artificial IntelligenceSearching: 25 Graduate University , Chinese academy of Sciences. ()QQ(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)

20、(2,4)(3.2)Artificial IntelligenceSearching: 26 Graduate University , Chinese academy of Sciences. ()Q(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Artificial IntelligenceSearching: 27 Graduate University , Chinese academy of Sciences. ()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Artificial IntelligenceSearch

21、ing: 28 Graduate University , Chinese academy of Sciences. ()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Artificial IntelligenceSearching: 29 Graduate University , Chinese academy of Sciences. ()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Artificial IntelligenceSearching: 30 Graduate

22、University , Chinese academy of Sciences. ()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)Artificial IntelligenceSearching: 31 Graduate University , Chinese academy of Sciences. QQQQ()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)(1,2)(1,2)(2,4)(1,2)(2,4)(3,1)(1,2)(2,4)(3,1)(4,3

23、)Artificial IntelligenceSearching: 32 Graduate University , Chinese academy of Sciences. 與與/或樹表示法（或樹表示法（1）q 基本概念基本概念 與與/或樹是用于表示問題及其求解過程的又一種形式化方或樹是用于表示問題及其求解過程的又一種形式化方法法. 復(fù)雜問題的簡化方法復(fù)雜問題的簡化方法 分解:把一個問題分解到不需再分解或不能再分解為把一個問題分解到不需再分解或不能再分解為止止,然后對每個子問題進行求解然后對每個子問題進行求解,然后把各子問題的解然后把各子問題的解復(fù)合起來復(fù)合起來,就得到原問題的解就得到原問

24、題的解. 等價變換:利用同構(gòu)或同態(tài)的等價變換利用同構(gòu)或同態(tài)的等價變換,把復(fù)雜問題轉(zhuǎn)把復(fù)雜問題轉(zhuǎn)換成若干個較為容易求解的新問題換成若干個較為容易求解的新問題.若新問題中有一若新問題中有一個可求解個可求解,則就得到了原問題的解則就得到了原問題的解.Artificial IntelligenceSearching: 33 Graduate University , Chinese academy of Sciences. 與與/或樹表示法（或樹表示法（2）例子例子:三階梵塔問題三階梵塔問題設(shè)有設(shè)有A,B,C三個金片以及三個鋼針三個金片以及三個鋼針,三個金片按自上而下從小到大的三個金片按自上而下從小到

25、大的順序穿在順序穿在1號鋼針上號鋼針上,要求把它們?nèi)恳频揭蟀阉鼈內(nèi)恳频?號鋼針上號鋼針上,而且每次只能而且每次只能移到一個金片移到一個金片,任何時候都不能把大的金片壓在小的金片上面任何時候都不能把大的金片壓在小的金片上面.用與用與/或樹表示或樹表示:問題分解問題分解(1)為了把三個金片全部移到為了把三個金片全部移到3號針上號針上,必須先把必須先把C移到移到3號針上號針上(2)為了移到為了移到C,必須把必須把A和和B移到移到2號針上號針上(3)當當C移到移到3針后針后,就可把就可把A和和B移到移到3針上針上,完成問題求解完成問題求解得到三個子問題得到三個子問題(1)把把A和和B移到移到2號

26、針的雙金片問題號針的雙金片問題(2)把把C移到移到3號針的單金片問題號針的單金片問題(3)把把A和和B移到移到3號針的雙金片問題號針的雙金片問題Artificial IntelligenceSearching: 34 Graduate University , Chinese academy of Sciences. 度量問題求解的性能度量問題求解的性能p 一般搜索策略可以通過下面四個準則來評價：一般搜索策略可以通過下面四個準則來評價：完備性：如果存在一個解答，該策略是否保證能夠找到？完備性：如果存在一個解答，該策略是否保證能夠找到？時間復(fù)雜性：需要多長時間可以找到解答？時間復(fù)雜性：需要多長時

27、間可以找到解答？空間復(fù)雜性：執(zhí)行搜索需要多少存儲空間？空間復(fù)雜性：執(zhí)行搜索需要多少存儲空間？最優(yōu)性：如果存在不同的幾個解答，該策略是否可以發(fā)現(xiàn)最高質(zhì)量的解答最優(yōu)性：如果存在不同的幾個解答，該策略是否可以發(fā)現(xiàn)最高質(zhì)量的解答？p 搜索策略反映了狀態(tài)空間或問題空間擴展的方法，也決定了狀態(tài)或問搜索策略反映了狀態(tài)空間或問題空間擴展的方法，也決定了狀態(tài)或問題的訪問順序。題的訪問順序。p 在在AI領(lǐng)域，狀態(tài)空間圖由初始狀態(tài)和算子隱含地表示，經(jīng)常是無限的領(lǐng)域，狀態(tài)空間圖由初始狀態(tài)和算子隱含地表示，經(jīng)常是無限的，它的復(fù)雜度根據(jù)下面三個值來表達：，它的復(fù)雜度根據(jù)下面三個值來表達： p 分支因子分支因子b：任何節(jié)點

28、的后繼的最大個數(shù)：任何節(jié)點的后繼的最大個數(shù)p 最淺的目標節(jié)點的深度最淺的目標節(jié)點的深度dp 狀態(tài)空間中任何路徑的最大長度狀態(tài)空間中任何路徑的最大長度mArtificial IntelligenceSearching: 35 Graduate University , Chinese academy of Sciences. 主要內(nèi)容主要內(nèi)容 概述概述 狀態(tài)空間搜索狀態(tài)空間搜索狀態(tài)空間的一般搜索過程狀態(tài)空間的一般搜索過程廣度優(yōu)先搜索廣度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索啟發(fā)式搜索啟發(fā)式搜索A A* *算法算法 問題規(guī)約搜索問題規(guī)約搜索 博弈博弈Artificial IntelligenceSear

29、ching: 36 Graduate University , Chinese academy of Sciences. 狀態(tài)空間搜索過程要點（狀態(tài)空間搜索過程要點（1）求解一個能夠滿足目標條件的問題可以表達為搜索一個圖以找到一個求解一個能夠滿足目標條件的問題可以表達為搜索一個圖以找到一個滿足目標狀態(tài)描述的節(jié)點問題滿足目標狀態(tài)描述的節(jié)點問題.搜索過程的要點如下搜索過程的要點如下:起始節(jié)點起始節(jié)點:對應(yīng)于初始狀態(tài)描述對應(yīng)于初始狀態(tài)描述后繼節(jié)點后繼節(jié)點:把適用于某個節(jié)點狀態(tài)描述的一些算符用來推算該節(jié)點把適用于某個節(jié)點狀態(tài)描述的一些算符用來推算該節(jié)點而得到的新節(jié)點而得到的新節(jié)點,稱為該節(jié)點的后繼節(jié)點

30、稱為該節(jié)點的后繼節(jié)點指針指針:從每個后繼節(jié)點返回指向其父輩節(jié)點從每個后繼節(jié)點返回指向其父輩節(jié)點檢查各后繼節(jié)點看是否為目標節(jié)點檢查各后繼節(jié)點看是否為目標節(jié)點.搜索過程擴展后繼節(jié)點的次序搜索過程擴展后繼節(jié)點的次序如果搜索是以接近起始節(jié)點的程度如果搜索是以接近起始節(jié)點的程度(由節(jié)點之間連結(jié)弧線的數(shù)目來由節(jié)點之間連結(jié)弧線的數(shù)目來衡量衡量)依次擴展節(jié)點依次擴展節(jié)點,稱為廣稱為廣(寬寬)度優(yōu)先搜索度優(yōu)先搜索如果搜索時首先擴展最新產(chǎn)生的節(jié)點如果搜索時首先擴展最新產(chǎn)生的節(jié)點,稱為深度優(yōu)先搜索稱為深度優(yōu)先搜索Artificial IntelligenceSearching: 37 Graduate Univer

31、sity , Chinese academy of Sciences. 狀態(tài)空間搜索過程要點（狀態(tài)空間搜索過程要點（2）指針指針 調(diào)整指針調(diào)整指針擴展一個節(jié)點擴展一個節(jié)點生成出該節(jié)點的所有后繼節(jié)點。生成出該節(jié)點的所有后繼節(jié)點?；〉馁M用弧的費用有一條弧連接有一條弧連接ni和和nj兩個節(jié)點兩個節(jié)點, 用用C(ni, nj)表示使用規(guī)則從表示使用規(guī)則從ni到到nj的的費用費用(耗散值耗散值)。 玉泉路玉泉路-天安門天安門路徑的耗散值路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。用。用C(ni, nj)表示從表示從ni到到

32、nj的路徑的耗散值。的路徑的耗散值。Artificial IntelligenceSearching: 38 Graduate University , Chinese academy of Sciences. 狀態(tài)空間的一般搜索過程（狀態(tài)空間的一般搜索過程（1）主要數(shù)據(jù)結(jié)構(gòu)主要數(shù)據(jù)結(jié)構(gòu)OPEN表表:存放剛生成的節(jié)點存放剛生成的節(jié)點,是還未擴展的節(jié)點是還未擴展的節(jié)點.一般是端一般是端節(jié)點節(jié)點.CLOSED表表:存放將要擴展或已擴展的節(jié)點存放將要擴展或已擴展的節(jié)點.或者是已被擴或者是已被擴展但還沒有在搜索樹中生成后繼節(jié)點的端節(jié)點展但還沒有在搜索樹中生成后繼節(jié)點的端節(jié)點,或者是非或者是非端節(jié)點端節(jié)

33、點Artificial IntelligenceSearching: 39 Graduate University , Chinese academy of Sciences. 狀態(tài)空間的一般搜索過程（狀態(tài)空間的一般搜索過程（2）(1)把初始節(jié)點把初始節(jié)點S0放入放入OPEN表表,并建立目前只包含并建立目前只包含S0的圖的圖,記為記為G(2)檢查檢查OPEN表是否為空表是否為空,若為空則問題無解若為空則問題無解,退出退出(3)把把OPEN表的第一個節(jié)點取出放入表的第一個節(jié)點取出放入CLOSED表表,記該節(jié)點為記該節(jié)點為n(4)考察考察n是否為目標節(jié)點是否為目標節(jié)點.如是如是,則問題得解則問題得

34、解,退出退出(5)擴展節(jié)點擴展節(jié)點n,生成一組子節(jié)點生成一組子節(jié)點.把其中不是節(jié)點把其中不是節(jié)點n先輩的那些節(jié)點記作集合先輩的那些節(jié)點記作集合M,并把并把這些子節(jié)點作為節(jié)點這些子節(jié)點作為節(jié)點n的子節(jié)點加入的子節(jié)點加入G中中(6)針對針對M中子節(jié)點的不同情況中子節(jié)點的不同情況,分別進行處理分別進行處理1.對于那些未曾在對于那些未曾在G中出現(xiàn)過的中出現(xiàn)過的M成員設(shè)置一個指向父節(jié)點成員設(shè)置一個指向父節(jié)點(即即n)的指針的指針,并并把它們放入把它們放入OPEN表表2.對于那些先前已在對于那些先前已在G中出現(xiàn)過的中出現(xiàn)過的M成員成員,確定是否需要修改它指向父節(jié)點確定是否需要修改它指向父節(jié)點的指針的指針3

35、.對于那些先前已在對于那些先前已在G中出現(xiàn)并且已經(jīng)擴展了的中出現(xiàn)并且已經(jīng)擴展了的M成員成員,確定是否需要修改確定是否需要修改其后繼節(jié)點指向父節(jié)點的指針其后繼節(jié)點指向父節(jié)點的指針(7)按某種搜索策略對按某種搜索策略對OPEN表中的節(jié)點進行排序表中的節(jié)點進行排序(8)轉(zhuǎn)第轉(zhuǎn)第(2)步步Artificial IntelligenceSearching: 40 Graduate University , Chinese academy of Sciences. 例子例子SOPENCLOSES 123 S 1,2,3 S 2,1,3 S 451,3 S,2 1,3,4,5 S,2 3,1,4,5 S,2

36、 1,4,5 S,2,3 61,4,5,6 S,2,3 Artificial IntelligenceSearching: 41 Graduate University , Chinese academy of Sciences. 2S13451,2,3 S 3,1,2 S OPENCLOSES 4,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1414,10,11,9,7,5,2 S,3,4,6,8,1,12

37、,13 Artificial IntelligenceSearching: 42 Graduate University , Chinese academy of Sciences. 2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 14OPEN表中的節(jié)點修改指針Artificial IntelligenceSearching: 43 Grad

38、uate University , Chinese academy of Sciences. 2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 Artificial IntelligenceSearching: 44 Graduate University , Chinese

39、academy of Sciences. 2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 CLOSE表中的節(jié)點修改指針Artificial IntelligenceSearching: 45 Graduate University , Chinese academy of S

40、ciences. 2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 CLOSE表中的節(jié)點(8)的后裔(10)修改指針Artificial IntelligenceSearching: 46 Graduate University , Chinese academy of Sci

41、ences. 狀態(tài)空間的一般搜索過程狀態(tài)空間的一般搜索過程(3)q注注:這是一個通用的搜索過程這是一個通用的搜索過程,后面討論的狀態(tài)空間各種搜索后面討論的狀態(tài)空間各種搜索策略都是其特例策略都是其特例.各種搜索策略的主要區(qū)別就是對各種搜索策略的主要區(qū)別就是對OPEN表中表中節(jié)點排序準則不同節(jié)點排序準則不同q算法結(jié)束后，將生成一個圖算法結(jié)束后，將生成一個圖G，稱為稱為搜索圖。同時由于每個。同時由于每個節(jié)點都有一個指針指向父節(jié)點，這些指針指向的節(jié)點構(gòu)成節(jié)點都有一個指針指向父節(jié)點，這些指針指向的節(jié)點構(gòu)成G的一個支撐樹，稱為的一個支撐樹，稱為搜索樹。 q從目標節(jié)點開始，將指針指向的狀態(tài)回串起來，即找到一

42、條從目標節(jié)點開始，將指針指向的狀態(tài)回串起來，即找到一條解路徑.q樹樹/不修改指針不修改指針; 圖圖/修改指針修改指針;q修改指針修改指針:找最優(yōu)解找最優(yōu)解 Artificial IntelligenceSearching: 47 Graduate University , Chinese academy of Sciences. 狀態(tài)空間的一般搜索過程狀態(tài)空間的一般搜索過程(4)搜索圖搜索圖2S134567891011121314Artificial IntelligenceSearching: 48 Graduate University , Chinese academy of Scien

43、ces. 狀態(tài)空間的一般搜索過程狀態(tài)空間的一般搜索過程(5)搜索樹搜索樹112S1324567891011121314Artificial IntelligenceSearching: 49 Graduate University , Chinese academy of Sciences. 廣度優(yōu)先搜索（廣度優(yōu)先搜索（1）搜索過程如下搜索過程如下:(1)把初始節(jié)點把初始節(jié)點S0放入放入OPEN表表(2)如果如果OPEN表為空表為空,則問題無解則問題無解,退出退出(3)把把OPEN表的第一個節(jié)點表的第一個節(jié)點(記為節(jié)點記為節(jié)點n)取出取出,放入放入CLOSED表表(4)考查節(jié)點考查節(jié)點n是否為

44、目標節(jié)點是否為目標節(jié)點.若是若是,則求得了問題的解則求得了問題的解,退退出出(5)若節(jié)點若節(jié)點n不可擴展不可擴展,則轉(zhuǎn)第則轉(zhuǎn)第(2)步步(6)擴展節(jié)點擴展節(jié)點n,將其子節(jié)點放入將其子節(jié)點放入OPEN表的表的尾部,并為每一個并為每一個子節(jié)點都配置指向父節(jié)點的指針子節(jié)點都配置指向父節(jié)點的指針,轉(zhuǎn)第轉(zhuǎn)第(2)步步Artificial IntelligenceSearching: 50 Graduate University , Chinese academy of Sciences. 2318476523184765283147652318476528314765283164752831476528

45、3164752831647528371465832147652814376528314576123784651238476512567312384765目標8234187654Artificial IntelligenceSearching: 51 Graduate University , Chinese academy of Sciences. 廣度優(yōu)先搜索（廣度優(yōu)先搜索（2）Complete? Yes (如果如果 b 是有限的是有限的)Time? 1+b+b2+b3+ +bd + b(bd-1) = O(bd+1)Space? O(bd+1)Optimal? Yes (如果每步代價為如果

46、每步代價為1)空間空間是大問題是大問題(和時間相比和時間相比)特點特點缺點缺點當目標節(jié)點距離初始節(jié)點較遠時會產(chǎn)生許多無用的節(jié)點當目標節(jié)點距離初始節(jié)點較遠時會產(chǎn)生許多無用的節(jié)點,搜索效率搜索效率低低優(yōu)點優(yōu)點只要問題有解只要問題有解,則總可以得到解則總可以得到解,而且是最短路徑的解而且是最短路徑的解Artificial IntelligenceSearching: 52 Graduate University , Chinese academy of Sciences. 深度優(yōu)先搜索（深度優(yōu)先搜索（1）搜索過程如下搜索過程如下:(1)把初始節(jié)點把初始節(jié)點S0放入放入OPEN表表(2)如果如果OPE

47、N表為空表為空,則問題無解則問題無解,退出退出(3)把把OPEN表的第一個節(jié)點表的第一個節(jié)點(記為節(jié)點記為節(jié)點n)取出取出,放入放入CLOSED表表(4)考查節(jié)點考查節(jié)點n是否為目標節(jié)點是否為目標節(jié)點.若是若是,則求得了問題的解則求得了問題的解,退退出出(5)若節(jié)點若節(jié)點n不可擴展不可擴展,則轉(zhuǎn)第則轉(zhuǎn)第(2)步步(6)擴展節(jié)點擴展節(jié)點n,將其子節(jié)點放入將其子節(jié)點放入OPEN表的表的首部,并為每一個并為每一個子節(jié)點都配置指向父節(jié)點的指針子節(jié)點都配置指向父節(jié)點的指針,轉(zhuǎn)第轉(zhuǎn)第(2)步步Artificial IntelligenceSearching: 53 Graduate University

48、, Chinese academy of Sciences. 23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476528364175283167548321476528371465281437652831457623456789abcd12384765目標Artificial IntelligenceSearching: 54 Graduate University , Chinese academy of S

49、ciences. 深度優(yōu)先搜索（深度優(yōu)先搜索（2）Complete? No: 當空間為無限深度時當空間為無限深度時Time? O(bm): 如果如果 m 比比d大很多則比較嚴重大很多則比較嚴重Space? O(bm), 線性空間線性空間Optimal? No特點特點缺點缺點如果目標節(jié)點不在搜索所進入的分支上如果目標節(jié)點不在搜索所進入的分支上,而該分支又是而該分支又是一個無窮分支一個無窮分支,則就得不到解則就得不到解.因此該算法是不完備的因此該算法是不完備的優(yōu)點優(yōu)點如果目標節(jié)點不在搜索所進入的分支上如果目標節(jié)點不在搜索所進入的分支上,則可以較快地則可以較快地得到解得到解Artificial In

50、telligenceSearching: 55 Graduate University , Chinese academy of Sciences. 有界深度優(yōu)先搜索有界深度優(yōu)先搜索q 定義搜索深度的界限定義搜索深度的界限dm,當搜索深度達到了深度界限當搜索深度達到了深度界限,而尚未出現(xiàn)目標節(jié)點時而尚未出現(xiàn)目標節(jié)點時,就就換一個分支進行搜索換一個分支進行搜索 搜索過程如下搜索過程如下:(1)把初始節(jié)點把初始節(jié)點S0放入放入OPEN表表,置置S0的深度的深度d(S0)=0(2)如果如果OPEN表為空表為空,則問題無解則問題無解,退出退出(3)把把OPEN表的第一個節(jié)點表的第一個節(jié)點(記為節(jié)點記為

51、節(jié)點n)取出取出,放入放入CLOSED表表(4)考查節(jié)點考查節(jié)點n是否為目標節(jié)點是否為目標節(jié)點.若是若是,則求得了問題的解則求得了問題的解,退出退出(5)如果節(jié)點如果節(jié)點n的深度的深度d(節(jié)點節(jié)點n)=dm,則轉(zhuǎn)第則轉(zhuǎn)第(2)步步(6)若節(jié)點若節(jié)點n不可擴展不可擴展,則轉(zhuǎn)第則轉(zhuǎn)第(2)步步(7)擴展節(jié)點擴展節(jié)點n,將其子節(jié)點放入將其子節(jié)點放入OPEN表的表的首部,并為每一個子節(jié)點都配置指向并為每一個子節(jié)點都配置指向父節(jié)點的指針父節(jié)點的指針,轉(zhuǎn)第轉(zhuǎn)第(2)步步Artificial IntelligenceSearching: 56 Graduate University , Chinese ac

52、ademy of Sciences. 迭代加深搜索（迭代加深搜索（1 1） 對于有界深度搜索策略，有下面幾點需要說明：對于有界深度搜索策略，有下面幾點需要說明： 1 1）在有界深度搜索算法中，深度限制）在有界深度搜索算法中，深度限制d dm m是一個很重要的參數(shù)。是一個很重要的參數(shù)。 2 2）深度限制）深度限制d dm m不能太大。不能太大。 3 3）有界深度搜索的主要問題是深度限制值）有界深度搜索的主要問題是深度限制值d dm m的選取。的選取。 問題：但是對很多問題，我們并不知道該值到底為多少，問題：但是對很多問題，我們并不知道該值到底為多少，直到該問題求解完成了，才可以確定出深度限制直到

53、該問題求解完成了，才可以確定出深度限制d dm m。Artificial IntelligenceSearching: 57 Graduate University , Chinese academy of Sciences. 迭代加深搜索（迭代加深搜索（2 2） 改進方法改進方法-迭代加深搜索算法迭代加深搜索算法 ：先任意給定一個較小的數(shù)作為先任意給定一個較小的數(shù)作為d dm m，然后按有界深度算法然后按有界深度算法搜索，若在此深度限制內(nèi)找到了解，則算法結(jié)束；如在搜索，若在此深度限制內(nèi)找到了解，則算法結(jié)束；如在此限度內(nèi)沒有找到問題的解，則增大深度限制此限度內(nèi)沒有找到問題的解，則增大深度限制d

54、 dm m，繼續(xù)繼續(xù)搜索。搜索。 迭代加深搜索是一種回避選擇最優(yōu)深度限制問題的策略迭代加深搜索是一種回避選擇最優(yōu)深度限制問題的策略，它是試圖嘗試所有可能的深度限制：首先深度為，它是試圖嘗試所有可能的深度限制：首先深度為0 0，然后深度為然后深度為1 1，然后為，然后為2 2，等等，一直進行下去。，等等，一直進行下去。 問題：問題：迭代加深搜索看起來會很浪費，因為很多節(jié)點都要擴展迭代加深搜索看起來會很浪費，因為很多節(jié)點都要擴展多次。多次。 Artificial IntelligenceSearching: 58 Graduate University , Chinese academy of S

55、ciences. 迭代加深搜索（迭代加深搜索（3 3）Artificial IntelligenceSearching: 59 Graduate University , Chinese academy of Sciences. 迭代加深搜索（迭代加深搜索（4 4）Artificial IntelligenceSearching: 60 Graduate University , Chinese academy of Sciences. 迭代加深搜索（迭代加深搜索（5 5）Artificial IntelligenceSearching: 61 Graduate University , Ch

56、inese academy of Sciences. 迭代加深搜索（迭代加深搜索（6 6）Artificial IntelligenceSearching: 62 Graduate University , Chinese academy of Sciences. 迭代加深搜索（迭代加深搜索（6 6）深度為深度為d，分支因子為，分支因子為b的深度優(yōu)先搜索生成的節(jié)點數(shù)為：的深度優(yōu)先搜索生成的節(jié)點數(shù)為：NDLS = b0 + b1 + b2 + + bd-2 + bd-1 + bd 深度為深度為d，分支因子為，分支因子為b的迭代加深搜索生成的節(jié)點數(shù)為的迭代加深搜索生成的節(jié)點數(shù)為NIDS = (d+

57、1)b0 + d b1 + (d-1)b2 + + 3bd-2 +2bd-1 + 1bd 對于對于 b = 10, d = 5, NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111 NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456增加增加 = (123,456 - 111,111)/111,111 = 11%Artificial IntelligenceSearching: 63 Graduate University , Chinese academy of Scie

58、nces. 迭代加深搜索（迭代加深搜索（7 7） Complete? Yes Time? (d+1)b0 + d b1 + (d-1)b2 + + bd = O(bd) Space? O(bd) Optimal? Yes, 如果每步代價為如果每步代價為1Artificial IntelligenceSearching: 64 Graduate University , Chinese academy of Sciences. 代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索q邊上標有代價邊上標有代價(或費用或費用)的樹稱為代價樹的樹稱為代價樹qg(x)表示從初始節(jié)點表示從初始節(jié)點S0到節(jié)點到節(jié)點x的代

59、價的代價,c(x1,x2)表示從父節(jié)點表示從父節(jié)點x1到子節(jié)點到子節(jié)點x2的代價的代價,則有則有 g(x2)=g(x1)+c(x1,x2)搜索過程如下搜索過程如下:1)把初始節(jié)點把初始節(jié)點S0放入放入OPEN表表,令令g(S0)=02)如果如果OPEN表為空表為空,則問題無解則問題無解,退出退出3)把把OPEN表的第一個節(jié)點表的第一個節(jié)點(記為節(jié)點記為節(jié)點n)取出取出,放入放入CLOSED表表4)考查節(jié)點考查節(jié)點n是否為目標節(jié)點是否為目標節(jié)點.若是若是,則求得了問題的解則求得了問題的解,退出退出5)若節(jié)點若節(jié)點n不可擴展不可擴展,則轉(zhuǎn)第則轉(zhuǎn)第(2)步步6)擴展節(jié)點擴展節(jié)點n,將其子節(jié)點放入將其

60、子節(jié)點放入OPEN表中表中,并為每一個子節(jié)點都配置指向父并為每一個子節(jié)點都配置指向父節(jié)點的指針節(jié)點的指針;計算各子節(jié)點的代價計算各子節(jié)點的代價,并按各節(jié)點的代價對并按各節(jié)點的代價對OPEN表中表中全部節(jié)點進行排序進行排序(按從小到大的順序按從小到大的順序),然后轉(zhuǎn)第然后轉(zhuǎn)第(2)步步Artificial IntelligenceSearching: 65 Graduate University , Chinese academy of Sciences. 代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索搜索過程如下搜索過程如下:1)把初始節(jié)點把初始節(jié)點S0放入放入OPEN表表2)如果如果OPEN表為空