1、第五章 形狀空間搜索戰略S0Sg問題全形狀空間問題的搜索空間解途徑 主要內容：形狀空間的搜索問題5.1 搜索的概念及種類5.2 盲目搜索5.3 啟發式搜索5.1 搜索的概念及種類搜索的概念：找到從初始現實到問題最終答案的一條推理道路，找到的這條道路是時間和空間復雜度最小的求解道路搜索種類：“盲目搜索 ，即系統根據事先確定好的某種固定排序依次或隨機調用規那么。“啟發式搜索，即思索問題領域可運用的知識，根據詳細情況動態地確定規那么的排序，優先調用較適宜的規那么運用。搜索例子：回溯搜索算法BACKTRACKDATADATA：當前形狀。前往值： 勝利：前往從當前形狀到目的形狀的途徑以規那么表的方式表示

2、 失敗：前往FAIL。四皇后問題皇后問題 在一個4*4的國際象棋棋盤上，一次一個地擺布四枚棋子，擺好后滿足每行、每列和對角線上只允許出現一枚棋子，即棋子之間不許相互攻擊。四皇后問題續 綜合數據庫：DATA=L(表，L的元素屬于ij，1i,j4。DATA非空，其表元素表示棋子所在的行和列 規那么集：if 1 i 4 且在i-1行上有一個皇后 then 在第ij位置放上皇后。搜索戰略 固定次序：R11, R12, R13, , R21, R22,R44( )( )Q(1,1)( )QQ(1,1)(1,1) (2,3)( )Q(1,1)(1,1) (2,3)( )QQ(1,1)(1,1) (2,3)

3、(1,1) (2,4)( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)Q(1,1) (2,4) (3.2)( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )Q(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4)

4、(3.2)Q(1,2)Q(1,2) (2,4)( )(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)( )(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)Q(1,2) (2,4) (3,1) (4,3)5.1 搜索的概念及種類5.2 盲目搜索5.3 啟發式搜索5.2.1 形狀空間圖的普通搜索算法5.2.2 寬度優先搜索戰略5.2.3 深度優先搜索戰略5.2.4 代價樹的寬度

5、優先搜索戰略5.2.5 代價樹的深度優先搜索戰略5.2 盲目搜索戰略5.2.1 形狀空間圖的普通搜索算法形狀空間表示法：用來表示問題及其搜索過程的一種方法。(P62)主要構成：1形狀，描畫問題求解過程中不同時辰情況的數據構造；2算符：使問題由一個形狀變為另一個形狀的操作。3形狀空間：一個問題的全部形狀及一切可用算符構成的集合。普通包括3部分初始形狀集合S，算符集合F，目的形狀集合G4問題的求解：從S出發經過一系列的算符運算，到達目的形狀。由初始形狀到目的形狀所用算符的序列構成了問題的一個求解形狀空間圖： 把形狀空間的問題求解過程用圖的方式表示出來。 節點代表形狀，弧代表算符5.2.1 形狀空間

6、圖的普通搜索算法幾個概念：擴展：用適宜的算符對某個節點進展操作，生成一組后繼節點，擴展過程就是求后繼節點的過程。已擴展節點：曾經求出了其后繼節點的節點。未擴展節點：尚未求出后繼節點的節點。OPEN表：存放未擴展的節點，記錄當前節點及其父節點。CLOSED表：存放已擴展節點，記錄編號、當前節點及其父節點。圖2.26的節點1，1能生成兩個后繼節點2，13，1形狀空間的普通搜索算法普通搜索算法的描畫：建立一個只含有初始節點S0的搜索圖G，把S0放入OPEN表中建立CLOSED表，且置為空表判別OPEN表能否為空表，假設為空，那么問題無解，退出選擇OPEN表中的第一個節點，把它從OPEN表移出，并放入

7、CLOSED表中，將此節點記為節點n調查節點n能否為目的節點，假設是，那么問題有解，勝利退出。問題的解就是沿著n到S0的途徑得到。假設不是轉擴展節點n生成一組不是n的祖先的后繼節點，并將它們記為集合M，將M中的這些節點作為n的后繼節點參與圖G中對未在G中出現過的OPEN和CLOSED表中未出現過的集合M中的節點，設置一個指向父節點n的指針，并把這些節點放入OPEN表中；對于已在G中出現過的M中的節點，確定能否需求修正指向父節點的指針；對于已在G中出現過并已在closed表中的M中的節點，確定能否需求修正通向他們后繼節點的指針。按某一恣意方式或某種戰略重排OPEN表中節點的順序轉特例圖的一些概念

8、：1節點深度： 根節點深度=0，其它節點深度=父節點深度+12途徑 設一節點序列為(n0, n1,nk)，對于i=1,k，假設節點ni-1具有一個后繼節點ni，那么該序列稱為從n0到nk的途徑。3途徑的耗費值一條途徑的耗費值等于銜接這條途徑各節點間一切耗費值的總和。用C(ni, nj)表示從ni到nj的途徑的耗費值。0123節點類型闡明.mkmjmln擴展點n，產生mk：沒在OPEN和CLOSED表中出現過mj：在OPEN表中出現過ml：在CLOSED表中出現過S123645將要擴展節點6S126453修正4節點的前往指針S126453將要擴展節點1S12645修正2和4的前往指針5.2 無信

9、息圖搜索過程盲目搜索戰略5.2.2 寬度優先搜索5.2.3 深度優先搜索5.2.4 代價樹的寬度優先5.2.5 代價樹的深度優先1、定義假設搜索是以接近起始節點的程度依次擴展節點的，那么這種搜索就叫做寬度優先搜索(breadth-first search)。2、特點這種搜索是逐層進展的；在對下一層的任一節點進展搜索之前，必需搜索完本層的一切節點。5.2.2 寬度優先搜索戰略3、寬度優先搜索算法(1) 把起始節點放到OPEN表中(假設該起始節點為一目的節點，那么求得一個解答)。(2) 假設OPEN是個空表，那么沒有解，失敗退出；否那么繼續。(3) 把第一個節點(節點n)從OPEN表移出，并把它放

10、入CLOSED的擴展節點表中。 (4) 擴展節點n。假設沒有后繼節點，那么轉向上述第(2)步。 (5) 把n的一切后繼節點放到OPEN表末端，并提供從這些后繼節點回到n的指針。 (6) 假設n的任一個后繼節點是個目的節點，那么找到一個解答，勝利退出；否那么轉向第(2)步。例：把寬度優先搜索運用于八數碼難題時所生成的搜索樹，這個問題就是要把初始棋局變為如下目的棋局的問題： 1 2 3 8 4 7 6 55.2.2 寬度優先搜索戰略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

11、 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目的82 3 41 8 7 6 54寬度優先搜索的性質當問題有解時，一定能找到解。當問題為單位耗費值，且問題有解時，一定能找到最優解。算法與問題無關，具有通用性。時間效率和空間效率都比較低。1、定義 在此搜索中，首先擴展最新產生的(即最深的)節點。深度相等的節點可以恣意陳列。 這種盲目(無信息)搜索叫做深度優先搜索(dep

12、th-first search)。2、特點 首先，擴展最深的節點的結果使得搜索沿著形狀空間某條單一的途徑從起始節點向下進展下去；只需當搜索到達一個沒有后裔的形狀時，它才思索另一條替代的途徑。3、深度界限 為了防止思索太長的途徑(防止搜索過程沿著無益的途徑擴展下去)，往往給出一個節點擴展的最大深度界限。任何節點假設到達了深度界限，那么都將把它們作為沒有后繼節點處置。 5.2.3 深度優先搜索戰略3、深度優先搜索算法(1) 把起始節點放到OPEN表中(假設該起始節點為一目的節點，那么求得一個解答)。(2) 假設OPEN是個空表，那么沒有解，失敗退出；否那么繼續。(3) 把第一個節點(節點n)從OP

13、EN表移出，并把它放入CLOSED的擴展節點表中。 (4) 調查節點n能否為目的節點，假設是，那么找到問題的解，用回溯法求解途徑，退出 5假設沒有后繼節點，那么轉向上述第(2)步。 (6) 擴展節點n，把n的一切后繼節點放到OPEN表前端，并提供從這些后繼節點回到n的指針。轉向第(2)步。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

14、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 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789101112131 2 3 8 47 6 5目的深度優先搜索的性質普通不能保證找到最優解。當深度限制不合理時，能夠找不到解。最壞情況時，搜索空間等同于窮舉。1、定義 形狀空間圖中各節點之間有向邊的代價是不同的，有向邊上標有代價的搜索樹成為代價搜索樹。2、特點 每次從OPEN表中選擇一個代價最小的節點，移入CLOSED表。3、C(

15、i,j):從節點i到其后繼節點j的連線代價； gx:從初始節點到恣意節點x的途徑代價； g(j)=g(i)+C(i,j).5.2.4 代價樹的寬度優先搜索4、代價樹的寬度優先搜索算法(1) 把起始節點放到OPEN表中，令g(S0)=0。(2) 假設OPEN是個空表，那么沒有解，失敗退出；否那么繼續。(3) 把OPEN表中代價最小的節點即排在最前端的節點n，移入CLOSED的擴展節點表中。 (4) 假設n是目的節點，問題得解，退出。否那么繼續。 (5) 判別節點n能否可擴展。假設否那么轉向第(2)步，假設是那么轉向(6)。 (6) 對節點n進展擴展，將他們的一切后繼節點放到OPEN表中，并對每個

16、后繼節點j計算其總代價g(j)=g(j)+C(i,j),為每個后繼節點指向n節點的指針，然后根據節點的代價大小對OPEN表中的一切節點進展從小到大的排序。 (7) 轉向第(2)步。例子：推銷員游覽問題P193ACBDE768765gC節點n父節點AACBDE768765gC節點n父節點A66BA77CAACBDE768765gC節點n父節點A66BA71175CDABACBDE768765gC節點n父節點A66BA71114157578CDDEABCC節點擴展順序：A，B，C，D，D，E道路：A-C-E代價樹的寬度優先搜索每次從OPEN表中的全體節點中選擇代價最小的節點移入CLOSED表進展擴

17、展或判別。代價樹的深度優先搜索從剛剛擴展的節點的后繼節點中選擇一個代價最小的節點移入CLOSED表中，并進展擴展或判別。5.2.5 代價樹的深度優先搜索4、代價樹的深度優先搜索算法(1) 把起始節點放到OPEN表中，令g(S0)=0。(2) 假設OPEN是個空表，那么沒有解，失敗退出；否那么繼續。(3) 把OPEN表中的第一個節點代價最小的節點n，移入CLOSED表。 (4) 假設n是目的節點，問題得解，退出。否那么繼續。 (5) 判別節點n能否可擴展。假設否那么轉向第(2)步，假設是那么轉向(6)。 (6) 對節點n進展擴展，并將其后繼節點按有向邊代價C(i,j)從小到大排序后放到OPEN表

18、前端，并為每個后繼節點設置指向n節點的指針。 (7) 轉向第(2)步。ACBDE768765gC節點n父節點AACBDE768765gC節點n父節點A66BA77CAACBDE768765gC節點n父節點A66BA71175CDABACBDE768765gC節點n父節點A66BA71117187578CDECABDD節點擴展順序：A，B，C，D，E道路：A-B-D-EACBDE768765gC節點n父節點A66BA71114157578CDDEABCC節點擴展順序：A，B，C，D，D，E道路：A-C-E5.1 搜索的概念及種類5.2 盲目搜索5.3 啟發式搜索5.3.1 啟發信息與估價函數5.

19、3.2 最正確優先搜索5.3.3 A*搜索算法5.3 啟發式圖搜索 5.3.1啟發信息與估價函數定義利用與問題有關的知識即：啟發信息來引導搜索，到達減少搜索范圍，降低問題復雜度的搜索過程稱為啟發式搜索方法。中心問題：啟發信息運用，啟發才干度量和如何獲得啟發信息。啟發信息的強度強：降低搜索任務量，但能夠導致找不到最優解。弱：普通導致任務量加大，極限情況下變為盲目搜索，但能夠可以找到最優解。希望：引入啟發知識，在保證找到最正確解的前提下，盡能夠減少搜索范圍，提高搜索效率。搜索算法的效果：可以用啟發才干的強弱來度量。思索解途徑的耗費值和求得途徑所需搜索的耗費值兩者的某種組合最小。思索搜索方法對求解一

20、切能夠遇見的問題，其平均的組合耗費最小。問題的關鍵如何尋覓最有希望的節點 啟發搜索過程中，要對OPEN表進展排序，這就需求有一種方法來計算待擴展節點有希望通向目的節點的不同程度。 我們總希望能找到最有希望通向目的節點的待擴展節點優先擴展。根本思想定義一個估價函數fEvaluation Function，對當前的搜索形狀進展評價，找出一個“最有希望的節點來擴展。估價函數的格式：f(n) = g(n) + h(n)f(n)：估價函數g(n)：代價函數， 初始節點到節點n已實踐付出的代價 h(n)：啟發函數， 從節點n到目的節點的最優途徑的估計代價5.3.2 最正確優先搜索部分最正確優先搜索全局最正

21、確優先搜索部分最正確優先搜索：(1) 把起始節點放到OPEN表中，并計算估價函數f(S0)。(2) 假設OPEN是個空表，那么沒有解，失敗退出；否那么繼續。(3) 把OPEN表中的第一個節點股價函數最小的節點n，移入CLOSED表。(4) 假設n是目的節點，問題得解，退出。否那么繼續。(5) 判別節點n能否可擴展。假設否那么轉向第(2)步，假設是那么轉向(6)。(6) 對節點n進展擴展，并對其一切后繼節點計算估價函數fn的值，并按其值從小到大排序后放到OPEN表前端，并為每個后繼節點設置指向n節點的指針。(7) 轉向第(2)步。全局最正確優先搜索：(1) 把起始節點放到OPEN表中，并計算估價

22、函數f(S0)。(2) 假設OPEN是個空表，那么沒有解，失敗退出；否那么繼續。(3) 把OPEN表中的第一個節點股價函數最小的節點n，移入CLOSED表。(4) 假設n是目的節點，問題得解，退出。否那么繼續。(5) 判別節點n能否可擴展。假設否那么轉向第(2)步，假設是那么轉向(6)。(6) 對節點n進展擴展，并對其一切后繼節點計算估價函數fn的值，并為每個后繼節點設置指向n節點的指針。把這些后繼節點都送入OPEN表，然后對OPEN表中的全部節點按照估價函數值從小到大的順序排序。(7) 轉向第(2)步。例子定義評價函數：f(n) = g(n) + h(n)= d(n)+h(n)；d(n)：代表節點的深度，表示從初始節點到當前節點的耗費值；h(n)：為當前節點“不在位的牌數。2 8 31 6 47 51 2 38 47 6 5h計算舉例h(n) =4 2 8 31 6 47 51 2 3457 6 82 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 3