ch3產(chǎn)生式系統(tǒng)的搜索策略

第三章產(chǎn)生式系統(tǒng)的搜索策略狀態(tài)空間：由給定問題的所有可能的狀態(tài)組成的空間（相當(dāng)于全集G）搜索空間：按某種策略在狀態(tài)空間中選取的部分空間（G的子集）解路徑（解空間）：求解問題的一條有效路徑。搜索策略的基本思路：搜索空間必須包含解路徑，如果問題有解，且盡量縮小搜索空間。搜索策略的評價準(zhǔn)則：總體費用最低9/16/20231費用的劃分：a規(guī)則應(yīng)用的費用：執(zhí)行規(guī)則時所花的費用b控制費用：選擇規(guī)則所花的費用。9/16/20232第三章目錄3.1回溯策略3.2圖搜索策略3.3啟發(fā)式圖搜索策略1）A算法2）爬山算法3）分支界限算法4）動態(tài)規(guī)劃算法5）A*算法9/16/202336）h函數(shù)與A*的關(guān)系7）關(guān)于單調(diào)性限制8）A*算法示例9/16/202343.1回溯算法9/16/202359/16/20236例四皇后問題9/16/20237定義綜合數(shù)據(jù)庫：設(shè)：DATA={ij︱1<=i,j<=4},其中：ij表示棋子所在行列如：24表示第二行第四列有一枚棋子因為棋盤上可放入的棋子數(shù)為0～4個所以集合中元素數(shù)位0～4個，即length（DATA）=0～49/16/202389/16/202399/16/2023109/16/2023119/16/2023129/16/2023139/16/2023143.2圖搜索策略9/16/202315圖搜索策略圖搜索的實質(zhì)是從問題空間中找出一張包含目標(biāo)節(jié)點的子圖。圖搜索的結(jié)果：1，一個完整的搜索圖G。2一個解路徑，用指針表示的解路徑。ProcedureGraphSearch1G=G0(G0=s),open=(s)//s:初始狀態(tài)2closed=()3Loop:ifopen=()thenexit(fall)4n←first(open)remove(n,open),add(n,closed)5ifgoal(n)thenexit(success)6{mj}←expand(n),//mj不含n的先輩節(jié)點7open←add(open，mj)//mj不在open，closed中9/16/202316標(biāo)記mj每個到n節(jié)點指針確定是否需要修改已在open，closed中的每個節(jié)點到n的指針確定是否需要修改已在closed中的每個節(jié)點的后繼節(jié)點原來的指針。8按照某種方式排列open表中的節(jié)點，goloop9/16/2023179/16/2023189/16/202319深度優(yōu)先算法Procedruedepth-First-Search1G=G0(G0=s),open=(s),closed=()//s:初始狀態(tài)2Loop:ifopen=()thenexit(fall)3n←first(open)4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先輩節(jié)點7open←add(open，mj)//mj不在open，closed中標(biāo)記mj每個到n節(jié)點指針，按照節(jié)點深度遞減順序排列open中的節(jié)點8goloop9/16/202320討論1：如果問題有解，有深度優(yōu)先搜索算法，是否能夠找到解？不一定.解空間是否有限？討論2：本算法的改進之處是open中節(jié)點按照深度優(yōu)先排列，但是沒有對深度加以控制，可能造成搜索代價太大9/16/202321寬度優(yōu)先算法Procedruebreadth-First-Search1G=G0(G0=s),open=(s),closed=()//s:初始狀態(tài)2Loop:ifopen=()thenexit(fall)3n←first(open)4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先輩節(jié)點7open←add(open，mj)//mj不在open，closed中9/16/202322

標(biāo)記每個到n節(jié)點指針，按照節(jié)點深度遞增順序排列open中的節(jié)點8goloop理論上可以利用寬度優(yōu)先搜索能夠找到解，如果問題有解的話。討論：寬度優(yōu)先算法和深度優(yōu)先算法可能出現(xiàn)組合爆炸。都沒有利用任何啟發(fā)式信息，所以稱為無信息搜索策略。9/16/202323：寬度優(yōu)先例題：由一張桌子T、三個積木A、B、C組成一個積木世界，初始狀態(tài)是A在B上，B在桌子上，C在桌子上；目標(biāo)狀態(tài)是：A、B、C依次從上到下排列在桌子上。如圖9/16/202324解：1）狀態(tài)描述（P1，P2，P3）表示按A、B、C順序依次分別在P1,P2,P3上其中Pi是積木或者桌子。初始狀態(tài)時（B、T、T）,目標(biāo)狀態(tài)可以表示（B、C、T）2）定義操作:move(x,y)表示將積木x移到Y(jié)上；約束條件:aX頂部必須是空的b如果Y是積木，Y的頂部必須是空的c同一種狀態(tài)出現(xiàn)不得多于一次。9/16/2023251）解題過程2）open表和closed表3）節(jié)點樣子畫出整個圖G和解路徑4）程序何時結(jié)束5）改用深度優(yōu)先如何？9/16/2023263.3啟發(fā)式圖搜索策略基本概念啟發(fā)式圖搜索的實質(zhì)是利用啟發(fā)信息有目的地進行搜索，減少搜索的盲目性。降低搜索空間找到最佳解啟發(fā)式信息用于解決open表中節(jié)點的排列次序問題，方法是利用一個評價函數(shù)計算open表中節(jié)點的評價函數(shù)值，按照函數(shù)值從小到大排列所有節(jié)點。9/16/202327評價函數(shù)的目的：把最有希望得到最佳解或者解的排列在前面。路徑：給定節(jié)點序列（n0，n1，…nk）。如果該序列中的任一節(jié)點ni-1都有后繼節(jié)點ni，則該節(jié)點序列為從n0到nk的一條路徑，路徑長度為K路徑耗散值：路徑耗散值等于該路徑上所有相鄰節(jié)點間耗散值的總和。9/16/202328設(shè)：路徑山任兩點間的耗散值為才C(ni,nj),則從ni到nk的路徑耗散值為C(ni,nj)=C(ni,nj)+C(nj,nk)最佳路徑耗散值：最佳路徑上的實際耗散值，記為：K(ni,nj).K(ni,nj)<=C(ni,nj)9/16/202329定義幾個函數(shù)1）g*(n)=k(s,n):從初始節(jié)點s到當(dāng)前節(jié)點n的最佳路徑的耗散值。2)h*(n)=k(n,t):從當(dāng)前節(jié)點n到目標(biāo)節(jié)點t的最佳路徑的好三者。3)f*(n)=g*(n)+h*(n):從初始節(jié)點s通過當(dāng)前節(jié)點n到目標(biāo)節(jié)點t的最佳路徑的耗散值。9/16/2023304)評價函數(shù)：f(n)=g(n)+h(n),其中f，g，h分別是f*，g*，h*的估計值。通常約定:f(n)按照升序排列。討論：有上述定義，得:1)g(n)>=g*(n)2)當(dāng)h=0且g(n)=d(n)時，f(n)=d(n)既寬度優(yōu)先策略，d(n):節(jié)點深度。3）h(n)稱為啟發(fā)函數(shù)。9/16/2023313.1.1A算法1G=G0(G0=s),open=(s),closed=()，f(s)=g(s)+h(s)//s:初始狀態(tài)2Loop:ifopen=()thenexit(fall)3n←first(open)h()4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先輩節(jié)點計算f(n,mi)=g(n,mi)+h(mi),(自s經(jīng)過n，mi到目標(biāo)節(jié)點的耗散值)9/16/202332open←add(open，mj)標(biāo)記mj到n的指針(mj不在open，closed中)iff(n,mk)<f(mk)thenf(mk)←f(n,mk)標(biāo)記mk到n的指針(mk在open中)iff(n,mL)<f(mL)thenf(mL)←f(n,mL)標(biāo)記mL到n的指針(mL在closed中)

add(mL,open),把mL放回到open中7Open中的節(jié)點按f值升序排列8goloop9/16/2023339/16/202334例八數(shù)碼問題令：g(n)=d(n)節(jié)點深度h(n)=w(n)不在位的數(shù)碼個數(shù)(啟發(fā)函數(shù))則f(n)=d(n)+w(n)如初始節(jié)點s的f值f(0)=d(0)+w(0)=0+4=4有4個數(shù)碼不在位。9/16/2023359/16/202336對于f(n)=g(n)+h(n),如果單獨考慮g(n)或者h(n),即，1)f(n)=g(n)只考慮搜索過的路徑已經(jīng)耗費的費用；//分支界限算法2）f(n)=h(n)只考慮未來的發(fā)展趨勢//爬山算法那么可以得到兩種特殊的算法：爬山算法和分支界限算法。9/16/2023373.3.2爬山算法ProcedureHill_Climbing1n=s2Loop:ifgoal(n)thenexit(success)3{mi}←expangd(n),計算每個h(mi)nextn←h(mi)最小值的節(jié)點4ifh(n)<h(nextn)thenexit(fail)5n←nextn6goloop優(yōu)點，缺點9/16/2023383.3.3分支界限算法f(n)=g(n)ProcedureBranch_Bound1queue(s-s),g(s)=0//queue中保存的是從s出發(fā)的路徑。2Loop：ifqueue=0thenexit（fail）3path←FIRST(queue)，n←LAST(pATH)//取第一條路徑，及該路徑的最后節(jié)點n4ifgoal(n)thenexit(success)5{mj}←expand(n),計算g(mj)=g(n,mj)remove(s-n,queue),add(s-mj,queue)//刪除原來的路徑，添加長度加一的路徑。9/16/2023396queue隊列中分支按g值升序排列7GOLOOP例下圖右八城市，城市間的耗散值已經(jīng)給出，利用分支界限算法給出從S到t的最佳路徑。9/16/2023409/16/2023413.3.4動態(tài)規(guī)劃算法Proceduredynamic_Programming1queue(s-s),g(s)=0//queue中保存的是從s出發(fā)的路徑。2Loop：ifqueue=0thenexit（fail）3path←FIRST(queue)，n←LAST(pATH)//取第一條路徑，及該路徑的最后節(jié)點n4ifgoal(n)thenexit(success)5{mj}←expand(n),計算g(mj)=g(n,mj)remove(s-n,queue),add(s-mj,queue)9/16/202342//刪除原來的路徑，添加長度加一的路徑。6僅保留queue中到達某一公共節(jié)點路徑中耗散值最小的路徑，余者刪除；queue隊列中分支按g值升序排列7GOLOOP9/16/2023439/16/202344討論a動態(tài)規(guī)劃與分支界限差別在于去掉公共路徑的冗余部分，提高效率。b如果問題空間是樹結(jié)構(gòu)，動態(tài)規(guī)劃與分支界限相同。因為對于樹結(jié)構(gòu)不存在到達同一節(jié)點有多重路徑的情況。C動態(tài)規(guī)劃改進的代價。比如上例中，增加一個城市。9/16/202345A算法總結(jié)1初始狀態(tài)，open=（s）2正常情況下（非成功非失敗），取open中的第一個節(jié)點n，將n由open轉(zhuǎn)移到closed。3擴充節(jié)點n，將新節(jié)點加入到open中4修改某些節(jié)點的路徑5open中節(jié)點按照升序排列值得重視的一點：A算法失敗的唯一原因是open表為空9/16/202346思考題：圖中：s是起始點t是目標(biāo)節(jié)點；如果存在從s到t的一條最佳路徑。而n是最佳路徑上的一點。1）f*(s)f*(n)f*(t)的關(guān)系2）如果f*(s)=10,g*(n)=4問h*(n)=?9/16/2023473.3.5A*算法（最佳圖搜索算法）A*算法定義：對于算法A，如果有h（n）≤h*（n）,即h（n）以h*（n）為上界，則稱該算法稱為A*算法。如果令h（n）=0，則滿足h（n）≤h*（n）

這就是分支界限算法和動態(tài)規(guī)劃算法。再令g(n)=d(n)(d(n)是節(jié)點深度）則f(n)=d(n);A*算法就是寬度優(yōu)先算法。寬度優(yōu)先算法能找到最佳解。例：第二章中八數(shù)碼問題令h(n)=w(n)=不在位數(shù)字個數(shù)。9/16/202348算法可采納性：給定任意圖，設(shè)存在從開始節(jié)點s到目標(biāo)節(jié)點t的路徑。如果算法能夠結(jié)束在s到t的最佳路徑上，則稱該算法是可采納的。A*是具有可采納性。定理1對于有限圖，如果從s到t存在路徑，則A算法一定成功結(jié)束。9/16/202349推論1.1因為A*算法是A算法的一個特例。所以在有限圖上如果如果從s到t存在路徑，則A*算法一定成功結(jié)束。定理2對于無限圖，如果存在s到t路徑，則A*算法一定成功結(jié)束。9/16/202350推論2.1open表中任一滿足f(n)≦f*(s)的節(jié)點n最終都將被A*選作擴展節(jié)點。定理3如果存在節(jié)點s到目標(biāo)節(jié)點t路徑，則A*算法一定能找到最佳解結(jié)束。推論3.1A*選來擴展的節(jié)點都有f(n)≦f*(s)9/16/202351小結(jié)1如果存在節(jié)點s到目標(biāo)節(jié)點t路徑，則A*算法一定能找到最佳解結(jié)束。2open表中所有滿足f(n)≦f*(s)的節(jié)點n最終都將被A*選作擴展節(jié)點。3A*選來擴展的節(jié)點都有f(n)≦f*(s)4f*(s)作為A*的一個衡量上限。9/16/2023523.3.6h函數(shù)和A*算法的關(guān)系本節(jié)重點來討論h函數(shù)（即啟發(fā)信息量）對A*算法搜索效率的影響總結(jié)。定義：給定兩個A*算法A1和A2，都有f(n1)=g(n1)+h(n1)f(n2)=g(n2)+h(n2)如果對于所有非目標(biāo)節(jié)點n，有h(n1)<h(n2)則算法A2比算法A1有較多啟發(fā)信息。討論：啟發(fā)信息與h函數(shù)值成正比。極端情況下，完全沒有啟發(fā)信息時h=0，則此時A*算法就是寬度優(yōu)先算法。9/16/202353定理：給定兩個A*算法A1和A2如果A2的啟發(fā)式信息比A1多，則在任何存在節(jié)點s到目標(biāo)節(jié)點t的路徑上，搜索結(jié)束時，由A2擴展的每一個節(jié)點必定被A1擴展。(A1擴展的節(jié)點多)

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

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

9/16/202356定理5如果好h(n)滿足單調(diào)性限制條件，則A*算法擴展了節(jié)點n之后，就找到了到達節(jié)點n的最佳路徑，即：如果A*選中節(jié)點n，在單調(diào)性限制條件下，有g(shù)(n)=g*(n)9/16/2023573.38A*算法示例迷宮問題給定迷宮圖如下，找出從入口到出口的最短路徑。9/16/202358解1）綜合數(shù)據(jù)庫定義狀態(tài)集：{（x，y）∣1≤x，y≤4}其中（x，y）表示任意節(jié)點的坐標(biāo)所以問題表示為求解從（1,1）到（4,4）的最短路徑。2規(guī)則集（定義4條移動規(guī)則）右移R1：if（x，y）then（x+1，y）左移R2：if（x，y）then（x-1，y）9/16/202359上移R3：if（x，y）then（x+1，y+1）下移R4：if（x，y）then（x+1，y-1）兩種解法：寬度優(yōu)先，設(shè)定h(n)9/16/2023609/16/2023613）A*算法f函數(shù)定義f(n)=g(n)+h(n)設(shè)每一步的耗散值為1（