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