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

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