---
# System prepended metadata

title: AI Ch.3
tags: [110-2, NTNU, CSIE, 選修, AI]

---

---
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`
<!-- tag順序 [學校] [系 必選]  or  [學程 學程名(不含學程的 e.g. 大師創業)] [課程] [開課學期]-->
<!-- 網址名稱 AI110-1_[] -->
## 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')    
```
:::
