人工智能搜索策略課件

1、第1-2章 搜索策略基本概念狀態(tài)空間的搜索策略 A算法與/或圖的搜索策略其它搜索策略搜索的完備性和效率第1-2章 搜索策略基本概念狀態(tài)空間的搜索策略與/或樹的搜索策略搜索的完備性和效率基本概念推理什么是推理：依據(jù)一定的規(guī)則（策略）從已知的事實(shí)推出新事實(shí)（結(jié)論）的過程稱為推理。基本概念推理推理方式及其分類 演繹推理、歸納推理、默認(rèn)推理 確定推理、不確定推理 單調(diào)推理、非單調(diào)推理 啟發(fā)式推理、非啟發(fā)式推理 基本概念 - 搜索什么叫搜索：根據(jù)問題的實(shí)際情況不斷尋找可用的知識(shí)，從而構(gòu)造一條代價(jià)較小的推理線路，使問題得到解的過程稱為搜索。盲目搜索：按預(yù)定的控制策略進(jìn)行搜索，在搜索過程中獲得的中間信息不用

2、來改進(jìn)控制策略。啟發(fā)式搜索：在搜索過程中加入了與問題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝最有利的方向前進(jìn)，加速求解過程并得到最優(yōu)解。基本概念 - 狀態(tài)空間表示法狀態(tài)：描述某一類事物中各不同事物之間的差異而引入的一組變量或多維數(shù)組。 Sk=(Sk0,Sk1,Skn)算符(算子) ：引起狀態(tài)中某些分量發(fā)生變化，從而使問題從一個(gè)狀態(tài)改變到另一個(gè)狀態(tài)的操作，以F指示。狀態(tài)空間：以SP指示，表示問題的全部可能的狀態(tài)及其相互關(guān)系，狀態(tài)和算符的集合。一般用三元式表示： SP = ( S0 , F , Sg )基本概念 - 狀態(tài)空間表示法狀態(tài)空間以SP指示，也可表示為一個(gè)二元組： SP = （S, F）S-在問題

3、求解（即搜索）過程中所有可達(dá)的合法狀態(tài)構(gòu)成的集合；F-操作算子的集合，操作算子的執(zhí)行導(dǎo)致狀態(tài)的變遷。 所以，狀態(tài)空間又可描述為一個(gè)有向圖，其節(jié)點(diǎn)指示狀態(tài)，節(jié)點(diǎn)間的有向弧表示狀態(tài)變遷，弧上的標(biāo)簽則指示導(dǎo)致狀態(tài)變遷的操作算子。狀態(tài)可通過定義某種數(shù)據(jù)結(jié)構(gòu)來描述，用于記載問題求解（即搜索）過程中某一時(shí)刻問題現(xiàn)狀的快照。 狀態(tài)空間表示法舉例：八數(shù)碼游戲八數(shù)碼游戲問題：一個(gè)33棋盤，有八張牌1，2， 8及一個(gè)空格，空格周圍的牌可以向空格移動(dòng)。求解：給定一個(gè)初始狀態(tài)S0 、一個(gè)目標(biāo)狀態(tài)Sg ，求從S0到Sg的走步序列。 S0狀態(tài)狀態(tài) Sg狀態(tài)狀態(tài)解：解： 綜合數(shù)據(jù)庫(kù)（狀態(tài)及狀態(tài)空間描述）綜合數(shù)據(jù)庫(kù)（狀態(tài)及狀

4、態(tài)空間描述） 定義：矩陣定義：矩陣（Sij）表示任何狀態(tài)，其中：表示任何狀態(tài)，其中： Sij0,1, 8 1i,j3 Sij 互不相同互不相同狀態(tài)空間：狀態(tài)空間：9 9！=362,880=362,880 種狀態(tài)種狀態(tài)狀態(tài)空間表示法舉例：八數(shù)碼游戲八數(shù)碼游戲 規(guī)則集規(guī)則集（算符（算符F）設(shè)：空格移動(dòng)代替數(shù)碼移動(dòng)。至多有四種移動(dòng)的可能：上、下、左、右。設(shè)：空格移動(dòng)代替數(shù)碼移動(dòng)。至多有四種移動(dòng)的可能：上、下、左、右。定義：定義： S Sijij為矩陣第為矩陣第i i行行j j列的數(shù)碼列的數(shù)碼; ; 其中：其中：i i0 0,j,j0 0表示空格所在的位置，則表示空格所在的位置，則S Si0j0i0j

5、0=0 =0 （0 0代表空格）代表空格）空格空格左移規(guī)則：左移規(guī)則： if jif j0 0-1-11 then j1 then j0 0j j0 0-1; S-1; Si0j0i0j00 0解釋：如果當(dāng)前空格不在第一列，則空格左移一位，新的空格位置賦值為解釋：如果當(dāng)前空格不在第一列，則空格左移一位，新的空格位置賦值為0 0。同理：同理：右移規(guī)則：右移規(guī)則：if jif j0 0+1+13 then j3 then j0 0j j0 0+1; S+1; Si0j0i0j00 0 上移規(guī)則：上移規(guī)則：if iif i0 0-1-11 then i1 then i0 0i i0 0-1; S-1

6、; Si0j0i0j00 0 下移規(guī)則：下移規(guī)則：if iif i0 0+1+13 then i3 then i0 0i i0 0+1; S+1; Si0j0i0j00 0狀態(tài)空間表示法舉例：八數(shù)碼游戲八數(shù)碼游戲 控制策略控制策略需要解決的問題需要解決的問題： 在當(dāng)前可用的規(guī)則中如何選擇其中之一來實(shí)現(xiàn)狀態(tài)的在當(dāng)前可用的規(guī)則中如何選擇其中之一來實(shí)現(xiàn)狀態(tài)的轉(zhuǎn)換轉(zhuǎn)換 實(shí)時(shí)判斷是否到達(dá)目標(biāo)狀態(tài)實(shí)時(shí)判斷是否到達(dá)目標(biāo)狀態(tài)狀態(tài)空間表示法舉例：八數(shù)碼游戲八數(shù)碼游戲 隨機(jī)產(chǎn)生的八數(shù)碼排列轉(zhuǎn)換成目標(biāo)共有兩種可能，而隨機(jī)產(chǎn)生的八數(shù)碼排列轉(zhuǎn)換成目標(biāo)共有兩種可能，而且這兩種不可能同時(shí)成立，也就是奇數(shù)排列和偶數(shù)排列。且這

7、兩種不可能同時(shí)成立，也就是奇數(shù)排列和偶數(shù)排列。 狀態(tài)空間表示法舉例：八數(shù)碼游戲八數(shù)碼游戲某初始狀態(tài)某初始狀態(tài) 奇數(shù)排列奇數(shù)排列 偶數(shù)排列偶數(shù)排列計(jì)算公式 （），其中（）就是一個(gè)數(shù)的前面比這個(gè)數(shù)小的數(shù)的個(gè)數(shù)，判斷為奇數(shù)或偶數(shù) 設(shè)N個(gè)傳教士帶領(lǐng)N個(gè)野人劃船渡河，且為安全起見，渡河需遵從二個(gè)約束： 1）船上人數(shù)不得超過載重限量，設(shè)為K個(gè)人； 2）為預(yù)防野人攻擊，任何時(shí)刻（包括兩岸、船上）野人數(shù)目不得超過傳教士。 狀態(tài)空間表示法舉例：傳教士和野人問題傳教士和野人問題狀態(tài)空間表示法舉例：傳教士和野人問題傳教士和野人問題 為便于理解狀態(tài)空間表示方法，我們簡(jiǎn)化該問題到一為便于理解狀態(tài)空間表示方法，我們簡(jiǎn)化該

8、問題到一個(gè)特例：個(gè)特例：N=3N=3，K=2K=2；并以；并以變量變量mm和和c c分別指示傳教士和分別指示傳教士和野人在左岸或船上的實(shí)際人數(shù)，變量野人在左岸或船上的實(shí)際人數(shù)，變量b b指示船是否在左指示船是否在左岸（值岸（值1 1指示船在左岸，否則為指示船在左岸，否則為0 0）。從而上述。從而上述約束條件約束條件轉(zhuǎn)變?yōu)檗D(zhuǎn)變?yōu)閙 + c = cm + c = c。 考慮到在這個(gè)渡河問題中，左岸的狀態(tài)描述（考慮到在這個(gè)渡河問題中，左岸的狀態(tài)描述（mm、c c和和b b）可以決定右岸的狀態(tài)，所以整個(gè)問題狀態(tài)就可以）可以決定右岸的狀態(tài)，所以整個(gè)問題狀態(tài)就可以左岸的狀態(tài)來描述，以簡(jiǎn)化問題的表示。左岸的

9、狀態(tài)來描述，以簡(jiǎn)化問題的表示。 設(shè)初始狀態(tài)下傳教士、野人和船都在左岸，目標(biāo)狀設(shè)初始狀態(tài)下傳教士、野人和船都在左岸，目標(biāo)狀態(tài)下這三者均在右岸，態(tài)下這三者均在右岸，問題狀態(tài)以三元組（問題狀態(tài)以三元組（m,c,bm,c,b）表示）表示，則問題求解任務(wù)可描述為：則問題求解任務(wù)可描述為： (3(3，3 3，1 1） （0 0，0 0，0 0） 在這個(gè)簡(jiǎn)單問題中，狀態(tài)空間可能的狀態(tài)總數(shù)為在這個(gè)簡(jiǎn)單問題中，狀態(tài)空間可能的狀態(tài)總數(shù)為4 44 42 = 32 2 = 32 ，但由于要遵守安全約束，只有，但由于要遵守安全約束，只有2020個(gè)狀個(gè)狀態(tài)是合法的。下面是幾個(gè)不合法狀態(tài)的例子：態(tài)是合法的。下面是幾個(gè)不合法

10、狀態(tài)的例子： (1 (1，0 0，1 1），）， （1 1，2 2，1 1），）， （2 2，3 3，1 1） 鑒于存在不合法狀態(tài)，還會(huì)導(dǎo)致某些合法狀態(tài)不可鑒于存在不合法狀態(tài)，還會(huì)導(dǎo)致某些合法狀態(tài)不可達(dá)，例如狀態(tài)（達(dá)，例如狀態(tài)（0 0，0 0，1 1），（），（0 0，3 3，0 0）。結(jié)果，這個(gè)）。結(jié)果，這個(gè)問題總共只有問題總共只有1616個(gè)可達(dá)的合法狀態(tài)。個(gè)可達(dá)的合法狀態(tài)。狀態(tài)空間表示法舉例：傳教士和野人問題傳教士和野人問題 渡河問題中的渡河問題中的操作算子操作算子可以定義可以定義2 2類：類：L(m,c)L(m,c)、R(m,c)R(m,c)，分別指示從左岸到右岸的劃船操作和從，分別指示

11、從左岸到右岸的劃船操作和從右岸回到左岸的劃船操作。右岸回到左岸的劃船操作。由于由于mm和和c c取值的可能取值的可能組合只有組合只有5 5個(gè)：個(gè)：1010，2020，11 11，0101，0202，故而總共，故而總共有有1010個(gè)操作算子。個(gè)操作算子。 渡河問題狀態(tài)空間的有向圖渡河問題狀態(tài)空間的有向圖 狀態(tài)空間表示法舉例：傳教士和野人問題傳教士和野人問題狀態(tài)空間表示法舉例：傳教士和野人問題傳教士和野人問題基本概念 - 與/或樹表示法與/或樹又稱問題歸約。問題歸約是人們求解問題常用的策略，就是把復(fù)雜的問題變換為若干需要同時(shí)處理的較為簡(jiǎn)單的子問題后再加以分別求解。只有當(dāng)這些子問題全部解決時(shí)，問題才

12、算解決，問題的解答就由子問題的解答聯(lián)合構(gòu)成?；靖拍?- 與/或樹表示法與/或圖：應(yīng)用問題歸約策略得到的狀態(tài)空間圖。與節(jié)點(diǎn)：用園弧將幾條節(jié)點(diǎn)間關(guān)聯(lián)弧連接在一起去指示問題分解為若干子問題，只有這些子問題全部解決才會(huì)導(dǎo)致問題的解決。 或節(jié)點(diǎn)：?jiǎn)栴}（子問題）也可能激活多條重寫規(guī)則（等價(jià)變換）；顯然，只要有一條激活的重寫規(guī)則能導(dǎo)致最終的解答成功即可。 基本概念 - 與/或樹表示法本原問題：不可或不需再通過變換，可以直接得到問題的解的子問題。 端節(jié)點(diǎn)與終止節(jié)點(diǎn)：沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為端節(jié)點(diǎn)（葉節(jié)點(diǎn)）。本原問題對(duì)應(yīng)的節(jié)點(diǎn)稱為終止節(jié)點(diǎn)?；靖拍?- 與/或樹表示法可解節(jié)點(diǎn)： 終止節(jié)點(diǎn)是可解節(jié)點(diǎn)。 如果非終止節(jié)

13、點(diǎn)有“或”子節(jié)點(diǎn)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)至少有一個(gè)能解，則該非終止節(jié)點(diǎn)是可解節(jié)點(diǎn)。 如果非終止節(jié)點(diǎn)有“與”子節(jié)點(diǎn)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)都能解，則該非終止節(jié)點(diǎn)是可解節(jié)點(diǎn)?；靖拍?- 與/或樹表示法不可解節(jié)點(diǎn)： 沒有后裔的非終止節(jié)點(diǎn)是不可解節(jié)點(diǎn)（該節(jié)點(diǎn)是葉節(jié)點(diǎn)但不是本原問題）。 如果非終止節(jié)點(diǎn)有“或”子節(jié)點(diǎn)，當(dāng)且僅當(dāng)所有子節(jié)點(diǎn)都不能解，則該非終止節(jié)是不可解節(jié)點(diǎn)。 如果非終止節(jié)點(diǎn)有“與”子節(jié)點(diǎn)，至少有一個(gè)子節(jié)點(diǎn)不能解，則該非終止節(jié)點(diǎn)是不可解節(jié)點(diǎn)。解樹：由可解節(jié)點(diǎn)構(gòu)成，并且由這些可解節(jié)點(diǎn)可推出初始節(jié)點(diǎn)為可解節(jié)點(diǎn)的子樹。基本概念 - 與/或樹表示法目標(biāo)目標(biāo)初始節(jié)點(diǎn)sabc與或圖是一個(gè)超圖，節(jié)點(diǎn)間通過連接符連接。

14、K-連接符：.K個(gè)目標(biāo)目標(biāo)初始節(jié)點(diǎn) 解圖：基本概念 - 與/或樹表示法解圖的耗散值計(jì)算解圖的耗散值計(jì)算：設(shè)K_連接符的耗散值為K，G的耗散值為K(n,N) 若n 是N的一個(gè)元素，則K(n,N)=0 若n有一個(gè)到解圖中后繼節(jié)點(diǎn)集n1, n2 ni的外向連接符，設(shè)該連接符的耗散值為Cn，則 K(n,N) Cn+ K(n1,N)+ K(n2,N)+ + K(ni,N)基本概念 - 與/或樹表示法左圖耗散值左圖耗散值 K(n0,N) 1+ K(n1,N) 1+1+ K(n3,N) 1+1+2+ K(n5,N)+ K(n6,N) 1+1+2+2+ K(n7,N)+ K(n8,N)+2+ K(n7,N)+

15、 K(n8,N) 1+ 1+ 2+ 2+ 0+ 0+ 2+ 0+ 0 8n4n5n0n8n7n0n3n6n7n5n8n1右圖耗散值右圖耗散值 K(n0,N) 2+ K(n4,N) + K(n5,N) 2+ 1+K(n5N) + 2+K(n7,N) +K(n8,N) 2+ 1+ 2+K(n7,N) +K(n8,N) + 2+K(n7,N) +K(n8,N) 2+ 1+ 2+ 0+ 0+ 2+ 0+ 0 7與/或樹表示法舉例：梵塔問題梵塔問題 （1 1 1） （3 3 3） （1 2 2） （3 2 2） （3 2 2） （3 3 3） （1 1 1） （1 2 2） （1 1 1） （1 1 3

16、） （3 2 2） （3 2 1） （3 2 1） （3 3 1） （3 3 1） （3 3 3） （1 2 3） （1 2 2） （1 1 3） （1 2 3） ( c b a )與/或樹表示法舉例：符號(hào)積分問題符號(hào)積分問題符號(hào)積分是求不定積分原函數(shù)的問題，通過應(yīng)用各種代數(shù)和三角變換以及不定積分性質(zhì)（如函數(shù)和積分、分部積分等）可以把復(fù)雜的積分問題逐步歸約為若干個(gè)本原積分問題（可利用積分表直接求出原函數(shù)）。六十年代開發(fā)的SAINT系統(tǒng)。就是一個(gè)應(yīng)用問題歸約的符號(hào)積分系統(tǒng)。 與/或樹表示法舉例：符號(hào)積分問題符號(hào)積分問題作為一個(gè)例子，觀察： ( sin3x + x4/(x2 + 1) ) dx=s

17、in3xdx + (x4/(x2 + 1)dx=-(1 - cos2x)dcosx + (x2 - 1 + 1/(1 + x2)dx= (-dcosx + cos2xdcosx) + (x2dx - dx + (1/(1 + x2)dx ) = -cosx + cos3x/3 + x3/3 - x + arctgx 該積分問題首先分解為二個(gè)獨(dú)立的子問題，然后分別變換這二個(gè)積分子問題，并分解變換結(jié)果為若干本原積分問題，分別求解這些本原問題后再聯(lián)合成最終解答。 第1-2章 搜索策略基本概念狀態(tài)空間的搜索策略與/或樹的搜索策略搜索的完備性和效率第1-2章 搜索策略基本概念狀態(tài)空間的搜索策略與/或樹的

18、搜索策略搜索的完備性和效率狀態(tài)空間的搜索策略狀態(tài)空間的搜索以SE指示，可表示為一個(gè)五元組：SE = (S,F,E,S0,Sg)E -搜索引擎；S0 -問題的初始狀態(tài)， S0 S;Sg -問題的目標(biāo)狀態(tài)集， Sg S。狀態(tài)空間搜索的基本思想就是通過搜索引擎尋找一個(gè)操作算子的調(diào)用序列，使問題從初始狀態(tài)變遷到目標(biāo)狀態(tài)之一，而變遷過程中的狀態(tài)序列或相應(yīng)的操作算子調(diào)用序列稱為從初始狀態(tài)到目標(biāo)狀態(tài)的 解答路徑。搜索引擎可以設(shè)計(jì)為任意實(shí)現(xiàn)搜索算法的控制系統(tǒng)。 狀態(tài)空間的搜索策略通常，狀態(tài)空間的解答路徑有多條，但最短的只有1條或少數(shù)幾條。上述渡河問題就有無數(shù)條解答路徑（因?yàn)閯澊僮骺赡妫?，但只?條是最短的，

19、都包含11個(gè)操作算子的調(diào)用。由于一個(gè)狀態(tài)可以有多個(gè)可供選擇的操作算子，導(dǎo)致了多個(gè)待搜索的解答路徑。除了少數(shù)像渡河這樣的簡(jiǎn)單問題外，描述狀態(tài)空間的一般圖都很大，無法直觀地畫出，只能將其視為隱含圖，在搜索解答路徑的過程中只畫出搜索時(shí)直接涉及到的節(jié)點(diǎn)和弧線，構(gòu)成所謂的 搜索圖。 狀態(tài)空間的搜索策略八數(shù)碼問題的搜索圖。對(duì)于八數(shù)碼游戲，可能的棋盤布局（問題狀態(tài)）總共9!=362880個(gè)，由于棋盤的對(duì)稱性，實(shí)際只有這個(gè)總數(shù)的一半。顯然，我們無法直觀地畫出整個(gè)狀態(tài)空間的一般圖，但搜索圖則小得多，可以圖示。狀態(tài)空間、搜索圖和解答狀態(tài)空間、搜索圖和解答路徑之間的關(guān)系路徑之間的關(guān)系 狀態(tài)空間的搜索策略盡管狀態(tài)空間

20、可以很大（例如國(guó)際象棋），但只要確保搜索空間足夠小，就能在合理的時(shí)間范圍內(nèi)搜索到問題解答。搜索空間的壓縮程度主要取決于搜索引擎采用的搜索算法。換言之，當(dāng)問題有解時(shí)，使用不同的搜索策略，找到解答路徑時(shí)，搜索圖的大小是有區(qū)別的。 一些基本概念節(jié)點(diǎn)深度：根節(jié)點(diǎn)深度=0其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+10123一些基本概念（續(xù)1）路徑設(shè)一節(jié)點(diǎn)序列為(n0, n1,nk)，對(duì)于i=1,k，若節(jié)點(diǎn)ni-1具有一個(gè)后繼節(jié)點(diǎn)ni，則該序列稱為從n0到nk的路徑。路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。用C(ni, nj)表示從ni到nj的路徑的耗散值。一些基本概念（續(xù)1）擴(kuò)展一個(gè)節(jié)點(diǎn)生

21、成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)，并給出它們之間的耗散值。這一過程稱為“擴(kuò)展一個(gè)節(jié)點(diǎn)”。狀態(tài)空間的一般搜索過程一般圖搜索算法一般圖搜索算法為建立該算法，令： s -指示初始狀態(tài)節(jié)點(diǎn)；G -指示搜索圖；OPEN -作為存放待擴(kuò)展節(jié)點(diǎn)的表；CLOSED -作為存放已被擴(kuò)展節(jié)點(diǎn)的表；MOVE-FIRST(OPEN) -指示取OPEN表首的節(jié)點(diǎn)作為當(dāng)前要被擴(kuò)展的節(jié)點(diǎn)n，同時(shí)將節(jié)點(diǎn)n移至CLOSE表；SNS -子節(jié)點(diǎn)集合； 狀態(tài)空間的一般搜索過程該算法的一般過程如下：1） G := s； / 即算法開始時(shí)搜索圖只包括初始狀態(tài)節(jié)點(diǎn)； 2 ） OPEN := (s), CLOSED := ()； / 即此時(shí)僅有作為

22、待擴(kuò)展節(jié)點(diǎn)，而CLOSE表為空； 3）若OPEN是空表，則算法以失敗結(jié)束； / 因?yàn)榇藭r(shí)未搜索到解答（目標(biāo)狀態(tài)），又無法繼續(xù)搜索； 4） n := MOVE-FIRST(OPEN)； 5）若n是目標(biāo)狀態(tài)節(jié)點(diǎn)，則搜索成功結(jié)束，并給出解答路徑； 6）擴(kuò)展節(jié)點(diǎn)n，將非節(jié)點(diǎn)n祖先的子節(jié)點(diǎn)置于子節(jié)點(diǎn)集合SNS中，并插入搜索圖G中； 狀態(tài)空間的一般搜索過程 7） 標(biāo)記和修改指針： 把SNS中的子節(jié)點(diǎn)分為三類：（1）全新節(jié)點(diǎn)，（2）已出現(xiàn)于OPEN表的節(jié)點(diǎn)，（3）已出現(xiàn)于CLOSED表的節(jié)點(diǎn)； / 后二類子節(jié)點(diǎn)實(shí)際上意味著具有新老二個(gè)父節(jié)點(diǎn)； 加第1類子節(jié)點(diǎn)于OPEN表，并建立從子節(jié)點(diǎn)到父節(jié)點(diǎn)n的指針； 比

23、較第2類子節(jié)點(diǎn)經(jīng)由新、老父節(jié)點(diǎn)到達(dá)初始狀態(tài)節(jié)點(diǎn)s的路徑代價(jià)，若經(jīng)由新父節(jié)點(diǎn)的代價(jià)較小， 則移動(dòng)子節(jié)點(diǎn)指向老父節(jié)點(diǎn)的指針，改為指向新父節(jié)點(diǎn)n； 對(duì)于第3類子節(jié)點(diǎn)作與第2類同樣的處理，并把這些子節(jié)點(diǎn)從CLOSED表中移出，重新加入OPEN表；8） 按某種原則重新排序OPEN表中的節(jié)點(diǎn)；9） 返回語句3）； Back算法A狀態(tài)空間的一般搜索過程狀態(tài)空間的一般搜索過程討論：1 OPEN中的節(jié)點(diǎn)是尚未擴(kuò)充的節(jié)點(diǎn)2 CLOSED的節(jié)點(diǎn)是已經(jīng)擴(kuò)充過的節(jié)點(diǎn) 3 G中的每個(gè)節(jié)點(diǎn)都唯一地指向一個(gè)父節(jié)點(diǎn)4 mi mj mk ml其中： mi是當(dāng)前被擴(kuò)充的全部節(jié)點(diǎn) mj是新擴(kuò)充的節(jié)點(diǎn) mk是已經(jīng)在OPEN中的節(jié)點(diǎn) m

24、l是已經(jīng)在CLOSED中的節(jié)點(diǎn)5 n是當(dāng)前被選中的節(jié)點(diǎn)，它是OPEN表中排列在最前面的一個(gè)節(jié)點(diǎn)。6 該算法對(duì)于連通圖及樹都適用。例：n=1S23456當(dāng)前節(jié)點(diǎn)ml節(jié)點(diǎn)討論： 空心節(jié)點(diǎn)是已經(jīng)在OPEN中的節(jié)點(diǎn)，如：1，4，5 實(shí)心節(jié)點(diǎn)是已經(jīng)在CLOSED中的節(jié)點(diǎn)，如：S，2，3 擴(kuò)充節(jié)點(diǎn)2后，對(duì)其原來搜索路徑進(jìn)行修改，由原來指向節(jié)點(diǎn)3改為指向節(jié)點(diǎn)1 對(duì)后繼節(jié)點(diǎn)4的搜索路徑進(jìn)行修改，由原來指向節(jié)點(diǎn)6改為指向節(jié)點(diǎn)2表示圖本身的連接關(guān)系搜索路徑修改后的搜索圖如下：n=1S23456下面給出兩種對(duì)下面給出兩種對(duì)OPEN表中節(jié)點(diǎn)按照某種規(guī)則排列的算法：表中節(jié)點(diǎn)按照某種規(guī)則排列的算法： 深度優(yōu)先算法深度優(yōu)先

25、算法 寬度優(yōu)先算法寬度優(yōu)先算法狀態(tài)空間的一般搜索過程一般圖搜索算法中，提高搜索效率的關(guān)鍵在于優(yōu)化OPEN表中節(jié)點(diǎn)的排序方式，若每次排在表首的節(jié)點(diǎn)都在最終搜索到的解答路徑上，則算法不會(huì)擴(kuò)展任何多余的節(jié)點(diǎn)就可快速結(jié)束搜索。所以排序方式成為研究搜索算法的焦點(diǎn)，并由此形成了多種搜索策略。一種簡(jiǎn)單的排序策略就是按預(yù)先確定的順序或隨機(jī)地排序新加入到OPEN表中的節(jié)點(diǎn)，常用的方式是深度優(yōu)先和寬度優(yōu)先。 狀態(tài)空間的一般搜索過程廣（寬）度優(yōu)先搜索寬度優(yōu)先-擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是置于OPEN表的后端（未部），即OPEN表作為排隊(duì)表使用，先進(jìn)先出，使搜索優(yōu)先向橫廣方向發(fā)展。 先進(jìn)先出排序策略使寬度優(yōu)先法能確

26、保搜索到最短的解答路徑。2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目標(biāo)82 3 41 8 7 6 54寬度優(yōu)先搜索的性質(zhì)當(dāng)問題有解時(shí)，一定能找到解當(dāng)問題為單位耗散值，且問題有解時(shí)，一定能找到最優(yōu)解方

27、法與問題無關(guān)，具有通用性效率較低屬于圖搜索方法深度優(yōu)先搜索深度優(yōu)先-擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是置于OPEN表的前端（首部），即OPEN表作為棧表使用，后進(jìn)先出，使搜索優(yōu)先向縱深方向發(fā)展。 當(dāng)一個(gè)問題有多個(gè)解答或多條解答路徑，且只須找到其中一個(gè)時(shí)，深度優(yōu)先法十分適用。例如8數(shù)碼游戲，若不限定從初始布局轉(zhuǎn)變到目標(biāo)布局所需移動(dòng)的棋牌個(gè)數(shù)（即移動(dòng)步數(shù)），則存在多條解答路徑，應(yīng)用深度優(yōu)先法可隨機(jī)地找到其中一條。深度優(yōu)先搜索 不過有些問題的狀態(tài)空間搜索或許會(huì)無限延伸，而又存在較短的解答路徑，則可以對(duì)搜索深度加以限制，以求提高搜索效率并確保尋找到較短的解答路徑。有界深度優(yōu)先如果當(dāng)前節(jié)點(diǎn)的深度不超過限定的

28、界限，則擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是置于OPEN表的前端（首部） ，后進(jìn)先出，使搜索優(yōu)先向縱深方向發(fā)展。 2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8

29、37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789abcd1 2 3 8 47 6 5目標(biāo)深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制最壞情況時(shí)，搜索空間等同于窮舉是一個(gè)通用的與問題無關(guān)的方法狀態(tài)空間搜索 上述二種搜索方法可直接應(yīng)用一般圖搜索算法實(shí)現(xiàn)，且只要問題有解就一定能搜索到解答。由于不需要設(shè)計(jì)特別的節(jié)點(diǎn)排序方法，從而簡(jiǎn)單易行，適合于許多復(fù)雜度不高的問題求解任務(wù)。 這兩種搜索方法的共同缺點(diǎn)是節(jié)點(diǎn)排序的盲目性，由于不采用領(lǐng)域?qū)ｉT知識(shí)去指導(dǎo)排序，往往會(huì)在白白搜索了大量無關(guān)的狀態(tài)節(jié)點(diǎn)后才碰到解答，所以也

30、稱為盲目搜索。 狀態(tài)空間搜索 只要引入與應(yīng)用領(lǐng)域相關(guān)的啟發(fā)式知識(shí)來指導(dǎo)OPEN表中節(jié)點(diǎn)的排序，使最有希望出現(xiàn)在較短解答路徑上的節(jié)點(diǎn)優(yōu)先考察，就能顯著提高搜索的有效性。用啟發(fā)式知識(shí)指導(dǎo)排序可劃分為二種方式: 局部排序-這是對(duì)上述深度優(yōu)先法的改進(jìn)，僅對(duì)新擴(kuò)展出來的子節(jié)點(diǎn)排序，使這些節(jié)點(diǎn)中最有希望者能優(yōu)先取出考察和擴(kuò)展。如：代價(jià)樹深度優(yōu)先。 全局排序-對(duì)OPEN表中的所有節(jié)點(diǎn)排序，使最有希望的節(jié)點(diǎn)排在表首。如：代價(jià)樹廣度優(yōu)先。 代價(jià)樹的廣度優(yōu)先搜索代價(jià)樹廣度優(yōu)先-對(duì)OPEN表中的所有節(jié)點(diǎn)按代價(jià)大小排序，使最有希望的節(jié)點(diǎn)排在表首，又稱為分枝界限法。是一種全局排序方法。 代價(jià)樹：邊上標(biāo)有代價(jià)（費(fèi)用）的樹

31、。代價(jià)：若用g(x)表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的代價(jià)，用c(x1,x2)表示從父節(jié)點(diǎn)x1到子節(jié)點(diǎn)x2的代價(jià)，則有： g(x2) = g(x1) + c(x1,x2)最有希望的節(jié)點(diǎn)：代價(jià)最小的節(jié)點(diǎn)。代價(jià)樹的廣度優(yōu)先搜索 例：巡回推銷員問題，從A出發(fā)并返回。ABCDE75100125125755010050125100A-E-D-B-C-A : 375代價(jià)樹的深度優(yōu)先搜索代價(jià)樹深度優(yōu)先-這是對(duì)上述深度優(yōu)先法的改進(jìn)，僅對(duì)新擴(kuò)展出來的子節(jié)點(diǎn)按代價(jià)大小排序，使這些節(jié)點(diǎn)中最有希望者能優(yōu)先取出考察和擴(kuò)展。是一種局部排序方法。啟發(fā)式搜索 搜索是一種試探性的查尋過程，引入啟發(fā)式知識(shí)可以減少搜索的盲目性，增加試探

32、的準(zhǔn)確性，為此就稱應(yīng)用啟發(fā)式知識(shí)的搜索是啟發(fā)式搜索。 啟發(fā)式知識(shí)對(duì)于搜索的指導(dǎo)作用可歸納為三方面： 選擇下一個(gè)要被擴(kuò)展的節(jié)點(diǎn)，排序OPEN表中的待擴(kuò)展節(jié)點(diǎn)是一種常用的方法。在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，僅僅有選擇性地生成部分有用的節(jié)點(diǎn)，而非所有可能的子節(jié)點(diǎn)。修剪掉某些估計(jì)不可能導(dǎo)致成功的子節(jié)點(diǎn)。 本節(jié)只討論如何應(yīng)用第一方面的啟發(fā)式知識(shí)于一般圖搜索。本節(jié)只討論如何應(yīng)用第一方面的啟發(fā)式知識(shí)于一般圖搜索。 啟發(fā)式搜索 啟發(fā)式信息用于解決OPEN表中節(jié)點(diǎn)的排列次序問題，方法是利用一個(gè)評(píng)(估)價(jià)函數(shù)計(jì)算OPEN表中節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值，按照函數(shù)值從大到?。ɑ驈男〉酱螅┡帕兴泄?jié)點(diǎn)。 一種有效的方法就是設(shè)計(jì)體現(xiàn)啟發(fā)式知識(shí)

33、的所謂評(píng)價(jià)函數(shù)來計(jì)算每個(gè)節(jié)點(diǎn)的得分，以便用于排列它們?cè)贠PEN表中的位置。 應(yīng)用這種評(píng)價(jià)函數(shù)來實(shí)現(xiàn)啟發(fā)式搜索的典型是算法A，其將評(píng)價(jià)函數(shù)f設(shè)計(jì)為：?jiǎn)l(fā)式搜索 -算法A算法A，其將評(píng)價(jià)函數(shù)f設(shè)計(jì)為： f(n) = g(n) + h(n) n-搜索圖中的某個(gè)當(dāng)前被擴(kuò)展的節(jié)點(diǎn)； f(n)-從初始狀態(tài)節(jié)點(diǎn)s0, 經(jīng)由節(jié)點(diǎn)n到達(dá)目標(biāo)狀節(jié)點(diǎn)sg，估計(jì)的最小路徑代價(jià)； g(n)-從s0到x ,估計(jì)的最小路徑代價(jià)； h(n)-從n到sg,估計(jì)的最小路徑代價(jià)； 通常我們可以用至今已發(fā)現(xiàn)的自s0到n的最短路徑作為g(n)值，但h(n)則要依賴于啟發(fā)式知識(shí)來加以估算，故h(n)稱為啟發(fā)式函數(shù)。 s0啟發(fā)式搜索 -算

34、法A啟發(fā)式函數(shù)舉例：移動(dòng)將牌游戲其中，B-黑色 W-白色 規(guī)則：每跨過1張牌費(fèi)用為1，最多可跨多2張牌。要求把所有的B都移到所有W的右邊。 啟發(fā)式搜索 -算法A算法A的設(shè)計(jì)與前述一般圖算法類同，主要的不同是在算法第（6）步中增加了子節(jié)點(diǎn)函數(shù)f的計(jì)算，在第（7）步中依賴于f值確定子節(jié)點(diǎn)指向父節(jié)點(diǎn)指針的修改，并在第（8）步中按f值從小到大排序OPEN表中的節(jié)點(diǎn)。算法A第（6）和第（7）步的修改如下： 啟發(fā)式搜索 -算法A (6) 擴(kuò)展節(jié)點(diǎn)n,將非節(jié)點(diǎn)n祖先的子節(jié)點(diǎn)置于子節(jié)點(diǎn)集合SNS中， 并插入搜索圖G中，對(duì)于SNS中每個(gè)子節(jié)點(diǎn)ni,計(jì)算f(n,ni) = g(n,ni) + h(ni);(7)

35、標(biāo)記和修改指針把SNS中的子節(jié)點(diǎn)分為三類（同一般圖搜索算法）；加第1類子節(jié)點(diǎn)于OPEN表（同一般圖搜索算法）；比較第2類子節(jié)點(diǎn)ni經(jīng)由新、老父節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值f(n,ni)、f(ni);若f(n,ni) f(ni)點(diǎn),則令f(ni) = f(n,ni),并移動(dòng)子節(jié)點(diǎn)指向老父節(jié)點(diǎn)的指針，改為指向新父節(jié)點(diǎn)。對(duì)第3類子節(jié)點(diǎn)作與第2類同樣的處理，并把這些子節(jié)點(diǎn)從CLOSED表中移出，重新加入OPEN表。 算法A1, OPEN:=(s), f(s):=g(s)+h(s);2, LOOP: IF OPEN=( ) THEN EXIT(FAIL);3, n:=FIRST(OPEN);4, IF GOAL(n

36、) THEN EXIT(SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) mi, 計(jì)算f(n, mi):=g(n, mi)+h(mi);算法A（續(xù)）ADD(mj, OPEN), 標(biāo)記mj到n的指針；IF f(n, mk)f(mk) THEN f(mk):=f(n, mk), 標(biāo)記mk到n的指針；IF f(n, ml)啟發(fā)式搜索 - A*算法(最佳圖搜索算法) 定義幾個(gè)函數(shù) g g* *(n)=k(s,n)(n)=k(s,n)：從初始節(jié)點(diǎn)s到節(jié)點(diǎn)n的最小代價(jià)路徑的實(shí)際代價(jià)值。 h h* *(n)=min k(n,t(n)=min k

37、(n,ti i) )：從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)集 ti 中所有節(jié)點(diǎn)最小代價(jià)路徑的實(shí)際代價(jià)值中的最小值。 f f* *(n)= g(n)= g* *(n) + h(n) + h* *(n)(n) ：從初始節(jié)點(diǎn)s約束通過節(jié)點(diǎn)n的最小代價(jià)路徑的代價(jià)值。g*(n)h*(n)sntf*(n)= g*(n) + h*(n)啟發(fā)式搜索 - A*算法(最佳圖搜索算法) 評(píng)價(jià)函數(shù)：f(n)= g(n) + h(n)f(n)= g(n) + h(n) 其中： f, g, h分別是f*, g*, h*的估計(jì)值。通常約定： f(n) 按照升序排列。 將評(píng)價(jià)函數(shù)f與f *相比較，實(shí)際上，f(n)、g(n)和h(n)分別是f*

38、(n)、g*(n)和h*(n)的近似值。 在理想的情況下，設(shè)計(jì)評(píng)價(jià)函數(shù)f時(shí)可以讓 g(n) = g*(n), h(n) = h*(n),則應(yīng)用該評(píng)價(jià)函數(shù)的算法A就能在搜索過程中,每次都正確地選擇下一個(gè)從OPEN表中取出加以擴(kuò)展的節(jié)點(diǎn)，從而不會(huì)擴(kuò)展任何無關(guān)的節(jié)點(diǎn)，就可順利地獲取解答路徑。 啟發(fā)式搜索 - A*算法(最佳圖搜索算法) 然而g*(n)和h*(n)在最短解答路徑找到前是未知的，故而幾乎不可能設(shè)計(jì)出這種理想的評(píng)價(jià)函數(shù)；而且對(duì)于復(fù)雜的應(yīng)用領(lǐng)域，即便是要設(shè)計(jì)接近于f*的f往往也是困難的。 一般來講，g(n)g(n)的值容易從迄今已生成的搜索樹中計(jì)算出來，不必專門定義計(jì)算公式。 例如就以節(jié)點(diǎn)深

39、度d(n)作為g(n),并有g(shù)(n)gg(n)g* *(n)(n)。 然而h(n)h(n)的設(shè)計(jì)依賴于啟發(fā)式知識(shí)的應(yīng)用，所以如何挖掘貼切的啟發(fā)式知識(shí)是設(shè)計(jì)評(píng)價(jià)函數(shù)乃至算法A的關(guān)鍵。 前述八數(shù)碼游戲例使用的啟發(fā)式函數(shù)w(n)就不夠貼切，從而在搜索過程中錯(cuò)誤地選用了節(jié)點(diǎn)d加以擴(kuò)展（見圖） 。 啟發(fā)式搜索 - A*算法(最佳圖搜索算法) 其實(shí)我們可以設(shè)計(jì)更接近于h*(n)的h(n)，如p(n),其值是節(jié)點(diǎn)n與目標(biāo)狀態(tài)節(jié)點(diǎn)相比較，每個(gè)錯(cuò)位棋牌在假設(shè)不受阻攔的情況下，移動(dòng)到目標(biāo)狀態(tài)相應(yīng)位置所需走步（移動(dòng)次數(shù)）的總和。顯然p(n)比w(n)更接近于h*(n)，因?yàn)閜(n)不僅考慮了錯(cuò)位因素，還考慮了錯(cuò)位的

40、距離（移動(dòng)次數(shù)）。啟發(fā)式搜索 - A*算法(最佳圖搜索算法) OPEN CLOSE0 sbac seacdi sblacdim sbenacdim sbdeqacdimo sbdel1成功結(jié)束啟發(fā)式搜索 - A*算法(最佳圖搜索算法) 評(píng)價(jià)函數(shù)：f(n)= g(n) + h(n)f(n)= g(n) + h(n) 其中： f, g, h分別是f*, g*, h*的估計(jì)值。 綜述： (1) g(n)比較容易得到，由上述定義，得： g(n) g*(n) (2) 關(guān)鍵設(shè)計(jì)啟發(fā)函數(shù)h(n)。 (3)當(dāng)h0 且g(n)=d(n)時(shí)， f(n)= d(n) 即 寬度優(yōu)先策略， d(n)：節(jié)點(diǎn)深度啟發(fā)式搜索

41、 - A*算法A*算法(最佳圖搜索算法) 定義： 對(duì)于算法A，如果有h(n) h*(n) ，即h(n) 在h*(n) 的下界范圍內(nèi)，則該算法稱為A*算法。 性質(zhì)啟發(fā)式搜索 - A*算法性質(zhì) 1.算法可采納性： （證明略） 給定任意圖，設(shè)存在從初始節(jié)點(diǎn)s s到目標(biāo)節(jié)點(diǎn)t t的路徑。如果算法能夠結(jié)束在從s s到t t的最佳解路徑上，則稱該算法是可采納的。定理1.1：對(duì)有限圖，如果從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。為了證明無限圖問題，有2個(gè)引理：?jiǎn)l(fā)式搜索 - A*算法性質(zhì) 1.算法可采納性： （證明略）引理1.1 ：對(duì)無限圖，若有從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的路徑，則A*不結(jié)束

42、時(shí)，在OPEN表中即使最小的一個(gè)f值也將增到任意大，或有f(n)f*(s)。引理1.2：A*結(jié)束前，OPEN表中必存在f(n)f*(s)。啟發(fā)式搜索 - A*算法性質(zhì) 1.算法可采納性： （證明略）定理1.2：對(duì)無限圖，若從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則A*一定成功結(jié)束。推論1.1：OPEN表上任一具有f(n) h* (n),則h(n)過強(qiáng)，使算法A失去可采納性，從而不能確保找到最短解答路徑。 設(shè)計(jì)接近、又總是 h* (n)的h(n)成為應(yīng)用A*算法搜索問題解答的關(guān)鍵，以壓縮搜索圖，提高搜索效率。 啟發(fā)式搜索 - A*算法性質(zhì)算法最優(yōu)性： （啟發(fā)式函數(shù)的強(qiáng)弱及其影響啟發(fā)式函數(shù)的強(qiáng)弱及其影

43、響 ）定理定理1-41-4： 給定兩個(gè)A*算法A1、A2，如果A2的啟發(fā)信息比A1多，則在任何存在從節(jié)點(diǎn)s s到目標(biāo)節(jié)點(diǎn)t t 路徑的圖上，搜索結(jié)束時(shí)由A2擴(kuò)充的每一個(gè)節(jié)點(diǎn)必定被A1擴(kuò)充。（ A1擴(kuò)充的節(jié)點(diǎn)數(shù)至少與A2 擴(kuò)充的節(jié)點(diǎn)數(shù)一樣多)。 （證明略）啟發(fā)式搜索 - A*算法性質(zhì)算法最優(yōu)性： （啟發(fā)式函數(shù)的強(qiáng)弱及其影響啟發(fā)式函數(shù)的強(qiáng)弱及其影響 ） 可以證明，對(duì)于解決同一問題的兩個(gè)算法A1和A2，若有h1(n) h2(n) h* (n)，則t(A1) t(A2) 其中，h1、h2分別是算法A1、A2 的啟發(fā)式函數(shù)，t指示相應(yīng)算法達(dá)到目標(biāo)狀態(tài)時(shí)搜索圖含的節(jié)點(diǎn)總數(shù)。 啟發(fā)式搜索 - A*算法性質(zhì)

44、算法最優(yōu)性： （啟發(fā)式函數(shù)的強(qiáng)弱及其影響啟發(fā)式函數(shù)的強(qiáng)弱及其影響 ）再以八數(shù)碼游戲?yàn)槔?，正因?yàn)閣(n) p(n) h* (n),所以采用p(n)擴(kuò)展出的節(jié)點(diǎn)總數(shù)不會(huì)比采用w(n)時(shí)多。更明顯的例子是采用寬度優(yōu)先法解決八數(shù)碼問題，其相當(dāng)于h(n)0，則搜索樹會(huì)變得比采用w(n)時(shí)龐大得多。 啟發(fā)式搜索 - A*算法性質(zhì) 算法最優(yōu)性： （啟發(fā)式函數(shù)的強(qiáng)弱及其影響啟發(fā)式函數(shù)的強(qiáng)弱及其影響 ） 三種算法的搜索代價(jià)三種算法的搜索代價(jià),其中IDS為深度搜索,h1采用的啟發(fā)式函數(shù)為w(n), h2采用的啟發(fā)式函數(shù)為p(n),d為解的長(zhǎng)度.隨機(jī)產(chǎn)生1200個(gè)八數(shù)碼問題統(tǒng)計(jì): d=12 IDS = 3,644,

45、035 nodes A*(h1) = 227 nodes A*(h2) = 73 nodes d=24 IDS = too many nodes A*(h1) = 39,135 nodes A*(h2) = 1,641 nodes啟發(fā)式搜索 - A*算法性質(zhì) 3.h(x)的單調(diào)性限制：?jiǎn)握{(diào)性定義單調(diào)性定義：給定一個(gè)啟發(fā)函數(shù)h，如果對(duì)于所有節(jié)點(diǎn)ni 、 nj （ nj是ni的子節(jié)點(diǎn)）滿足 h(ni) h(nj) c(ni, nj) 且 h(t) 0 ，則稱h 滿足單調(diào)性限制。上式可以寫成 h(ni) c(ni, nj) h(nj) 可以理解為三角形邊長(zhǎng)和不等式。tninjh(ni)h(nj)c(

46、ni, nj) 單調(diào)性限制的作用是：避免重復(fù)計(jì)單調(diào)性限制的作用是：避免重復(fù)計(jì)算某些節(jié)點(diǎn)的算某些節(jié)點(diǎn)的f值（主要針對(duì)連通圖而值（主要針對(duì)連通圖而言）以便減少搜索代價(jià)。言）以便減少搜索代價(jià)。啟發(fā)式搜索 - A*算法性質(zhì) h(x)的單調(diào)性限制：結(jié)論結(jié)論1 1（定理（定理1-51-5） 如果h(n)滿足單調(diào)性限制條件，則A*算法擴(kuò)充了節(jié)點(diǎn)n之后，就已經(jīng)找到了到達(dá)節(jié)點(diǎn)n的最佳路徑，即：如果A*選中節(jié)點(diǎn)n，在單調(diào)性限制條件下，有 g(n) g*(n) 結(jié)論結(jié)論2 2（定理（定理1-61-6） 如果h 滿足單調(diào)性限制，則由A*擴(kuò)充的節(jié)點(diǎn)序列的f 值是非遞減的。啟發(fā)式搜索 - A*算法的改進(jìn) 問題的提出： 因

47、A算法第6步對(duì)ml類（第3類）節(jié)點(diǎn)可能要重新放回到OPEN表中，因此可能會(huì)導(dǎo)致多次重復(fù)擴(kuò)展同一個(gè)節(jié)點(diǎn)，導(dǎo)致搜索效率下降。s(10)A(1)B(5)C(8)G 目標(biāo)631118一個(gè)例子：OPEN表CLOSED表s(10)s(10)A(7) B(8) C(9)A(7) s(10)B(8) C(9) G(14)A(5) C(9) G(14)C(9) G(12)B(7) G(12)A(4) G(12)G(11)B(8) s(10)A(5) B(8) s(10)C(9) A(5) s(10)B(7) C(9) s(10)A(4) B(7) C(9) s(10)出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因在前面的擴(kuò)展中，并沒有

48、找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑，如節(jié)點(diǎn)A。s(10)A(1)B(5)C(8)G 目標(biāo)631118解決的途徑對(duì)h加以限制能否對(duì)h增加適當(dāng)?shù)南拗疲沟玫谝淮螖U(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，就找到了從s到該節(jié)點(diǎn)的最短路徑。要求滿足單調(diào)性限制對(duì)算法加以改進(jìn)能否對(duì)算法加以改進(jìn)，避免或減少節(jié)點(diǎn)的多次擴(kuò)展。改進(jìn)的條件可采納性不變不多擴(kuò)展節(jié)點(diǎn)不增加算法的復(fù)雜性對(duì)算法加以改進(jìn)一些結(jié)論：推論1.1 ： OPEN表上任以具有f(n) f*(s)的節(jié)點(diǎn)定會(huì)被擴(kuò)展。推論1.2： A*選作擴(kuò)展的任一節(jié)點(diǎn)，定有f(n)f*(s)。n基本思想：n按照節(jié)點(diǎn)的按照節(jié)點(diǎn)的f值從小到大排序值從小到大排序 OPEN表中的節(jié)點(diǎn)，以表中的節(jié)點(diǎn)，以 f

49、*(s)為界將為界將OPEN表的節(jié)點(diǎn)劃分為兩個(gè)部分。表的節(jié)點(diǎn)劃分為兩個(gè)部分。nf f*(s)的節(jié)點(diǎn)，稱為的節(jié)點(diǎn)，稱為NEST。改進(jìn)的出發(fā)點(diǎn)OPEN = ( )f*(s)f值小于f*(s)的節(jié)點(diǎn)f值大于等于f*(s)的節(jié)點(diǎn)fm：到目前為止已擴(kuò)展節(jié)點(diǎn)的最大f值，用fm代替f*(s)修正過程A1, OPEN:=(s), f(s)=g(s)+h(s), fm:=0;2, LOOP: IF OPEN=( ) THEN EXIT(FAIL);3, NEST:=ni|f(ni)fmIF NEST ( ) THEN n:=NEST中g(shù)最小的節(jié)點(diǎn) ELSE n:=FIRST(OPEN), fm:=f(n);4,

50、 , 8: 同過程A。s(10)A(1)B(5)C(8)G 目標(biāo)631118前面的例子：OPEN表CLOSED表fms(0+10)s(0+10)10A(6+1) B(3+5) C(1+8)s(0+10) C(1+8)10A(6+1) B(2+5)s(0+10) C(1+8) B(2+5)10A(3+1) s(0+10)C(1+8)B(2+5)A(3+1)10G(11+0) h的單調(diào)化方法如果令：f(n) = max f(n的父節(jié)點(diǎn)), g(n)+h(n) 則容易證明，這樣處理后的h是單調(diào)的。第1-2章 搜索策略基本概念狀態(tài)空間的搜索策略與/或樹的搜索策略搜索的完備性和效率第1-2章 搜索策略基

51、本概念狀態(tài)空間的搜索策略與/或樹的搜索策略搜索的完備性和效率 可以把 與/或圖（樹）視為對(duì)一般圖的擴(kuò)展；或反之，把一般圖視為與/或圖的特例，即一般圖不允許節(jié)點(diǎn)間具有“與”關(guān)系，所以又可把一般圖稱為或圖。與一般圖類似，與/或圖也有根節(jié)點(diǎn)，用于指示初始狀態(tài)。由于同父子節(jié)點(diǎn)間可以存在“與”關(guān)系，父、子節(jié)點(diǎn)間不能簡(jiǎn)單地以弧線關(guān)聯(lián)，需要引入超連接概念。同樣原因，在典型的與/或圖中，解答路徑往往不復(fù)存在，代之以廣義的解路徑-解圖。 與/或樹的一般搜索過程 與/或樹的一般搜索過程與/或樹的一般搜索過程解圖的生成-自根節(jié)點(diǎn)開始選一外向連接，并從該連接指向的每個(gè)子節(jié)點(diǎn)出發(fā)，再選一外向連接，如此反復(fù)進(jìn)行，直到所有

52、外向連接都指向終節(jié)點(diǎn)為止。解圖是遵從問題歸約策略而搜索到的，解圖中不存在節(jié)點(diǎn)或節(jié)點(diǎn)組之間的“或”關(guān)系；換言之，解圖純粹是一種“與”圖。另外，正因?yàn)榕c或圖中存在“或”關(guān)系，所以往往會(huì)搜索到多個(gè)解圖，本例中就有4個(gè)。 與/或樹的一般搜索過程初始節(jié)點(diǎn)S0對(duì)應(yīng)原始問題的描述。用可適用的分解或等價(jià)變換算符求得S0的后繼節(jié)點(diǎn)集合。從每個(gè)后裔設(shè)置指向父輩節(jié)點(diǎn)的指針（用于標(biāo)示可解或不可解，并指出一個(gè)到終葉節(jié)點(diǎn)的解圖），刪去沒有意義的節(jié)點(diǎn)。繼續(xù)擴(kuò)展節(jié)點(diǎn)和設(shè)置指針的過程，直至S0被標(biāo)示為可解或不可解為止。 與/或樹的一般搜索過程基本思想：把新生成的子節(jié)點(diǎn)放入OPEN表的尾部。算法：1）把初始節(jié)點(diǎn)S0放入OPEN表

53、。2）把OPEN表中首節(jié)點(diǎn)（記為n）取出放入CLOSE表。3）如果節(jié)點(diǎn)n可擴(kuò)展，則 i)擴(kuò)展n，將其子節(jié)點(diǎn)配置指針，放入OPEN表尾部。 ii)這些子節(jié)點(diǎn)是否有終止節(jié)點(diǎn)，若是，應(yīng)用可解標(biāo)示過程。若S0被標(biāo)示可解，則得到解樹搜索成功；否則從OPEN表中刪除具有可解先輩的節(jié)點(diǎn)。 iii)轉(zhuǎn)2）與/或樹的廣度優(yōu)先搜索算法： （續(xù)）4）如果節(jié)點(diǎn)n不可擴(kuò)展，則 i)應(yīng)用不可解標(biāo)示過程。若S0被標(biāo)示為不可解，則搜索失??；否則從OPEN表中刪除具有不可解先輩的節(jié)點(diǎn)。 ii)轉(zhuǎn)2）流程圖： (略) 舉例：與/或樹的廣度優(yōu)先搜索基本思想：把新生成的子節(jié)點(diǎn)放入OPEN表的首部。算法： （與廣度優(yōu)先類似）流程圖：

54、(略) 舉例：與/或樹的深度優(yōu)先搜索基本思想：考慮付出的代價(jià)，選擇擴(kuò)展節(jié)點(diǎn)時(shí)，先走幾步，選擇代價(jià)最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。由于局部圖中有多個(gè)葉結(jié)點(diǎn)，不能像一般圖搜索那樣通過對(duì)某一結(jié)點(diǎn)的評(píng)價(jià)來實(shí)現(xiàn)對(duì)整個(gè)局部圖的評(píng)價(jià)，因此對(duì)于與或圖搜索來說，就是通過對(duì)局部圖的評(píng)價(jià)來選擇待擴(kuò)展的結(jié)點(diǎn)。與或圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索_ AO*算法 建立一個(gè)搜索圖G G，僅包含初始節(jié)點(diǎn)s s，s s 的耗散值為 q(s)=h(s)q(s)=h(s)，如果s s 是終節(jié)點(diǎn)，則標(biāo)記s s 為SOLVED UntilUntil s s已標(biāo)記SOLVED do:do: beginbegin 從s s出發(fā)沿著有標(biāo)記的連接符找出一

55、個(gè)G G的待擴(kuò)充的 局部解圖GG 任取GG中一個(gè)非終節(jié)點(diǎn)n n作為當(dāng)前節(jié)點(diǎn)。 擴(kuò)充節(jié)點(diǎn)n n ，生成n n的全部子節(jié)點(diǎn)并將其加入到G G中 對(duì)于未在G中出現(xiàn)過的子節(jié)點(diǎn)njnj ，計(jì)算其耗散值 q(nj)=h(nj)q(nj)=h(nj)；對(duì)于子節(jié)點(diǎn)中屬于終節(jié)點(diǎn)者，標(biāo)記 SOLVED并賦值為0 0CONTINUEAO*算法 建立一個(gè)僅包含節(jié)點(diǎn)n n的單一節(jié)點(diǎn)集S Until SUntil S為空 dodo： beginbegin 從S S中移出這樣節(jié)點(diǎn)mm，該mm節(jié)點(diǎn)的子節(jié)點(diǎn)不在S S中 計(jì)算修改m耗散值 q(m)q(m) ： 對(duì)指向節(jié)點(diǎn)集n1i, n2i nkin1i, n2i nki的每個(gè)連

56、接符i，分 別計(jì)算 qi(m)=Ci+q(n1i)+ q(n2i)+ + q(nKi)qi(m)=Ci+q(n1i)+ q(n2i)+ + q(nKi) 令： q(m)= min qi(m)q(m)= min qi(m) 即：取耗散值最小的連接 符的耗散值作為q(m)q(m)CONTINUEAO*算法 標(biāo)記該具有最小耗散值的連接符，如果原來對(duì) mm的某個(gè)連接符所做的標(biāo)記與新標(biāo)記的連接符不同， 則保留新標(biāo)記，去掉原來標(biāo)記。 如果該連接符的所有后繼節(jié)點(diǎn)都已標(biāo)記SOLVED， 則此mm節(jié)點(diǎn)標(biāo)記SOLVED 如果mm已標(biāo)記SOLVED或者mm修正后的耗散值與原來 的耗散值不同，則將mm的所有父節(jié)點(diǎn)加入

57、到S S中，這 些節(jié)點(diǎn)必須通過有標(biāo)記的連接符與節(jié)點(diǎn)mm相連 endend endend AO*算法的兩個(gè)過程n圖生成過程，即擴(kuò)展節(jié)點(diǎn)從最優(yōu)的局部圖中選擇一個(gè)節(jié)點(diǎn)擴(kuò)展n計(jì)算耗散值的過程對(duì)當(dāng)前的局部圖重新計(jì)算耗散值A(chǔ)O*算法舉例其中： h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0設(shè)：K連接符的耗散值為K目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8初始節(jié)點(diǎn)n0n1(2)n4(1)n5(1)紅色：4黃色：3目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5

58、n6n7n8初始節(jié)點(diǎn)n0n4(1)n5(1)紅色：4黃色：6n1n2(4)n3(4)5目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8紅色：5黃色：6初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8紅色：5黃色：6初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)21AO*算法的討論1 在外循環(huán)選擇當(dāng)前節(jié)點(diǎn)n n 并對(duì)其擴(kuò)充時(shí)，如果節(jié)點(diǎn)n n 無后繼節(jié)點(diǎn)，則在內(nèi)循環(huán)修改耗散值時(shí)可以對(duì)節(jié)點(diǎn)n n 賦一個(gè)很大的q q 值，即放棄此路徑。 外循環(huán)選擇當(dāng)前節(jié)點(diǎn)的原則：

59、選最可能使局部解圖耗散值變化較大的節(jié)點(diǎn)，以加快算法收斂速度。AO*算法的討論2 對(duì)h(n) h(n) 的單調(diào)限制：設(shè)節(jié)點(diǎn)n n 的子節(jié)點(diǎn)集為n1, n2 n1, n2 nknk，其耗散值為 h(n) Cn+ h(n1)+ h(n2)+ + h(nk)h(n) Cn+ h(n1)+ h(n2)+ + h(nk) CnCn：連接符的耗散值, 如果h(n)h(n)滿足單調(diào)限制，且h(ti)=0 h(ti)=0 ti tiNN，則有 h(n) hh(n) h* *(n) (n) 。此時(shí)，AO*算法一定能夠找到最佳解圖 （如果sNsN有解） AO*算法僅考慮h(n)h(n)而不考慮g g(n)(n) ，

60、原因是內(nèi)循環(huán)的回溯修正計(jì)算使計(jì)算g g(n)(n)值沒有意義。 AO*算法不適用于有環(huán)圖（因?yàn)楹纳⒅档挠?jì)算可能會(huì)無休止）。解樹的代價(jià)：從起始節(jié)點(diǎn)為根的最優(yōu)解樹的代價(jià)，記為h*(s)。任一節(jié)點(diǎn)x為根的解樹的最小代價(jià)h(x)定義：1）若x為終止節(jié)點(diǎn)，則h(x)=0；2）若x為或節(jié)點(diǎn)，則h(x)=minc(x,yi)+h(yi)3）若x為與節(jié)點(diǎn)，則h(x)= maxc(x,yi)+h(yi) 或 h(x)= (c(x,yi)+h(yi)與/或樹的啟發(fā)式搜索希望樹：可能構(gòu)成最優(yōu)解樹的一部分的樹。希望樹T的定義：1）初始節(jié)點(diǎn)S0在T中。2）如果節(jié)點(diǎn)x在T中，則一定有 i）x是一個(gè)或節(jié)點(diǎn)，則具有minc(