產(chǎn)生式系統(tǒng)的搜索策略講義課件(PPT 68頁).ppt

08 03 2020 1 第三章產(chǎn)生式系統(tǒng)的搜索策略 狀態(tài)空間 由給定問題的所有可能的狀態(tài)組成的空間 相當(dāng)于全集G 搜索空間 按某種策略在狀態(tài)空間中選取的部分空間 G的子集 解路徑 解空間 求解問題的一條有效路徑 搜索策略的基本思路 搜索空間必須包含解路徑 如果問題有解 且盡量縮小搜索空間 搜索策略的評價(jià)準(zhǔn)則 總體費(fèi)用最低 08 03 2020 2 費(fèi)用的劃分 a規(guī)則應(yīng)用的費(fèi)用 執(zhí)行規(guī)則時(shí)所花的費(fèi)用b控制費(fèi)用 選擇規(guī)則所花的費(fèi)用 08 03 2020 3 第三章目錄 3 1回溯策略3 2圖搜索策略3 3啟發(fā)式圖搜索策略1 A算法2 爬山算法3 分支界限算法4 動態(tài)規(guī)劃算法5 A 算法 08 03 2020 4 6 h函數(shù)與A 的關(guān)系7 關(guān)于單調(diào)性限制8 A 算法示例 08 03 2020 5 3 1回溯算法 08 03 2020 6 08 03 2020 7 例四皇后問題 08 03 2020 8 定義綜合數(shù)據(jù)庫 設(shè) DATA ij 1 i j 4 其中 ij表示棋子所在行列如 24表示第二行第四列有一枚棋子因?yàn)槠灞P上可放入的棋子數(shù)為0 4個(gè)所以集合中元素?cái)?shù)位0 4個(gè) 即length DATA 0 4 08 03 2020 9 08 03 2020 10 08 03 2020 11 08 03 2020 12 08 03 2020 13 08 03 2020 14 08 03 2020 15 3 2圖搜索策略 08 03 2020 16 圖搜索策略 圖搜索的實(shí)質(zhì)是從問題空間中找出一張包含目標(biāo)節(jié)點(diǎn)的子圖 圖搜索的結(jié)果 1 一個(gè)完整的搜索圖G 2一個(gè)解路徑 用指針表示的解路徑 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é)點(diǎn)7open add open mj mj不在open closed中 08 03 2020 17 標(biāo)記mj每個(gè)到n節(jié)點(diǎn)指針確定是否需要修改已在open closed中的每個(gè)節(jié)點(diǎn)到n的指針確定是否需要修改已在closed中的每個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)原來的指針 8按照某種方式排列open表中的節(jié)點(diǎn) goloop 08 03 2020 18 08 03 2020 19 08 03 2020 20 深度優(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é)點(diǎn)7open add open mj mj不在open closed中標(biāo)記mj每個(gè)到n節(jié)點(diǎn)指針 按照節(jié)點(diǎn)深度遞減順序排列open中的節(jié)點(diǎn)8goloop 08 03 2020 21 討論1 如果問題有解 有深度優(yōu)先搜索算法 是否能夠找到解 不一定 解空間是否有限 討論2 本算法的改進(jìn)之處是open中節(jié)點(diǎn)按照深度優(yōu)先排列 但是沒有對深度加以控制 可能造成搜索代價(jià)太大 08 03 2020 22 寬度優(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é)點(diǎn)7open add open mj mj不在open closed中 08 03 2020 23 標(biāo)記每個(gè)到n節(jié)點(diǎn)指針 按照節(jié)點(diǎn)深度遞增順序排列open中的節(jié)點(diǎn)8goloop理論上可以利用寬度優(yōu)先搜索能夠找到解 如果問題有解的話 討論 寬度優(yōu)先算法和深度優(yōu)先算法可能出現(xiàn)組合爆炸 都沒有利用任何啟發(fā)式信息 所以稱為無信息搜索策略 08 03 2020 24 寬度優(yōu)先例題 由一張桌子T 三個(gè)積木A B C組成一個(gè)積木世界 初始狀態(tài)是A在B上 B在桌子上 C在桌子上 目標(biāo)狀態(tài)是 A B C依次從上到下排列在桌子上 如圖 08 03 2020 25 解 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é)上 約束條件 aX頂部必須是空的b如果Y是積木 Y的頂部必須是空的c同一種狀態(tài)出現(xiàn)不得多于一次 08 03 2020 26 1 解題過程2 open表和closed表3 節(jié)點(diǎn)樣子畫出整個(gè)圖G和解路徑4 程序何時(shí)結(jié)束5 改用深度優(yōu)先如何 08 03 2020 27 3 3啟發(fā)式圖搜索策略 基本概念啟發(fā)式圖搜索的實(shí)質(zhì)是利用啟發(fā)信息有目的地進(jìn)行搜索 減少搜索的盲目性 降低搜索空間找到最佳解啟發(fā)式信息用于解決open表中節(jié)點(diǎn)的排列次序問題 方法是利用一個(gè)評價(jià)函數(shù)計(jì)算open表中節(jié)點(diǎn)的評價(jià)函數(shù)值 按照函數(shù)值從小到大排列所有節(jié)點(diǎn) 08 03 2020 28 評價(jià)函數(shù)的目的 把最有希望得到最佳解或者解的排列在前面 路徑 給定節(jié)點(diǎn)序列 n0 n1 nk 如果該序列中的任一節(jié)點(diǎn)ni 1都有后繼節(jié)點(diǎn)ni 則該節(jié)點(diǎn)序列為從n0到nk的一條路徑 路徑長度為K路徑耗散值 路徑耗散值等于該路徑上所有相鄰節(jié)點(diǎn)間耗散值的總和 08 03 2020 29 設(shè) 路徑山任兩點(diǎn)間的耗散值為才C ni nj 則從ni到nk的路徑耗散值為C ni nj C ni nj C nj nk 最佳路徑耗散值 最佳路徑上的實(shí)際耗散值 記為 K ni nj K ni nj C ni nj 08 03 2020 30 定義幾個(gè)函數(shù)1 g n k s n 從初始節(jié)點(diǎn)s到當(dāng)前節(jié)點(diǎn)n的最佳路徑的耗散值 2 h n k n t 從當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)t的最佳路徑的好三者 3 f n g n h n 從初始節(jié)點(diǎn)s通過當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)t的最佳路徑的耗散值 08 03 2020 31 4 評價(jià)函數(shù) f n g n h n 其中f g h分別是f g h 的估計(jì)值 通常約定 f n 按照升序排列 討論 有上述定義 得 1 g n 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 稱為啟發(fā)函數(shù) 08 03 2020 32 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é)點(diǎn)計(jì)算f n mi g n mi h mi 自s經(jīng)過n mi到目標(biāo)節(jié)點(diǎn)的耗散值 08 03 2020 33 open 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é)點(diǎn)按f值升序排列8goloop 08 03 2020 34 08 03 2020 35 例八數(shù)碼問題令 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ù)碼不在位 08 03 2020 36 08 03 2020 37 對于f n g n h n 如果單獨(dú)考慮g n 或者h(yuǎn) n 即 1 f n g n 只考慮搜索過的路徑已經(jīng)耗費(fèi)的費(fèi)用 分支界限算法2 f n h n 只考慮未來的發(fā)展趨勢 爬山算法那么可以得到兩種特殊的算法 爬山算法和分支界限算法 08 03 2020 38 3 3 2爬山算法 ProcedureHill Climbing1n s2Loop ifgoal n thenexit success 3 mi expangd n 計(jì)算每個(gè)h mi nextn h mi 最小值的節(jié)點(diǎn)4ifh n h nextn thenexit fail 5n nextn6goloop優(yōu)點(diǎn) 缺點(diǎn) 08 03 2020 39 3 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é)點(diǎn)n4ifgoal n thenexit success 5 mj expand n 計(jì)算g mj g n mj remove s n queue add s mj queue 刪除原來的路徑 添加長度加一的路徑 08 03 2020 40 6queue隊(duì)列中分支按g值升序排列7GOLOOP例下圖右八城市 城市間的耗散值已經(jīng)給出 利用分支界限算法給出從S到t的最佳路徑 08 03 2020 41 08 03 2020 42 3 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é)點(diǎn)n4ifgoal n thenexit success 5 mj expand n 計(jì)算g mj g n mj remove s n queue add s mj queue 08 03 2020 43 刪除原來的路徑 添加長度加一的路徑 6僅保留queue中到達(dá)某一公共節(jié)點(diǎn)路徑中耗散值最小的路徑 余者刪除 queue隊(duì)列中分支按g值升序排列7GOLOOP 08 03 2020 44 08 03 2020 45 討論a動態(tài)規(guī)劃與分支界限差別在于去掉公共路徑的冗余部分 提高效率 b如果問題空間是樹結(jié)構(gòu) 動態(tài)規(guī)劃與分支界限相同 因?yàn)閷τ跇浣Y(jié)構(gòu)不存在到達(dá)同一節(jié)點(diǎn)有多重路徑的情況 C動態(tài)規(guī)劃改進(jìn)的代價(jià) 比如上例中 增加一個(gè)城市 08 03 2020 46 A算法總結(jié) 1初始狀態(tài) open s 2正常情況下 非成功非失敗 取open中的第一個(gè)節(jié)點(diǎn)n 將n由open轉(zhuǎn)移到closed 3擴(kuò)充節(jié)點(diǎn)n 將新節(jié)點(diǎn)加入到open中4修改某些節(jié)點(diǎn)的路徑5open中節(jié)點(diǎn)按照升序排列值得重視的一點(diǎn) A算法失敗的唯一原因是open表為空 08 03 2020 47 思考題 圖中 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問h n 08 03 2020 48 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é)點(diǎn)深度 則f n d n A 算法就是寬度優(yōu)先算法 寬度優(yōu)先算法能找到最佳解 例 第二章中八數(shù)碼問題令h n w n 不在位數(shù)字個(gè)數(shù) 08 03 2020 49 算法可采納性 給定任意圖 設(shè)存在從開始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的路徑 如果算法能夠結(jié)束在s到t的最佳路徑上 則稱該算法是可采納的 A 是具有可采納性 定理1對于有限圖 如果從s到t存在路徑 則A算法一定成功結(jié)束 08 03 2020 50 推論1 1因?yàn)锳 算法是A算法的一個(gè)特例 所以在有限圖上如果如果從s到t存在路徑 則A 算法一定成功結(jié)束 定理2對于無限圖 如果存在s到t路徑 則A 算法一定成功結(jié)束 08 03 2020 51 推論2 1open表中任一滿足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 1A 選來擴(kuò)展的節(jié)點(diǎn)都有f n f s 08 03 2020 52 小結(jié)1如果存在節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t路徑 則A 算法一定能找到最佳解結(jié)束 2open表中所有滿足f n f s 的節(jié)點(diǎn)n最終都將被A 選作擴(kuò)展節(jié)點(diǎn) 3A 選來擴(kuò)展的節(jié)點(diǎn)都有f n f s 4f s 作為A 的一個(gè)衡量上限 08 03 2020 53 3 3 6h函數(shù)和A 算法的關(guān)系 本節(jié)重點(diǎn)來討論h函數(shù) 即啟發(fā)信息量 對A 算法搜索效率的影響總結(jié) 定義 給定兩個(gè)A 算法A1和A2 都有f n1 g n1 h n1 f n2 g n2 h n2 如果對于所有非目標(biāo)節(jié)點(diǎn)n 有h n1 h n2 則算法A2比算法A1有較多啟發(fā)信息 討論 啟發(fā)信息與h函數(shù)值成正比 極端情況下 完全沒有啟發(fā)信息時(shí)h 0 則此時(shí)A 算法就是寬度優(yōu)先算法 08 03 2020 54 定理 給定兩個(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)多 注意搜索空間小 不代表能夠找到最佳解 08 03 2020 55 當(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 解路徑相同 08 03 2020 56 3 37h函數(shù)單調(diào)性限制 單調(diào)性限制的作用是 避免重復(fù)計(jì)算某些節(jié)點(diǎn)的f值 主要對連通圖而言 以便減少搜索代價(jià) 單調(diào)性定義 給定一個(gè)啟發(fā)函數(shù)h 如果對于所有節(jié)點(diǎn)ni和nj nj是ni的子節(jié)點(diǎn) 如果滿足h ni h nj c ni nj h t 0 則稱h滿足單調(diào)性限制 上式可以寫成h ni h nj c ni nj 可以理解為三角不等式 08 03 2020 57 定理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 08 03 2020 58 3 38A 算法示例 迷宮問題給定迷宮圖如下 找出從入口到出口的最短路徑 08 03 2020 59 解1 綜合數(shù)據(jù)庫定義狀態(tài)集 x y 1 x y 4 其中 x y 表示任意節(jié)點(diǎn)的坐標(biāo)所以問題表示為求解從 1 1 到 4 4 的最短路徑 2規(guī)則集 定義4條移動規(guī)則 右移R1 if x y then x