# Summary ## Problem-solving procedure - **Formulatet the goal** Determine what success means - **Use the goal to formulate problem** Initial state actions goal state states path cost - **Search for rhe solution** -- *state space vs. search tree* state 是一種狀態 tree 中的 node 則含括了state、parent、child 等資訊 -- *search strategies* completeness optimality: 是否為最佳解 time complexity space complpexity ## Uninformed search strategies aka. blind strategies: uses only information available in problem definition <--> *informed* or *heuristic* search: 可以知道一個非目標節點是好是壞 - *BFS* | Measurement | Value | | ----------- | ----- | | completeness | yes | | optimality | yes | | time complexity | O($b^{d+1}$) | | space complexity | O($b^{d+1}$) | cons: space too big - *Uniform-Cost Search* aka. dijkstra | Measurement | Value | | ----------- | ----- | | completeness | yes | | optimality | yes | | time complexity | O($b^{1+[C/\epsilon]}$) | | space complexity | O($b^{1+[C/\epsilon]}$) | UCS is the same as BFS when all step-costs are equal - *DFS* | Measurement | Value | | ----------- | ----- | | completeness | no | | optimality | no | | time complexity | O($b^m$) | | space complexity | O($bm$) | m = max. depth Terrible if m is much larger than d But if many solutions, then faster than BFS Much less memory than BFS - *Depth-Limited Search* Solve the infinitte-apth problem 但無法確認是不是 optimal - *Iterarive Deeping Search* combins benefits of DFS and BFS | Measurement | Value | | ----------- | ----- | | completeness | yes | | optimality | yes | | time complexity | O($b^d$) | | space complexity | O($bd$) | 看起來雖然一直重複走，但還是比BFS快，因為假設答案在樹的右下角，BFS在生node的時候連gaol下面那層都生了，而IDS則是找到goal那層而已 - *Bidirectional Search* $b^{d/2}+b^{d/2}<b^d$ (BFS) 從兩邊找，，要是問題很好 reverse 的情況才行 | Measurement | Value | | ----------- | ----- | | completeness | yes | | optimality | yes | | time complexity | O($b^{d/2}$) | | space complexity | O($b^{d/2}$) | ## Tree search vs. Graph-search garph-search 會用 list 記下走過的 node，如果再走到一次，就會直接放棄那條路徑 --> 但在BFS那種的就會出錯  ## Search with partial information