人工智能課件cumt-第三章-搜索策略.ppt

1、2020/7/31,1,第3章 搜索策略,問題求解系統(tǒng)劃分為兩大類 知識貧乏系統(tǒng) 依靠搜索技術解決問題 知識貧乏、缺乏針對性 效率低 知識豐富系統(tǒng) 依靠推理技術解決問題 基于豐富知識的推理技術，直截了當 效率高,2020/7/31,2,第3章 搜索策略,兩大類搜索技術: 1、一般圖搜索、啟發(fā)式搜索 2、基于問題歸約的與或圖搜索 兩種典型的推理技術: 1、基于歸結的演繹推理 歸結反演 2、基于規(guī)則的演繹推理 正向演繹推理 逆向演繹推理,2020/7/31,3,3.1 引言,對于給定的問題，智能系統(tǒng)的行為一般是找到能夠達到所希望目標的動作序列，并使其所付出的代價最小、性能最好。 基于給定的問題，問

2、題求解的第一步是目標的表示。 搜索就是找到智能系統(tǒng)的動作序列的過程。,2020/7/31,4,搜索算法的輸入是給定的問題，輸出是表示為動作序列的方案。 一旦有了方案，就可以執(zhí)行該方案所給出的動作了。（執(zhí)行階段） 因此，求解問題包括：,目標表示 搜索 執(zhí)行,2020/7/31,5,（1）初始狀態(tài)集合：定義了初始的環(huán)境。 （2）操作符集合：把一個問題從一個狀態(tài)變換為另一個狀態(tài)的動作集合。 （3）目標檢測函數(shù)：用來確定一個狀態(tài)是不是目標。 （4）路徑費用函數(shù)：對每條路徑賦予一定費用的函數(shù)。,其中，初始狀態(tài)集合和操作符集合定義了問題的搜索空間。,一般給定問題就是確定該問題的一些基本信息，一個問題由4部

3、分組成:,2020/7/31,6,和通常的搜索空間不同，人工智能中大多數(shù)問題的狀態(tài)空間在問題求解之前不是全部知道的。,在人工智能中，搜索問題一般包括兩個重要的問題：,搜索什么 搜索什么通常指的就是目標。 在哪里搜索 在哪里搜索就是“搜索空間”。搜索空間通常是指一系列狀態(tài)的匯集，因此稱為狀態(tài)空間。,2020/7/31,7,所以，人工智能中的搜索可以分成兩個階段： 狀態(tài)空間的生成階段 在該狀態(tài)空間中對所求問題狀態(tài)的搜索,搜索可以根據(jù)是否使用啟發(fā)式信息分為 盲目搜索 啟發(fā)式搜索,2020/7/31,8,盲目搜索 只是可以區(qū)分出哪個是目標狀態(tài)。 一般是按預定的搜索策略進行搜索。 沒有考慮到問題本身的特

4、性，這種搜索具有很大的盲目性，效率不高，不便于復雜問題的求解。,啟發(fā)式搜索 是在搜索過程中加入了與問題有關的啟發(fā)式信息，用于指導搜索朝著最有希望的方向前進，加速問題的求解并找到最優(yōu)解。,2020/7/31,9,根據(jù)問題的表示方式分為 狀態(tài)空間搜索 與或圖搜索,狀態(tài)空間搜索是用狀態(tài)空間法來求解問題所進行的搜索,與/或圖搜索是指用問題規(guī)約方法來求解問題時所進行的搜索。,2020/7/31,10,考慮一個問題的狀態(tài)空間為一棵樹的形式。 寬度優(yōu)先搜索 深度優(yōu)先搜索,如果根節(jié)點首先擴展，然后是擴展根節(jié)點生成的所有節(jié)點，然后是這些節(jié)點的后繼，如此反復下去。,在樹的最深一層的節(jié)點中擴展一個節(jié)點。只有當搜索遇

5、到一個死亡節(jié)點（非目標節(jié)點并且是無法擴展的節(jié)點）的時候，才返回上一層選擇其他的節(jié)點搜索。,2020/7/31,11,無論是寬度優(yōu)先搜索還是深度優(yōu)先搜索，遍歷節(jié)點的順序一般都是固定的，即一旦搜索空間給定，節(jié)點遍歷的順序就固定了。這種類型的遍歷稱為“確定性”的，也就是盲目搜索。 對于啟發(fā)式搜索，在計算每個節(jié)點的參數(shù)之前無法確定先選擇哪個節(jié)點擴展，這種搜索一般也稱為非確定的。,2020/7/31,12,完備性： 如果存在一個解答，該策略是否保證能夠找到？ 時間復雜性： 需要多長時間可以找到解答？ 空間復雜性： 執(zhí)行搜索需要多少存儲空間？ 最優(yōu)性： 如果存在不同的幾個解答，該策略是否可以發(fā)現(xiàn)最高質(zhì)量的

6、解答？,搜索策略評價標準:,2020/7/31,13,有許多智力問題(如梵塔問題、旅行商問題、八皇后問題、農(nóng)夫過河問題等)和實際問題（如路徑規(guī)劃、機器人行動規(guī)劃等）都可以歸結為狀態(tài)空間搜索。,用狀態(tài)空間搜索來求解問題的系統(tǒng)均定義一個狀態(tài)空間，并通過適當?shù)乃阉魉惴ㄔ跔顟B(tài)空間中搜索解答路徑。,3.2 基于狀態(tài)空間圖的搜索技術,2020/7/31,14,狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示,(1)狀態(tài)空間的表示 狀態(tài)空間記為SP，可表示為二元組： SP=(S,O) S問題求解（即搜索）過程中所有可能到達的合法狀態(tài)構成的集合； O操作算子的集合，操作算子的執(zhí)行會導致問題狀態(tài)的變遷 ； 狀態(tài)用于記載問

7、題求解（即搜索）過程中某一時刻問題現(xiàn)狀的快照； 抽象為矢量形式 Q=q0,q1,qnT 每個元素qi稱為狀態(tài)分量 給定每個狀態(tài)分量qi的值就得到一個具體的狀態(tài) Qk=q0k,q1k,qnkT,2020/7/31,15,狀態(tài),表示狀態(tài)的變遷,操作算子,問題的狀態(tài)空間是一個表示該問題的全部可能狀態(tài)及其變遷的有向圖。,節(jié)點 狀態(tài) 有向弧 狀態(tài)的變遷 弧上的標簽 導致狀態(tài)變遷的操作算子,用狀態(tài)空間搜索來求解問題的系統(tǒng)均定義一個狀態(tài)空間，并通過適當?shù)乃阉魉惴ㄔ跔顟B(tài)空間中搜索解答路徑。,2020/7/31,16,例1：走迷宮是人們熟悉的一種游戲。,狀態(tài)空間搜索,2020/7/31,17,格子、入口和出口節(jié)

8、點狀態(tài) 通道有向弧操作算子 迷宮可以由一個有向圖表示,2020/7/31,18,例2:在一個33的方格棋盤上放置著1,2,3,4,5,6,7,8八個數(shù)碼，每個數(shù)碼占一格，且有一個空格。這些數(shù)碼可在棋盤上移動，其移動規(guī)則是：與空格相鄰的數(shù)碼方可移入空格。 現(xiàn)在的問題是：對于指定的初始棋局和目標棋局，給出數(shù)碼的移動序列。該問題稱為八數(shù)碼問題。,2020/7/31,19,2 3 1 8 4 7 6 5,2020/7/31,20,2020/7/31,21,狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示,(2)狀態(tài)空間表示的經(jīng)典例子“傳教士和野人問題” 問題的描述： N個傳教士帶領N個野人劃船過河； 3個安全約

9、束條件： 1)船上人數(shù)不得超過載重限量，設為K個人； 2)任何時刻（包括兩岸、船上）野人數(shù)目不得超過傳教士； 3)允許在河的某一岸或者在船上只有野人而沒有傳教士；,2020/7/31,22,狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示,(2)狀態(tài)空間表示的經(jīng)典例子“傳教士和野人問題” 特例：N=3，K=2 狀態(tài)分量m傳教士在左岸的實際人數(shù) 狀態(tài)分量c野人在左岸的實際人數(shù) 狀態(tài)分量b指示船是否在左岸(1、0) 3個安全約束條件 m c (左岸安全)且 N-m N-c(右岸安全); m=0且0c N (左岸沒有傳道士，右岸一定安全); N-m=0且0N-cN (右岸沒有傳道士，左岸一定安全);,2020

10、/7/31,23,設初始狀態(tài)下傳教士、野人和船都在左岸，目標狀態(tài)下這三者均在右岸，問題狀態(tài)以（m,c,b）表示。,問題的求解任務可描述為：(3,3,1) (0,0,0) 該簡單問題可能到達的合法狀態(tài)： 可能狀態(tài)總數(shù)：442=32 根據(jù)條件得出合法狀態(tài)：20 m c 且 N-m N-c (左岸安全且右岸安全) m=1,c=1；m=2,c=2 m=0且0c N(左岸沒有傳道士) m=0,c=0,1,2,3 N-m=0且0N-cN(右岸沒有傳道士) m=3,c=0,1,2,3 不可能到達的合法狀態(tài)： (0,0,1),(0,3,0),(3,0,1),(3,3,0) 可能到達的合法狀態(tài)共16個,2020

11、/7/31,24,狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示,(2)狀態(tài)空間表示的經(jīng)典例子“傳教士和野人問題” 定義2類操作算子： L(x,y)指示從左岸到右岸的劃船操作 R(x,y)指示從右岸到左岸的劃船操作 x + y K=2(船的載重限制)； x和y取值的可能組合只有5個 10，20，11，01，02 ( 允許在船上只有野人而沒有傳教士 ) 共有10個操作算子,2020/7/31,25,渡河問題的狀態(tài)空間有向圖,2020/7/31,26,狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示,由此例可以看出 用狀態(tài)空間方法表示問題時，首先必須定義狀態(tài)的描述形式，通過使用這種描述形式可把問題的一切狀態(tài)都表示出

12、來。另外，還要定義一組操作，通過使用這些操作可把問題由一種狀態(tài)轉變?yōu)榱硪环N狀態(tài)。 問題的求解過程是一個不斷把操作作用于狀態(tài)的過程。如果在使用某個操作后得到的新狀態(tài)是目標狀態(tài)，就得到了問題的一個解。這個解是從初始狀態(tài)到目標狀態(tài)所用操作構成的序列。,2020/7/31,27,狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示,由此例可以看出 要使問題由一種狀態(tài)轉變到另一種狀態(tài)時，就必須使用一次操作。這樣，在從初始狀態(tài)轉變到目標狀態(tài)時，就可能存在多個操作序列(即得到多個解)。那么，其中使用操作最少或較少的解才為最優(yōu)解(因為只有在使用操作時所付出的代價為最小的解才是最優(yōu)解)。 對其中的某一個狀態(tài)，可能存在多個操作

13、使該狀態(tài)變到幾個不同的后繼狀態(tài)那么到底用哪個操作進行搜索呢?這就有賴于搜索策略了不同的搜索策略有不同的順序，這就是本章后面要討論的問題。,2020/7/31,28,課堂練習,有一農(nóng)夫帶一只狐貍、一只小羊和一籃菜過河（從左岸到右岸）。假設船太小，農(nóng)夫每次只能帶一樣東西過河；考慮到安全，無農(nóng)夫看管時，狐貍和小羊不能在一起，小羊和那籃菜也不能在一起。請為該問題的解決設計狀態(tài)空間，并畫出狀態(tài)空間圖。,2020/7/31,29,解析,以變量m、f、s、v分別指示農(nóng)夫、狐貍、小羊、菜,且每個變量只可取值1(表示在左岸)或0(表示在右岸)。問題狀態(tài)可以四元組(m、f、s、v)描述,設初始狀態(tài)下均在左岸,目標

14、狀態(tài)下都到達右岸。從而,問題求解任務可描述為 (1, 1, 1, 1) -(0, 0, 0, 0) 由于問題簡單,狀態(tài)空間中可能的狀態(tài)總數(shù)為2222 = 16,由于要遵從安全限制,合法的狀態(tài)只有(除初、目狀態(tài)外): 1110，1101，1011，1010，0101，0001，0010，0100；不合法狀態(tài)有: 0111,1000,1100,0011,0110,1001 設計二類操作算子:Lx、Rx,x為m、f、s、v時分別指示農(nóng)夫獨自,帶狐貍,帶小羊,帶菜過河；狀態(tài)空間圖如下所示.由于Lx和Rx是互逆操作,故而解答路徑可有無數(shù)條,但最近的只有二條;都是7個操作步. 思考：為什么不把船的狀態(tài)放到

15、狀態(tài)空間中去？,2020/7/31,30,解析:四元組(m、f、s、v),2020/7/31,31,狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示,(3)狀態(tài)空間的搜索 狀態(tài)空間的搜索記為SE，可表示為五元組： SE=(S,O,E,I,G)； E搜索引擎； I問題的初始狀態(tài)，I S； G問題的目標狀態(tài)集合，G S。 搜索引擎E可以設計為實現(xiàn)任何搜索算法的控制系統(tǒng)。 基本思想通過搜索引擎E尋找一個操作算子的調(diào)用序列，使問題從初始狀態(tài)I變遷到目標狀態(tài)G之一。 解答路徑初-目變遷過程中的狀態(tài)序列或相應的操作算子調(diào)用序列。,2020/7/31,32,狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示,或圖（一般圖） 一個

16、狀態(tài)可以有多個可供選擇的操作算子； 操作算子間的選擇是一種“或”的關系; 這樣的有向圖稱為或圖。,2020/7/31,33,狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示,(3)狀態(tài)空間的搜索 或圖（一般圖） 一個狀態(tài)可以有多個可供選擇的操作算子； 操作算子間的選擇是一種“或”的關系，這樣的有向圖稱為或圖。 狀態(tài)空間一般都表示為或圖（一般圖） 搜索圖在搜索解答路徑的過程中畫出搜索時涉及到的節(jié)點和弧線，構成所謂的搜索圖。,狀態(tài)空間搜索,一般圖搜索,2020/7/31,34,狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示,(3)狀態(tài)空間的搜索 狀態(tài)空間、搜索圖和解答路徑之間的關系,S0,Sg,2020/7/31,

17、35,狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示,(4)一般圖搜索例子八數(shù)碼游戲 求解的問題： 給定初始布局(即初始狀態(tài))和目標布局(即目標狀態(tài))， 如何移動數(shù)碼才能從初始布局到達目標布局？ 解答 就是一個合法的棋牌走步序列。,初始布局,目標布局,2020/7/31,36,狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示,(4)一般圖搜索例子八數(shù)碼游戲 用一般圖搜索方法解決該問題的步驟： 1、為問題狀態(tài)的表示建立數(shù)據(jù)結構 2、制定操作算子集合 3、設計搜索引擎 第一步：為問題狀態(tài)的表示建立數(shù)據(jù)結構 33的一個矩陣S 矩陣元素Sij0,1,2,3,4,5,6,7,8,其中1i,j3 數(shù)字0表示空格 數(shù)字1-8

18、表示相應的棋牌 八數(shù)碼問題就可表示為：,2020/7/31,37,狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示,初始布局,目標布局,移動數(shù)碼,(4)一般圖搜索例子八數(shù)碼游戲,2020/7/31,38,狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示,(4)一般圖搜索例子八數(shù)碼游戲 第二步：制定操作算子集 直觀方法為每個棋牌制定一套可能的走步：左、上、右、下四種移動。 需要32個操作算子 簡易方法僅為空格制定這4種走步。 僅需4個操作算子 第三步：設計搜索引擎 問題狀態(tài)空間的大小與問題涉及的元素個數(shù)是程指數(shù)級爆炸式增長（即，組合爆炸問題） 如，棋盤布局（問題狀態(tài)）總共有9!=362880個 研究焦點是解決組合爆

19、炸問題，通過壓縮搜索空間，提高搜索效率。,2020/7/31,39,狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示,狀態(tài)空間、搜索圖和解答路徑之間的關系,S0,Sg,2020/7/31,40,狀態(tài)空間搜索2.一般圖搜索策略,（1）搜索術語 1、節(jié)點深度 根節(jié)點指示初始狀態(tài)，令其深度為0； 搜索圖中的其他節(jié)點的深度dn就可以遞歸地定義為其父節(jié)點深度dn-1加1：dn= dn-1+1。,根節(jié)點深度=0,第n-1層節(jié)點dn-1,第n層節(jié)點dn= dn-1+1,搜索圖,2020/7/31,41,狀態(tài)空間搜索2.一般圖搜索策略,（1）搜索術語 2、節(jié)點擴展 應用操作算子將上一狀態(tài)（節(jié)點ni）變遷到下一狀態(tài)（節(jié)點

20、nj） 節(jié)點ni稱為被擴展節(jié)點（父節(jié)點） 節(jié)點nj稱為ni的子節(jié)點,節(jié)點ni,節(jié)點nj,2020/7/31,42,（1）搜索術語 3、路徑 節(jié)點ni到nj的路徑是由相鄰節(jié)點間的弧線構成的折線 要求路徑是無環(huán)的 4、路徑代價相鄰節(jié)點ni和ni+1間的路徑代價記為C(ni, ni+1) 通常令任意相鄰節(jié)點間的路徑代價相同，并以路徑長度1指示。 即C(ni, ni+1)=1 。,狀態(tài)空間搜索2.一般圖搜索策略,節(jié)點ni,節(jié)點ni+1,節(jié)點nj,2020/7/31,43,狀態(tài)空間搜索2.一般圖搜索策略,（1）搜索術語 4、路徑代價,目標狀態(tài)節(jié)點ng,節(jié)點ni,節(jié)點nk,C(nk,ng),C(ni,nk

21、),C(ni,ng),2020/7/31,44,狀態(tài)空間搜索2.一般圖搜索策略,（2）一般圖搜索算法 符號說明： s-初始狀態(tài)節(jié)點 G-搜索圖 OPEN-存放待擴展節(jié)點的表 CLOSE-存放已被擴展的節(jié)點的表 MOVE-FIRST(OPEN)-取OPEN表首的節(jié)點作為當前要被擴展的節(jié)點n，同時將節(jié)點n移至CLOSE表 一般圖搜索算法劃分為二個階段： 1、初始化 2、搜索循環(huán),2020/7/31,45,狀態(tài)空間搜索2.一般圖搜索策略,（2）一般圖搜索算法 算法劃分為二個階段： 1、初始化 建立只包含初始狀態(tài)節(jié)點s的搜索圖G:=s OPEN:=s CLOSE:= 2、搜索循環(huán) MOVE-FIRST

22、(OPEN)-取出OPEN表首的節(jié)點n作為擴展的節(jié)點，同時將其移到close表 擴展出n的子節(jié)點,插入搜索圖G和OPEN表 適當?shù)臉擞浐托薷闹羔?排序OPEN表 通過循環(huán)地執(zhí)行該算法，搜索圖G會因不斷有新節(jié)點加入而逐步長大，直到搜索到目標節(jié)點。,2020/7/31,46,以下面的八數(shù)碼為例，看一般圖的搜索算法,初始布局,目標布局,狀態(tài)空間搜索2.一般圖搜索策略,2020/7/31,47,2020/7/31,48,2020/7/31,49,2020/7/31,50,2020/7/31,51,2020/7/31,52,2020/7/31,53,2020/7/31,54,2020/7/31,55,2

23、020/7/31,56,2020/7/31,57,2020/7/31,58,2020/7/31,59,2020/7/31,60,2020/7/31,61,2020/7/31,62,2020/7/31,63,2020/7/31,64,2020/7/31,65,2020/7/31,66,狀態(tài)空間搜索2.一般圖搜索策略,（2）一般圖搜索算法搜索過程中的指針修改 節(jié)點n擴展后的子節(jié)點分為3類： (i)全新節(jié)點 (ii)已出現(xiàn)在OPEN表中的節(jié)點 (iii)已出現(xiàn)的CLOSE表中的節(jié)點 指針標記和修改的方法： (i)類節(jié)點：加入OPEN表，建立從子節(jié)點到父節(jié)點n的指針 (ii)類節(jié)點、 (iii)類節(jié)點

24、 比較經(jīng)由老父節(jié)點、新父節(jié)點n到達初始狀態(tài)節(jié)點的路徑代價 經(jīng)由新父節(jié)點n的代價比較小，則將原子節(jié)點指向老父節(jié)點的指針，修改為指向新父節(jié)點n (iii)類節(jié)點還得從CLOSE表中移出，重新加入OPEN表。,2020/7/31,67,狀態(tài)空間搜索2.一般圖搜索策略,S,n4,ni,nj,n1,n2,n3,n31,n32,節(jié)點ni是當前擴展的節(jié)點； 擴展出4個后續(xù)節(jié)點； n1、n2是新節(jié)點，只需建立指向父節(jié)點的指針，并加入OPEN表；,2020/7/31,68,狀態(tài)空間搜索2.一般圖搜索策略,S,n4,ni,nj,n1,n2,n3,n31,n32,n4已經(jīng)存在于OPEN表，并且已有父節(jié)點nj n4經(jīng)

25、nj的路徑代價大 取消n4指向nj的指針 改為建立n4指向新父節(jié)點ni的指針 n3已經(jīng)存在于CLOSE表，并且已有父節(jié)點nj 需要做和n4同樣的比較和指針修改工作。并且要重新加入open表。,2020/7/31,69,狀態(tài)空間搜索2.一般圖搜索策略,（2）一般圖搜索算法 OPEN表中節(jié)點簡單的排序方式： 深度優(yōu)先擴展當前節(jié)點后生成的子節(jié)點總是置于OPEN表的前端，即OPEN表作為棧，后進先出，使搜索優(yōu)先向縱深方向發(fā)展。,2020/7/31,70,深度優(yōu)先實例,2 3 1 8 4 7 6 5,1,2,3,4,6,8,9,11,13,14,16,18,19,目標,5,7,10,12,15,17,2

26、0,21,2020/7/31,71,深度優(yōu)先搜索,在深度優(yōu)先搜索中，首先擴展最新產(chǎn)生的(最深的)節(jié)點，深度 相等的節(jié)點可以任意排列。 “最晚產(chǎn)生的節(jié)點最先擴展”,起始節(jié)點深度為0 任何其他節(jié)點的深度等于其父輩節(jié)點深度加上1 :dn=dn-1+1,2020/7/31,72,深度優(yōu)先搜索,很明顯這樣做，不一定找到最佳解，而且由于深度的限制，可能找不到解，然而，若不加深度限制，可能沿著一條路線無限制地擴展下去，這當然是不允許的。 為保證找到解，應選擇適當?shù)纳疃冉缦蓿蛘卟扇〔粩嗉哟笊疃冉缦薜霓k法，反復搜索，直到找到解。這種改進的方法叫做迭代加深搜索。,2020/7/31,73,Procedure D

27、epth First Search Begin 把初始節(jié)點壓入棧，并設置棧頂指針； While 棧不空 do Begin 彈出棧頂元素； If 棧頂元素=goal，成功返回并結束； Else 以任意次序把棧頂元素的子女壓入棧中； End While End,基于棧實現(xiàn)的深度優(yōu)先搜索算法：,2020/7/31,74,初始節(jié)點放到棧中，棧指針指向棧的最上邊的元素。 為了對該節(jié)點進行檢測，需要從棧中彈出該節(jié)點，如果是目標，該算法結束，否則把其子節(jié)點以任何順序壓入棧中。該過程直到棧變成為空。 遍歷一棵樹的過程（下圖）。,2020/7/31,75,深度優(yōu)先搜索的性質(zhì),一般不能保證找到最優(yōu)解 當深度限制不

28、合理時，可能找不到解，可以將算法改為可變深度限制 最壞情況時，搜索空間等同于窮舉 是一個通用的與問題無關的方法,2020/7/31,76,深度優(yōu)先搜索的優(yōu)點是比寬度優(yōu)先搜索算法需要較少的空間，該算法只需要保存搜索樹的一部分，它由當前正在搜索的路徑和該路徑上還沒有完全展開的節(jié)點標志所組成。 深度優(yōu)先搜索的存儲器要求是深度約束的線性函數(shù)。,深度優(yōu)先搜索的優(yōu)點,2020/7/31,77,深度優(yōu)先搜索的缺點,既不是完備的，也不是最優(yōu)的。 主要問題是可能搜索到了錯誤的路徑上。很多問題可能具有很深甚至是無限的搜索樹，如果不幸選擇了一個錯誤的路徑，則深度優(yōu)先搜索會一直搜索下去，而不會回到正確的路徑上。這樣一

29、來對于這些問題，深度優(yōu)先搜索要么陷入無限的循環(huán)而不能給出一個答案，要么最后找到一個答案，但路徑很長而且不是最優(yōu)的答案。,2020/7/31,78,狀態(tài)空間搜索2.一般圖搜索策略,（2）一般圖搜索算法 OPEN表中節(jié)點簡單的排序方式： 深度優(yōu)先擴展當前節(jié)點后生成的子節(jié)點總是置于OPEN表的前端，即OPEN表作為棧，后進先出，使搜索優(yōu)先向縱深方向發(fā)展。 寬度優(yōu)先擴展當前節(jié)點后生成的子節(jié)點總是置于OPEN表的后端，即OPEN表作為隊列，先進先出，使搜索優(yōu)先向橫向方向發(fā)展。,2020/7/31,79,寬度優(yōu)先實例,2 3 1 8 4 7 6 5,1,2,5,6,7,3,目標,8,4,9,10,11,1

30、2,13,14,15,16,17,2020/7/31,80,寬度優(yōu)先搜索,如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索。 這種搜索是逐層進行的，在對下一層的任意節(jié)點進行搜索之前，必須搜索完本層的所有節(jié)點。 “先產(chǎn)生的節(jié)點先擴展”,2020/7/31,81,Procedure Breadth-first-search Begin 把初始節(jié)點放入隊列； Repeat 取得隊列最前面的元素為current; If current=goal 成功返回并結束； Else do Begin 如果current有子女，則current的子女 以任意次序添加到隊列的尾部； En

31、d Until 隊列為空 End,采用隊列結構，寬度優(yōu)先算法可以表示如下：,2020/7/31,82,寬度優(yōu)先搜索算法原理： 如果當前的節(jié)點不是目標節(jié)點，則把當點節(jié)點的子孫以任意順序增加到隊列的后面，并把隊列的前端元素定義為current。 如果目標發(fā)現(xiàn)，則算法終止。,2020/7/31,83,寬度優(yōu)先搜索的性質(zhì),當問題有解時，一定能找到解 當問題為單位代價時，且問題有解時，一定能找到最優(yōu)解 方法與問題無關，具有通用性 效率較低 屬于圖搜索方法,2020/7/31,84,寬度優(yōu)先搜索是一種盲目搜索，時間和空間復雜度都比較高，當目標節(jié)點距離初始節(jié)點較遠時會產(chǎn)生許多無用的節(jié)點，搜索效率低。 寬度優(yōu)

32、先搜索中，時間需求是一個很大的問題，特別是當搜索的深度比較大時，尤為嚴重，但是空間需求是比執(zhí)行時間更嚴重的問題。,寬度優(yōu)先搜索優(yōu)點： 目標節(jié)點如果存在，用寬度優(yōu)先搜索算法總可以找到該目標節(jié)點，而且是最?。醋疃搪窂剑┑墓?jié)點。,寬度優(yōu)先搜索的優(yōu)點和缺點,2020/7/31,85,總結,適用場合 深度優(yōu)先當一個問題有多個解答或多條解答路徑，且只須找到其中一個時；往往應對搜索深度加以限制。 寬度優(yōu)先確保搜索到最短的解答路徑。 共同優(yōu)缺點： 可直接應用一般圖搜索算法實現(xiàn)，不需要設計特別的節(jié)點排序方法，從而簡單易行，適合于許多復雜度不高的問題求解任務。 節(jié)點排序的盲目性，由于不采用領域專門知識去指導排序

33、，往往會在白白搜索了大量無關的狀態(tài)節(jié)點后才碰到解答，所以也稱為盲目搜索。,2020/7/31,86,有界深度搜索和迭代加深搜索,有界深度優(yōu)先搜索過程總體上按深度優(yōu)先算法方法進行，但對搜索深度需要給出一個深度限制dm，當深度達到了dm的時候，如果還沒有找到解答，就停止對該分支的搜索，換到另外一個分支進行搜索。,2020/7/31,87,策略說明:,（1）深度限制dm很重要。當問題有解，且解的路徑長度小于或等于dm時，則搜索過程一定能夠找到解，但是和深度優(yōu)先搜索一樣這并不能保證最先找到的是最優(yōu)解。 但是當dm取得太小，解的路徑長度大于dm時，則搜索過程中就找不到解，即這時搜索過程甚至是不完備的。,

34、2020/7/31,88,（2）深度限制dm不能太大。當dm太大時，搜索過程會產(chǎn)生過多的無用節(jié)點，既浪費了計算機資源，又降低了搜索效率。 （3）有界深度搜索的主要問題是深度限制值dm的選取。,2020/7/31,89,改進方法： （迭代加深搜索） 先任意給定一個較小的數(shù)作為dm，然后按有界深度算法搜索，若在此深度限制內(nèi)找到了解，則算法結束；如在此限制內(nèi)沒有找到問題的解，則增大深度限制dm，繼續(xù)搜索。,2020/7/31,90,迭代加深搜索，試圖嘗試所有可能的深度限制： 首先深度為0， 然后深度為1， 然后為2，等等。 如果初始深度為0，則該算法只生成根節(jié)點，并檢測它。 如果根節(jié)點不是目標，則深

35、度加1，通過典型的深度優(yōu)先算法，生成深度為1的樹。 當深度限制為m時，樹的深度為m。,2020/7/31,91,迭代加深搜索看起來會很浪費，因為很多節(jié)點都可能擴展多次。 然而對于很多問題，這種多次的擴展負擔實際上很小，直覺上可以想象，如果一棵樹的分支系數(shù)很大，幾乎所有的節(jié)點都在最底層上，則對于上面各層節(jié)點擴展多次對整個系統(tǒng)來說影響不是很大。,2020/7/31,92,搜索最優(yōu)策略的比較,表注：b是分支系數(shù)，d是解答的深度，m是搜索樹的最大深度，l是深度限制。,2020/7/31,93,寬度優(yōu)先搜索、深度優(yōu)先搜索和迭代加深搜索都可以用于生成和測試算法。 寬度優(yōu)先搜索需要指數(shù)數(shù)量的空間，深度優(yōu)先搜

36、索的空間復雜度和最大搜索深度呈線性關系。,2020/7/31,94,迭代加深搜索對一棵深度受控的樹采用深度優(yōu)先的搜索。它結合了寬度優(yōu)先和深度優(yōu)先搜索的優(yōu)點。 和寬度優(yōu)先搜索一樣，它是最優(yōu)的，也是完備的。但對空間要求和深度優(yōu)先搜索一樣是適中的。,2020/7/31,95,狀態(tài)空間搜索2.一般圖搜索策略,（2）一般圖搜索算法 常用的簡單方式： 深度優(yōu)先 寬度優(yōu)先 【缺點：節(jié)點排序的盲目性】 在白白搜索了大量無關的狀態(tài)節(jié)點后才碰到解答，效率低 提高一般圖搜索效率的關鍵 優(yōu)化OPEN表中節(jié)點的排序方式,盲目搜索,2020/7/31,96,1,2,5,6,3,4,最理想情況： 每次排序后OPEN表 表首

37、元素n 總在解答路徑上,2020/7/31,97,啟發(fā)式搜索,啟發(fā)式知識指導OPEN表排序的一般圖搜索： 全局排序對OPEN表中的所有節(jié)點排序，使最有希望的節(jié)點排在表首。 A算法， A*算法（掌握?。?局部排序僅對新擴展出來的子節(jié)點排序，使這些新節(jié)點中最有希望者能優(yōu)先取出考察和擴展； 爬山法（了解，對深度優(yōu)先法的改進）；,2020/7/31,98,啟發(fā)式搜索1.A算法（掌握）,【基本思想】 設計體現(xiàn)啟發(fā)式知識的評價函數(shù)f(n)； 指導一般圖搜索中OPEN表待擴展節(jié)點的排序： 【評價函數(shù)f(n)=g(n)+h(n) （掌握） 】 n-搜索圖G中的節(jié)點； f(n)- G中從初始狀態(tài)節(jié)點s，經(jīng)由節(jié)點

38、n到達目標節(jié)點ng，估計的最小路徑代價； g(n)- G中從s到n，目前實際的路徑代價； h(n)-從n到ng，估計的最小路徑代價；,2020/7/31,99,啟發(fā)式搜索1.A算法（掌握）,S,n,ng,目標狀態(tài)節(jié)點ng,初始狀態(tài)節(jié)點S,節(jié)點n,搜索圖G,h(n): n-ng的估計最小路徑代價,g(n):s-n的實際路徑代價,f(n):s-n-ng的估計最小路徑代價,2020/7/31,100,啟發(fā)式搜索1.A算法（掌握）,【評價函數(shù)f(n)=g(n)+h(n) （掌握） 】 n-搜索圖G中的節(jié)點； f(n)- G中從s經(jīng)n到ng，估計的最小路徑代價； g(n)- G中從s到n，目前實際的路徑

39、代價； h(n)-從n到ng，估計的最小路徑代價； h(n)值-依賴于啟發(fā)式知識加以計算； h(n)稱為啟發(fā)式函數(shù)（掌握意義?。?。 如何用評價函數(shù)來實現(xiàn)A算法? （ 掌握?。?2020/7/31,101,啟發(fā)式搜索1.A算法（掌握）,A算法的設計與一般圖搜索相同，劃分為二個階段： 1、初始化 建立只包含初始狀態(tài)節(jié)點s的搜索圖G:=s OPEN:=s CLOSE:= 2、搜索循環(huán) MOVE-FIRST(OPEN)-取出OPEN表首的節(jié)點n 擴展出n的子節(jié)點,插入搜索圖G和OPEN表 適當?shù)臉擞浐托薷闹羔槪ㄗ庸?jié)點父節(jié)點） 排序OPEN表（評價函數(shù)f(n)的值排序） 通過循環(huán)地執(zhí)行該算法，搜索圖會因

40、不斷有新節(jié)點加入而逐步長大，直到搜索到目標節(jié)點。,2020/7/31,102,啟發(fā)式搜索1.A算法（掌握）,算法A的設計與一般圖搜索類似，劃分為二個階段： 1、初始化 2、搜索循環(huán) MOVE-FIRST(OPEN)-取出OPEN表首的節(jié)點n 擴展出n的子節(jié)點,插入搜索圖G和OPEN表 對每個子節(jié)點ni,計算f(n,ni)=g(n,ni)+h(ni) 適當?shù)臉擞浐托薷闹羔槪ㄗ庸?jié)點父節(jié)點） 排序OPEN表（評價函數(shù)f(n)的值排序）,2020/7/31,103,啟發(fā)式搜索1.A算法（掌握）,擴展出n的子節(jié)點,插入搜索圖G和OPEN表 對每個子節(jié)點ni,計算f(n,ni)=g(n,ni)+h(ni)

41、 適當?shù)臉擞浐托薷闹羔槪ㄗ庸?jié)點父節(jié)點） (i)全新節(jié)點：f(ni)=f(n,ni) (ii)已出現(xiàn)在OPEN表中的節(jié)點 (iii)已出現(xiàn)的CLOSE表中的節(jié)點 IF f(ni)f(n,ni) THEN 修改指針指向新父結點n f(ni)=f(n,ni) 排序OPEN表（f(n)值從小到大排序）,2020/7/31,104,2.若OPEN表是空表，則失敗退出；,算法A,3.選擇OPEN表上的第一個節(jié)點，把它從OPEN表移出并放進CLOSE表中，稱此節(jié)點為節(jié)點n；,1.建立一個只包含起始節(jié)點S的搜索圖G,把S放到一個叫OPEN的未擴展節(jié)點表中；建立一個叫做CLOSE的已擴展節(jié)點表，其初始為空表；,

42、5.擴展節(jié)點n，同時生成不是n的祖先的那些子節(jié)點的集合M,把M的這些成員作為n的后繼節(jié)點添入圖G中；對于M中每個子節(jié)點ni,計算f(n,ni) = g(n,ni) + h(ni);,4.若n為一目標節(jié)點，則有解成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的；,2020/7/31,105,6.對那些未曾在G中出現(xiàn)過的M成員（全新節(jié)點）設置一個通向n的指針。把M的這些成員加進OPEN表。對已經(jīng)在OPEN表上的每一個M成員，比較子節(jié)點ni經(jīng)由新、老父節(jié)點的評價函數(shù)值f(n,ni)、f(ni);若f(n,ni) f(ni)點,則令f(ni) = f(n,ni),并移動子節(jié)點指向老父節(jié)點的指

43、針，改為指向新父節(jié)點。對已在CLOSE表上的每個M成員，作與第2類同樣的處理，并把這些子結點從CLOSE表移出，重新加入OPEN表。,7.按f(n)排序OPEN表中的節(jié)點，f(n)值最小者排在首位，重排OPEN表； 8.轉2。,此過程生成一個明確的圖G(搜索圖）和一個G的子集T(搜索樹）。,2020/7/31,106,啟發(fā)式搜索1.A算法（掌握）,A算法實例八數(shù)碼游戲 1)設計評價函數(shù)f(n) f(n)=d(n)+w(n),其中 d(n)-節(jié)點n在搜索圖中的節(jié)點深度，對g(n)的度量； w(n)-代表啟發(fā)式函數(shù)h(n),其值是節(jié)點n與目標狀態(tài)節(jié)點ng相比較，不考慮空格，錯位的棋牌個數(shù)；,202

44、0/7/31,107,啟發(fā)式搜索1.A算法（掌握）,啟發(fā)式算法A實例八數(shù)碼游戲 1)設計評價函數(shù)f(n) f(n)計算實例,初始布局s,目標布局ng,w(s):錯位的棋牌個數(shù),d(s):當前節(jié)點深度,f(s),h(n): n-ng的最小路徑代價,g(n):s-n的最小路徑代價,f(n):s-n-ng的最小路徑代價,注：W(S)不考慮空格,2020/7/31,108,狀態(tài)空間搜索2.一般圖搜索策略,（1）搜索術語 1、節(jié)點深度 根節(jié)點指示初始狀態(tài)，令其深度為0； 搜索圖中的其他節(jié)點的深度dn就可以遞歸地定義為其父節(jié)點深度dn-1加1：dn= dn-1+1。,根節(jié)點深度=0,第n-1層節(jié)點dn-1

45、,第n層節(jié)點dn= dn-1+1,搜索圖G,2020/7/31,109,啟發(fā)式搜索1.A算法（掌握）,啟發(fā)式算法A實例八數(shù)碼游戲 1)設計評價函數(shù)f(n) f(n)計算實例,初始布局s,目標布局ng,w(s):錯位的棋牌個數(shù),d(s):當前節(jié)點深度,f(s),h(n): n-ng的最小路徑代價,g(n):s-n的最小路徑代價,f(n):s-n-ng的最小路徑代價,0,4,4,注：W(S)不考慮空格,2020/7/31,110,初始化,OPEN:=s4,CLOSE:=,2020/7/31,111,循環(huán)1,CLOSE:=s4,OPEN:=a b c,OPEN:=a6 b4 c6,OPEN:=b4

46、a6 c6,2020/7/31,112,循環(huán)2,CLOSE:=s4 b4,OPEN:=a6 c6 d e i,OPEN:=a6 c6 d5 e5 i6,OPEN:=d5 e5 a6 c6 i6,2020/7/31,113,循環(huán)3,CLOSE:=s4 b4 d5,OPEN:=e5 a6 c6 i6 j k,OPEN:=e5 a6 c6 i6 j7 k6,OPEN:=e5 a6 c6 i6 k6 j7,2020/7/31,114,循環(huán)4,CLOSE:=s4,b4,d5,e5,OPEN:=a6 c6 i6 k6 j7 l m,OPEN:=a6 c6 i6 k6 j7 l5 m7,OPEN:=l5 a

47、6 c6 i6 k6 j7 m7,2020/7/31,115,CLOSE:=s4,b4,d5,e5,l5,循環(huán)5,OPEN:=a6 c6 i6 k6 j7 m7 n,OPEN:=a6 c6 i6 k6 j7 m7 n5,OPEN:=n5 a6 c6 i6 k6 j7 m7,2020/7/31,116,循環(huán)6,CLOSE:=s4,b4,d5, e5,l5,n5,OPEN:=a6 c6 i6 k6 j7 m7 o g,OPEN:=a6 c6 i6 k6 j7 m7 o7 g5,OPEN:=g5 a6 c6 i6 k6 j7 m7 o7,2020/7/31,117,循環(huán)7,成功結束,2020/7/3

48、1,118,最理想搜索圖G,2020/7/31,119,判斷失誤,2020/7/31,120,例 2 給定4L和3L的水壺各一個，水壺上沒有刻度，可以向水壺中加水。 如何在4L的壺中準確地得到2L水？,（x,y）4L壺里的水有xL，3L壺里的水有yL， n表示搜索空間中的任一節(jié)點。 則給出下面的啟發(fā)式函數(shù)：,2020/7/31,121,h(n) = 2 如果0 x 4并且0 y 3 = 4 如果0 x 4或者0 y 3 = 8 如果 x = 0并且 y = 3 或者 x =4 并且 y= 0 =10 如果 x = 0 并且 y = 0 或者 x = 4并且 y = 3 假定g (n)表示搜索樹

49、中搜索的深度，則根據(jù)圖搜索策略得下圖的搜索空間。,2020/7/31,122,水壺問題的狀態(tài)空間擴展圖,在第0步，由節(jié)點O可以得到 g + h =10。 在第1步，得到兩個節(jié)點M和N，其估價函數(shù)值都為1+8=9，因此可以任選一個節(jié)點擴展。,2020/7/31,123,水壺問題的狀態(tài)空間擴展圖,假定選擇了節(jié)點M，在第2步擴展M得到了兩個后繼點P和R，對于P有2+4=6，對于R有2+10=12。現(xiàn)在，在節(jié)點P、R、N中，節(jié)點P具有最小的估價函數(shù)值，所以選擇節(jié)點P擴展。 在第3步，可以得到節(jié)點S，其中3+4=7?，F(xiàn)在，在節(jié)點S、R、N中，節(jié)點S的估價函數(shù)值最小，所以下一步就會選擇S節(jié)點擴展。該過程一

50、直進行下去，直到到達目標節(jié)點。,2020/7/31,124,啟發(fā)式搜索2.實現(xiàn)啟發(fā)式搜索的關鍵因素（理解）,實現(xiàn)啟發(fā)式搜索應考慮的關鍵因素： （1）搜索算法的可采納性(Admissibility); （2）啟發(fā)式函數(shù)h(n)的強弱及其影響；,2020/7/31,125,啟發(fā)式搜索2.實現(xiàn)啟發(fā)式搜索的關鍵因素,（1）搜索算法的可采納性(Admissibility) 1)定義 在存在從初始狀態(tài)節(jié)點到目標狀態(tài)節(jié)點解答路徑的情況下，若一個搜索法總能找到最短（代價最?。┑慕獯鹇窂?，則稱該狀態(tài)空間中的搜索算法具有可采納性，也叫最優(yōu)性。 如，寬度優(yōu)先的搜索算法是可采納的，只是搜索效率不高。 2) A算法的可

51、采納性定義f*(n)=g*(n)+h*(n) n-搜索圖G中最短解答路徑的節(jié)點； f*(n)- s經(jīng)節(jié)點n到ng的最短解答路徑的路徑代價； g*(n)-該路徑前段（從s到n）的路徑代價； h*(n)-該路徑后段（從n到ng）的路徑代價；,2020/7/31,126,啟發(fā)式搜索2.實現(xiàn)啟發(fā)式搜索的關鍵因素,（1）搜索算法的可采納性(Admissibility) 3) 評價函數(shù)f與f*的比較 f(n)、g(n)、h(n)分別是 f*(n)、g*(n)、h*(n)的近似值（估計值） 理想情況下： 若g(n)=g*(n)、h(n)=h*(n)， 則搜索過程中，每次都正確選擇， 不擴展任何無關的節(jié)點。

52、實際情況：設計接近f*的f是很困難的 在算法執(zhí)行過程中， g(n)容易從已經(jīng)生成的搜索樹中計算出來,S,n,搜索圖G,ng,2020/7/31,127,啟發(fā)式搜索2.實現(xiàn)啟發(fā)式搜索的關鍵因素,（1）搜索算法的可采納性(Admissibility) 3) 評價函數(shù)f與f*的比價 理想情況下： 若g(n)=g*(n)、h(n)=h*(n)，不擴展無關的節(jié)點 實際情況： 設計接近f*的f是很困難的 在算法執(zhí)行過程中， g(n)容易從已經(jīng)生成的搜索樹中計算出來，比如就以節(jié)點深度d(n)當做g(n),且有g(n)=g*(n) h(n)盡可能靠近h*(n) A算法的關鍵。,2020/7/31,128,啟發(fā)

53、式搜索2.實現(xiàn)啟發(fā)式搜索的關鍵因素,（1）搜索算法的可采納性(Admissibility) 4)改進啟發(fā)式函數(shù)八數(shù)碼游戲 f(n)=d(n)+w(n),其中 w(n)-表示錯位的棋牌個數(shù)，不夠貼切，錯誤的擴展了節(jié)點d； p(n)-節(jié)點n與目標狀態(tài)節(jié)點比較，錯位棋牌在不受阻攔的情況下，移動到目標狀態(tài)相應位置所需走步（移動次數(shù)）的總和； p(n)比w(n)更接近于h*(n)-p(n)不僅考慮了棋牌的錯位因素，還考慮了錯位的距離（移動距離）,2020/7/31,129,啟發(fā)式搜索2.實現(xiàn)啟發(fā)式搜索的關鍵因素,4)改進啟發(fā)式函數(shù)八數(shù)碼游戲 f(s)計算實例,初始布局s,目標布局ng,w(s):錯位的棋

54、牌個數(shù),d(s):當前節(jié)點深度,f(s),0,4,4,p(s):錯位棋牌移動距離,d(s):當前節(jié)點深度,f(s),0,5,5,1,1,1,2,2020/7/31,130,初始化,OPEN:=s5,CLOSE:=,2020/7/31,131,循環(huán)1,CLOSE:=s5,OPEN:=a b c,OPEN:=a7 b5 c7,OPEN:=b5 a7 c7,2020/7/31,132,循環(huán)2,CLOSE:=s5 b5,OPEN:=a7 c7 d e i,OPEN:=a7 c7 d7 e5 i7,OPEN:=e5 a7 c7 d7 i7,2020/7/31,133,循環(huán)3,CLOSE:=s5 b5 e

55、5,OPEN:=a7 c7 d7 i7 l m,OPEN:=a7 c7 d7 i7 l5 m7,OPEN:=l5 a7 c7 d7 i7 m7,2020/7/31,134,CLOSE:=s5,b5,e5,l5,循環(huán)4,OPEN:=a7 c7 d7 i7 m7 n,OPEN:=a7 c7 d7 i7 m7 n5,OPEN:=n5 a7 c7 d7 i7 m7,2020/7/31,135,CLOSE:=s5,b5, e5,l5, n5,循環(huán)5,OPEN:=a7 c7 d7 i7 m7 o g,OPEN:=a7 c7 d7 i7 m7 o7 g5,OPEN:=g5 a7 c7 d7 i7 m7 o7

56、,2020/7/31,136,循環(huán)6,成功結束,最理想搜索圖G,2020/7/31,137,避免了錯誤選擇,2020/7/31,138,啟發(fā)式搜索2.實現(xiàn)啟發(fā)式搜索的關鍵因素,（1）搜索算法的可采納性(Admissibility) 5) A*算法定義： 1、在A算法中，規(guī)定h(n)h*(n); 2、經(jīng)如此限制以后的A算法就是A*算法。 A*算法是可采納的，即總能搜索到最短解答路徑 【回顧：八數(shù)碼游戲的h(n)】 w(n)-錯位的棋牌個數(shù) p(n)-錯位棋牌在不受阻攔的情況下，移動到目標狀態(tài)相應位置所需走步（移動次數(shù)）的總和；,2020/7/31,139,啟發(fā)式搜索2.實現(xiàn)啟發(fā)式搜索的關鍵因素,

57、（1）搜索算法的可采納性(Admissibility) 5) A*算法定義： 1、在A算法中，規(guī)定h(n)h*(n); 2、經(jīng)如此限制以后的A算法就是A*算法。 A*算法是可采納的，即總能搜索到最短解答路徑 證明：【人工智能 上冊陸汝鈐P248】 1）如果存在一條從初始狀態(tài)到目標狀態(tài)的解答路徑，則一定存在一條最短解答通路； 2）設狀態(tài)n是最短解答路徑上的一個狀態(tài)，那么經(jīng)過有限步后，n必然會成為OPEN表的第一個節(jié)點； 3）因為最短解答路徑只有有限個節(jié)點n，所以有限步后算法必然因到達目標狀態(tài)ng。這就是最優(yōu)解。 證明完畢。,2020/7/31,140,啟發(fā)式搜索2.實現(xiàn)啟發(fā)式搜索的關鍵因素,（1

58、）搜索算法的可采納性(Admissibility) 5)滿足可采納性條件的算法A*算法 證明： 2）設狀態(tài)n是最短解答路徑上的一個狀態(tài)，那么經(jīng)過有限步后，n必然會成為OPEN表的第一個節(jié)點； f(n)=g(n)+h(n) 根據(jù)假設，n在最短解答路徑上 經(jīng)過有限步驟后，g(n)= g*(n) f(n)=g*(n)+h(n) h(n)h*(n) f(n)=g*(n)+h(n) g*(n)+h*(n)=f*(n) f*(n)= f*(ng) f(n) f*(ng),2020/7/31,141,啟發(fā)式搜索2.實現(xiàn)啟發(fā)式搜索的關鍵因素,（1）搜索算法的可采納性(Admissibility) 5)滿足可采納性條件的算法A*算法 證明： 2）設狀態(tài)n是最短解答路徑上的一個狀態(tài)，那么經(jīng)過有限步后，n必然會成為OPEN表的第一個節(jié)點； 設OPEN表中n之前的節(jié)點只有有限個，設為N個，其中估計值最小者為a1，并稱之為第一代節(jié)點；由第一代節(jié)點生成的節(jié)點稱為第二代節(jié)點，其中估計值最小者為a2； a2a1+e(其中，e0，表示每擴展一次起碼的代價) 擴展j代后， aj a1+(j-1)e 當j足夠大時一定有aj f*(ng)