ch3產生式系統(tǒng)的搜索策略課件

ch3產生式系統(tǒng)的搜索策略2022/12/26ch3產生式系統(tǒng)的搜索策略ch3產生式系統(tǒng)的搜索策略2022/12/26ch3產生式系1費用的劃分：a規(guī)則應用的費用：執(zhí)行規(guī)則時所花的費用b控制費用：選擇規(guī)則所花的費用。2022/12/26ch3產生式系統(tǒng)的搜索策略2費用的劃分：2022/12/26ch3產生式系統(tǒng)的搜索策略2第三章目錄3.1回溯策略3.2圖搜索策略3.3啟發(fā)式圖搜索策略1）A算法2）爬山算法3）分支界限算法4）動態(tài)規(guī)劃算法5）A*算法2022/12/26ch3產生式系統(tǒng)的搜索策略3第三章目錄3.1回溯策略2022/12/26ch3產生式系統(tǒng)6）h函數與A*的關系7）關于單調性限制8）A*算法示例2022/12/26ch3產生式系統(tǒng)的搜索策略46）h函數與A*的關系2022/12/26ch3產3.1回溯算法2022/12/26ch3產生式系統(tǒng)的搜索策略53.1回溯算法2022/12/26ch3產生式系統(tǒng)的搜索2022/12/26ch3產生式系統(tǒng)的搜索策略62022/12/26ch3產生式系統(tǒng)的搜索策略6例四皇后問題2022/12/26ch3產生式系統(tǒng)的搜索策略7例四皇后問題2022/12/26ch3產生式系統(tǒng)的搜索策略定義綜合數據庫：設：DATA={ij︱1<=i,j<=4},其中：ij表示棋子所在行列如：24表示第二行第四列有一枚棋子因為棋盤上可放入的棋子數為0～4個所以集合中元素數位0～4個，即length（DATA）=0～42022/12/26ch3產生式系統(tǒng)的搜索策略8定義綜合數據庫：2022/12/26ch3產生式系統(tǒng)的搜索策2022/12/26ch3產生式系統(tǒng)的搜索策略92022/12/26ch3產生式系統(tǒng)的搜索策略92022/12/26ch3產生式系統(tǒng)的搜索策略102022/12/26ch3產生式系統(tǒng)的搜索策略102022/12/26ch3產生式系統(tǒng)的搜索策略112022/12/26ch3產生式系統(tǒng)的搜索策略112022/12/26ch3產生式系統(tǒng)的搜索策略122022/12/26ch3產生式系統(tǒng)的搜索策略122022/12/26ch3產生式系統(tǒng)的搜索策略132022/12/26ch3產生式系統(tǒng)的搜索策略132022/12/26ch3產生式系統(tǒng)的搜索策略142022/12/26ch3產生式系統(tǒng)的搜索策略143.2圖搜索策略2022/12/26ch3產生式系統(tǒng)的搜索策略153.2圖搜索策略2022/12/26ch3產生式系統(tǒng)的搜索策圖搜索策略圖搜索的實質是從問題空間中找出一張包含目標節(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中2022/12/26ch3產生式系統(tǒng)的搜索策略16圖搜索策略圖搜索的實質是從問題空間中找出一張包含目標節(jié)點的子標記mj每個到n節(jié)點指針確定是否需要修改已在open，closed中的每個節(jié)點到n的指針確定是否需要修改已在closed中的每個節(jié)點的后繼節(jié)點原來的指針。8按照某種方式排列open表中的節(jié)點，goloop2022/12/26ch3產生式系統(tǒng)的搜索策略17標記mj每個到n節(jié)點指針2022/12/26ch3產生式系統(tǒng)2022/12/26ch3產生式系統(tǒng)的搜索策略182022/12/26ch3產生式系統(tǒng)的搜索策略182022/12/26ch3產生式系統(tǒng)的搜索策略192022/12/26ch3產生式系統(tǒng)的搜索策略19深度優(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中標記mj每個到n節(jié)點指針，按照節(jié)點深度遞減順序排列open中的節(jié)點8goloop2022/12/26ch3產生式系統(tǒng)的搜索策略20深度優(yōu)先算法Procedruedepth-First-Se討論1：如果問題有解，有深度優(yōu)先搜索算法，是否能夠找到解？不一定.解空間是否有限？討論2：本算法的改進之處是open中節(jié)點按照深度優(yōu)先排列，但是沒有對深度加以控制，可能造成搜索代價太大2022/12/26ch3產生式系統(tǒng)的搜索策略21討論1：如果問題有解，有深度優(yōu)先搜索算法，是否能夠找到解？2寬度優(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中2022/12/26ch3產生式系統(tǒng)的搜索策略22寬度優(yōu)先算法Procedruebreadth-First-

標記每個到n節(jié)點指針，按照節(jié)點深度遞增順序排列open中的節(jié)點8goloop理論上可以利用寬度優(yōu)先搜索能夠找到解，如果問題有解的話。討論：寬度優(yōu)先算法和深度優(yōu)先算法可能出現組合爆炸。都沒有利用任何啟發(fā)式信息，所以稱為無信息搜索策略。2022/12/26ch3產生式系統(tǒng)的搜索策略23標記每個到n節(jié)點指針，按照節(jié)點深度遞增順序排列：寬度優(yōu)先例題：由一張桌子T、三個積木A、B、C組成一個積木世界，初始狀態(tài)是A在B上，B在桌子上，C在桌子上；目標狀態(tài)是：A、B、C依次從上到下排列在桌子上。如圖2022/12/26ch3產生式系統(tǒng)的搜索策略24：寬度優(yōu)先例題：2022/12/26ch3產生式系統(tǒng)的搜索策解：1）狀態(tài)描述（P1，P2，P3）表示按A、B、C順序依次分別在P1,P2,P3上其中Pi是積木或者桌子。初始狀態(tài)時（B、T、T）,目標狀態(tài)可以表示（B、C、T）2）定義操作:move(x,y)表示將積木x移到Y上；約束條件:aX頂部必須是空的b如果Y是積木，Y的頂部必須是空的c同一種狀態(tài)出現不得多于一次。2022/12/26ch3產生式系統(tǒng)的搜索策略25解：1）狀態(tài)描述（P1，P2，P3）表示按A、B、C順序依次1）解題過程2）open表和closed表3）節(jié)點樣子畫出整個圖G和解路徑4）程序何時結束5）改用深度優(yōu)先如何？2022/12/26ch3產生式系統(tǒng)的搜索策略261）解題過程2）open表和closed表2022/12/3.3啟發(fā)式圖搜索策略基本概念啟發(fā)式圖搜索的實質是利用啟發(fā)信息有目的地進行搜索，減少搜索的盲目性。降低搜索空間找到最佳解啟發(fā)式信息用于解決open表中節(jié)點的排列次序問題，方法是利用一個評價函數計算open表中節(jié)點的評價函數值，按照函數值從小到大排列所有節(jié)點。2022/12/26ch3產生式系統(tǒng)的搜索策略273.3啟發(fā)式圖搜索策略基本概念2022/12/26ch3產生評價函數的目的：把最有希望得到最佳解或者解的排列在前面。路徑：給定節(jié)點序列（n0，n1，…nk）。如果該序列中的任一節(jié)點ni-1都有后繼節(jié)點ni，則該節(jié)點序列為從n0到nk的一條路徑，路徑長度為K路徑耗散值：路徑耗散值等于該路徑上所有相鄰節(jié)點間耗散值的總和。2022/12/26ch3產生式系統(tǒng)的搜索策略28評價函數的目的：把最有希望得到最佳解或者解的排列設：路徑山任兩點間的耗散值為才C(ni,nj),則從ni到nk的路徑耗散值為C(ni,nj)=C(ni,nj)+C(nj,nk)最佳路徑耗散值：最佳路徑上的實際耗散值，記為：K(ni,nj).K(ni,nj)<=C(ni,nj)2022/12/26ch3產生式系統(tǒng)的搜索策略29設：路徑山任兩點間的耗散值為才C(ni,nj),則從ni到n定義幾個函數1）g*(n)=k(s,n):從初始節(jié)點s到當前節(jié)點n的最佳路徑的耗散值。2)h*(n)=k(n,t):從當前節(jié)點n到目標節(jié)點t的最佳路徑的好三者。3)f*(n)=g*(n)+h*(n):從初始節(jié)點s通過當前節(jié)點n到目標節(jié)點t的最佳路徑的耗散值。2022/12/26ch3產生式系統(tǒng)的搜索策略30定義幾個函數2022/12/26ch3產生式系統(tǒng)的搜索策略34)評價函數：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)既寬度優(yōu)先策略，d(n):節(jié)點深度。3）h(n)稱為啟發(fā)函數。2022/12/26ch3產生式系統(tǒng)的搜索策略314)評價函數：f(n)=g(n)+h(n),其中f，g，h分3.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經過n，mi到目標節(jié)點的耗散值)2022/12/26ch3產生式系統(tǒng)的搜索策略323.1.1A算法1G=G0(G0=s),open=(s),open←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中的節(jié)點按f值升序排列8goloop2022/12/26ch3產生式系統(tǒng)的搜索策略33open←add(open，mj)標記mj到n的指針(m2022/12/26ch3產生式系統(tǒng)的搜索策略342022/12/26ch3產生式系統(tǒng)的搜索策略34例八數碼問題令：g(n)=d(n)節(jié)點深度h(n)=w(n)不在位的數碼個數(啟發(fā)函數)則f(n)=d(n)+w(n)如初始節(jié)點s的f值f(0)=d(0)+w(0)=0+4=4有4個數碼不在位。2022/12/26ch3產生式系統(tǒng)的搜索策略35例八數碼問題2022/12/26ch3產生式系統(tǒng)的搜索策2022/12/26ch3產生式系統(tǒng)的搜索策略362022/12/26ch3產生式系統(tǒng)的搜索策略36對于f(n)=g(n)+h(n),如果單獨考慮g(n)或者h(n),即，1)f(n)=g(n)只考慮搜索過的路徑已經耗費的費用；//分支界限算法2）f(n)=h(n)只考慮未來的發(fā)展趨勢//爬山算法那么可以得到兩種特殊的算法：爬山算法和分支界限算法。2022/12/26ch3產生式系統(tǒng)的搜索策略37對于f(n)=g(n)+h(n),如果單獨考慮g(n)或者h3.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)點，缺點2022/12/26ch3產生式系統(tǒng)的搜索策略383.3.2爬山算法ProcedureHill_Climb3.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)//刪除原來的路徑，添加長度加一的路徑。2022/12/26ch3產生式系統(tǒng)的搜索策略393.3.3分支界限算法f(n)=g(n)Procedure6queue隊列中分支按g值升序排列7GOLOOP例下圖右八城市，城市間的耗散值已經給出，利用分支界限算法給出從S到t的最佳路徑。2022/12/26ch3產生式系統(tǒng)的搜索策略406queue隊列中分支按g值升序排列2022/12/26c2022/12/26ch3產生式系統(tǒng)的搜索策略412022/12/26ch3產生式系統(tǒng)的搜索策略413.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)2022/12/26ch3產生式系統(tǒng)的搜索策略423.3.4動態(tài)規(guī)劃算法Proceduredynamic_P//刪除原來的路徑，添加長度加一的路徑。6僅保留queue中到達某一公共節(jié)點路徑中耗散值最小的路徑，余者刪除；queue隊列中分支按g值升序排列7GOLOOP2022/12/26ch3產生式系統(tǒng)的搜索策略43//刪除原來的路徑，添加長度加一的路徑。2022/2022/12/26ch3產生式系統(tǒng)的搜索策略442022/12/26ch3產生式系統(tǒng)的搜索策略44討論a動態(tài)規(guī)劃與分支界限差別在于去掉公共路徑的冗余部分，提高效率。b如果問題空間是樹結構，動態(tài)規(guī)劃與分支界限相同。因為對于樹結構不存在到達同一節(jié)點有多重路徑的情況。C動態(tài)規(guī)劃改進的代價。比如上例中，增加一個城市。2022/12/26ch3產生式系統(tǒng)的搜索策略45討論a動態(tài)規(guī)劃與分支界限差別在于去掉公共路徑的冗余部分，A算法總結1初始狀態(tài)，open=（s）2正常情況下（非成功非失敗），取open中的第一個節(jié)點n，將n由open轉移到closed。3擴充節(jié)點n，將新節(jié)點加入到open中4修改某些節(jié)點的路徑5open中節(jié)點按照升序排列值得重視的一點：A算法失敗的唯一原因是open表為空2022/12/26ch3產生式系統(tǒng)的搜索策略46A算法總結1初始狀態(tài)，open=（s）2022/12/26思考題：圖中：s是起始點t是目標節(jié)點；如果存在從s到t的一條最佳路徑。而n是最佳路徑上的一點。1）f*(s)f*(n)f*(t)的關系2）如果f*(s)=10,g*(n)=4問h*(n)=?2022/12/26ch3產生式系統(tǒng)的搜索策略47思考題：圖中：s是起始點t是目標節(jié)點；如果存在從s到t的3.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)先算法能找到最佳解。例：第二章中八數碼問題令h(n)=w(n)=不在位數字個數。2022/12/26ch3產生式系統(tǒng)的搜索策略483.3.5A*算法（最佳圖搜索算法）A*算法定義：20算法可采納性：給定任意圖，設存在從開始節(jié)點s到目標節(jié)點t的路徑。如果算法能夠結束在s到t的最佳路徑上，則稱該算法是可采納的。A*是具有可采納性。定理1對于有限圖，如果從s到t存在路徑，則A算法一定成功結束。2022/12/26ch3產生式系統(tǒng)的搜索策略49算法可采納性：2022/12/26ch3產生式系統(tǒng)的搜索策略推論1.1因為A*算法是A算法的一個特例。所以在有限圖上如果如果從s到t存在路徑，則A*算法一定成功結束。定理2對于無限圖，如果存在s到t路徑，則A*算法一定成功結束。2022/12/26ch3產生式系統(tǒng)的搜索策略50推論1.12022/12/26ch3產生式系統(tǒng)的搜索策略5推論2.1open表中任一滿足f(n)≦f*(s)的節(jié)點n最終都將被A*選作擴展節(jié)點。定理3如果存在節(jié)點s到目標節(jié)點t路徑，則A*算法一定能找到最佳解結束。推論3.1A*選來擴展的節(jié)點都有f(n)≦f*(s)2022/12/26ch3產生式系統(tǒng)的搜索策略51推論2.12022/12/26ch3產生式系統(tǒng)的搜索策略51小結1如果存在節(jié)點s到目標節(jié)點t路徑，則A*算法一定能找到最佳解結束。2open表中所有滿足f(n)≦f*(s)的節(jié)點n最終都將被A*選作擴展節(jié)點。3A*選來擴展的節(jié)點都有f(n)≦f*(s)4f*(s)作為A*的一個衡量上限。2022/12/26ch3產生式系統(tǒng)的搜索策略52小結2022/12/26ch3產生式系統(tǒng)的搜索策略523.3.6h函數和A*算法的關系本節(jié)重點來討論h函數（即啟發(fā)信息量）對A*算法搜索效率的影響總結。定義：給定兩個A*算法A1和A2，都有f(n1)=g(n1)+h(n1)f(n2)=g(n2)+h(n2)如果對于所有非目標節(jié)點n，有h(n1)<h(n2)則算法A2比算法A1有較多啟發(fā)信息。討論：啟發(fā)信息與h函數值成正比。極端情況下，完全沒有啟發(fā)信息時h=0，則此時A*算法就是寬度優(yōu)先算法。2022/12/26ch3產生式系統(tǒng)的搜索策略533.3.6h函數和A*算法的關系本節(jié)重點來討論h函數（即啟發(fā)定理：給定兩個A*算法A1和A2如果A2的啟發(fā)式信息比A1多，則在任何存在節(jié)點s到目標節(jié)點t的路徑上，搜索結束時，由A2擴展的每一個節(jié)點必定被A1擴展。(A1擴展的節(jié)點多)

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

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

2022/12/26ch3產生式系統(tǒng)的搜索策略563.37h函數單調性限制單調性限制的作用是：避免重復計算某定理5如果好h(n)滿足單調性限制條件，則A*算法擴展了節(jié)點n之后，就找到了到達節(jié)點n的最佳路徑，即：如果A*選中節(jié)點n，在單調性限制條件下，有g(n)=g*(n)2022/12/26ch3產生式系統(tǒng)的搜索策略57定理52022/12/26ch3產生式系統(tǒng)的搜索策略573.38A*算法示例迷宮問題給定迷宮圖如下，找出從入口到出口的最短路徑。2022/12/26ch3產生式系統(tǒng)的搜索策略583.38A*算法示例迷宮問題2022/12/26ch3產生式解1）綜合數據庫定義狀態(tài)集：{（x，y）∣1≤x，y≤4}其中（x，y）表示任意節(jié)點的坐標所以問題表示為求解從（1,1）到（4,4）的最短路徑。2規(guī)則集（定義4條移動規(guī)則）右移R1：if（x，y）then（x+1，y）左移R2：if（x，y）then（x-1，y）2022/12/26ch3產生式系統(tǒng)的搜索策略59解1）綜合數據庫2022/12/26ch3產生式系統(tǒng)的搜上移R3：if（x，y）then（x+1，y+1）下移R4：if（x，y）then（x+1，y-1）兩種解法：寬度優(yōu)先，設定h(n)2022/12/26ch3產生式系統(tǒng)的搜索策略60上移R3：if（x，y）then（x+1，y+1）2022022/12/26ch3產生式系統(tǒng)的搜索策略612022/12/26ch3產生式系統(tǒng)的搜索策略613）A*算法f函數定義f(n)=g(n)+h(n)設每一步的耗散值為1（單位耗散值）定義：g(n=d(n)從初始節(jié)點s到當前節(jié)點n的搜索深度。h(n)=∣-xn∣+∣-yn∣其中是（xg，yg）目標節(jié)點的坐標，（xn，yn）是當前節(jié)點的坐標。顯然滿足：h(n)≤h*(n)4）Open表節(jié)點排序先按f值排序，如果f值相同，則深度優(yōu)先，2022/12/26ch3產生式系統(tǒng)的搜索策略623）A*算法f函數定義f(n)=g(n)+h(n)2022/2022/12/26ch3產生式系統(tǒng)的搜索策略632022/12/26ch3產生式系統(tǒng)的搜索策略63關于f函數值的意義的討論為了調整g和h在h中的作用比例，設f=g+w*h1）令w=0則f=g，此時，A*成為寬度優(yōu)先算法。特點：可擴大搜索范圍便于找到最佳解，但是費用比較大。2）令w為一個大的整數，則加大了h在f函數中的作用力度。其意義在于：不考慮到目前已經消耗的費用，只關心當前節(jié)點到目標節(jié)點剩余的搜索工作量。2022/12/26ch3產生式系統(tǒng)的搜索策略64關于f函數值的意義的討論2022/12/26ch3產生式系統(tǒng)本章算法匯總1.回溯策略2.圖搜索策略

A算法：h(n)=0g(n)=-d(n)深度優(yōu)先

F(n)=g(n)+h(n)g(n)=0爬山算法

h(n)=0分支界限算法各分支只保留一個動態(tài)規(guī)劃算法h(n)=0g(n)=d(n)寬度優(yōu)先算法A*算法。。。。。。。2022/12/26ch3產生式系統(tǒng)的搜索策略65本章算法匯總1.回溯策略2022/12/26ch3產生式系統(tǒng)本章例題匯總1.四皇后問題回溯策略2積木世界問題寬度優(yōu)先3八數碼問題A算法4八城市s-t分支界限算法。5迷宮問題A*算法2022/12/26ch3產生式系統(tǒng)的搜索策略66本章例題匯總1.四皇后問題回溯策略2022/1演講完畢，謝謝聽講!再見，seeyouagain2022/12/26ch3產生式系統(tǒng)的搜索策略演講完畢，謝謝聽講!再見，seeyouagain202267ch3產生式系統(tǒng)的搜索策略2022/12/26ch3產生式系統(tǒng)的搜索策略ch3產生式系統(tǒng)的搜索策略2022/12/26ch3產生式系68費用的劃分：a規(guī)則應用的費用：執(zhí)行規(guī)則時所花的費用b控制費用：選擇規(guī)則所花的費用。2022/12/26ch3產生式系統(tǒng)的搜索策略69費用的劃分：2022/12/26ch3產生式系統(tǒng)的搜索策略2第三章目錄3.1回溯策略3.2圖搜索策略3.3啟發(fā)式圖搜索策略1）A算法2）爬山算法3）分支界限算法4）動態(tài)規(guī)劃算法5）A*算法2022/12/26ch3產生式系統(tǒng)的搜索策略70第三章目錄3.1回溯策略2022/12/26ch3產生式系統(tǒng)6）h函數與A*的關系7）關于單調性限制8）A*算法示例2022/12/26ch3產生式系統(tǒng)的搜索策略716）h函數與A*的關系2022/12/26ch3產3.1回溯算法2022/12/26ch3產生式系統(tǒng)的搜索策略723.1回溯算法2022/12/26ch3產生式系統(tǒng)的搜索2022/12/26ch3產生式系統(tǒng)的搜索策略732022/12/26ch3產生式系統(tǒng)的搜索策略6例四皇后問題2022/12/26ch3產生式系統(tǒng)的搜索策略74例四皇后問題2022/12/26ch3產生式系統(tǒng)的搜索策略定義綜合數據庫：設：DATA={ij︱1<=i,j<=4},其中：ij表示棋子所在行列如：24表示第二行第四列有一枚棋子因為棋盤上可放入的棋子數為0～4個所以集合中元素數位0～4個，即length（DATA）=0～42022/12/26ch3產生式系統(tǒng)的搜索策略75定義綜合數據庫：2022/12/26ch3產生式系統(tǒng)的搜索策2022/12/26ch3產生式系統(tǒng)的搜索策略762022/12/26ch3產生式系統(tǒng)的搜索策略92022/12/26ch3產生式系統(tǒng)的搜索策略772022/12/26ch3產生式系統(tǒng)的搜索策略102022/12/26ch3產生式系統(tǒng)的搜索策略782022/12/26ch3產生式系統(tǒng)的搜索策略112022/12/26ch3產生式系統(tǒng)的搜索策略792022/12/26ch3產生式系統(tǒng)的搜索策略122022/12/26ch3產生式系統(tǒng)的搜索策略802022/12/26ch3產生式系統(tǒng)的搜索策略132022/12/26ch3產生式系統(tǒng)的搜索策略812022/12/26ch3產生式系統(tǒng)的搜索策略143.2圖搜索策略2022/12/26ch3產生式系統(tǒng)的搜索策略823.2圖搜索策略2022/12/26ch3產生式系統(tǒng)的搜索策圖搜索策略圖搜索的實質是從問題空間中找出一張包含目標節(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中2022/12/26ch3產生式系統(tǒng)的搜索策略83圖搜索策略圖搜索的實質是從問題空間中找出一張包含目標節(jié)點的子標記mj每個到n節(jié)點指針確定是否需要修改已在open，closed中的每個節(jié)點到n的指針確定是否需要修改已在closed中的每個節(jié)點的后繼節(jié)點原來的指針。8按照某種方式排列open表中的節(jié)點，goloop2022/12/26ch3產生式系統(tǒng)的搜索策略84標記mj每個到n節(jié)點指針2022/12/26ch3產生式系統(tǒng)2022/12/26ch3產生式系統(tǒng)的搜索策略852022/12/26ch3產生式系統(tǒng)的搜索策略182022/12/26ch3產生式系統(tǒng)的搜索策略862022/12/26ch3產生式系統(tǒng)的搜索策略19深度優(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中標記mj每個到n節(jié)點指針，按照節(jié)點深度遞減順序排列open中的節(jié)點8goloop2022/12/26ch3產生式系統(tǒng)的搜索策略87深度優(yōu)先算法Procedruedepth-First-Se討論1：如果問題有解，有深度優(yōu)先搜索算法，是否能夠找到解？不一定.解空間是否有限？討論2：本算法的改進之處是open中節(jié)點按照深度優(yōu)先排列，但是沒有對深度加以控制，可能造成搜索代價太大2022/12/26ch3產生式系統(tǒng)的搜索策略88討論1：如果問題有解，有深度優(yōu)先搜索算法，是否能夠找到解？2寬度優(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中2022/12/26ch3產生式系統(tǒng)的搜索策略89寬度優(yōu)先算法Procedruebreadth-First-

標記每個到n節(jié)點指針，按照節(jié)點深度遞增順序排列open中的節(jié)點8goloop理論上可以利用寬度優(yōu)先搜索能夠找到解，如果問題有解的話。討論：寬度優(yōu)先算法和深度優(yōu)先算法可能出現組合爆炸。都沒有利用任何啟發(fā)式信息，所以稱為無信息搜索策略。2022/12/26ch3產生式系統(tǒng)的搜索策略90標記每個到n節(jié)點指針，按照節(jié)點深度遞增順序排列：寬度優(yōu)先例題：由一張桌子T、三個積木A、B、C組成一個積木世界，初始狀態(tài)是A在B上，B在桌子上，C在桌子上；目標狀態(tài)是：A、B、C依次從上到下排列在桌子上。如圖2022/12/26ch3產生式系統(tǒng)的搜索策略91：寬度優(yōu)先例題：2022/12/26ch3產生式系統(tǒng)的搜索策解：1）狀態(tài)描述（P1，P2，P3）表示按A、B、C順序依次分別在P1,P2,P3上其中Pi是積木或者桌子。初始狀態(tài)時（B、T、T）,目標狀態(tài)可以表示（B、C、T）2）定義操作:move(x,y)表示將積木x移到Y上；約束條件:aX頂部必須是空的b如果Y是積木，Y的頂部必須是空的c同一種狀態(tài)出現不得多于一次。2022/12/26ch3產生式系統(tǒng)的搜索策略92解：1）狀態(tài)描述（P1，P2，P3）表示按A、B、C順序依次1）解題過程2）open表和closed表3）節(jié)點樣子畫出整個圖G和解路徑4）程序何時結束5）改用深度優(yōu)先如何？2022/12/26ch3產生式系統(tǒng)的搜索策略931）解題過程2）open表和closed表2022/12/3.3啟發(fā)式圖搜索策略基本概念啟發(fā)式圖搜索的實質是利用啟發(fā)信息有目的地進行搜索，減少搜索的盲目性。降低搜索空間找到最佳解啟發(fā)式信息用于解決open表中節(jié)點的排列次序問題，方法是利用一個評價函數計算open表中節(jié)點的評價函數值，按照函數值從小到大排列所有節(jié)點。2022/12/26ch3產生式系統(tǒng)的搜索策略943.3啟發(fā)式圖搜索策略基本概念2022/12/26ch3產生評價函數的目的：把最有希望得到最佳解或者解的排列在前面。路徑：給定節(jié)點序列（n0，n1，…nk）。如果該序列中的任一節(jié)點ni-1都有后繼節(jié)點ni，則該節(jié)點序列為從n0到nk的一條路徑，路徑長度為K路徑耗散值：路徑耗散值等于該路徑上所有相鄰節(jié)點間耗散值的總和。2022/12/26ch3產生式系統(tǒng)的搜索策略95評價函數的目的：把最有希望得到最佳解或者解的排列設：路徑山任兩點間的耗散值為才C(ni,nj),則從ni到nk的路徑耗散值為C(ni,nj)=C(ni,nj)+C(nj,nk)最佳路徑耗散值：最佳路徑上的實際耗散值，記為：K(ni,nj).K(ni,nj)<=C(ni,nj)2022/12/26ch3產生式系統(tǒng)的搜索策略96設：路徑山任兩點間的耗散值為才C(ni,nj),則從ni到n定義幾個函數1）g*(n)=k(s,n):從初始節(jié)點s到當前節(jié)點n的最佳路徑的耗散值。2)h*(n)=k(n,t):從當前節(jié)點n到目標節(jié)點t的最佳路徑的好三者。3)f*(n)=g*(n)+h*(n):從初始節(jié)點s通過當前節(jié)點n到目標節(jié)點t的最佳路徑的耗散值。2022/12/26ch3產生式系統(tǒng)的搜索策略97定義幾個函數2022/12/26ch3產生式系統(tǒng)的搜索策略34)評價函數：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)既寬度優(yōu)先策略，d(n):節(jié)點深度。3）h(n)稱為啟發(fā)函數。2022/12/26ch3產生式系統(tǒng)的搜索策略984)評價函數：f(n)=g(n)+h(n),其中f，g，h分3.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經過n，mi到目標節(jié)點的耗散值)2022/12/26ch3產生式系統(tǒng)的搜索策略993.1.1A算法1G=G0(G0=s),open=(s),open←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中的節(jié)點按f值升序排列8goloop2022/12/26ch3產生式系統(tǒng)的搜索策略100open←add(open，mj)標記mj到n的指針(m2022/12/26ch3產生式系統(tǒng)的搜索策略1012022/12/26ch3產生式系統(tǒng)的搜索策略34例八數碼問題令：g(n)=d(n)節(jié)點深度h(n)=w(n)不在位的數碼個數(啟發(fā)函數)則f(n)=d(n)+w(n)如初始節(jié)點s的f值f(0)=d(0)+w(0)=0+4=4有4個數碼不在位。2022/12/26ch3產生式系統(tǒng)的搜索策略102例八數碼問題2022/12/26ch3產生式系統(tǒng)的搜索策2022/12/26ch3產生式系統(tǒng)的搜索策略1032022/12/26ch3產生式系統(tǒng)的搜索策略36對于f(n)=g(n)+h(n),如果單獨考慮g(n)或者h(n),即，1)f(n)=g(n)只考慮搜索過的路徑已經耗費的費用；//分支界限算法2）f(n)=h(n)只考慮未來的發(fā)展趨勢//爬山算法那么可以得到兩種特殊的算法：爬山算法和分支界限算法。2022/12/26ch3產生式系統(tǒng)的搜索策略104對于f(n)=g(n)+h(n),如果單獨考慮g(n)或者h3.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)點，缺點2022/12/26ch3產生式系統(tǒng)的搜索策略1053.3.2爬山算法ProcedureHill_Climb3.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)//刪除原來的路徑，添加長度加一的路徑。2022/12/26ch3產生式系統(tǒng)的搜索策略1063.3.3分支界限算法f(n)=g(n)Procedure6queue隊列中分支按g值升序排列7GOLOOP例下圖右八城市，城市間的耗散值已經給出，利用分支界限算法給出從S到t的最佳路徑。2022/12/26ch3產生式系統(tǒng)的搜索策略1076queue隊列中分支按g值升序排列2022/12/26c2022/12/26ch3產生式系統(tǒng)的搜索策略1082022/12/26ch3產生式系統(tǒng)的搜索策略413.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)2022/12/26ch3產生式系統(tǒng)的搜索策略1093.3.4動態(tài)規(guī)劃算法Proceduredynamic_P//刪除原來的路徑，添加長度加一的路徑。6僅保留queue中到達某一公共節(jié)點路徑中耗散值最小的路徑，余者刪除；queue隊列中分支按g值升序排列7GOLOOP2022/12/26ch3產生式系統(tǒng)的搜索策略110//刪除原來的路徑，添加長度加一的路徑。2022/2022/12/26ch3產生式系統(tǒng)的搜索策略1112022/12/26ch3產生式系統(tǒng)的搜索策略44討論a動態(tài)規(guī)劃與分支界限差別在于去掉公共路徑的冗余部分，提高效率。b如果問題空間是樹結構，動態(tài)規(guī)劃與分支界限相同。因為對于樹結構不存在到達同一節(jié)點有多重路徑的情況。C動態(tài)規(guī)劃改進的代價。比如上例中，增加一個城市。2022/12/26ch3產生式系統(tǒng)的搜索策略112討論a動態(tài)規(guī)劃與分支界限差別在于去掉公共路徑的冗余部分，A算法總結1初始狀態(tài)，open=（s）2正常情況下（非成功非失?。pen中的第一個節(jié)點n，將n由open轉移到closed。3擴充節(jié)點n，將新節(jié)點加入到open中4修改某些節(jié)點的路徑5open中節(jié)點按照升序排列值得重視的一點：A算法失敗的唯一原因是open表為空2022/12/26ch3產生式系統(tǒng)的搜索策略113A算法總結1初始狀態(tài)，open=（s）2022/12/26思考題：圖中：s是起始點t是目標節(jié)點；如果存在從s到t的一條最佳路徑。而n是最佳路徑上的一點。1）f*(s)f*(n)f*(t)的關系2）如果f*(s)=10,g*(n)=4問h*(n)=?2022/12/26ch3產生式系統(tǒng)的搜索策略114思考題：圖中：s是起始點t是目標節(jié)點；如果存在從s到t的3.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)先算法能找到最佳解。例：第二章中八數碼問題令h(n)=w(n)=不在位數字個數。2022/12/26ch3產生式系統(tǒng)的搜索策略1153.3.5A*算法（最佳圖搜索算法）A*算法定義：20算法可采納性：給定任意圖，設存在從開始節(jié)點s到目標節(jié)點t的路徑。如果算法能夠結束在s到t的最佳路徑上，則稱該算法是可采納的。A*是具有可采納性。定理1對于有限圖，如果從s到t存在路徑，則A算法一定成功結束。2022/12/26ch3產生式系統(tǒng)的搜索策略116算法可采納性：2022/12/26ch3產生式系統(tǒng)的搜索策略推論1.1因為A*算法是A算法的一個特例。所以在有限圖上如果如果從s到t存在路徑，則A*算法一定成功結束。定理2對于無限圖，如果存在s到t路徑，則A*算法一定成功結束。2022/12/26ch3產生式系統(tǒng)的搜索策略117推論1.12022/12/26ch3產生式系統(tǒng)的搜索策略5推論2.1open表中任一滿足f(n)≦f*(s)的節(jié)點n最終都將被A*選作擴展節(jié)點。定理3如果存在節(jié)點s到目標節(jié)點t路徑，則A*算法一定能找到最佳解結束。推論3.1A*選來擴展的節(jié)點都有f(n)≦f*(s)2022/12/26ch3產生式系統(tǒng)的搜索策略118推論2.12022/12/26ch3產生式系統(tǒng)的搜索策略51小結1如果存在節(jié)點s到目標節(jié)點t路徑，則A*算法一定能找到最佳解結束。2open表中所有滿足f(n)≦f*(s)的節(jié)點n最終都將被A*選作擴展節(jié)點。3A*選來擴展的節(jié)點都有f(n)≦f*(s)4f*(s)作為A*的一個衡量上限。2022/12/26ch3產生式系統(tǒng)的搜索策略119小結2022/12/26ch3產生式系統(tǒng)的搜索策略523.3.6h函數和A*算法的關系本節(jié)重點來討論h函數（即啟發(fā)信息量）對A*算法搜索效率的影響總結。定義：給定兩個A*算法A1和A2，都有f(n1)=g(n1)+h(n1)f(n2)=g(n2)+h(n2)如果對于所有非目標節(jié)點n，有h(n1)<h(n2)則算法A2比算法A1有較多啟發(fā)信息。討論：啟發(fā)信息與h函數值成正比。極端情況下，完全沒有啟發(fā)信息時h=0，則此時A*算法就是寬度優(yōu)先算法。2022/12/26ch3產生式系統(tǒng)的搜索策略1203.3.6h函數和A*算法的關系本節(jié)重點來討論h函數（即啟發(fā)定理：給定兩個A*算法A1和A2如果A2的啟發(fā)式信息比A1多，則在任何存在節(jié)點s到目標節(jié)點t的路徑上，搜索結束時，由A2擴展的每一個節(jié)點必定被A1擴展。(A1擴展的節(jié)點多)

注意搜索空間小，不代表能夠找到最佳解。2022/12/26ch3產生式系統(tǒng)的搜索策略121定理：2022/1