# Search Problems 搜尋問題由以下三個部分組成 - State Space - Successor function - Start State 跟 Goal Test ## State Space 「狀態的空間」，或者說你有多少狀態。 狀態是個實用的抽象概念，它可以有很多種實體化： - 例如 TSP 問題中，一個狀態可能包含當前在哪個城市，已經走過哪些城市，以及經過哪些路徑 - $(\text{current city, visited cities, paths list})$ - 或者經典的九宮格數字 puzzle 中，當前每個位置放了甚麼數字 - 又或者經典的 8 皇后問題中，當前 8 個皇后的所在位置 ## Successor function 負責定義從某個狀態，可以到哪些狀態。 這個 function 會告訴你 Action (從 A State 到 B State) 跟 Cost (這個 Action 的費用，或是其他費用) ## Start State 跟 Goal Test Start State 顧名思義就是起始狀態。 Goal Test 則是檢查當前是否為 Goal。 那甚麼是 GOAL 呢？ - 你要自己定義怎樣的狀態是 Goal 狀態 - 或者定義在怎樣的限制或情境下，就算是 Goal 任何可以從 Start State 到 Goal 的路徑，就是該 Goal 的一個 Solution。 ## State Space Graphs 就是依照各個狀態之間的關聯所構建的 Graph，通常 Edge 上有 Cost。 ## Search Trees 從 Start State 開始，展開各個可以抵達的狀態。 但有時會因為 State Space Graphs 有環，而導致無限展開。 --- # General Tree Search 如果想找到一個 Goal 的 Solution，該怎麼做？ 那就是開始「搜尋 Searching」；第一個方法是 Tree Search，也就是以某個「策略 Strategy」展開 Search Tree，來找到可以抵達 Goal 的路徑。 ## BFS & DFS 經典的搜尋演算法；不管 COST，就是分別以廣度跟深度去做展開。 遇到平手的狀況可以自己設計如何 break tie。 :::warning b 是分支度，m 是深度 ::: - DFS： - 時間複雜度：最壞是展開整棵樹，如果遇到環的話就會遇到上面說的無限展開 - 空間複雜度：每層節點會記住可分支的節點，所以是 $O(bm)$ - BFS： - 時間複雜度：因為是逐層展開，如果 Goal 的深度是 s，複雜度最差就是 $O(b^s)$ - 空間複雜度：只會記住最後一層，一樣是 $O(b^s)$ ## Uniform Cost Search / UCS 上面兩個都沒有考慮到 Cost，UCS 就是考慮了 Cost，然後每次挑 Cost 最小的節點展開。 - 如果 cheapest solution 花費是 $C^*$，並且每個 Edge 至少要 $\epsilon$ 的花費，那麼等效深度就是 $\frac{C^*}{\epsilon}$ - 時間複雜度：最差就是把每個深度都是 $\frac{C^*}{\epsilon}$ 的節點展開，$O(b^{\frac{C^*}{\epsilon}})$ - 空間複雜度：最差一樣是 $O(b^{\frac{C^*}{\epsilon}})$，記錄了最深層的每個節點 ## Greedy Search 不管路徑上的 Cost，只相信自己設計的 Heuristic Function。 ### Heuristic Function 自己設計用來評估當前狀態，到 Goal 的「預估花費」。 但是最差的情況會像是更慘的 DFS。 ## AStar Search 結合了 UCS 跟 Greedy Search，同時評估目前下來的 Cost，以及預估到 Goal 的 Cost。