AI Ch.3 - HackMD

--- title: AI Ch.3 --- # Artificial Intelligence NTNU 人工智慧 ##### [Back to Note Overview](https://reurl.cc/XXeYaE) ##### [Back to Artificial Intelligence](https://hackmd.io/@NTNUCSIE112/AI110-2) {%hackmd @sophie8909/pink_theme %} ###### tags: `AI` `110-2` `CSIE` `選修` `NTNU`   ## Ch.03 Solving Problem by Searching ### Search algorithm 把問題當 input ，return 一個以一連串動作為形式的 solution - Search algorithm 分幾類 - General-purpose - Uniformed search - 未用到知識的搜尋 - e.g. 在一個不知道哪裡的地方到處亂走 - Informed search - 用到知識的搜尋 - e.g. 在台北往高雄知道要往南走 - Solution - 可以將 initial state(s) 轉換到 goal state(s)，的一連串動作 - e.g. 從初始狀態到目標狀態的 path - Optimal solution - e.g. cost 或拜訪 node 最少的 path ### 名詞解釋 - Frontier 一組被生成但沒有被展開的 node (leaf) ### 3.3 Searching for solution #### Searching 方法 - Tree - 沒辦法避免重複的點 - Graph - 有 explored set(closed set)(走過的) 和 frontier(open set)(要走的) - 如果當前要走的點在 explored set 中(走過)，就將其捨棄掉 #### Representation of nodes - State - Parent-node - Action - Depth - Path-cost #### 判斷 Search algorithm 的方法 - Completeness - 如果至少有一解的時候，能不能找到 - Optimality - 是否可以找到最佳解 - Time complexity - Space complexity ### 3.4 Uninformed Search - 也稱為 blind search - 不知道過程中的非目標狀態是否更有機會找到答案 #### 3.4.1 Breadth-first Search - 每個 arc cost=1 - 概念 - 選擇最淺且沒展開過的node 展開 - Implement - Frontier 是一個 FIFO 的 queue - 時間複雜度 - $O(b^d)$ b:一層展開的數量 d:層數 - Complete:當有一個解的時候會找到解 - Optimal: If each arc has cost c=1(step) - Memory 會是問題 #### 3.4.2 Dijkstra's Algorithm - 每個 arc cost>0 - path cost = 所有 arc 的 cost 的總和 - 生成一個最小 cost 的 path - Frontier 是以 cost 遞增排列 - 距離短的東西先展開 - Complete & Optimal - 在 $c\geq \varepsilon> 0$ - 否則會卡在 0-cost 的 loop - 時間與空間複雜度: $O(b^{1+C^*/\varepsilon})$ - $C^*$ 為最佳解的 cost #### 3.4.3 Depth-first Search - 概念 - 選擇 Frontier 中最深且沒展開的 node 展開 - 實作 - Frontier 為一個 LIFO 的 stack - 既不 complete 也不 optimal - 可能一直往錯誤的方向走 - 時間複雜度: $O(b^d)$ - d 為所有 path 中最深的 depth - 空間複雜度 $O(b×d)$ #### 3.4.4 Depth-limit DFS **Iterative Deepening DFS** 他說這個讚讚 ##### Depth-limit DFS 有限制深度 DFS ##### Iterative Deepening DFS 用深度 d (d=0, 1, 2...) 迭代的呼叫 dfs - 時間複雜度: $O(b^d)$ - 空間複雜度 $O(b×d)$ - 當 b 為有限時 complete - 當 path 的 cost 是一個 node 深度的非遞減函數 optimal - 當有很大的搜尋空間且答案的深度為未知時，IDS 為首選，因為 IDS 有 BFS 跟 DFS 的 best #### 3.4.5 Bidirectional Search 同時跑兩個 BFS - 一個從初始狀態開始 - 一個從目標狀態開始 - 當兩搜尋遇到時停止 ### 3.5 Informed Search - 策略 - 基於 evaluation function $f(n)$ 選擇一個看似最佳解做 exploration - $g(n)$：從初始狀態到 node n 的 path cost - $h(n)$：從 node n 到最終狀態的 estimated cost，又稱 heuristic function - e.g. 路由器距離的 estimated cost > 直線距離 #### 3.5.1 Greedy Best-First Search - 先選 h(n) 最小 #### 3.5.2 **A* Search** 他說這個讚讚 - 選 $f(n)=g(n)+h(n)$ 最小 - $h(n)\leq\text{true cost}$ - $h(n)$ 估算的越接近實際值越好 - optimal （用tree的） - complete - 時間複雜度：$O(b^d)$ - 空間複雜度：$O(b^d)$ - 空間占用是指數成長的 #### Two different Admissible Heuristics - $h_1(n)$ = total **Hamming** distance - number of misplaced tiles - $h_2(n)$ = total **Manhattan** distance - number of squares to desired location for each tile #### 3.5.3 **Lterative Deepening A* Search** 他說這個讚讚節省記憶體，因為相較bfs不需要記下所有之前的點，不會多太多運算 #### 3.5.5 Memory-bounded Heuristic Search - IDA* - RBFS - MA* - SMA* ##### IDA* - 每次迭代 DFS 都用最小的 f-cost 決定是否繼續展開或 cutoff - 下一次迭代的 f-cost 由上一次迭代的最小的 cost 決定 - optimal - complete ## 講義內容 ### Search Algorithm 這個問題可以理解為「輸入問題後在一連串動作之後回傳答案」 Formulate>Search>Execution 搜尋演算法包含 1. 一般問題 General-purpose 2. Uninformed search（未用到知識） 3. Informed search（利用已知知識） ### What is Solution？將初始狀態（initial state）轉換到目標狀態（goal state）的一連串行為 e.g. - 一條從初始狀態到目標狀態的路徑 - 最佳解（optimal solution）：最低 cost 或經過最少節點的路徑 ### 3.3 Searching For Solutions - Two Method - Tree Search - Graph Search ### p.20 實作找迷宮解 :::spoiler code ```python= import random def dfs(): #廣度優先搜尋，非遞迴版本 while True: if Queue == []: return False #無解，則立即結束 p = Queue.pop() #取出Queue中第一個節點p if p == goal: return True #有解，也立即結束 if maze[p+1] == ' ': #未走過的東邊新節點才能加入Queue Queue.append(p+1) #東邊節點放入Queue maze[p+1] = '<' #記住回去的方向 if maze[p+W+2] == ' ': #未走過的南邊新節點才能加入Queue Queue.append(p+W+2) #南邊節點放入Queue maze[p+W+2] = '^' #記住回去的方向 if maze[p-1] == ' ': #未走過的西邊新節點才能加入Queue Queue.append(p-1) #西邊節點放入Queue maze[p-1] = '>' #記住回去的方向 if maze[p-W-2] == ' ': #未走過的北邊新節點才能加入Queue Queue.append(p-W-2) #北邊節點放入Queue maze[p-W-2] = 'v' #記住回去的方向 H = 5 W = 8 #盤面高度H 寬度W maze = ['*']*(H+2)*(W+2) #建立一個外圍加一層牆壁的(H+2)X(W+2)盤面，格子全部設定為* random.seed(1238) #亂數種子固定，則接下來產生的亂數迷宮會固定，便於偵錯 for i in range(H+2): for j in range(W+2): if 1 <= i <= H and 1 <= j <= W and random.random() < 0.8: maze[i*(W+2)+j] = ' ' #有0.8機率格子設定為通路 print(maze[i*(W+2)+j], end="") print() start = W + 3 goal = H * (W+2) + W #起始點在左上角，終點在右下角 if maze[start]=='*': #若起始點危障礙，則Queue為空，必無解 Queue = [] else: #若起始點非障礙，則Queue存入起始點 Queue = [start] maze[start] = '<' if dfs(): #呼叫廣度優先搜尋法，若有解，輸出盤面每一格子回去的方向 print() for i in range(H+2): for j in range(W+2): print(maze[i*(W+2)+j], end='') print() else: #若無解，輸出'no solution' print('no solution') ``` :::