第三章產生式系統的搜索策略狀態空間：由給定問題的所有可能的狀態組成的空間（相當于全集G）搜索空間：按某種策略在狀態空間中選取的部分空間（G的子集）解路徑（解空間）：求解問題的一條有效路徑。搜索策略的基本思路：搜索空間必須包含解路徑，如果問題有解，且盡量縮小搜索空間。搜索策略的評價準則：總體費用最低2/3/20231費用的劃分：

a規則應用的費用：執行規則時所花的費用

b控制費用：選擇規則所花的費用。2/3/20232第三章目錄3.1回溯策略3.2圖搜索策略3.3啟發式圖搜索策略

1）A算法

2）爬山算法

3）分支界限算法

4）動態規劃算法

5）A*算法2/3/20233

6）h函數與A*的關系

7）關于單調性限制

8）A*算法示例2/3/202343.1回溯算法2/3/202352/3/20236例四皇后問題2/3/20237定義綜合數據庫：設：DATA={ij︱1<=i,j<=4},其中：ij表示棋子所在行列如：24表示第二行第四列有一枚棋子因為棋盤上可放入的棋子數為0～4個所以集合中元素數位0～4個，即length（DATA）=0～42/3/202382/3/202392/3/2023102/3/2023112/3/2023122/3/2023132/3/2023143.2圖搜索策略2/3/202315圖搜索策略圖搜索的實質是從問題空間中找出一張包含目標節點的子圖。圖搜索的結果：1，一個完整的搜索圖G。2一個解路徑，用指針表示的解路徑。ProcedureGraphSearch1G=G0(G0=s),open=(s)//s:初始狀態2closed=()3Loop:ifopen=()thenexit(fall)4n←first(open)remove(n,open),add(n,closed)5ifgoal(n)thenexit(success)6{mj}←expand(n),//mj不含n的先輩節點7open←add(open，mj)//mj不在open，closed中2/3/202316標記mj每個到n節點指針確定是否需要修改已在open，closed中的每個節點到n的指針確定是否需要修改已在closed中的每個節點的后繼節點原來的指針。8按照某種方式排列open表中的節點，goloop2/3/2023172/3/2023182/3/202319深度優先算法Procedruedepth-First-Search1G=G0(G0=s),open=(s),closed=()//s:初始狀態2Loop:ifopen=()thenexit(fall)3n←first(open)4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先輩節點7open←add(open，mj)//mj不在open，closed中標記mj每個到n節點指針，按照節點深度遞減順序排列open中的節點

8goloop2/3/202320討論1：如果問題有解，有深度優先搜索算法，是否能夠找到解？不一定.解空間是否有限？討論2：本算法的改進之處是open中節點按照深度優先排列，但是沒有對深度加以控制，可能造成搜索代價太大2/3/202321寬度優先算法Procedruebreadth-First-Search1G=G0(G0=s),open=(s),closed=()//s:初始狀態2Loop:ifopen=()thenexit(fall)3n←first(open)4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先輩節點7open←add(open，mj)//mj不在open，closed中2/3/202322

標記每個到n節點指針，按照節點深度遞增順序排列open中的節點

8goloop

理論上可以利用寬度優先搜索能夠找到解，如果問題有解的話。討論：寬度優先算法和深度優先算法可能出現組合爆炸。都沒有利用任何啟發式信息，所以稱為無信息搜索策略。2/3/202323：寬度優先例題：由一張桌子T、三個積木A、B、C組成一個積木世界，初始狀態是A在B上，B在桌子上，C在桌子上；目標狀態是：A、B、C依次從上到下排列在桌子上。如圖2/3/202324解：1）狀態描述（P1，P2，P3）表示按A、B、C順序依次分別在P1,P2,P3上其中Pi是積木或者桌子。初始狀態時（B、T、T）,目標狀態可以表示（B、C、T）2）定義操作:move(x,y)表示將積木x移到Y上；約束條件:aX頂部必須是空的b如果Y是積木，Y的頂部必須是空的

c同一種狀態出現不得多于一次。2/3/2023251）解題過程2）open表和closed表3）節點樣子畫出整個圖G和解路徑4）程序何時結束5）改用深度優先如何？2/3/2023263.3啟發式圖搜索策略基本概念啟發式圖搜索的實質是利用啟發信息有目的地進行搜索，減少搜索的盲目性。降低搜索空間找到最佳解啟發式信息用于解決open表中節點的排列次序問題，方法是利用一個評價函數計算open表中節點的評價函數值，按照函數值從小到大排列所有節點。2/3/202327評價函數的目的：把最有希望得到最佳解或者解的排列在前面。路徑：給定節點序列（n0，n1，…nk）。如果該序列中的任一節點ni-1都有后繼節點ni，則該節點序列為從n0到nk的一條路徑，路徑長度為K路徑耗散值：路徑耗散值等于該路徑上所有相鄰節點間耗散值的總和。2/3/202328設：路徑山任兩點間的耗散值為才C(ni,nj),則從ni到nk的路徑耗散值為C(ni,nj)=C(ni,nj)+C(nj,nk)最佳路徑耗散值：最佳路徑上的實際耗散值，記為：K(ni,nj).K(ni,nj)<=C(ni,nj)2/3/202329定義幾個函數1）g*(n)=k(s,n):從初始節點s到當前節點n的最佳路徑的耗散值。2)h*(n)=k(n,t):從當前節點n到目標節點t的最佳路徑的好三者。3)f*(n)=g*(n)+h*(n):從初始節點s通過當前節點n到目標節點t的最佳路徑的耗散值。2/3/2023304)評價函數：f(n)=g(n)+h(n),其中f，g，h分別是f*，g*，h*的估計值。通常約定:f(n)按照升序排列。討論：有上述定義，得:1)g(n)>=g*(n)2)當h=0且g(n)=d(n)時，f(n)=d(n)既寬度優先策略，d(n):節點深度。

3）h(n)稱為啟發函數。2/3/2023313.1.1A算法1G=G0(G0=s),open=(s),closed=()，f(s)=g(s)+h(s)//s:初始狀態2Loop:ifopen=()thenexit(fall)3n←first(open)h()4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先輩節點

計算f(n,mi)=g(n,mi)+h(mi),(自s經過n，mi到目標節點的耗散值)2/3/202332open←add(open，mj)標記mj到n的指針(mj不在open，closed中)iff(n,mk)<f(mk)thenf(mk)←f(n,mk)標記mk到n的指針(mk在open中)iff(n,mL)<f(mL)thenf(mL)←f(n,mL)標記mL到n的指針(mL在closed中)

add(mL,open),把mL放回到open中7Open中的節點按f值升序排列

8goloop2/3/2023332/3/202334例八數碼問題令：g(n)=d(n)節點深度

h(n)=w(n)不在位的數碼個數(啟發函數)則f(n)=d(n)+w(n)如初始節點s的f值f(0)=d(0)+w(0)=0+4=4有4個數碼不在位。2/3/2023352/3/202336對于f(n)=g(n)+h(n),如果單獨考慮g(n)或者h(n),即，

1)f(n)=g(n)只考慮搜索過的路徑已經耗費的費用；//分支界限算法

2）f(n)=h(n)只考慮未來的發展趨勢//爬山算法那么可以得到兩種特殊的算法：爬山算法和分支界限算法。2/3/2023373.3.2爬山算法ProcedureHill_Climbing1n=s2Loop:ifgoal(n)thenexit(success)3{mi}←expangd(n),計算每個h(mi)

nextn←h(mi)最小值的節點4ifh(n)<h(nextn)thenexit(fail)5n←nextn6goloop優點，缺點2/3/2023383.3.3分支界限算法f(n)=g(n)ProcedureBranch_Bound1queue(s-s),g(s)=0//queue中保存的是從s出發的路徑。2Loop：ifqueue=0thenexit（fail）3path←FIRST(queue)，n←LAST(pATH)//取第一條路徑，及該路徑的最后節點n4ifgoal(n)thenexit(success)5{mj}←expand(n),計算g(mj)=g(n,mj)

remove(s-n,queue),add(s-mj,queue)//刪除原來的路徑，添加長度加一的路徑。2/3/2023396queue隊列中分支按g值升序排列7GOLOOP例下圖右八城市，城市間的耗散值已經給出，利用分支界限算法給出從S到t的最佳路徑。2/3/2023402/3/2023413.3.4動態規劃算法Proceduredynamic_Programming1queue(s-s),g(s)=0//queue中保存的是從s出發的路徑。2Loop：ifqueue=0thenexit（fail）3path←FIRST(queue)，n←LAST(pATH)//取第一條路徑，及該路徑的最后節點n4ifgoal(n)thenexit(success)5{mj}←expand(n),計算g(mj)=g(n,mj)

remove(s-n,queue),add(s-mj,queue)2/3/202342

//刪除原來的路徑，添加長度加一的路徑。6僅保留queue中到達某一公共節點路徑中耗散值最小的路徑，余者刪除；queue隊列中分支按g值升序排列7GOLOOP2/3/2023432/3/202344討論a動態規劃與分支界限差別在于去掉公共路徑的冗余部分，提高效率。

b如果問題空間是樹結構，動態規劃與分支界限相同。因為對于樹結構不存在到達同一節點有多重路徑的情況。C動態規劃改進的代價。比如上例中，增加一個城市。2/3/202345A算法總結1初始狀態，open=（s）2正常情況下（非成功非失敗），取open中的第一個節點n，將n由open轉移到closed。3擴充節點n，將新節點加入到open中4修改某些節點的路徑5open中節點按照升序排列值得重視的一點：A算法失敗的唯一原因是open表為空2/3/202346思考題：圖中：s是起始點t是目標節點；如果存在從s到t的一條最佳路徑。而n是最佳路徑上的一點。1）f*(s)f*(n)f*(t)的關系2）如果f*(s)=10,g*(n)=4問h*(n)=?2/3/2023473.3.5A*算法（最佳圖搜索算法）A*算法定義：

對于算法A，如果有h（n）≤

h*（n）,即h（n）以h*（n）為上界，則稱該算法稱為A*算法。如果令h（n）=0，則滿足h（n）≤

h*（n）

這就是分支界限算法和動態規劃算法。再令g(n)=d(n)(d(n)是節點深度）則f(n)=d(n);A*算法就是寬度優先算法。寬度優先算法能找到最佳解。例：第二章中八數碼問題令h(n)=w(n)=不在位數字個數。2/3/202348算法可采納性：給定任意圖，設存在從開始節點s到目標節點t的路徑。如果算法能夠結束在s到t的最佳路徑上，則稱該算法是可采納的。A*是具有可采納性。定理1

對于有限圖，如果從s到t存在路徑，則A算法一定成功結束。2/3/202349推論1.1

因為A*算法是A算法的一個特例。所以在有限圖上如果如果從s到t存在路徑，則A*算法一定成功結束。定理2

對于無限圖，如果存在s到t路徑，則A*算法一定成功結束。2/3/202350推論2.1open表中任一滿足f(n)≦f*(s)的節點n最終都將被A*選作擴展節點。定理3

如果存在節點s到目標節點t路徑，則A*算法一定能找到最佳解結束。推論3.1A*選來擴展的節點都有f(n)≦f*(s)2/3/202351小結

1如果存在節點s到目標節點t路徑，則A*算法一定能找到最佳解結束。

2open表中所有滿足f(n)≦f*(s)的節點n最終都將被A*選作擴展節點。

3A*選來擴展的節點都有f(n)≦f*(s)4f*(s)作為A*的一個衡量上限。2/3/2023523.3.6h函數和A*算法的關系本節重點來討論h函數（即啟發信息量）對A*算法搜索效率的影響總結。定義：給定兩個A*算法A1

和A2，都有

f(n1)=g(n1)+h(n1)f(n2)=g(n2)+h(n2)

如果對于所有非目標節點n，有h(n1)<h(n2)

則算法A2比算法A1有較多啟發信息。討論：啟發信息與h函數值成正比。極端情況下，完全沒有啟發信息時h=0，則此時A*算法就是寬度優先算法。2/3/202353定理：給定兩個A*算法A1

和A2如果A2的啟發式信息比A1多，則在任何存在節點s到目標節點t的路徑上，搜索結束時，由A2擴展的每一個節點必定被A1擴展。(A1擴展的節點多)

注意搜索空間小，不代表能夠找到最佳解。2/3/202354當h=0時，除最下面一層節點外，所有節點都進入closed表。求解路徑如圖紅線所示。當考慮到h時，被擴充的節點只有s、c、j，解路徑相同2/3/2023553.37h函數單調性限制單調性限制的作用是：避免重復計算某些節點的f值（主要對連通圖而言）以便減少搜索代價。單調性定義：給定一個啟發函數h，如果對于所有節點ni和nj(nj是ni的子節點)，如果滿足h(ni)-h(nj)≤c(ni,nj)h(t)=0,則稱h滿足單調性限制。

上式可以寫成h(ni)-≤h(nj)+c(ni,nj)可以理解為三角不等式。

2/3/202356定理5

如果好h(n)滿足單調性限制條件，則A*算法擴展了節點n之后，就找到了到達節點n的最佳路徑，即：如果A*選中節點n，在單調性限制條件下，有g(n)=g*(n)2/3/2023573.38A*算法示例迷宮問題給定迷宮圖如下，找出從入口到出口的最短路徑。2/3/202358解1）綜合數據庫定義狀態集：{（x，y）∣1≤x，y≤4}

其中（x，y）表示任意節點的坐標所以問題表示為求解從（1,1）到（4,4）的最短路徑。2規則集（定義4條移動規則）右移R1：if（x，y）then（x+1，y）左移R2：if（x，y）then（x-1，y）2/3/202359上移R3：if（x，y）then（x+1，y+1）下移R4：if（x，y）then（x+1，y-1）兩種解法：寬度優先，設定h(n)2/3/2023602/3/2023613）A*算法f函數定義f(n)=g(n)