第5章搜索求解策略第5章搜索求解策略15.1基本概念一、狀態(tài)空間表示法狀態(tài)空間表示法是用“狀態(tài)”和“算符”（“操作”）來表示問題的一種方法?；诮獯鹂臻g的問題表示和求解方法，它是以狀態(tài)和算符為基礎(chǔ)來表示和求解問題的(1)狀態(tài)（state）：表示問題解法中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu)；Q=[q0，q1，…，qn]TQ表狀態(tài)，qi為狀態(tài)分量(2)算符（operator）：把問題從一種狀態(tài)變換為另一種狀態(tài)的手段；稱為操作符或算符。F：{f1,f2,……}狀態(tài)空間：由狀態(tài)變量和操作表示的符號體系，包含了問題求解時全部可能狀態(tài)及其相互關(guān)系。三元組表示（S，F(xiàn)，G）5.1基本概念一、狀態(tài)空間表示法2例設(shè)有三枚錢幣，其排列處在“正，正，反”狀態(tài)，現(xiàn)允許每次可翻動其中任意一個錢幣，問只允許操作三次的情況下，如何翻動錢幣使其變成“正，正，正”或“反，反，反”狀態(tài)。狀態(tài)：(q1,q2,q3)“正面”用“1”表示，“反面”用“0”表示初始狀態(tài)集合：{（1,1,0）}目標(biāo)狀態(tài)集合：{（1，1，1），(0,0,0)}操作：f1：翻q1，f2：翻q2，f3：翻q3F={f1,f2,f3}例設(shè)有三枚錢幣，其排列處在“正，正，反”狀態(tài)，現(xiàn)允許每次可翻3例：MC問題問題：3個傳教士(Missionary)，3個野人(Cannibal)，一條船，可同時乘坐2個人，要求在任何時刻，在河的兩岸，傳教士人數(shù)不能少于野人的人數(shù)。問：如何過河？狀態(tài)：用三元組(m,c,b)表示左岸的傳教士、野人和船數(shù)。m={0,1,2,3}，c={0,1,2,3}，b={0,1}共4×4×2＝32種狀態(tài)其中有16種可行，14種不可行（危險），2種達不到。初始狀態(tài)：S=（3，3，1）或S331目標(biāo)狀態(tài)：G=（0，0，0）或S000操作符（規(guī)則）Pij（左右），qij（右左）左右：p01,p10,p11,p02,p20條件：船在左岸右左：q01,q10,q11,q02,q20條件：船在右岸F={p01,p10,p11,p02,p20,q01,q10,q11,q02,q20}例：MC問題問題：3個傳教士(Missionary)，3個4MC問題狀態(tài)空間圖ppassqquitq11q11q02

(210)不合法p11(000)(330)達不到MC問題狀態(tài)空間圖ppassq11q11q025二、與/或樹（圖）表示法1、分解：大問題分解為若干個易解子問題，子問題解決了，大問題也就解決了。ABC或圖ABCD與圖2、變換：大問題變成若干個易解子問題，只要有一個子問題解決了，大問題也就解決了。二、與/或樹（圖）表示法1、分解：大問題分解為若干個易解子問6一些關(guān)于與或圖的術(shù)語HMBCDEFGAN父節(jié)點與節(jié)點弧線或節(jié)點子節(jié)點端節(jié)點一些關(guān)于與或圖的術(shù)語HMBCDEFGAN父節(jié)點與節(jié)點弧線或節(jié)7基本概念本原問題：不能再分解或變換，而且直接可解的子問題。終止節(jié)點：不能分解或變換，可直接求解可解節(jié)點：終止節(jié)點“或”節(jié)點，其子節(jié)點至少有一個是可解節(jié)點“與”節(jié)點，其子節(jié)點均為可解節(jié)點不可解節(jié)點：可解節(jié)點的三個條件都不滿足的節(jié)點解樹：由可解節(jié)點構(gòu)成，并可推出初始節(jié)點為可解節(jié)點的子樹基本概念本原問題：不能再分解或變換，而且直接可解的子問題。8梵塔問題可以分解為三個子問題：(1)最大盤以上由1至2(2)最大盤由1至3(3)其余盤由2至3問題的形式化表示：三元組(I,j,k)I---C所在鋼針號j----B所在鋼針號k---A所在鋼針號問題：（1，1，1）（3，3，3）ABC123ABC123梵塔問題可以分解為三個子問題：ABC123ABC1239三階梵塔問題的與/或樹（113）（123）

（111）（113）

（123）（122）

（111）（333）

（122）（322）

（111）（122）

（322）（333）

（321）（331）

（322）（321）

（331）（333）

三階梵塔問題的與/或樹（113）（123）（11110三、搜索根據(jù)問題的實際情況不斷尋找可利用的知識，從而構(gòu)造一條代價較少的推理路線，使問題得到圓滿解決的過程。類型：1、問題表示方式：狀態(tài)空間搜索與/或樹搜索2、是否使用啟發(fā)式信息盲目搜索：按預(yù)定的控制策略進行搜索，在搜索過程中獲得的中間結(jié)果不用來改進控制策略。啟發(fā)式搜索：搜索過程中加入與問題有關(guān)的啟發(fā)性信息。（動態(tài)地確定操作規(guī)則排序）三、搜索根據(jù)問題的實際情況不斷尋找可利用的知識，從而構(gòu)造一條115.2狀態(tài)空間的搜索策略基本思想：初態(tài)作為當(dāng)前節(jié)點進行擴展生成子節(jié)點，檢查目標(biāo)狀態(tài)是否出現(xiàn)，不出現(xiàn)則按策略選一個子節(jié)點進行擴展直到目標(biāo)狀態(tài)出現(xiàn)或沒有可供擴展的子節(jié)點。一、一般的圖搜索過程：OPEN表：存放尚未被擴展的節(jié)點CLOSED表：存放已被擴展的節(jié)點5.2狀態(tài)空間的搜索策略基本思想：12圖搜索算法：1.把初始節(jié)點S放入OPEN表，建立一個僅包含S的圖G（搜索圖）2.如果OPEN表空，則以失敗退出。3.把OPEN表中的第一個節(jié)點取出放入CLOSED表，稱此節(jié)點為n.4.如果n是目標(biāo)節(jié)點，則成功地結(jié)束，解路徑可通過回溯G中從n到S的指針獲得。5.擴展節(jié)點n，產(chǎn)生一組子節(jié)點。把不是n的祖先的那些子節(jié)點記作集合M，把M的這些成員作為n的后繼節(jié)點加入G中。6.對于M的那些未曾在G中出現(xiàn)的成員，建立到n的指針，并把這些成員加到OPEN表中。對于那些已在G中出現(xiàn)的成員，決定是否要修改它指向父節(jié)點的指針。對于那些已在G中出現(xiàn)且已擴展的成員，決定是否要修改其后繼節(jié)點指向父節(jié)點的指針。7.按某種搜索策略重排OPEN表中的節(jié)點8.轉(zhuǎn)第2步圖搜索算法：1.把初始節(jié)點S放入OPEN表，建立一個僅包含S13圖搜索的一般過程開始把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點嗎？擴展節(jié)點n，將其子節(jié)點處理后放入OPEN表，為每個子節(jié)點配置指向節(jié)點n的指針重排OPEN表失敗成功是是否否節(jié)點n可擴展嗎？否是圖搜索的一般過程開始把S放入OPEN表OPEN表為空表？把第14說明：這個一般的圖搜索過程，通過不斷循環(huán)生成一個顯式表示的圖G（搜索圖）和一個G的子集T（搜索樹）樹T是由（6）中標(biāo)記的指針決定的，除根節(jié)點s外，G中每個節(jié)點只有一個指針指向G中的一個父節(jié)點OPEN表中的節(jié)點（未擴展節(jié)點）是搜索樹的端節(jié)點，即尚未被選作為擴展的節(jié)點；CLOSED表中的節(jié)點（已擴展節(jié)點），可以是已被擴展而不能生成后繼節(jié)點的那些端節(jié)點，也可以是樹中的非端節(jié)點（7）中對OPEN表上的節(jié)點進行排序是為了在（3）中能選出一個“最好”的節(jié)點優(yōu)先擴展，不同的排序方法可構(gòu)成形式多樣的專門搜索算法如果隱含圖是一棵樹，不會（6）中討論的特殊節(jié)點，否則可能這些節(jié)點***上述算法的關(guān)鍵一步是（7），對OPEN表的排序，即決定節(jié)點的擴展順序，典型的有兩種節(jié)點擴展順序，得到兩種搜索算法（廣度優(yōu)先搜索、深度優(yōu)先搜索）說明：15二、寬度優(yōu)先（廣度優(yōu)先）基本思想是：從節(jié)點S0開始，逐層地對節(jié)點進行擴展，并考察它是否為目標(biāo)節(jié)點，在第n層節(jié)點沒有全部考察完之前，不對第n+1層的節(jié)點進行擴展。OPEN表：按“先進先出”排特點：一種高代價搜索，但若有解存在，則必能找到它。二、寬度優(yōu)先（廣度優(yōu)先）基本思想是：16例子

八數(shù)碼難題（8-puzzleproblem）

1238456712384567（目標(biāo)狀態(tài)）（初始狀態(tài)）規(guī)定：將牌移入空格的順序為：從空格左邊開始順時針旋轉(zhuǎn)。不許斜向移動，也不返回先輩節(jié)點。從圖可見，要擴展26個節(jié)點，共生成46個節(jié)點之后才求得解（目標(biāo)節(jié)點）。例子

八數(shù)碼難題（8-puzzleproblem）12171238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345圖八數(shù)碼難題的寬度優(yōu)先搜索樹1345612384567123845671238456712384567123845672324252627123678221238456712384567123845671238456712384567123845671238456714151617181920211238456712384567123841238456741238567118三、深度優(yōu)先搜索首先擴展最新產(chǎn)生的(即最深的)節(jié)點。深度相等的節(jié)點可以任意排列。與寬度優(yōu)先搜索算法最根本的不同在于：將擴展的后繼節(jié)點放在OPEN表的前端。（先進后出）三、深度優(yōu)先搜索首先擴展最新產(chǎn)生的(即最深的)節(jié)點。深度相等19問題不一定能找到解

找到的解不一定是最佳解

為了對深度優(yōu)先搜索作改進,要解決兩個問題：①回溯問題;②有圈造成死循環(huán)問題。

問題不一定能找到解為了對深度優(yōu)先搜索作改進,要解決兩個問20四、有界深度優(yōu)先搜索如果問題有解且路徑長度≤dm,則一定可求得解；否則得不到解。問題：dm不易確定這種方法不一定能找到解路徑（如果解路徑的深度超出了限制深度）另外它得到的解也不一定是最優(yōu)解改進先定一個較小的dm，若未找到解且closed中有待擴展的節(jié)點，就將其送回open表。不斷改進dm。最優(yōu)解：增設(shè)一表R，每找到一個解就將其放入R的前面。最后求得的解一定最優(yōu)四、有界深度優(yōu)先搜索如果問題有解且路徑長度≤dm,則一定可求21五、代價樹的廣度優(yōu)先搜索—分枝界限法有些問題并不要求有應(yīng)用算符序列為最少的解，而是要求具有某些特性的解。搜索樹中每條連接弧線上的有關(guān)代價以及隨之而求得的具有最小代價的解答路徑。代價樹：各邊標(biāo)有代價值的樹----一種加權(quán)樹代價計算g(x)-------sx代價g(x2)=g(x1)+c(x1,x2)基本思想：OPEN表中的全部節(jié)點按代價從小到大排五、代價樹的廣度優(yōu)先搜索—分枝界限法有些問題并不要求有應(yīng)用算22代價樹的廣度優(yōu)先搜索開始把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點嗎？擴展節(jié)點n，將其子節(jié)點處理后放入OPEN表，為每個子節(jié)點配置指向節(jié)點n的指針，計算各節(jié)點代價。把OPEN表中的全部節(jié)點按代價從小到大排失敗成功是是否否節(jié)點n可擴展嗎？否是代價樹的廣度優(yōu)先搜索開始把S放入OPEN表OPEN表為空表？23例下圖是一個交通圖，設(shè)A城市是出發(fā)地，E城市是目的地，邊上的數(shù)字代表兩城市之間的交通費。試求從A到E最小費用的旅行路線。Ac1d1e28例下圖是一個交通圖，設(shè)A城市是出發(fā)地，E城市是目的地，邊上的24六、代價樹的深度優(yōu)先搜索---爬山法基本思想：將擴展的后繼節(jié)點按邊代價從小到大的順序放在OPEN表的前端。代價樹的廣度優(yōu)先搜索法是完備的且找到的解一定是最優(yōu)解代價樹的深度優(yōu)先搜索法是不完備的且找到的解不一定是最優(yōu)解六、代價樹的深度優(yōu)先搜索---爬山法基本思想：將擴展的后繼節(jié)25七、啟發(fā)式搜索問題提出：從理論上講窮舉式搜索能解決任何狀態(tài)空間問題，但很顯然窮舉搜索只能解決狀態(tài)空間很小的簡單問題，對于復(fù)雜問題會出現(xiàn)“組合爆炸”n階Hanoi塔問題的狀態(tài)空間圖中有2的n次方減1個結(jié)點；博弈問題中，為了取勝可以將所有的算法都試一下，然后選擇最佳走步。就所有可能的棋局數(shù)來講，一字棋是9！=3.6*10^9，國際象棋是10^120，圍棋是10^761。假設(shè)每步可以選擇一種棋局，用極限并行速度（10^-104秒/步）計算，國際象棋的算法得用10^16年即1億億年才可以算完。解決：利用問題的啟發(fā)性信息來引導(dǎo)搜索減少搜索范圍降低問題復(fù)雜度啟發(fā)信息：進行搜索技術(shù)一般需要某些有關(guān)具體問題領(lǐng)域的特性的信息，把此種信息叫做啟發(fā)信息。把利用啟發(fā)信息的搜索方法叫做啟發(fā)性搜索方法。七、啟發(fā)式搜索問題提出：26啟發(fā)性信息類型1）用于擴展節(jié)點的選擇即決定下一個擴展節(jié)點,以免象在廣度優(yōu)先和深度優(yōu)先搜索中那樣盲目地擴展2）用于生成節(jié)點的選擇即用于決定生成哪個或哪幾個后繼節(jié)點,而不是生成所有的節(jié)點3）用于刪除節(jié)點的選擇即決定用于從搜索樹中拋棄或修剪的節(jié)點我們討論的主要是基于“擴展節(jié)點的選擇”的啟發(fā)式搜索，這種搜索總是選擇“最有希望”的節(jié)點作為下一個被擴展的節(jié)點。這種搜索叫做有序搜索(orderedsearch)。1、估價函數(shù)------評估節(jié)點的方法用來估算節(jié)點希望程度的量度，叫做估價函數(shù)啟發(fā)性信息類型1）用于擴展節(jié)點的選擇27f(x)=g(x)+h(x)

其中:f(x):從初始節(jié)點S0到目標(biāo)節(jié)點Sg的最優(yōu)路徑的代價估計值①g(x)為從初始節(jié)點S0到節(jié)點x的實際代價值。

②h(x)為啟發(fā)函數(shù),是從節(jié)點x到目標(biāo)節(jié)點Sg的最優(yōu)路徑的代價h*(n)的估計值。g(x)、h(x)作用分析一般地,在f(n)中,g(n)的比重越大,越傾向于寬度優(yōu)先搜索方式;h(n)的比重越大,越傾向于深度優(yōu)先搜索方式。保持g(n)項就保持了搜索的寬度優(yōu)先趨勢,這有利于搜索的完備性,但影響搜索的效率。在特殊情況下,如果只希望找到達到目標(biāo)結(jié)點的路徑而不關(guān)心已付出的代價,則g(n)的作用可以忽略。h(n)>>g(n)時,也可以忽略g(n),這時有f(n)=h(n),這有利于搜索的效率,但影響搜索的完備性。f(x)=g(x)+h(x)

其中:28定義h（x）的原則：節(jié)點x處在最佳路徑上的摡率節(jié)點x與目標(biāo)節(jié)點集之間的距離度量或差異度量根據(jù)格局或狀態(tài)的特點來打分一般來說,評價一個結(jié)點的價值,必須綜合考慮兩方面的因素:已經(jīng)付出的代價和將要付出的代價。啟發(fā)式算法通常由兩部分組成:啟發(fā)方法使用該方法搜索狀態(tài)空間的算法。啟發(fā)式搜索基本思想：以一般的圖搜索算法為基礎(chǔ)定義啟發(fā)函數(shù)h（x）計算每個待擴展節(jié)點的啟發(fā)函數(shù)值每次擴展節(jié)點后以節(jié)點的啟發(fā)函數(shù)值為依據(jù)對待擴展節(jié)點排序?qū)嵸|(zhì)：選擇OPEN表上具有最小f值的節(jié)點作為下一個要擴展的節(jié)點。定義h（x）的原則：29開始把S放入OPEN表，計算估價函數(shù)f(s)OPEN表為空表？選取OPEN表中f值最小的節(jié)點i放入CLOSED表i為目標(biāo)節(jié)點嗎？擴展i，得后繼節(jié)點j，計算f(j)，提供返回節(jié)點i的指針，利用f(j)對OPEN表重新排序，調(diào)整親子關(guān)系及指針失敗成功圖

有序搜索算法框圖是否是否算法開始把S放入OPEN表，計算估價函數(shù)f(s)OPEN表為30例：八數(shù)碼難題（8-puzzleproblem）f(n)=h(n)+g(n)=w(n)+d(n)

h(n)=w(n),w(n)是將牌不在位個數(shù),例如,與目標(biāo)狀態(tài)相比,初始狀態(tài)w(n)=4,即有4個將牌(1,2,6,8)不在位。g(n)=d(n),d(n)是搜索的深度。一般根節(jié)點(初始狀態(tài))的深度是為0,其他子節(jié)點深度為父結(jié)點深度加1。

規(guī)定規(guī)則為空格移動(走步規(guī)則),規(guī)則選取順序為:左、上、右、下?？刂撇呗詾?選取評價函數(shù)值最小者進行擴展(往下搜索)。12384567（目標(biāo)狀態(tài)）12384567（初始狀態(tài)）例：八數(shù)碼難題（8-puzzleproblem）f(n)315714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712384567（5）（7）1238456712384567（6）（7）12384567（5）8132456712384567（5）（7）圖八數(shù)碼難題的有序搜索樹123846（4）757145631238456712384567123845632人工智能第五章33A算法利用評價函數(shù)f(n)=g(n)+h(n)來排列OPEN表節(jié)點順序的圖搜索算法稱為A算法。實現(xiàn)類型：局部擇優(yōu)搜索、全局擇優(yōu)搜索2、局部擇優(yōu)搜索----類似深度優(yōu)先基本思想：在當(dāng)前擴展的子節(jié)點中選f(x)值最小的子節(jié)點為下一個考察的節(jié)點實現(xiàn)：節(jié)點n擴展后的各子節(jié)點計算出估價值后，按由小到大次序放到OPEN表的首部分析：可把深度優(yōu)先、代價樹的深度優(yōu)先看成其特例。3、全局擇優(yōu)搜索----類似廣度優(yōu)先節(jié)點n擴展后的各子節(jié)點計算出估價值后，送入OPEN表，然后OPEN表中全部節(jié)點按估價值由小到大排A算法利用評價函數(shù)f(n)=g(n)+h(n)來排344、A*算法(AlgorithmA*)幾個有用的記號f（x）=g（x）+h（x）f*(x)=g*（x）+h*（x）g*（x）：從節(jié)點S到節(jié)點x的一條最佳路徑的實際代價h*（x）：從節(jié)點x到某目標(biāo)節(jié)點的一條最佳路徑的代價f*(x)：從S開始約束通過節(jié)點x的一條最佳路徑的代價分析：g是g*（x）的估計；對于g（n）來說，一個明顯的選擇就是搜索樹中從Ｓ到n這段路徑的代價，這一代價可以由從n到Ｓ尋找指針時，把所遇到的各段弧線的代價加起來給出（這條路徑就是到目前為止用搜索算法找到的從S到n的最小代價路徑)。這個定義包含了g（x）≥g*（x）。h是h*（x）的估計；對于h（n），它依賴于有關(guān)問題的領(lǐng)域的啟發(fā)信息。4、A*算法(AlgorithmA*)幾個有用的記號35A*算法---又稱最佳圖搜索算法，由著名人工智能學(xué)者Nilsson提出。定義：如果A算法中使用的啟發(fā)函數(shù)h(n)對任何節(jié)點n都有h(n)≤h*(n)，則稱其為A*算法(AlgorithmA*)。對于寬度優(yōu)先搜索算法，h(n)=0，滿足h(n)≤h*(n)。寬度優(yōu)先算法是A*算法的特殊情形。A*算法的性質(zhì)：（1）可采納性如果一個搜索算法對于任何具有解路徑的圖都能找到一條最佳解路徑。則稱此算法是可采納的。結(jié)論：A*算法是可采納的證明：對有限圖，A*算法一定會在有限步結(jié)束對無限圖，只有從S0到Sg有路徑存在，則A*算法也必然會結(jié)束A*算法一定會終止在最優(yōu)路徑上A*算法---又稱最佳圖搜索算法，由著名人工智能學(xué)者Nils36a)對有限圖，A*算法一定會在有限步結(jié)束證明：因為搜索圖為有限圖，所以會出現(xiàn)以下情況：算法找到解，則成功結(jié)束（算法第4步）算法找不到解，則必然會因OPEN表變空而結(jié)束（算法第2步）b)對無限圖，只有從S0到Sg有路徑存在，則A*算法也必然會結(jié)束證明：（分2步）第1步證明：A*結(jié)束前,OPEN表中必存在節(jié)點n，它是最佳路徑上的一個節(jié)點，且滿足

f(n)<=f*(s)證明:設(shè)從初始節(jié)點s到目標(biāo)節(jié)點t的一條最佳路徑序列為

(n0=s,n1,…,nk=t)a)對有限圖，A*算法一定會在有限步結(jié)束證明：因為搜索圖為37算法初始化時,s在OPEN中,由于A*沒有結(jié)束,在OPEN中存在最佳路徑上的節(jié)點。設(shè)OPEN表中的第一個節(jié)點n是處在最佳路徑序列中(至少有一個這樣的節(jié)點,因s一開始是在OPEN上),顯然n的先輩節(jié)點np,已在CLOSED中,因此能找到s到np,的最佳路徑,而n也在最佳路徑上,因而s到n的最佳路徑也能找到,因此有：f(n)=g(n)+h(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)因為：最佳路徑上的所有節(jié)點的f*值都應(yīng)相等

所以f(n)≤f*(s)。[證畢]第2步證明A*算法一定會終止證明：

（反證法）假定A*不結(jié)束,設(shè)：e-----圖中各邊的最小代價d*(n)-------從s到任一節(jié)點n的最短路徑長度(設(shè)每個弧的長度均為1)算法初始化時,s在OPEN中,由于A*沒有結(jié)束,在OP38所以g*(n)≥d*(n)e因g(n)≥g*(n)所以g(n)≥d*(n)e因h(n)≥0(設(shè)h(n)≥0)所以f(n)=g(n)+h(n)≥g(n)所以f(n)≥d*(n)e若A*不結(jié)束,則隨著搜索的進行，d*(n)會無限增大,所以f值將增到任意大，這與第1步證明的結(jié)果“f(n)≤f*(s)”矛盾，因f*(s)一定是有限值。所以，A*算法一定會終止c)A*算法一定會終止在最優(yōu)路徑上證明：反證法若A*算法不是在最優(yōu)路徑上終止，而是在某個目標(biāo)節(jié)點t結(jié)束則f(t)=g(t)>f*(s)而根據(jù)b)證明可知：在A*結(jié)束前，OPEN表中存在最優(yōu)路徑上的節(jié)點n,且有f(n)≤f*(s),所以f(n)≤f*(s)<f(t)這時算法A*應(yīng)選n作為當(dāng)前點擴展,不可能選t,從而也不會去測試目標(biāo)節(jié)點t,即這與假定A*選t結(jié)束矛盾。所以A*只能結(jié)束在最佳路徑上。[證畢]所以g*(n)≥d*(n)e因g(n)39（2）A*算法的最優(yōu)性（信息性）應(yīng)用A*的過程中,如果選作擴展的節(jié)點n,其評價函數(shù)值f(n)=f*(n),則不會去擴展多余的節(jié)點就可找到解?？梢韵胂竦絝(n)越接近于f*(n),擴展的節(jié)點數(shù)就會越少,即啟發(fā)函數(shù)中,應(yīng)用的啟發(fā)信息(問題知識)愈多,擴展的節(jié)點數(shù)就較少。定理:有A*算法A1，A2,A1：f1(n)=g1(n)+h1(n)A2：f2(n)=g2(n)+h2(n)

若A2比A1有較多的啟發(fā)信息(即對所有非目標(biāo)節(jié)點均有h2(n)>h1(n)),則在搜索過程中，被A2擴展的節(jié)點也必定由A1擴展,即A1擴展的節(jié)點不會比A2擴展的節(jié)點少，亦即A2擴展的節(jié)點集是A1擴展的節(jié)點集的子集。

（2）A*算法的最優(yōu)性（信息性）應(yīng)用A*的過程中,如果選40證明:使數(shù)學(xué)歸納法,對節(jié)點的深度應(yīng)用歸納法。

對深度d(n)=0的節(jié)點(即初始節(jié)點s),若s為目標(biāo)節(jié)點,則A1和A2都不擴展s,否則A1和A2都擴展了s(2)設(shè)深度d(n)≤k時,對所有路徑的端節(jié)點,定理結(jié)論都成立。

(3)證明d(n)=k+1時,所有路徑的端節(jié)點,結(jié)論成立。（反證法）

設(shè)A2搜索樹上有一個節(jié)點n(d(n)=k+1)被A2擴展了,而對應(yīng)于A1搜索樹上的這個節(jié)點n,沒有被A1擴展。根據(jù)歸納法假設(shè)條件,A1擴展了n的父節(jié)點,n是在A1搜索樹上,因此A1結(jié)束時,n必定保留在其OPEN表上,n沒有被A1選擇擴展,有

f1(n)≥f*(s),

即g1(n)+h1(n)≥f*(s)

所以h1(n)≥f*(s)-g1(n)(1)

另一方面A2擴展了n,有

f2(n)≤f*(s),

即g2(n)+h2(n)≤f*(s)

所以h2(n)≤f*(s)-g2(n)(2)

由于d=k時,A2擴展的節(jié)點,A1也一定擴展,故有

g1(n)≤g2(n)(因A1擴展的節(jié)點數(shù)可能較多)

所以h1(n)≥f*(s)-g1(n)≥f*(s)-g2(n)(3)

比較式(2)、(3)可得:至少在節(jié)點n上有h1≥h2(n),這與定理的前提條件矛盾,因此存在節(jié)點n的假設(shè)不成立。[證畢]

證明:使數(shù)學(xué)歸納法,對節(jié)點的深度應(yīng)用歸納法。41（3）單調(diào)性-----指h(n)的單調(diào)限制在A*算法中,每當(dāng)要擴展一個節(jié)點時,都要先檢查其子節(jié)點是否已在OPEN表或CLOSED表中,有時還需要調(diào)整指向父節(jié)點的指針,這就增加了搜索的代價.如果對啟發(fā)函數(shù)h(n)加上單調(diào)限制,就可以減少檢查及調(diào)整的工作量,提高搜索效率.單調(diào)限制是指h(n)滿足兩個條件:(1) h(Sg)=0(2) 設(shè)nj是節(jié)點ni的任意子節(jié)點,則有:h(ni)-h(nj)c(ni,nj)其中,Sg是目標(biāo)節(jié)點,c(ni,nj)是節(jié)點ni到其子節(jié)點nj的弧代價.將上式改寫成: h(ni)

h(nj)+c(ni,nj)可看出:節(jié)點ni到目標(biāo)節(jié)點最優(yōu)費用的估價不會超過從節(jié)點ni到其子節(jié)點nj的弧代價加上從nj到目標(biāo)節(jié)點最優(yōu)費用的估價.可以證明:(1)如果滿足單調(diào)限制,則當(dāng)A*選擇節(jié)點n擴展時,就已經(jīng)發(fā)現(xiàn)了通向節(jié)點n的最佳路徑.即:g(n)=g*(n)(2)如果A*滿足單調(diào)限制,則A*所擴展節(jié)點序列的估價函數(shù)值是單調(diào)上升的.（3）單調(diào)性-----指h(n)的單調(diào)限制在42A*算法的理論意義A*算法的理論意義在于給出了求解最佳解的條件h(n)≤h*(n)。對給定的問題,函數(shù)h*(n)(n是變量)在問題有解的條件下客觀上是存在的。但在問題求解過程中不可能都明確知道例：八數(shù)碼難題h(n)=w(n)(將牌不在位個數(shù))，顯然有h(n)=W(n)≤h*(n)h(n)=p(n)（每一個將牌與其目標(biāo)位置之間距離的總和），

顯然有h(n)=p(n)≤h*(n)h(n)取值分析：

①h(n)=0:即啟發(fā)函數(shù)啟發(fā)信息為0,f(n)=h(n)+g(n)=g(n)d(n)(搜索深度),此實際上是寬度優(yōu)先搜索。②h(n)=W(n):f(n)=h(n)+g(n)=W(n)+d(n)(搜索深度)(前面例子中：初始狀態(tài):W(n)=4,d(n)=0)

③h(n)=p(n):f(n)=h(n)+g(n)=p(n)+d(n)(搜索深度)。(前面例子中：初始狀態(tài)：p(n)=5,d(n)=0)都是A*算法A*算法的理論意義A*算法的理論意義在于給出了求解最佳解的條43h(n)=p(n)“▲”節(jié)點為被擴的節(jié)點“■”節(jié)點為生成的節(jié)點d)h(n)=p(n)“▲”節(jié)點為被擴的節(jié)點d)445.3與或樹（圖）搜索5.3與或樹（圖）搜索45與或圖表示法特點與或圖表示問題特點可分解的問題可變換的問題例：如何上班問題開自家車車況好（自己修車，他人修車）足夠燃料（車開到加油站，自帶燃料）步行身體狀況好足夠的時間公交車步行到車站騎車到車站與或圖表示法特點與或圖表示問題特點46上班問題開自家車步行乘公交車車況好燃料足他人修自己修他人修加油站自帶燃油燃油箱身體好時間夠步行到車站騎車到車站與或圖的構(gòu)成與節(jié)點：分解問題或節(jié)點：變換問題弧:相關(guān)節(jié)點的聯(lián)結(jié)終止節(jié)點：本原問題與或圖表示法與節(jié)點,或節(jié)點,終止節(jié)點端節(jié)點可解節(jié)點不可解節(jié)點解圖上班問題開自家車步行乘公交車車況好燃料足他人修自己修他人修加47與或圖例子1可解節(jié)點23B端節(jié)點（不可擴展節(jié)點）54t1At2t3t4終止節(jié)點開自家車步行車況好燃料足自己修他人修加油站自帶燃油燃油箱身體好時間夠步行到車站騎車到車站上班問題乘公交車與或圖例子1可解節(jié)點23B端節(jié)點（不可擴展節(jié)點）54t1At48一、與或樹搜索的一般過程1、幾個概念可解標(biāo)示過程：由可解子節(jié)點來確定父節(jié)點，祖父節(jié)點等為可解節(jié)點的過程不可解標(biāo)示過程：由不可解子節(jié)點來確定父節(jié)點，祖父節(jié)點等為不可解節(jié)點的過程2、基本思想：對與或樹（圖）標(biāo)記（示）可解與不可解的遞歸過程，通過對終節(jié)點的可解與否最終確定初始節(jié)點是否可解。擴展（自上而下）標(biāo)示（自下而上）結(jié)束條件：初始節(jié)點為可解或不可解一、與或樹搜索的一般過程1、幾個概念49搜索過程（1）把原始問題作為初始節(jié)點S0,并將其作為當(dāng)前節(jié)點（2）應(yīng)用分解或變換算符過程對當(dāng)前節(jié)點進行擴展（3）為每個子節(jié)點設(shè)置指向父節(jié)點的指針（4）選擇適當(dāng)?shù)淖庸?jié)點作為當(dāng)前節(jié)點，反復(fù)應(yīng)用（2）（3）步，在此期間要多次應(yīng)用可解標(biāo)示過程和不可解標(biāo)示過程，直到初始節(jié)點被標(biāo)示為可解節(jié)點或不可解節(jié)點。搜索樹：搜索過程所形成的節(jié)點和指針結(jié)構(gòu)解樹：若已標(biāo)示初始節(jié)點是可解的，則由初始節(jié)點及其下屬的可解節(jié)點就構(gòu)成了解樹節(jié)點的刪除可解節(jié)點的不可解后裔不可解節(jié)點的全部后裔搜索過程（1）把原始問題作為初始節(jié)點S0,并將其作為當(dāng)前節(jié)點50二、與或樹的廣度優(yōu)先搜索（1）把初始節(jié)點S0放入OPEN表（2）把OPEN表中的第一個節(jié)點（n）取出放入CLOSED表（3）n可擴展OPEN表按“先進先出”排子節(jié)點加入OPEN表尾時要判斷其是否為終止節(jié)點。若是，則標(biāo)示可解并調(diào)用可解標(biāo)示過程標(biāo)示其祖先節(jié)點。若S0可解則結(jié)束，否則刪去具有可解祖先的子節(jié)點。（4）n不可擴展標(biāo)示為不可解節(jié)點并調(diào)用不可解標(biāo)示過程標(biāo)示其祖先節(jié)點。若S0不可解則結(jié)束，否則刪去具有不可解祖先的子節(jié)點。（5）轉(zhuǎn)（2）二、與或樹的廣度優(yōu)先搜索（1）把初始節(jié)點S0放入OPEN表51解樹構(gòu)成：1,2,3,4,5,t1,t2,t3,t4解樹構(gòu)成：52三、與或樹的深度優(yōu)先搜索（1）把初始節(jié)點S0放入OPEN表（2）把OPEN表中的第一個節(jié)點（n）取出放入CLOSED表（3）n可擴展OPEN表按“后進先出”排子節(jié)點加入OPEN表首時要判斷其是否為終止節(jié)點。若是，則標(biāo)示可解并調(diào)用可解標(biāo)示過程標(biāo)示其祖先節(jié)點。若S0可解則結(jié)束，否則刪去具有可解祖先的子節(jié)點。（4）n不可擴展（若深度≥界限，當(dāng)不可擴展處理）標(biāo)示為不可解節(jié)點并調(diào)用不可解標(biāo)示過程標(biāo)示其祖先節(jié)點。若S0不可解則結(jié)束，否則刪去具有不可解祖先的子節(jié)點。（5）轉(zhuǎn)（2）三、與或樹的深度優(yōu)先搜索（1）把初始節(jié)點S0放入OPEN表53四、與或樹的有序搜索根據(jù)代價決定搜索路線-----求最優(yōu)解樹是與或圖啟發(fā)式搜索的一種特例與或圖啟發(fā)式搜索算法也稱為AO*算法1、擴展節(jié)點時代價計算節(jié)點x的代價為h(x)X：終止節(jié)點h(x)=0端節(jié)點（非終止）h(x)=∞或節(jié)點與節(jié)點四、與或樹的有序搜索根據(jù)代價決定搜索路線-----求最優(yōu)解樹54根節(jié)點的代價-----解樹的代價左邊的解樹S0,A,t1,C,t3H(s0)=2+4+6+2=14(按和)H(s0)=8+2=10(按最大)右邊的解樹s0,B,t2,D,t4H(s0)=1+5+3+2=11(按和)H(s0)=6+2=8(按最大)無論按和代價還是最大代價，右邊的解樹都是最優(yōu)解樹根節(jié)點的代價-----解樹的代價左邊的解樹S0,A,t1,C55問題1）由于h(yi)不是終止節(jié)點則無法知道其值引入啟發(fā)函數(shù)計算h(yi)2）每當(dāng)有一代新節(jié)點生成時，都要自下而上地重新計算其先輩節(jié)點的代價h3）選出擴展的節(jié)點應(yīng)是代價最小的部分解樹（圖）中的節(jié)點希望樹：可能成為最優(yōu)解樹的一部分2、希望樹T在搜索過程中任一時刻求出的局部解圖（樹）其代價都是最小的。這個局部解圖即是希望圖（樹）1)S0在T中2)x在T中若x為“或”接點，則滿足min{c(x,yi)+h(yi)}的子節(jié)點yi也在T中若x為“與”接點，則其所有子節(jié)點yi也在T中問題1）由于h(yi)不是終止節(jié)點則無法知道其值563、與或樹的有序搜索過程目標(biāo)：尋找最小代價的解樹，最優(yōu)解圖(樹)方法：按解圖生成的方法,分步生成局部解圖,重新計算節(jié)點的耗散值（代價）,從中選擇一個代價最小的局部解圖用于擴展，同時使用標(biāo)示過程。與其他搜索過程的不同點：從OPEN表中選希望樹T的端節(jié)點N作為當(dāng)前節(jié)點送入CLOSED表擴展N時所產(chǎn)生的子節(jié)點均需計算自身及其先輩節(jié)點的h值具體過程：（1）把S0放入OPEN表中，計算h(S0)（2）計算希望樹T（3）依次在OPEN表中取出T的端節(jié)點n放入CLOSED表（4）根據(jù)n的三種可能做以下工作：3、與或樹的有序搜索過程目標(biāo)：尋找最小代價的解樹，最優(yōu)解圖(57n的三種可能：

“終止節(jié)點”、不是但可擴展、不是且不可擴展“終止節(jié)點”①標(biāo)記n為可解節(jié)點②在T上應(yīng)用可解標(biāo)記過程，對n的先輩節(jié)點中的所有可解節(jié)點進行標(biāo)記③如果初始節(jié)點S0被標(biāo)記為可解，則T就是最優(yōu)解樹，成功退出④否則，從OPEN表中刪去具有可解先輩的所有節(jié)點⑤轉(zhuǎn)（2）n的三種可能：

“終止節(jié)點”、不是但可擴展、不是且不可擴展“58不是“終止節(jié)點”但可擴展①擴展節(jié)點n，生成n的所有子節(jié)點②把這些子節(jié)點都放入OPEN表，并為每一個子節(jié)點設(shè)置指向父節(jié)點n的指針③計算這些子節(jié)點及其先輩節(jié)點的h值④轉(zhuǎn)（2）不是“終止節(jié)點”且不可擴展①標(biāo)記n為不可解節(jié)點②在T上應(yīng)用不可解標(biāo)記過程，對n的先輩節(jié)點中的所有不可解節(jié)點進行標(biāo)記③如果初始節(jié)點S0被標(biāo)記為不可解，則問題無解，失敗退出④否則，從OPEN表中刪去具有不可解先輩的所有節(jié)點⑤轉(zhuǎn)（2）不是“終止節(jié)點”但可擴展①擴展節(jié)點n，生成n的所有子節(jié)點不59與或樹示例：

設(shè)：在搜索過程中每次擴展兩層且按一層或節(jié)點、一層與節(jié)點的間隔方式進行擴展按和計算。10、S0擴展兩層判斷：右子樹為當(dāng)前的T按“和”計算與或樹示例：

設(shè)：在搜索過程中每次擴展兩層且按一層或節(jié)點、一6020、擴展E30計算T右子樹h(s0)=12左子樹h(s0)=9所以T應(yīng)改為左子樹按“和”計算20、擴展E30計算T按“和”計算6140、擴展B因H，I可解，調(diào)用可解標(biāo)記過程得：G，B可解計算T，仍是左子樹刪除可解節(jié)點的后裔（B的后裔）40、擴展B因H，I可解，調(diào)用可解標(biāo)記過程得：G，B可解6250、擴展CN，P可解，調(diào)用可解標(biāo)記過程得：M，C，A可解，所以推出S0為可解節(jié)點，結(jié)束。50、擴展CN，P可解，調(diào)用可解標(biāo)記過程得：M，C，A可解，63五、博弈樹的啟發(fā)式搜索1、博弈樹諸如下棋、打牌、競技、戰(zhàn)爭等一類競爭性智能活動稱為博弈。博弈樹：以一方立場（我方）來看博弈過程用圖表示出來，得到的與或樹初始節(jié)點為博弈的初始格局。與或節(jié)點交替出現(xiàn)，我方擴展節(jié)點之間是“或”的關(guān)系，敵方為“與”節(jié)點。使我方獲勝的終局都是本原問題，使敵方獲勝的終局都是不可解節(jié)點博弈的特點：二人零和，全信息，非偶然二人零和：結(jié)果必有一方獲勝，或平局。全信息：參與者都了解對手當(dāng)前和過去的走步，也可以推測出將要走的招術(shù)。非偶然:根據(jù)當(dāng)前情況（一般不能看到終局），選取對自己最為有利而對對方最為不利的對策五、博弈樹的啟發(fā)式搜索1、博弈樹64如何找到博弈必勝的策略思路：盡選擇對自己有利的方案，向前盡量多看幾步基本概念靜態(tài)估值：每個結(jié)點的勢態(tài)估計值。倒推值：由每個結(jié)點的靜態(tài)估值倒推出父結(jié)點的估計值?；蚬?jié)點(MAX節(jié)點)，其倒推值選取各分枝中最大值。與節(jié)點(MIN節(jié)點)，其倒推值選取各分枝中最小值?；舅枷?極大極小法)。以一定深度生成博奕樹(擴展一級或二級),應(yīng)用各節(jié)點的靜態(tài)估計值計算出(倒推出)每個非端節(jié)點的倒退值。選取”或”節(jié)點(我方，MAX)得分極大的棋步(對或節(jié)點來說)選取”與”節(jié)點(敵方，MIN)得分極小的棋步(對與節(jié)點來說)逐級搜索，求解博奕問題。如何找到博弈必勝的策略652、博奕樹極大極小搜索一字棋游戲極小極大分析法：設(shè)有九個空格，由MAX，MIN二人對弈，輪到誰走棋誰就往空格上放一只自己的棋子，誰先使自己的棋子構(gòu)成“三子成一線”(同一行或列或?qū)蔷€全是某人的棋子)，誰就取得了勝利。用叉號表示MAX，用圓圈代表MIN。

為了不致于生成太大的博弈樹，

假設(shè)每次僅擴展兩層。估價函數(shù)定義：設(shè)棋局為P，估價函數(shù)為e(P)。e(p)=(所有空格都放上MAX的棋子之后,MAX的三子成線(行、列、對角)的總數(shù))—(所有空格都放上MIN的棋子之后,MIN的三子成線(行、列、對角)的總數(shù))2、博奕樹極大極小搜索一字棋游戲極小極大分析法：用66e(p)若P是MAX必勝的棋局，則e(P)＝+∞。若P是B必勝的棋局，則e(P)＝-∞。具有對稱性的兩個棋局算作一個棋局求解過程搜索樹端節(jié)點的估計值-表示MAX不可再分+表示MIN不可再分極大極小分析方法計算倒推值選取對MAX最有利的方案e(p)若P是MAX必勝的棋局，則e(P)＝+∞。求解過程67應(yīng)用極大極小分析法產(chǎn)生深度為2的博奕樹，以決定下一步應(yīng)該如何走棋靜態(tài)估值倒推值應(yīng)用極大極小分析法產(chǎn)生深度為2的博奕樹，以決定下一步應(yīng)該如何68六、－剪枝枝術(shù)極小極大分析法，實際是先生成一棵博弈樹，然后再計算其倒推值，至使極小極大分析法效率較低。于是在極小極大分析法的基礎(chǔ)上提出了α-β剪枝技術(shù)?；舅枷耄哼吷刹┺臉溥呌嬎阍u估各節(jié)點的倒推值，并且根據(jù)評估出的倒推值范圍，及時停止擴展那些已無必要再擴展的子節(jié)點，即相當(dāng)于剪去了博弈樹上的一些分枝，從而節(jié)約了機器開銷，提高了搜索效率。SABC=2D=7E=1F未定六、－剪枝枝術(shù)極小極大分析法，實際是先生成一棵博弈樹，69－值“與”節(jié)點：取當(dāng)前子節(jié)點中最小倒推值作為其倒推值的上界---值“或”節(jié)點：取當(dāng)前子節(jié)點中最大倒推值作為其倒推值的下界---值－剪枝枝術(shù)的一般規(guī)律任何“或”節(jié)點x的值大于等于其先輩節(jié)點的值,則x以下的分枝可以停止搜索，并使x的倒推值為.這種剪枝稱為剪枝.任何“與”節(jié)點x的值小于等于其先輩節(jié)點的值,則x以下的分枝可以停止搜索，并使x的倒推值為.這種剪枝稱為剪枝一個節(jié)點的第一個子節(jié)點的倒推值是很重要。－值70S0S2S1S3S4S5S63523α剪枝α-β剪枝β剪枝α剪枝βS0BAE<=2CDJKTU>=2<=1>=1<=1<=-5-51IR>=555S981-2FGHMNPQ2L4*<=-2<=12>=2******βαS0S2S1S3S4S5S63523α剪枝α-β剪枝β剪枝α71α-β剪枝技術(shù)的搜索效率分析要進行α-β修剪，必須至少使某一部分的搜索樹生長到最大深度，因為α和β值必須以端節(jié)點的靜態(tài)估值為依據(jù)。因此采用α-β剪枝技術(shù)通常都要使用某種深度優(yōu)先的搜索方法。在一次搜索期間修剪的枝數(shù)取決于早期的α、β值與最終倒推值之間的近似程度。起始節(jié)點的最終倒推值等于某個端節(jié)點的靜態(tài)估值。如果在深度優(yōu)先搜索過程中第一次就遇到這個端節(jié)點，則修剪枝數(shù)最大。當(dāng)前修剪枝數(shù)最大時，需要生成和估計的端節(jié)點數(shù)就最少。

α-β剪枝技術(shù)的搜索效率分析要進行α-β修剪，必須至少使某一72第5章搜索求解策略第5章搜索求解策略735.1基本概念一、狀態(tài)空間表示法狀態(tài)空間表示法是用“狀態(tài)”和“算符”（“操作”）來表示問題的一種方法?；诮獯鹂臻g的問題表示和求解方法，它是以狀態(tài)和算符為基礎(chǔ)來表示和求解問題的(1)狀態(tài)（state）：表示問題解法中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu)；Q=[q0，q1，…，qn]TQ表狀態(tài)，qi為狀態(tài)分量(2)算符（operator）：把問題從一種狀態(tài)變換為另一種狀態(tài)的手段；稱為操作符或算符。F：{f1,f2,……}狀態(tài)空間：由狀態(tài)變量和操作表示的符號體系，包含了問題求解時全部可能狀態(tài)及其相互關(guān)系。三元組表示（S，F(xiàn)，G）5.1基本概念一、狀態(tài)空間表示法74例設(shè)有三枚錢幣，其排列處在“正，正，反”狀態(tài)，現(xiàn)允許每次可翻動其中任意一個錢幣，問只允許操作三次的情況下，如何翻動錢幣使其變成“正，正，正”或“反，反，反”狀態(tài)。狀態(tài)：(q1,q2,q3)“正面”用“1”表示，“反面”用“0”表示初始狀態(tài)集合：{（1,1,0）}目標(biāo)狀態(tài)集合：{（1，1，1），(0,0,0)}操作：f1：翻q1，f2：翻q2，f3：翻q3F={f1,f2,f3}例設(shè)有三枚錢幣，其排列處在“正，正，反”狀態(tài)，現(xiàn)允許每次可翻75例：MC問題問題：3個傳教士(Missionary)，3個野人(Cannibal)，一條船，可同時乘坐2個人，要求在任何時刻，在河的兩岸，傳教士人數(shù)不能少于野人的人數(shù)。問：如何過河？狀態(tài)：用三元組(m,c,b)表示左岸的傳教士、野人和船數(shù)。m={0,1,2,3}，c={0,1,2,3}，b={0,1}共4×4×2＝32種狀態(tài)其中有16種可行，14種不可行（危險），2種達不到。初始狀態(tài)：S=（3，3，1）或S331目標(biāo)狀態(tài)：G=（0，0，0）或S000操作符（規(guī)則）Pij（左右），qij（右左）左右：p01,p10,p11,p02,p20條件：船在左岸右左：q01,q10,q11,q02,q20條件：船在右岸F={p01,p10,p11,p02,p20,q01,q10,q11,q02,q20}例：MC問題問題：3個傳教士(Missionary)，3個76MC問題狀態(tài)空間圖ppassqquitq11q11q02

(210)不合法p11(000)(330)達不到MC問題狀態(tài)空間圖ppassq11q11q0277二、與/或樹（圖）表示法1、分解：大問題分解為若干個易解子問題，子問題解決了，大問題也就解決了。ABC或圖ABCD與圖2、變換：大問題變成若干個易解子問題，只要有一個子問題解決了，大問題也就解決了。二、與/或樹（圖）表示法1、分解：大問題分解為若干個易解子問78一些關(guān)于與或圖的術(shù)語HMBCDEFGAN父節(jié)點與節(jié)點弧線或節(jié)點子節(jié)點端節(jié)點一些關(guān)于與或圖的術(shù)語HMBCDEFGAN父節(jié)點與節(jié)點弧線或節(jié)79基本概念本原問題：不能再分解或變換，而且直接可解的子問題。終止節(jié)點：不能分解或變換，可直接求解可解節(jié)點：終止節(jié)點“或”節(jié)點，其子節(jié)點至少有一個是可解節(jié)點“與”節(jié)點，其子節(jié)點均為可解節(jié)點不可解節(jié)點：可解節(jié)點的三個條件都不滿足的節(jié)點解樹：由可解節(jié)點構(gòu)成，并可推出初始節(jié)點為可解節(jié)點的子樹基本概念本原問題：不能再分解或變換，而且直接可解的子問題。80梵塔問題可以分解為三個子問題：(1)最大盤以上由1至2(2)最大盤由1至3(3)其余盤由2至3問題的形式化表示：三元組(I,j,k)I---C所在鋼針號j----B所在鋼針號k---A所在鋼針號問題：（1，1，1）（3，3，3）ABC123ABC123梵塔問題可以分解為三個子問題：ABC123ABC12381三階梵塔問題的與/或樹（113）（123）

（111）（113）

（123）（122）

（111）（333）

（122）（322）

（111）（122）

（322）（333）

（321）（331）

（322）（321）

（331）（333）

三階梵塔問題的與/或樹（113）（123）（11182三、搜索根據(jù)問題的實際情況不斷尋找可利用的知識，從而構(gòu)造一條代價較少的推理路線，使問題得到圓滿解決的過程。類型：1、問題表示方式：狀態(tài)空間搜索與/或樹搜索2、是否使用啟發(fā)式信息盲目搜索：按預(yù)定的控制策略進行搜索，在搜索過程中獲得的中間結(jié)果不用來改進控制策略。啟發(fā)式搜索：搜索過程中加入與問題有關(guān)的啟發(fā)性信息。（動態(tài)地確定操作規(guī)則排序）三、搜索根據(jù)問題的實際情況不斷尋找可利用的知識，從而構(gòu)造一條835.2狀態(tài)空間的搜索策略基本思想：初態(tài)作為當(dāng)前節(jié)點進行擴展生成子節(jié)點，檢查目標(biāo)狀態(tài)是否出現(xiàn)，不出現(xiàn)則按策略選一個子節(jié)點進行擴展直到目標(biāo)狀態(tài)出現(xiàn)或沒有可供擴展的子節(jié)點。一、一般的圖搜索過程：OPEN表：存放尚未被擴展的節(jié)點CLOSED表：存放已被擴展的節(jié)點5.2狀態(tài)空間的搜索策略基本思想：84圖搜索算法：1.把初始節(jié)點S放入OPEN表，建立一個僅包含S的圖G（搜索圖）2.如果OPEN表空，則以失敗退出。3.把OPEN表中的第一個節(jié)點取出放入CLOSED表，稱此節(jié)點為n.4.如果n是目標(biāo)節(jié)點，則成功地結(jié)束，解路徑可通過回溯G中從n到S的指針獲得。5.擴展節(jié)點n，產(chǎn)生一組子節(jié)點。把不是n的祖先的那些子節(jié)點記作集合M，把M的這些成員作為n的后繼節(jié)點加入G中。6.對于M的那些未曾在G中出現(xiàn)的成員，建立到n的指針，并把這些成員加到OPEN表中。對于那些已在G中出現(xiàn)的成員，決定是否要修改它指向父節(jié)點的指針。對于那些已在G中出現(xiàn)且已擴展的成員，決定是否要修改其后繼節(jié)點指向父節(jié)點的指針。7.按某種搜索策略重排OPEN表中的節(jié)點8.轉(zhuǎn)第2步圖搜索算法：1.把初始節(jié)點S放入OPEN表，建立一個僅包含S85圖搜索的一般過程開始把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點嗎？擴展節(jié)點n，將其子節(jié)點處理后放入OPEN表，為每個子節(jié)點配置指向節(jié)點n的指針重排OPEN表失敗成功是是否否節(jié)點n可擴展嗎？否是圖搜索的一般過程開始把S放入OPEN表OPEN表為空表？把第86說明：這個一般的圖搜索過程，通過不斷循環(huán)生成一個顯式表示的圖G（搜索圖）和一個G的子集T（搜索樹）樹T是由（6）中標(biāo)記的指針決定的，除根節(jié)點s外，G中每個節(jié)點只有一個指針指向G中的一個父節(jié)點OPEN表中的節(jié)點（未擴展節(jié)點）是搜索樹的端節(jié)點，即尚未被選作為擴展的節(jié)點；CLOSED表中的節(jié)點（已擴展節(jié)點），可以是已被擴展而不能生成后繼節(jié)點的那些端節(jié)點，也可以是樹中的非端節(jié)點（7）中對OPEN表上的節(jié)點進行排序是為了在（3）中能選出一個“最好”的節(jié)點優(yōu)先擴展，不同的排序方法可構(gòu)成形式多樣的專門搜索算法如果隱含圖是一棵樹，不會（6）中討論的特殊節(jié)點，否則可能這些節(jié)點***上述算法的關(guān)鍵一步是（7），對OPEN表的排序，即決定節(jié)點的擴展順序，典型的有兩種節(jié)點擴展順序，得到兩種搜索算法（廣度優(yōu)先搜索、深度優(yōu)先搜索）說明：87二、寬度優(yōu)先（廣度優(yōu)先）基本思想是：從節(jié)點S0開始，逐層地對節(jié)點進行擴展，并考察它是否為目標(biāo)節(jié)點，在第n層節(jié)點沒有全部考察完之前，不對第n+1層的節(jié)點進行擴展。OPEN表：按“先進先出”排特點：一種高代價搜索，但若有解存在，則必能找到它。二、寬度優(yōu)先（廣度優(yōu)先）基本思想是：88例子

八數(shù)碼難題（8-puzzleproblem）

1238456712384567（目標(biāo)狀態(tài)）（初始狀態(tài)）規(guī)定：將牌移入空格的順序為：從空格左邊開始順時針旋轉(zhuǎn)。不許斜向移動，也不返回先輩節(jié)點。從圖可見，要擴展26個節(jié)點，共生成46個節(jié)點之后才求得解（目標(biāo)節(jié)點）。例子

八數(shù)碼難題（8-puzzleproblem）12891238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345圖八數(shù)碼難題的寬度優(yōu)先搜索樹1345612384567123845671238456712384567123845672324252627123678221238456712384567123845671238456712384567123845671238456714151617181920211238456712384567123841238456741238567190三、深度優(yōu)先搜索首先擴展最新產(chǎn)生的(即最深的)節(jié)點。深度相等的節(jié)點可以任意排列。與寬度優(yōu)先搜索算法最根本的不同在于：將擴展的后繼節(jié)點放在OPEN表的前端。（先進后出）三、深度優(yōu)先搜索首先擴展最新產(chǎn)生的(即最深的)節(jié)點。深度相等91問題不一定能找到解

找到的解不一定是最佳解

為了對深度優(yōu)先搜索作改進,要解決兩個問題：①回溯問題;②有圈造成死循環(huán)問題。

問題不一定能找到解為了對深度優(yōu)先搜索作改進,要解決兩個問92四、有界深度優(yōu)先搜索如果問題有解且路徑長度≤dm,則一定可求得解；否則得不到解。問題：dm不易確定這種方法不一定能找到解路徑（如果解路徑的深度超出了限制深度）另外它得到的解也不一定是最優(yōu)解改進先定一個較小的dm，若未找到解且closed中有待擴展的節(jié)點，就將其送回open表。不斷改進dm。最優(yōu)解：增設(shè)一表R，每找到一個解就將其放入R的前面。最后求得的解一定最優(yōu)四、有界深度優(yōu)先搜索如果問題有解且路徑長度≤dm,則一定可求93五、代價樹的廣度優(yōu)先搜索—分枝界限法有些問題并不要求有應(yīng)用算符序列為最少的解，而是要求具有某些特性的解。搜索樹中每條連接弧線上的有關(guān)代價以及隨之而求得的具有最小代價的解答路徑。代價樹：各邊標(biāo)有代價值的樹----一種加權(quán)樹代價計算g(x)-------sx代價g(x2)=g(x1)+c(x1,x2)基本思想：OPEN表中的全部節(jié)點按代價從小到大排五、代價樹的廣度優(yōu)先搜索—分枝界限法有些問題并不要求有應(yīng)用算94代價樹的廣度優(yōu)先搜索開始把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點嗎？擴展節(jié)點n，將其子節(jié)點處理后放入OPEN表，為每個子節(jié)點配置指向節(jié)點n的指針，計算各節(jié)點代價。把OPEN表中的全部節(jié)點按代價從小到大排失敗成功是是否否節(jié)點n可擴展嗎？否是代價樹的廣度優(yōu)先搜索開始把S放入OPEN表OPEN表為空表？95例下圖是一個交通圖，設(shè)A城市是出發(fā)地，E城市是目的地，邊上的數(shù)字代表兩城市之間的交通費。試求從A到E最小費用的旅行路線。Ac1d1e28例下圖是一個交通圖，設(shè)A城市是出發(fā)地，E城市是目的地，邊上的96六、代價樹的深度優(yōu)先搜索---爬山法基本思想：將擴展的后繼節(jié)點按邊代價從小到大的順序放在OPEN表的前端。代價樹的廣度優(yōu)先搜索法是完備的且找到的解一定是最優(yōu)解代價樹的深度優(yōu)先搜索法是不完備的且找到的解不一定是最優(yōu)解六、代價樹的深度優(yōu)先搜索---爬山法基本思想：將擴展的后繼節(jié)97七、啟發(fā)式搜索問題提出：從理論上講窮舉式搜索能解決任何狀態(tài)空間問題，但很顯然窮舉搜索只能解決狀態(tài)空間很小的簡單問題，對于復(fù)雜問題會出現(xiàn)“組合爆炸”n階Hanoi塔問題的狀態(tài)空間圖中有2的n次方減1個結(jié)點；博弈問題中，為了取勝可以將所有的算法都試一下，然后選擇最佳走步。就所有可能的棋局數(shù)來講，一字棋是9！=3.6*10^9，國際象棋是10^120，圍棋是10^761。假設(shè)每步可以選擇一種棋局，用極限并行速度（10^-104秒/步）計算，國際象棋的算法得用10^16年即1億億年才可以算完。解決：利用問題的啟發(fā)性信息來引導(dǎo)搜索減少搜索范圍降低問題復(fù)雜度啟發(fā)信息：進行搜索技術(shù)一般需要某些有關(guān)具體問題領(lǐng)域的特性的信息，把此種信息叫做啟發(fā)信息。把利用啟發(fā)信息的搜索方法叫做啟發(fā)性搜索方法。七、啟發(fā)式搜索問題提出：98啟發(fā)性信息類型1）用于擴展節(jié)點的選擇即決定下一個擴展節(jié)點,以免象在廣度優(yōu)先和深度優(yōu)先搜索中那樣盲目地擴展2）用于生成節(jié)點的選擇即用于決定生成哪個或哪幾個后繼節(jié)點,而不是生成所有的節(jié)點3）用于刪除節(jié)點的選擇即決定用于從搜索樹中拋棄或修剪的節(jié)點我們討論的主要是基于“擴展節(jié)點的選擇”的啟發(fā)式搜索，這種搜索總是選擇“最有希望”的節(jié)點作為下一個被擴展的節(jié)點。這種搜索叫做有序搜索(orderedsearch)。1、估價函數(shù)------評估節(jié)點的方法用來估算節(jié)點希望程度的量度，叫做估價函數(shù)啟發(fā)性信息類型1）用于擴展節(jié)點的選擇99f(x)=g(x)+h(x)

其中:f(x):從初始節(jié)點S0到目標(biāo)節(jié)點Sg的最優(yōu)路徑的代價估計值①g(x)為從初始節(jié)點S0到節(jié)點x的實際代價值。

②h(x)為啟發(fā)函數(shù),是從節(jié)點x到目標(biāo)節(jié)點Sg的最優(yōu)路徑的代價h*(n)的估計值。g(x)、h(x)作用分析一般地,在f(n)中,g(n)的比重越大,越傾向于寬度優(yōu)先搜索方式;h(n)的比重越大,越傾向于深度優(yōu)先搜索方式。保持g(n)項就保持了搜索的寬度優(yōu)先趨勢,這有利于搜索的完備性,但影響搜索的效率。在特殊情況下,如果只希望找到達到目標(biāo)結(jié)點的路徑而不關(guān)心已付出的代價,則g(n)的作用可以忽略。h(n)>>g(n)時,也可以忽略g(n),這時有f(n)=h(n),這有利于搜索的效率,但影響搜索的完備性。f(x)=g(x)+h(x)

其中:100定義h（x）的原則：節(jié)點x處在最佳路徑上的摡率節(jié)點x與目標(biāo)節(jié)點集之間的距離度量或差異度量根據(jù)格局或狀態(tài)的特點來打分一般來說,評價一個結(jié)點的價值,必須綜合考慮兩方面的因素:已經(jīng)付出的代價和將要付出的代價。啟發(fā)式算法通常由兩部分組成:啟發(fā)方法使用該方法搜索狀態(tài)空間的算法。啟發(fā)式搜索基本思想：以一般的圖搜索算法為基礎(chǔ)定義啟發(fā)函數(shù)h（x）計算每個待擴展節(jié)點的啟發(fā)函數(shù)值每次擴展節(jié)點后以節(jié)點的啟發(fā)函數(shù)值為依據(jù)對待擴展節(jié)點排序?qū)嵸|(zhì)：選擇OPEN表上具有最小f值的節(jié)點作為下一個要擴展的節(jié)點。定義h（x）的原則：101開始把S放入OPEN表，計算估價函數(shù)f(s)OPEN表為空表？選取OPEN表中f值最小的節(jié)點i放入CLOSED表i為目標(biāo)節(jié)點嗎？擴展i，得后繼節(jié)點j，計算f(j)，提供返回節(jié)點i的指針，利用f(j)對OPEN表重新排序，調(diào)整親子關(guān)系及指針失敗成功圖

有序搜索算法框圖是否是否算法開始把S放入OPEN表，計算估價函數(shù)f(s)OPEN表為102例：八數(shù)碼難題（8-puzzleproblem）f(n)=h(n)+g(n)=w(n)+d(n)

h(n)=w(n),w(n)是將牌不在位個數(shù),例如,與目標(biāo)狀態(tài)相比,初始狀態(tài)w(n)=4,即有4個將牌(1,2,6,8)不在位。g(n)=d(n),d(n)是搜索的深度。一般根節(jié)點(初始狀態(tài))的深度是為0,其他子節(jié)點深度為父結(jié)點深度加1。

規(guī)定規(guī)則為空格移動(走步規(guī)則),規(guī)則選取順序為:左、上、右、下?？刂撇呗詾?選取評價函數(shù)值最小者進行擴展(往下搜索)。12384567（目標(biāo)狀態(tài)）12384567（初始狀態(tài)）例：八數(shù)碼難題（8-puzzleproblem）f(n)1035714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712384567（5）（7）1238456712384567（6）（7）12384567（5）8132456712384567（5）（7）圖八數(shù)碼難題的有序搜索樹123846（4）7571456312384567123845671238456104人工智能第五章105A算法利用評價函數(shù)f(n)=g(n)+h(n)來排列OPEN表節(jié)點順序的圖搜索算法稱為A算法。實現(xiàn)類型：局部擇優(yōu)搜索、全局擇優(yōu)搜索2、局部擇優(yōu)搜索----類似深度優(yōu)先基本思想：在當(dāng)前擴展的子節(jié)點中選f(x)值最小的子節(jié)點為下一個考察的節(jié)點實現(xiàn)：節(jié)點n擴展后的各子節(jié)點計算出估價值后，按由小到大次序放到OPEN表的首部分析：可把深度優(yōu)先、代價樹的深度優(yōu)先看成其特例。3、全局擇優(yōu)搜索----類似廣度優(yōu)先節(jié)點n擴展后的各子節(jié)點計算出估價值后，送入OPEN表，然后OPEN表中全部節(jié)點按估價值由小到大排A算法利用評價函數(shù)f(n)=g(n)+h(n)來排1064、A*算法(AlgorithmA*)幾個有用的記號f（x）=g（x）+h（x）f*(x)=g*（x）+h*（x）g*（x）：從節(jié)點S到節(jié)點x的一條最佳路徑的實際代價h*（x）：從節(jié)點x到某目標(biāo)節(jié)點的一條最佳路徑的代價f*(x)：從S開始約束通過節(jié)點x的一條最佳路徑的代價分析：g是g*（x）的估計；對于g（n）來說，一個明顯的選擇就是搜索樹中從Ｓ到n這段路徑的代價，這一代價可以由從n到Ｓ尋找指針時，把所遇到的各段弧線的代價加起來給出（這條路徑就是到目前為止用搜索算法找到的從S到n的最小代價路徑)。這個定義包含了g（x）≥g*（x）。h是h*（x）的估計；對于h（n），它依賴于有關(guān)問題的領(lǐng)域的啟發(fā)信息。4、A*算法(AlgorithmA*)幾個有用的記號107A*算法---又稱最佳圖搜索算法，由著名人工智能學(xué)者Nilsson提出。定義：如果A算法中使用的啟發(fā)函數(shù)h(n)對任何節(jié)點n都有h(n)≤h*(n)，則稱其為A*算法(AlgorithmA*)。對于寬度優(yōu)先搜索算法，h(n)=0，滿足h(n)≤h*(n)。寬度優(yōu)先算法是A*算法的特殊情形。A*算法的性質(zhì)：（1）可采納性如果一個搜索算法對于任何具有解路徑的圖都能找到一條最佳解路徑。則稱此算法是可采納的。結(jié)論：A*算法是可采納的證明：對有限圖，A*算法一定會在有限步結(jié)束對無限圖，只有從S0到Sg有路徑存在，則A*算法也必然會結(jié)束A*算法一定會終止在最優(yōu)路徑上A*算法---又稱最佳圖搜索算法，由著名人工智能學(xué)者Nils108a)對有限圖，A*算法一定會在有限步結(jié)束證明：因為搜索圖為有限圖，所以會出現(xiàn)以下情況：算法找到解，則成功結(jié)束（算法第4步）算法找不到解，則必然會因OPEN表變空而結(jié)束（算法第2步）b)對無限圖，只有從S0到Sg有路徑存在，則A*算法也必然會結(jié)束證明：（分2步）第1步證明：A*結(jié)束前,OPEN表中必存在節(jié)點n，它是最佳路徑上的一個節(jié)點，且滿足

f(n)<=f*(s)證明:設(shè)從初始節(jié)點s到目標(biāo)節(jié)點t的一條最佳路徑序列為

(n0=s,n1,…,nk=t)a)對有限圖，A*算法一定會在有限步結(jié)束證明：因為搜索圖為109算法初始化時,s在OPEN中,由于A*沒有結(jié)束,在OPEN中存在最佳路徑上的節(jié)點。設(shè)OPEN表中的第一個節(jié)點n是處在最佳路徑序列中(至少有一個這樣的節(jié)點,因s一開始是在OPEN上),顯然n的先輩節(jié)點np,已在CLOSED中,因此能找到s到np,的最佳路徑