狀態(tài)空間搜索策略課件

第五章狀態(tài)空間搜索策略S0Sg問題全狀態(tài)空間問題的搜索空間解路徑主要內容：狀態(tài)空間的搜索問題第五章狀態(tài)空間搜索策略S0Sg問題全狀態(tài)空間問題的搜索15.1搜索的概念及種類5.2盲目搜索5.3啟發(fā)式搜索5.1搜索的概念及種類25.1搜索的概念及種類搜索的概念：找到從初始事實到問題最終答案的一條推理路線，找到的這條路線是時間和空間復雜度最小的求解路線搜索種類：“盲目搜索”，即系統(tǒng)根據(jù)事先確定好的某種固定排序（依次或隨機）調用規(guī)則?！皢l(fā)式搜索”，即考慮問題領域可應用的知識，根據(jù)具體情況動態(tài)地確定規(guī)則的排序，優(yōu)先調用較合適的規(guī)則使用。5.1搜索的概念及種類搜索的概念：3搜索例子：回溯搜索算法

BACKTRACK（DATA）

DATA：當前狀態(tài)。返回值：成功：返回從當前狀態(tài)到目標狀態(tài)的路徑（以規(guī)則表的形式表示） 失?。悍祷谾AIL。搜索例子：回溯搜索算法 BACKTRACK（DATA）4四皇后問題皇后問題

在一個4*4的國際象棋棋盤上，一次一個地擺布四枚棋子，擺好后滿足每行、每列和對角線上只允許出現(xiàn)一枚棋子，即棋子之間不許相互攻擊。四皇后問題皇后問題5四皇后問題（續(xù)）綜合數(shù)據(jù)庫：DATA=L(表），L的元素屬于{ij}，1≤i,j≤4。DATA非空，其表元素表示棋子所在的行和列規(guī)則集：if1≤i≤4且在i-1行上有一個皇后then在第ij位置放上皇后。搜索策略固定次序：R11,R12,R13,…,R21,R22,R44四皇后問題（續(xù)）綜合數(shù)據(jù)庫：DATA=L(表），L的元素屬6()()7()Q((1,1))()Q((1,1))8()QQ((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))9()Q((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))10()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,111()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,112()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,113()Q((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)14()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)15()((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)16()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))()((1,1))((1,1)(2,3))((1,1)17()((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)18()((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))()((1,1))((1,1)(2,3))((1,1)195.1搜索的概念及種類5.2盲目搜索5.3啟發(fā)式搜索5.2.1狀態(tài)空間圖的一般搜索算法5.2.2寬度優(yōu)先搜索策略5.2.3深度優(yōu)先搜索策略5.2.4代價樹的寬度優(yōu)先搜索策略5.2.5代價樹的深度優(yōu)先搜索策略5.1搜索的概念及種類5.2.1狀態(tài)空間圖的一般搜索算法205.2盲目搜索策略

5.2.1狀態(tài)空間圖的一般搜索算法狀態(tài)空間表示法：用來表示問題及其搜索過程的一種方法。(P62)主要構成：（1）狀態(tài)，描述問題求解過程中不同時刻狀況的數(shù)據(jù)結構；（2）算符：使問題由一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作。（3）狀態(tài)空間：一個問題的全部狀態(tài)及一切可用算符構成的集合。一般包括3部分（初始狀態(tài)集合S，算符集合F，目標狀態(tài)集合G）（4）問題的求解：從S出發(fā)經(jīng)過一系列的算符運算，到達目標狀態(tài)。由初始狀態(tài)到目標狀態(tài)所用算符的序列構成了問題的一個求解狀態(tài)空間圖：把狀態(tài)空間的問題求解過程用圖的形式表示出來。節(jié)點代表狀態(tài)，弧代表算符5.2盲目搜索策略

5.2.1狀態(tài)空間圖的一般搜索算法215.2.1狀態(tài)空間圖的一般搜索算法幾個概念：擴展：用合適的算符對某個節(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，1）（3，1）5.2.1狀態(tài)空間圖的一般搜索算法幾個概念：圖2.26的22狀態(tài)空間的一般搜索算法一般搜索算法的描述：建立一個只含有初始節(jié)點S0的搜索圖G，把S0放入OPEN表中建立CLOSED表，且置為空表判斷OPEN表是否為空表，若為空，則問題無解，退出選擇OPEN表中的第一個節(jié)點，把它從OPEN表移出，并放入CLOSED表中，將此節(jié)點記為節(jié)點n考察節(jié)點n是否為目標節(jié)點，若是，則問題有解，成功退出。問題的解就是沿著n到S0的路徑得到。若不是轉⑥擴展節(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é)點的指針。按某一任意方式或某種策略重排OPEN表中節(jié)點的順序轉③特例狀態(tài)空間的一般搜索算法一般搜索算法的描述：特例23圖的一些概念：（1）節(jié)點深度： 根節(jié)點深度=0，其它節(jié)點深度=父節(jié)點深度+1（2）路徑 設一節(jié)點序列為(n0,n1,…,nk)，對于i=1,…,k，若節(jié)點ni-1具有一個后繼節(jié)點ni，則該序列稱為從n0到nk的路徑。（3）路徑的消耗值 一條路徑的消耗值等于連接這條路徑各節(jié)點間所有消耗值的總和。用C(ni,nj)表示從ni到nj的路徑的消耗值。0123圖的一些概念：012324節(jié)點類型說明…...…...…...…...…...mkmjmln擴展點n，產生mk：沒在OPEN和CLOSED表中出現(xiàn)過mj：在OPEN表中出現(xiàn)過ml：在CLOSED表中出現(xiàn)過節(jié)點類型說明…...…...…...…...…...mkmj25S123645將要擴展節(jié)點6S123645將要擴展節(jié)點626S126453修改4節(jié)點的返回指針S126453修改4節(jié)點的返回指針27S126453將要擴展節(jié)點1S126453將要擴展節(jié)點128S12645修改2和4的返回指針S12645修改2和4的返回指針295.2無信息圖搜索過程

——盲目搜索策略5.2.2寬度優(yōu)先搜索5.2.3深度優(yōu)先搜索5.2.4代價樹的寬度優(yōu)先5.2.5代價樹的深度優(yōu)先5.2無信息圖搜索過程

——盲目搜索策略5.2.2寬度優(yōu)301、定義如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索(breadth-firstsearch)。2、特點這種搜索是逐層進行的；在對下一層的任一節(jié)點進行搜索之前，必須搜索完本層的所有節(jié)點。

5.2.2寬度優(yōu)先搜索策略1、定義5.2.2寬度優(yōu)先搜索策略313、寬度優(yōu)先搜索算法(1)把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標節(jié)點，則求得一個解答)。(2)如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。(3)把第一個節(jié)點(節(jié)點n)從OPEN表移出，并把它放入CLOSED的擴展節(jié)點表中。(4)擴展節(jié)點n。如果沒有后繼節(jié)點，則轉向上述第(2)步。(5)把n的所有后繼節(jié)點放到OPEN表末端，并提供從這些后繼節(jié)點回到n的指針。(6)如果n的任一個后繼節(jié)點是個目標節(jié)點，則找到一個解答，成功退出；否則轉向第(2)步。3、寬度優(yōu)先搜索算法32例：把寬度優(yōu)先搜索應用于八數(shù)碼難題時所生成的搜索樹，這個問題就是要把初始棋局變?yōu)槿缦履繕似寰值膯栴}：123847655.2.2寬度優(yōu)先搜索策略例：把寬度優(yōu)先搜索應用于八數(shù)碼難題時所生成的搜索樹，這個問題3323184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標82341876542323283234寬度優(yōu)先搜索的性質當問題有解時，一定能找到解。當問題為單位消耗值，且問題有解時，一定能找到最優(yōu)解。算法與問題無關，具有通用性。時間效率和空間效率都比較低。寬度優(yōu)先搜索的性質當問題有解時，一定能找到解。351、定義在此搜索中，首先擴展最新產生的(即最深的)節(jié)點。深度相等的節(jié)點可以任意排列。這種盲目(無信息)搜索叫做深度優(yōu)先搜索(depth-firstsearch)。2、特點首先，擴展最深的節(jié)點的結果使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點向下進行下去；只有當搜索到達一個沒有后裔的狀態(tài)時，它才考慮另一條替代的路徑。3、深度界限為了避免考慮太長的路徑(防止搜索過程沿著無益的路徑擴展下去)，往往給出一個節(jié)點擴展的最大深度界限。任何節(jié)點如果達到了深度界限，那么都將把它們作為沒有后繼節(jié)點處理。5.2.3深度優(yōu)先搜索策略1、定義5.2.3深度優(yōu)先搜索策略363、深度優(yōu)先搜索算法(1)把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標節(jié)點，則求得一個解答)。(2)如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。(3)把第一個節(jié)點(節(jié)點n)從OPEN表移出，并把它放入CLOSED的擴展節(jié)點表中。(4)考察節(jié)點n是否為目標節(jié)點，若是，則找到問題的解，用回溯法求解路徑，退出（5）如果沒有后繼節(jié)點，則轉向上述第(2)步。(6)擴展節(jié)點n，把n的所有后繼節(jié)點放到OPEN表前端，并提供從這些后繼節(jié)點回到n的指針。轉向第(2)步。3、深度優(yōu)先搜索算法372318476523184765283147652318476528314765283164752831476528316475283164752837146583214765281437652831457612378465123847652836417528316754832147652837146528143765283145761234567891011121312384765目標2323283238深度優(yōu)先搜索的性質一般不能保證找到最優(yōu)解。當深度限制不合理時，可能找不到解。最壞情況時，搜索空間等同于窮舉。深度優(yōu)先搜索的性質一般不能保證找到最優(yōu)解。391、定義狀態(tài)空間圖中各節(jié)點之間有向邊的代價是不同的，有向邊上標有代價的搜索樹成為代價搜索樹。2、特點每次從OPEN表中選擇一個代價最小的節(jié)點，移入CLOSED表。3、C(i,j):從節(jié)點i到其后繼節(jié)點j的連線代價；g（x）:從初始節(jié)點到任意節(jié)點x的路徑代價；g(j)=g(i)+C(i,j).5.2.4代價樹的寬度優(yōu)先搜索1、定義5.2.4代價樹的寬度優(yōu)先搜索404、代價樹的寬度優(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是否可擴展。若否則轉向第(2)步，若是則轉向(6)。(6)對節(jié)點n進行擴展，將他們的所有后繼節(jié)點放到OPEN表中，并對每個后繼節(jié)點j計算其總代價g(j)=g(j)+C(i,j),為每個后繼節(jié)點指向n節(jié)點的指針，然后根據(jù)節(jié)點的代價大小對OPEN表中的所有節(jié)點進行從小到大的排序。(7)轉向第(2)步。例子：推銷員旅行問題P1934、代價樹的寬度優(yōu)先搜索算法例子：推銷員旅行問題P19341ACBDE768765gC節(jié)點n父節(jié)點AACBDE768765gC節(jié)點n父節(jié)點A42ACBDE768765gC節(jié)點n父節(jié)點A66BA77CAACBDE768765gC節(jié)點n父節(jié)點A66BA77CA43ACBDE768765gC節(jié)點n父節(jié)點A66BA71175CDABACBDE768765gC節(jié)點n父節(jié)點A66BA77CA44ACBDE768765gC節(jié)點n父節(jié)點A66BA71114157578CDDEABCC節(jié)點擴展順序：A，B，C，D，D，E路線：A---C----EACBDE768765gC節(jié)點n父節(jié)點A66BA77CA節(jié)點45代價樹的寬度優(yōu)先搜索每次從OPEN表中的全體節(jié)點中選擇代價最小的節(jié)點移入CLOSED表進行擴展或判斷。代價樹的深度優(yōu)先搜索從剛剛擴展的節(jié)點的后繼節(jié)點中選擇一個代價最小的節(jié)點移入CLOSED表中，并進行擴展或判斷。5.2.5代價樹的深度優(yōu)先搜索代價樹的寬度優(yōu)先搜索每次從OPEN表中的全體節(jié)點中選擇代價最464、代價樹的深度優(yōu)先搜索算法

(1)把起始節(jié)點放到OPEN表中，令g(S0)=0。(2)如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。(3)把OPEN表中的第一個節(jié)點（代價最小的節(jié)點n），移入CLOSED表。(4)如果n是目標節(jié)點，問題得解，退出。否則繼續(xù)。(5)判斷節(jié)點n是否可擴展。若否則轉向第(2)步，若是則轉向(6)。(6)對節(jié)點n進行擴展，并將其后繼節(jié)點按有向邊代價（C(i,j)）從小到大排序后放到OPEN表前端，并為每個后繼節(jié)點設置指向n節(jié)點的指針。(7)轉向第(2)步。4、代價樹的深度優(yōu)先搜索算法47ACBDE768765gC節(jié)點n父節(jié)點AACBDE768765gC節(jié)點n父節(jié)點A48ACBDE768765gC節(jié)點n父節(jié)點A66BA77CAACBDE768765gC節(jié)點n父節(jié)點A66BA77CA49ACBDE768765gC節(jié)點n父節(jié)點A66BA71175CDABACBDE768765gC節(jié)點n父節(jié)點A66BA77CA50ACBDE768765gC節(jié)點n父節(jié)點A66BA71117187578CDECABDD節(jié)點擴展順序：A，B，C，D，E路線：A----B----D----EACBDE768765gC節(jié)點n父節(jié)點A66BA77CA節(jié)點51ACBDE768765gC節(jié)點n父節(jié)點A66BA71114157578CDDEABCC節(jié)點擴展順序：A，B，C，D，D，E路線：A---C----EACBDE768765gC節(jié)點n父節(jié)點A66BA77CA節(jié)點525.1搜索的概念及種類5.2盲目搜索5.3啟發(fā)式搜索5.3.1啟發(fā)信息與估價函數(shù)5.3.2最佳優(yōu)先搜索5.3.3A*搜索算法5.1搜索的概念及種類5.3.1啟發(fā)信息與估價函數(shù)535.3啟發(fā)式圖搜索

5.3.1啟發(fā)信息與估價函數(shù)定義利用與問題有關的知識（即：啟發(fā)信息）來引導搜索，達到減少搜索范圍，降低問題復雜度的搜索過程稱為啟發(fā)式搜索方法。核心問題：啟發(fā)信息應用，啟發(fā)能力度量和如何獲得啟發(fā)信息。啟發(fā)信息的強度強：降低搜索工作量，但可能導致找不到最優(yōu)解。弱：一般導致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解。5.3啟發(fā)式圖搜索

5.3.1啟發(fā)信息與估價函數(shù)定義54希望：引入啟發(fā)知識，在保證找到最佳解的前提下，盡可能減少搜索范圍，提高搜索效率。搜索算法的效果：可以用啟發(fā)能力的強弱來度量。考慮解路徑的消耗值和求得路徑所需搜索的消耗值兩者的某種組合最小?？紤]搜索方法對求解所有可能遇見的問題，其平均的組合消耗最小。希望：引入啟發(fā)知識，在保證找到最佳解的前提下，盡可能減少搜索55問題的關鍵如何尋找最有希望的節(jié)點啟發(fā)搜索過程中，要對OPEN表進行排序，這就需要有一種方法來計算待擴展節(jié)點有希望通向目標節(jié)點的不同程度。我們總希望能找到最有希望通向目標節(jié)點的待擴展節(jié)點優(yōu)先擴展。問題的關鍵如何尋找最有希望的節(jié)點56基本思想定義一個估價函數(shù)f（EvaluationFunction），對當前的搜索狀態(tài)進行評估，找出一個“最有希望”的節(jié)點來擴展?；舅枷攵x一個估價函數(shù)f（EvaluationFunct57估價函數(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)路徑的估計代價估價函數(shù)的格式：585.3.2最佳優(yōu)先搜索局部最佳優(yōu)先搜索全局最佳優(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是否可擴展。若否則轉向第(2)步，若是則轉向(6)。(6)對節(jié)點n進行擴展，并對其所有后繼節(jié)點計算估價函數(shù)f（n）的值，并按其值從小到大排序后放到OPEN表前端，并為每個后繼節(jié)點設置指向n節(jié)點的指針。(7)轉向第(2)步。全局最佳優(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是否可擴展。若否則轉向第(2)步，若是則轉向(6)。(6)對節(jié)點n進行擴展，并對其所有后繼節(jié)點計算估價函數(shù)f（n）的值，并為每個后繼節(jié)點設置指向n節(jié)點的指針。把這些后繼節(jié)點都送入OPEN表，然后對OPEN表中的全部節(jié)點按照估價函數(shù)值從小到大的順序排序。(7)轉向第(2)步。5.3.2最佳優(yōu)先搜索局部最佳優(yōu)先搜索局部最佳優(yōu)先搜索：59例子定義評價函數(shù)： f(n)=g(n)+h(n)=d(n)+h(n)； d(n)：代表節(jié)點的深度，表示從初始節(jié)點到當前節(jié)點的消耗值； h(n)：為當前節(jié)點“不在位”的牌數(shù)。

2831647512384765例子定義評價函數(shù)：2831260h計算舉例 h(n)=42

831

647512345768h計算舉例 h(n)=42831612831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s0(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目標123456283283283262A*算法是一種有序搜索算法，其特點在于對估價函數(shù)的定義上。令k(ni，nj)表示任意兩個節(jié)點ni和nj之間最小代價路徑的實際代價(對于兩節(jié)點間沒有通路的節(jié)點，函數(shù)k沒有定義)。于是，從節(jié)點n到某個具體的目標節(jié)點ti，某一條最小代價路徑的代價可由k(n,ti)給出。令h*(n)表示整個目標節(jié)點集合｛ti｝上所有k(n,ti)中最小的一個，因此，h*(n)就是從n到目標節(jié)點最小代價路徑的代價，而且從n到目標節(jié)點能夠獲得h*(n)的任一路徑就是一條從n到某個目標節(jié)點的最佳路徑(對于任何不能到達目標節(jié)點的節(jié)點n，函數(shù)h*沒有定義)。5.3.3A*算法A*算法是一種有序搜索算法，其特點在于對估價函數(shù)的定義63估價函數(shù)f(n)=g(n)+h(n)是對下列函數(shù)的一種估計或近似： f*(n)=g*(n)+h*(n)

f*(n)：從初始節(jié)點到節(jié)點n的一條最佳路徑的實際代價加上從節(jié)點n到目標節(jié)點的最佳路徑的代價之和。 g*(n)：從初始節(jié)點到節(jié)點n之間最小路徑的實際代價h*(n)：從節(jié)點n到目標節(jié)點的最小代價路徑上代價恒有：g*(n)≤g(n)在A*算法中，要求啟發(fā)函數(shù)h(n)是h*(n)的下界。 h(n)≤h*(n)極端情況下，若h(n)=0，一定能找到最佳解路徑估價函數(shù)f(n)=g(n)+h(n)是對下列函數(shù)的一64A*條件舉例8數(shù)碼問題h(n)=“不在位”的牌數(shù)h*(n)=“不在位”牌的距離和2

831

647512345768將牌1：1將牌2：1將牌6：1將牌8：2A*條件舉例8數(shù)碼問題2831265第五章狀態(tài)空間搜索策略S0Sg問題全狀態(tài)空間問題的搜索空間解路徑主要內容：狀態(tài)空間的搜索問題第五章狀態(tài)空間搜索策略S0Sg問題全狀態(tài)空間問題的搜索665.1搜索的概念及種類5.2盲目搜索5.3啟發(fā)式搜索5.1搜索的概念及種類675.1搜索的概念及種類搜索的概念：找到從初始事實到問題最終答案的一條推理路線，找到的這條路線是時間和空間復雜度最小的求解路線搜索種類：“盲目搜索”，即系統(tǒng)根據(jù)事先確定好的某種固定排序（依次或隨機）調用規(guī)則。“啟發(fā)式搜索”，即考慮問題領域可應用的知識，根據(jù)具體情況動態(tài)地確定規(guī)則的排序，優(yōu)先調用較合適的規(guī)則使用。5.1搜索的概念及種類搜索的概念：68搜索例子：回溯搜索算法

BACKTRACK（DATA）

DATA：當前狀態(tài)。返回值：成功：返回從當前狀態(tài)到目標狀態(tài)的路徑（以規(guī)則表的形式表示） 失?。悍祷谾AIL。搜索例子：回溯搜索算法 BACKTRACK（DATA）69四皇后問題皇后問題

在一個4*4的國際象棋棋盤上，一次一個地擺布四枚棋子，擺好后滿足每行、每列和對角線上只允許出現(xiàn)一枚棋子，即棋子之間不許相互攻擊。四皇后問題皇后問題70四皇后問題（續(xù)）綜合數(shù)據(jù)庫：DATA=L(表），L的元素屬于{ij}，1≤i,j≤4。DATA非空，其表元素表示棋子所在的行和列規(guī)則集：if1≤i≤4且在i-1行上有一個皇后then在第ij位置放上皇后。搜索策略固定次序：R11,R12,R13,…,R21,R22,R44四皇后問題（續(xù)）綜合數(shù)據(jù)庫：DATA=L(表），L的元素屬71()()72()Q((1,1))()Q((1,1))73()QQ((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))74()Q((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))75()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,176()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,177()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,178()Q((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)79()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)80()((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)81()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))()((1,1))((1,1)(2,3))((1,1)82()((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)83()((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))()((1,1))((1,1)(2,3))((1,1)845.1搜索的概念及種類5.2盲目搜索5.3啟發(fā)式搜索5.2.1狀態(tài)空間圖的一般搜索算法5.2.2寬度優(yōu)先搜索策略5.2.3深度優(yōu)先搜索策略5.2.4代價樹的寬度優(yōu)先搜索策略5.2.5代價樹的深度優(yōu)先搜索策略5.1搜索的概念及種類5.2.1狀態(tài)空間圖的一般搜索算法855.2盲目搜索策略

5.2.1狀態(tài)空間圖的一般搜索算法狀態(tài)空間表示法：用來表示問題及其搜索過程的一種方法。(P62)主要構成：（1）狀態(tài)，描述問題求解過程中不同時刻狀況的數(shù)據(jù)結構；（2）算符：使問題由一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作。（3）狀態(tài)空間：一個問題的全部狀態(tài)及一切可用算符構成的集合。一般包括3部分（初始狀態(tài)集合S，算符集合F，目標狀態(tài)集合G）（4）問題的求解：從S出發(fā)經(jīng)過一系列的算符運算，到達目標狀態(tài)。由初始狀態(tài)到目標狀態(tài)所用算符的序列構成了問題的一個求解狀態(tài)空間圖：把狀態(tài)空間的問題求解過程用圖的形式表示出來。節(jié)點代表狀態(tài)，弧代表算符5.2盲目搜索策略

5.2.1狀態(tài)空間圖的一般搜索算法865.2.1狀態(tài)空間圖的一般搜索算法幾個概念：擴展：用合適的算符對某個節(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，1）（3，1）5.2.1狀態(tài)空間圖的一般搜索算法幾個概念：圖2.26的87狀態(tài)空間的一般搜索算法一般搜索算法的描述：建立一個只含有初始節(jié)點S0的搜索圖G，把S0放入OPEN表中建立CLOSED表，且置為空表判斷OPEN表是否為空表，若為空，則問題無解，退出選擇OPEN表中的第一個節(jié)點，把它從OPEN表移出，并放入CLOSED表中，將此節(jié)點記為節(jié)點n考察節(jié)點n是否為目標節(jié)點，若是，則問題有解，成功退出。問題的解就是沿著n到S0的路徑得到。若不是轉⑥擴展節(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é)點的指針。按某一任意方式或某種策略重排OPEN表中節(jié)點的順序轉③特例狀態(tài)空間的一般搜索算法一般搜索算法的描述：特例88圖的一些概念：（1）節(jié)點深度： 根節(jié)點深度=0，其它節(jié)點深度=父節(jié)點深度+1（2）路徑 設一節(jié)點序列為(n0,n1,…,nk)，對于i=1,…,k，若節(jié)點ni-1具有一個后繼節(jié)點ni，則該序列稱為從n0到nk的路徑。（3）路徑的消耗值 一條路徑的消耗值等于連接這條路徑各節(jié)點間所有消耗值的總和。用C(ni,nj)表示從ni到nj的路徑的消耗值。0123圖的一些概念：012389節(jié)點類型說明…...…...…...…...…...mkmjmln擴展點n，產生mk：沒在OPEN和CLOSED表中出現(xiàn)過mj：在OPEN表中出現(xiàn)過ml：在CLOSED表中出現(xiàn)過節(jié)點類型說明…...…...…...…...…...mkmj90S123645將要擴展節(jié)點6S123645將要擴展節(jié)點691S126453修改4節(jié)點的返回指針S126453修改4節(jié)點的返回指針92S126453將要擴展節(jié)點1S126453將要擴展節(jié)點193S12645修改2和4的返回指針S12645修改2和4的返回指針945.2無信息圖搜索過程

——盲目搜索策略5.2.2寬度優(yōu)先搜索5.2.3深度優(yōu)先搜索5.2.4代價樹的寬度優(yōu)先5.2.5代價樹的深度優(yōu)先5.2無信息圖搜索過程

——盲目搜索策略5.2.2寬度優(yōu)951、定義如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索(breadth-firstsearch)。2、特點這種搜索是逐層進行的；在對下一層的任一節(jié)點進行搜索之前，必須搜索完本層的所有節(jié)點。

5.2.2寬度優(yōu)先搜索策略1、定義5.2.2寬度優(yōu)先搜索策略963、寬度優(yōu)先搜索算法(1)把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標節(jié)點，則求得一個解答)。(2)如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。(3)把第一個節(jié)點(節(jié)點n)從OPEN表移出，并把它放入CLOSED的擴展節(jié)點表中。(4)擴展節(jié)點n。如果沒有后繼節(jié)點，則轉向上述第(2)步。(5)把n的所有后繼節(jié)點放到OPEN表末端，并提供從這些后繼節(jié)點回到n的指針。(6)如果n的任一個后繼節(jié)點是個目標節(jié)點，則找到一個解答，成功退出；否則轉向第(2)步。3、寬度優(yōu)先搜索算法97例：把寬度優(yōu)先搜索應用于八數(shù)碼難題時所生成的搜索樹，這個問題就是要把初始棋局變?yōu)槿缦履繕似寰值膯栴}：123847655.2.2寬度優(yōu)先搜索策略例：把寬度優(yōu)先搜索應用于八數(shù)碼難題時所生成的搜索樹，這個問題9823184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標82341876542323283299寬度優(yōu)先搜索的性質當問題有解時，一定能找到解。當問題為單位消耗值，且問題有解時，一定能找到最優(yōu)解。算法與問題無關，具有通用性。時間效率和空間效率都比較低。寬度優(yōu)先搜索的性質當問題有解時，一定能找到解。1001、定義在此搜索中，首先擴展最新產生的(即最深的)節(jié)點。深度相等的節(jié)點可以任意排列。這種盲目(無信息)搜索叫做深度優(yōu)先搜索(depth-firstsearch)。2、特點首先，擴展最深的節(jié)點的結果使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點向下進行下去；只有當搜索到達一個沒有后裔的狀態(tài)時，它才考慮另一條替代的路徑。3、深度界限為了避免考慮太長的路徑(防止搜索過程沿著無益的路徑擴展下去)，往往給出一個節(jié)點擴展的最大深度界限。任何節(jié)點如果達到了深度界限，那么都將把它們作為沒有后繼節(jié)點處理。5.2.3深度優(yōu)先搜索策略1、定義5.2.3深度優(yōu)先搜索策略1013、深度優(yōu)先搜索算法(1)把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標節(jié)點，則求得一個解答)。(2)如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。(3)把第一個節(jié)點(節(jié)點n)從OPEN表移出，并把它放入CLOSED的擴展節(jié)點表中。(4)考察節(jié)點n是否為目標節(jié)點，若是，則找到問題的解，用回溯法求解路徑，退出（5）如果沒有后繼節(jié)點，則轉向上述第(2)步。(6)擴展節(jié)點n，把n的所有后繼節(jié)點放到OPEN表前端，并提供從這些后繼節(jié)點回到n的指針。轉向第(2)步。3、深度優(yōu)先搜索算法1022318476523184765283147652318476528314765283164752831476528316475283164752837146583214765281437652831457612378465123847652836417528316754832147652837146528143765283145761234567891011121312384765目標23232832103深度優(yōu)先搜索的性質一般不能保證找到最優(yōu)解。當深度限制不合理時，可能找不到解。最壞情況時，搜索空間等同于窮舉。深度優(yōu)先搜索的性質一般不能保證找到最優(yōu)解。1041、定義狀態(tài)空間圖中各節(jié)點之間有向邊的代價是不同的，有向邊上標有代價的搜索樹成為代價搜索樹。2、特點每次從OPEN表中選擇一個代價最小的節(jié)點，移入CLOSED表。3、C(i,j):從節(jié)點i到其后繼節(jié)點j的連線代價；g（x）:從初始節(jié)點到任意節(jié)點x的路徑代價；g(j)=g(i)+C(i,j).5.2.4代價樹的寬度優(yōu)先搜索1、定義5.2.4代價樹的寬度優(yōu)先搜索1054、代價樹的寬度優(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是否可擴展。若否則轉向第(2)步，若是則轉向(6)。(6)對節(jié)點n進行擴展，將他們的所有后繼節(jié)點放到OPEN表中，并對每個后繼節(jié)點j計算其總代價g(j)=g(j)+C(i,j),為每個后繼節(jié)點指向n節(jié)點的指針，然后根據(jù)節(jié)點的代價大小對OPEN表中的所有節(jié)點進行從小到大的排序。(7)轉向第(2)步。例子：推銷員旅行問題P1934、代價樹的寬度優(yōu)先搜索算法例子：推銷員旅行問題P193106ACBDE768765gC節(jié)點n父節(jié)點AACBDE768765gC節(jié)點n父節(jié)點A107ACBDE768765gC節(jié)點n父節(jié)點A66BA77CAACBDE768765gC節(jié)點n父節(jié)點A66BA77CA108ACBDE768765gC節(jié)點n父節(jié)點A66BA71175CDABACBDE768765gC節(jié)點n父節(jié)點A66BA77CA109ACBDE768765gC節(jié)點n父節(jié)點A66BA71114157578CDDEABCC節(jié)點擴展順序：A，B，C，D，D，E路線：A---C----EACBDE768765gC節(jié)點n父節(jié)點A66BA77CA節(jié)點110代價樹的寬度優(yōu)先搜索每次從OPEN表中的全體節(jié)點中選擇代價最小的節(jié)點移入CLOSED表進行擴展或判斷。代價樹的深度優(yōu)先搜索從剛剛擴展的節(jié)點的后繼節(jié)點中選擇一個代價最小的節(jié)點移入CLOSED表中，并進行擴展或判斷。5.2.5代價樹的深度優(yōu)先搜索代價樹的寬度優(yōu)先搜索每次從OPEN表中的全體節(jié)點中選擇代價最1114、代價樹的深度優(yōu)先搜索算法

(1)把起始節(jié)點放到OPEN表中，令g(S0)=0。(2)如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。(3)把OPEN表中的第一個節(jié)點（代價最小的節(jié)點n），移入CLOSED表。(4)如果n是目標節(jié)點，問題得解，退出。否則繼續(xù)。(5)判斷節(jié)點n是否可擴展。若否則轉向第(2)步，若是則轉向(6)。(6)對節(jié)點n進行擴展，并將其后繼節(jié)點按有向邊代價（C(i,j)）從小到大排序后放到OPEN表前端，并為每個后繼節(jié)點設置指向n節(jié)點的指針。(7)轉向第(2)步。4、代價樹的深度優(yōu)先搜索算法112ACBDE768765gC節(jié)點n父節(jié)點AACBDE768765gC節(jié)點n父節(jié)點A113ACBDE768765gC節(jié)點n父節(jié)點A66BA77CAACBDE768765gC節(jié)點n父節(jié)點A66BA77CA114ACBDE768765gC節(jié)點n父節(jié)點A66BA71175CDABACBDE768765gC節(jié)點n父節(jié)點A66BA77CA115ACBDE768765gC節(jié)點n父節(jié)點A66BA71117187578CDECABDD節(jié)點擴展順序：A，B，C，D，E路線：A----B----D----EACBDE768765gC節(jié)點n父節(jié)點A66BA77CA節(jié)點116ACBDE768765gC節(jié)點n父節(jié)點A66BA71114157578CDDEABCC節(jié)點擴展順序：A，B，C，D，D，E路線：A---C----EACBDE768765gC節(jié)點n父節(jié)點A66BA77CA節(jié)點1175.1搜索的概念及種類5.2盲目搜索5.3啟發(fā)式搜索5.3.1啟發(fā)信息與估價函數(shù)5.3.2最佳優(yōu)先搜索5.3.3A*搜索算法5.1搜索的概念及種類5.3.1啟發(fā)信息與估價函數(shù)1185.3啟發(fā)式圖搜索

5.3.1啟發(fā)信息與估價函數(shù)定義利用與問題有關的知識（即：啟發(fā)信息）來引導搜索，達到減少搜索范圍，降低問題復雜度的搜索過程稱為啟發(fā)式搜索方法。核心問題：啟發(fā)信息應用，啟發(fā)能力度量和如何獲得啟發(fā)信息。啟發(fā)信息的強度強：降低搜索工作量，但可能導致找不到最優(yōu)解。弱：一般導致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解。5.3啟發(fā)式圖搜索

5.3.1啟發(fā)信息與估價函數(shù)定義119希望：引入啟發(fā)知識，在保證找到最佳解的前提下，盡可能減少搜索范圍，提高搜索效率。搜索算法的效果：可以用啟發(fā)能力的強弱來度量?？紤]解路徑的消耗值和求得路徑所需搜索的消耗值兩者的某種組合最小?？紤]搜索方法對求解所有可能遇見的問題，其平均的組合消耗最小。希望：引入啟發(fā)知識，在保證找到最佳解的前提下，盡可能減少搜索120問題的關鍵如何尋找最有希望的節(jié)點啟發(fā)搜索過程中，要對OPEN表進行排序，這就需要有一種方法來計算待擴展節(jié)點有希望通向目標節(jié)點的不同程度。我們總希望能找到最有希望通向目標節(jié)點的待擴展節(jié)點優(yōu)先擴展。問題的關鍵如何尋找最有希望的節(jié)點121基本思想定義一個估價函數(shù)f（EvaluationFunction），對當前的搜索狀態(tài)進行評估，找出一個“最有希望”的節(jié)點來擴展?；舅枷攵x一個估價函數(shù)f（EvaluationFunct122估價函數(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)路徑的估計代價估價函數(shù)的格式：1235.3.2最佳優(yōu)先搜索