第五章狀態(tài)空間搜索策略ppt課件

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

2、 失敗：前往FAIL。四皇后問題皇后問題 在一個4*4的國際象棋棋盤上，一次一個地擺布四枚棋子，擺好后滿足每行、每列和對角線上只允許出現(xiàn)一枚棋子，即棋子之間不許相互攻擊。四皇后問題續(xù) 綜合數(shù)據(jù)庫：DATA=L(表，L的元素屬于ij，1i,j4。DATA非空，其表元素表示棋子所在的行和列 規(guī)那么集：if 1 i 4 且在i-1行上有一個皇后 then 在第ij位置放上皇后。搜索戰(zhàn)略 固定次序：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 啟發(fā)式搜索5.2.1 形狀空間圖的普通搜索算法5.2.2 寬度優(yōu)先搜索戰(zhàn)略5.2.3 深度優(yōu)先搜索戰(zhàn)略5.2.4 代價樹的寬度

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

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

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

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

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

10、入CLOSED的擴展節(jié)點表中。 (4) 擴展節(jié)點n。假設沒有后繼節(jié)點，那么轉(zhuǎn)向上述第(2)步。 (5) 把n的一切后繼節(jié)點放到OPEN表末端，并提供從這些后繼節(jié)點回到n的指針。 (6) 假設n的任一個后繼節(jié)點是個目的節(jié)點，那么找到一個解答，勝利退出；否那么轉(zhuǎn)向第(2)步。例：把寬度優(yōu)先搜索運用于八數(shù)碼難題時所生成的搜索樹，這個問題就是要把初始棋局變?yōu)槿缦履康钠寰值膯栴}： 1 2 3 8 4 7 6 55.2.2 寬度優(yōu)先搜索戰(zhàn)略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寬度優(yōu)先搜索的性質(zhì)當問題有解時，一定能找到解。當問題為單位耗費值，且問題有解時，一定能找到最優(yōu)解。算法與問題無關，具有通用性。時間效率和空間效率都比較低。1、定義 在此搜索中，首先擴展最新產(chǎn)生的(即最深的)節(jié)點。深度相等的節(jié)點可以恣意陳列。 這種盲目(無信息)搜索叫做深度優(yōu)先搜索(dep

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

13、EN表移出，并把它放入CLOSED的擴展節(jié)點表中。 (4) 調(diào)查節(jié)點n能否為目的節(jié)點，假設是，那么找到問題的解，用回溯法求解途徑，退出 5假設沒有后繼節(jié)點，那么轉(zhuǎn)向上述第(2)步。 (6) 擴展節(jié)點n，把n的一切后繼節(jié)點放到OPEN表前端，并提供從這些后繼節(jié)點回到n的指針。轉(zhuǎ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目的深度優(yōu)先搜索的性質(zhì)普通不能保證找到最優(yōu)解。當深度限制不合理時，能夠找不到解。最壞情況時，搜索空間等同于窮舉。1、定義 形狀空間圖中各節(jié)點之間有向邊的代價是不同的，有向邊上標有代價的搜索樹成為代價搜索樹。2、特點 每次從OPEN表中選擇一個代價最小的節(jié)點，移入CLOSED表。3、C(

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

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

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

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

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

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

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

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