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

1、第三章產(chǎn)生式系統(tǒng)的搜索策略狀態(tài)空間：由給定問(wèn)題的所有可能的狀態(tài)組成的空間（相當(dāng)于全集G）搜索空間：按某種策略在狀態(tài)空間中選取的部分空間（G的子集）解路徑（解空間）：求解問(wèn)題的一條有效路徑。搜索策略的基本思路：搜索空間必須包含解路徑，如果問(wèn)題有解，且盡量縮小搜索空間。搜索策略的評(píng)價(jià)準(zhǔn)則：總體費(fèi)用最低7/25/20221費(fèi)用的劃分： a 規(guī)則應(yīng)用的費(fèi)用：執(zhí)行規(guī)則時(shí)所花的費(fèi)用 b 控制費(fèi)用：選擇規(guī)則所花的費(fèi)用。7/25/20222第三章目錄3.1回溯策略3.2 圖搜索策略3.3 啟發(fā)式圖搜索策略 1）A算法 2）爬山算法 3）分支界限算法 4）動(dòng)態(tài)規(guī)劃算法 5）A*算法7/25/20223 6）h函

2、數(shù)與A*的關(guān)系 7）關(guān)于單調(diào)性限制 8）A*算法示例7/25/202243.1回溯算法 7/25/202257/25/20226例 四皇后問(wèn)題7/25/20227定義綜合數(shù)據(jù)庫(kù)：設(shè)：DATA=ij1=i,j=4,其中：ij表示棋子所在行列 如：24表示第二行第四列有一枚棋子因?yàn)槠灞P(pán)上 可放入的棋子數(shù)為04個(gè)所以集合中元素?cái)?shù)位0 4個(gè)，即length（DATA）=0 47/25/202287/25/202297/25/2022107/25/2022117/25/2022127/25/2022137/25/2022143.2圖搜索策略7/25/202215圖搜索策略圖搜索的實(shí)質(zhì)是從問(wèn)題空間中找出一

3、張包含目標(biāo)節(jié)點(diǎn)的子圖。圖搜索的結(jié)果：1，一個(gè)完整的搜索圖G。2一個(gè)解路徑，用指針表示的解路徑。Procedure GraphSearch1 G=G0(G0=s),open=(s) /s:初始狀態(tài)2 closed=() 3Loop:if open=() then exit(fall)4 nfirst(open) remove(n,open), add(n,closed)5 if goal(n) then exit(success)6mj expand(n), /mj不含n的先輩節(jié)點(diǎn)7 openadd(open，mj) / mj不在open，closed中7/25/202216標(biāo)記mj每個(gè)到n節(jié)點(diǎn)

4、指針確定是否需要修改已在open，closed中的每個(gè)節(jié)點(diǎn)到n的指針確定是否需要修改已在closed中的每個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)原來(lái)的指針。8按照某種方式排列open表中的節(jié)點(diǎn)，go loop7/25/2022177/25/2022187/25/202219深度優(yōu)先算法Procedrue depth-First-Search1 G=G0(G0=s),open=(s),closed=() /s:初始狀態(tài)2 Loop:if open=() then exit(fall)3 nfirst(open)4 if goal(n) then exit(success)5remove(n,open), add(n,

5、closed)6mj expand(n), /mj不含n的先輩節(jié)點(diǎn)7 openadd(open，mj) / mj不在open，closed中標(biāo)記mj每個(gè)到n節(jié)點(diǎn)指針，按照節(jié)點(diǎn)深度遞減順序排列open中的節(jié)點(diǎn) 8 go loop7/25/202220討論1：如果問(wèn)題有解，有深度優(yōu)先搜索算法，是否能夠找到解？不一定.解空間是否有限？討論2：本算法的改進(jìn)之處是open中節(jié)點(diǎn)按照深度優(yōu)先排列，但是沒(méi)有對(duì)深度加以控制，可能造成搜索代價(jià)太大7/25/202221寬度優(yōu)先算法Procedrue breadth-First-Search1 G=G0(G0=s),open=(s),closed=() /s:初始

6、狀態(tài)2 Loop:if open=() then exit(fall)3 nfirst(open)4 if goal(n) then exit(success)5remove(n,open), add(n,closed)6mj expand(n), /mj不含n的先輩節(jié)點(diǎn)7 openadd(open，mj) / mj不在open，closed中7/25/202222 標(biāo)記每個(gè)到n節(jié)點(diǎn)指針，按照節(jié)點(diǎn)深度遞增順序排列open中的節(jié)點(diǎn) 8 go loop 理論上可以利用寬度優(yōu)先搜索能夠找到解，如果問(wèn)題有解的話。討論：寬度優(yōu)先算法和深度優(yōu)先算法可能出現(xiàn)組合爆炸。都沒(méi)有利用任何啟發(fā)式信息，所以稱(chēng)為無(wú)信息

7、搜索策略。7/25/202223：寬度優(yōu)先例題： 由一張桌子T、三個(gè)積木A、B、C組成一個(gè)積木世界，初始狀態(tài)是A在B上，B在桌子上，C在桌子上；目標(biāo)狀態(tài)是：A、B、C依次從上到下排列在桌子上。如圖7/25/202224解：1）狀態(tài)描述（P1，P2，P3）表示按A、B、C順序依次分別在P1,P2,P3上其中Pi是積木或者桌子。初始狀態(tài)時(shí)（B、T、T）,目標(biāo)狀態(tài) 可以表示（B、C、T）2）定義操作:move(x,y)表示將積木x移到Y(jié)上 ；約束條件:a X頂部必須是空的 b 如果Y是積木，Y的頂部必須是空的 c 同一種狀態(tài)出現(xiàn)不得多于一次。7/25/2022251）解題過(guò)程 2）open表和clo

8、sed表3）節(jié)點(diǎn)樣子畫(huà)出整個(gè)圖G 和解路徑4）程序何時(shí)結(jié)束 5）改用深度優(yōu)先如何？7/25/2022263.3啟發(fā)式圖搜索策略基本概念啟發(fā)式圖搜索的實(shí)質(zhì)是利用啟發(fā)信息有目的地進(jìn)行搜索，減少搜索的盲目性。 降低搜索空間 找到最佳解啟發(fā)式信息用于解決open表中節(jié)點(diǎn)的排列次序問(wèn)題，方法是利用一個(gè)評(píng)價(jià)函數(shù)計(jì)算open表中節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值，按照函數(shù)值從小到大排列所有節(jié)點(diǎn)。7/25/202227 評(píng)價(jià)函數(shù)的目的：把最有希望得到最佳解或者解的排列在前面。路徑 ：給定節(jié)點(diǎn)序列（n0，n1，nk）。如果該序列中的任一節(jié)點(diǎn)ni-1都有后繼節(jié)點(diǎn)ni，則該節(jié)點(diǎn)序列為從n0到nk的一條路徑，路徑長(zhǎng)度為K路徑耗散值：路

9、徑耗散值等于該路徑上所有相鄰節(jié)點(diǎn)間耗散值的總和。7/25/202228設(shè)：路徑山任兩點(diǎn)間的耗散值為才C(ni,nj),則從ni到nk的路徑耗散值為C(ni,nj)=C(ni,nj)+C(nj,nk)最佳路徑耗散值：最佳路徑上的實(shí)際耗散值，記為：K(ni,nj).K(ni,nj)=g*(n) 2)當(dāng)h=0且g(n) =d(n) 時(shí)，f(n)=d(n)既寬度優(yōu)先策略，d(n):節(jié)點(diǎn)深度。 3）h(n)稱(chēng)為啟發(fā)函數(shù)。7/25/2022313.1.1A算法1 G=G0(G0=s),open=(s),closed=() ，f(s)=g(s)+ h(s) /s:初始狀態(tài)2 Loop:if open=()

10、then exit(fall)3 nfirst(open)h()4 if goal(n) then exit(success)5remove(n,open), add(n,closed)6mj expand(n), /mj不含n的先輩節(jié)點(diǎn) 計(jì)算f(n,mi)=g(n,mi)+h(mi),(自s經(jīng)過(guò)n，mi 到目標(biāo)節(jié)點(diǎn)的耗散值)7/25/202232openadd(open，mj) 標(biāo)記mj到n的指針 (mj不在open，closed中) if f(n, mk)f(mk) then f(mk) f(n, mk)標(biāo)記mk到n的指針(mk在open中)if f(n, mL)f(mL) then f(

11、mL) f(n, mL)標(biāo)記mL到n的指針(mL在closed中) add(mL,open),把mL放回到open中7 Open中的節(jié)點(diǎn)按f值升序排列 8 go loop7/25/2022337/25/202234例 八數(shù)碼問(wèn)題令：g(n)=d(n) 節(jié)點(diǎn)深度 h(n)=w(n) 不在位的數(shù)碼個(gè)數(shù)(啟發(fā)函數(shù))則 f(n)=d(n)+w(n)如初始節(jié)點(diǎn)s的f值f(0)=d(0)+w(0)=0+4=4有4個(gè)數(shù)碼不在位。7/25/2022357/25/202236對(duì)于f(n)=g(n)+h(n),如果單獨(dú)考慮g(n)或者h(yuǎn)(n),即， 1) f(n)=g(n) 只考慮搜索過(guò)的路徑已經(jīng)耗費(fèi)的費(fèi)用；/分

12、支界限算法 2）f(n)=h(n) 只考慮未來(lái)的發(fā)展趨勢(shì)/爬山算法那么可以得到兩種特殊的算法：爬山算法和分支界限算法。7/25/2022373.3.2爬山算法Procedure Hill _Climbing1 n=s2 Loop: if goal(n) then exit(success)3mi expangd(n),計(jì)算每個(gè)h(mi) nextn h(mi)最小值的節(jié)點(diǎn)4 if h(n)h(nextn) then exit(fail)5 n nextn6go loop 優(yōu)點(diǎn)，缺點(diǎn)7/25/2022383.3.3分支界限算法f(n)=g(n)Procedure Branch_Bound1 qu

13、eue(s-s),g(s)=0 /queue中保存的是從s出發(fā)的路徑。2 Loop：ifqueue=0 then exit（fail）3 pathFIRST(queue)，n LAST(pATH) /取第一條路徑，及該路徑的最后節(jié)點(diǎn)n4 if goal(n) then exit(success)5 mj expand(n), 計(jì)算g(mj)= g(n,mj) remove(s-n,queue),add(s-mj,queue) /刪除原來(lái)的路徑，添加長(zhǎng)度加一的路徑。7/25/2022396 queue隊(duì)列中分支按g值升序排列7 GO LOOP例 下圖右八城市，城市間的耗散值已經(jīng)給出，利用分支界限

14、算法給出從S到t的最佳路徑。7/25/2022407/25/2022413.3.4動(dòng)態(tài)規(guī)劃算法Procedure dynamic_Programming1 queue(s-s),g(s)=0 /queue中保存的是從s出發(fā)的路徑。2 Loop：ifqueue=0 then exit（fail）3 pathFIRST(queue)，n LAST(pATH) /取第一條路徑，及該路徑的最后節(jié)點(diǎn)n4 if goal(n) then exit(success)5 mj expand(n), 計(jì)算g(mj)= g(n,mj) remove(s-n,queue),add(s-mj,queue)7/25/2

15、02242 /刪除原來(lái)的路徑，添加長(zhǎng)度加一的路徑。6 僅保留queue中到達(dá)某一公共節(jié)點(diǎn)路徑中耗散值最小的路徑，余者刪除；queue隊(duì)列中分支按g值升序排列7 GO LOOP7/25/2022437/25/202244討論 a 動(dòng)態(tài)規(guī)劃與分支界限差別在于去掉公共路徑的冗余部分，提高效率。 b 如果問(wèn)題空間是樹(shù)結(jié)構(gòu)，動(dòng)態(tài)規(guī)劃與分支界限相同。因?yàn)閷?duì)于樹(shù)結(jié)構(gòu)不存在到達(dá)同一節(jié)點(diǎn)有多重路徑的情況。C動(dòng)態(tài)規(guī)劃 改進(jìn)的代價(jià)。比如上例中，增加一個(gè)城市。7/25/202245A算法總結(jié)1 初始狀態(tài)，open=（s）2 正常情況下（非成功非失?。?，取open中的第一個(gè)節(jié)點(diǎn)n，將n由open 轉(zhuǎn)移到closed。3

16、 擴(kuò)充節(jié)點(diǎn)n ，將新節(jié)點(diǎn)加入到open中4修改某些節(jié)點(diǎn)的路徑5 open中節(jié)點(diǎn)按照升序排列值得重視的一點(diǎn)：A算法失敗的唯一原因是open表為空7/25/202246思考題：圖中：s是起始點(diǎn) t是目標(biāo)節(jié)點(diǎn)；如果存在從s到t的一條最佳路徑。而n是最佳路徑上的一點(diǎn)。1）f*(s) f*(n) f*(t) 的關(guān)系2）如果f*(s)=10 ,g*(n)=4 問(wèn)h*(n)=?7/25/2022473.3.5 A*算法（最佳圖搜索算法）A*算法定義： 對(duì)于算法A，如果有h（n） h*（n）,即h（n）以h*（n）為上界，則稱(chēng) 該算法稱(chēng)為A*算法。如果令h（n）=0，則滿足h（n） h*（n） 這就是分支界限

17、算法 和動(dòng)態(tài)規(guī)劃算法。再令g(n)=d(n) (d(n)是節(jié)點(diǎn)深度）則f(n)=d(n);A*算法就是寬度優(yōu)先算法。寬度優(yōu)先算法能找到最佳解。 例：第二章中八數(shù)碼問(wèn)題 令h(n)=w(n)=不在位數(shù)字個(gè)數(shù)。7/25/202248算法可采納性：給定任意圖，設(shè)存在從開(kāi)始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的路徑。如果算法能夠結(jié)束在s到t的最佳路徑上，則稱(chēng)該算法是可采納的。A*是具有可采納性。定理1 對(duì)于有限圖，如果從s到t存在路徑，則A算法一定成功結(jié)束。7/25/202249推論1.1 因?yàn)锳*算法是A算法的一個(gè)特例。所以在有限圖上如果如果從s到t存在路徑，則A*算法一定成功結(jié)束。定理2 對(duì)于無(wú)限圖，如果存在s到t

18、路徑，則A*算法一定成功結(jié)束。7/25/202250推論2.1 open表中任一滿足f(n) f*(s)的節(jié)點(diǎn)n最終都將被A*選作擴(kuò)展節(jié)點(diǎn)。定理3 如果存在節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t路徑，則A*算法一定能找到最佳解結(jié)束。推論3.1 A*選來(lái)擴(kuò)展的節(jié)點(diǎn)都有f(n) f*(s)7/25/202251小結(jié) 1如果存在節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t路徑，則A*算法一定能找到最佳解結(jié)束。 2 open表中所有滿足f(n) f*(s)的節(jié)點(diǎn)n最終都將被A*選作擴(kuò)展節(jié)點(diǎn)。 3 A*選來(lái)擴(kuò)展的節(jié)點(diǎn)都有f(n) f*(s) 4 f*(s)作為A*的一個(gè)衡量上限。7/25/2022523.3.6h函數(shù)和A*算法的關(guān)系本節(jié)重點(diǎn)來(lái)討論h

19、函數(shù)（即啟發(fā)信息量）對(duì)A*算法搜索效率的影響總結(jié)。 定義：給定兩個(gè)A*算法A1 和A2，都有 f(n1)=g(n1)+h(n1) f(n2)=g(n2)+h(n2) 如果對(duì)于所有非目標(biāo)節(jié)點(diǎn)n，有h(n1) h(n2) 則算法A2 比算法A1有較多啟發(fā)信息。 討論：?jiǎn)l(fā)信息與h函數(shù)值成正比。極端情況下，完全沒(méi)有啟發(fā)信息時(shí)h=0，則此時(shí)A*算法就是寬度優(yōu)先算法。7/25/202253定理： 給定兩個(gè)A*算法A1 和A2 如果A2的啟發(fā)式信息比A1多，則在任何存在節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的路徑上，搜索結(jié)束時(shí)，由A2擴(kuò)展的每一個(gè)節(jié)點(diǎn)必定被A1擴(kuò)展。(A1擴(kuò)展的節(jié)點(diǎn)多) 注意搜索空間小，不代表能夠找到最佳解。

20、7/25/202254當(dāng)h=0時(shí)，除最下面一層節(jié)點(diǎn)外，所有節(jié)點(diǎn)都進(jìn)入closed表。求解路徑如圖紅線所示。當(dāng)考慮到h時(shí)，被擴(kuò)充的節(jié)點(diǎn)只有s、c、 j，解路徑相同7/25/2022553.37 h函數(shù)單調(diào)性限制單調(diào)性限制的作用是：避免重復(fù)計(jì)算某些節(jié)點(diǎn)的f值（主要對(duì)連通圖而言）以便減少搜索代價(jià)。單調(diào)性定義：給定一個(gè)啟發(fā)函數(shù)h，如果對(duì)于所有節(jié)點(diǎn)ni和nj (nj是ni的子節(jié)點(diǎn))，如果滿足 h(ni)-h(nj) c(ni,nj) h(t)=0,則稱(chēng)h滿足單調(diào)性限制。 上式可以寫(xiě)成h(ni)- h(nj)+ c(ni,nj)可以理解為三角不等式。 7/25/202256定理5 如果好h(n)滿足單調(diào)性限制條件，則A*算法擴(kuò)展了節(jié)點(diǎn)n之后，就找到了到達(dá)節(jié)點(diǎn)n的最佳路徑， 即：如果A*選中節(jié)點(diǎn)n，在單調(diào)性限制條件下，有g(shù)(n)=g*(n)7/25/2022573.38A*算法示例迷宮問(wèn)題給定迷宮圖如下，找出從入口到出口的最短路徑。7/25/202258解 1）綜合數(shù)據(jù)庫(kù) 定義 狀態(tài)集：（x，y）1x，y4 其中（x，y）表示任意節(jié)點(diǎn)的坐標(biāo) 所以問(wèn)題表示為求解從（1,1）到（4,4）的最短路徑。2規(guī)則集（定義4條移動(dòng)規(guī)則） 右移R1： if（x，y）then （x+1，y） 左移R2： if（x，y）then （x-1，y）7/25/202259上移