[人工智慧導論](https://app.notion.com/p/3e6fc631b0308131b213f0a3d93fe91d) › [W2（9/17）](https://app.notion.com/p/3e6fc631b0308175a433e5fa4bc500df) › 05｜影片 [1:23:14–1:43:47](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4994s)｜投影片 Ch3 p.18–26｜上一章 [04 BFS 與 UCS 搜尋（1:08–1:23）](https://app.notion.com/p/3e6fc631b030811291c5ebaf18c949df)｜下一章 [06 Greedy 與 A* 搜尋（1:56–2:11）](https://app.notion.com/p/3e6fc631b03081f7acf6d56761c8225c) ## 重點 - DFS（depth-first search，深度優先搜尋：每次都挑最深的節點往下挖）只要記一條路徑，記憶體 O(bm)，非常省；但可能在很深的錯誤分支白花 O(b^m) 的時間，不保證找得到，找到的也不一定最好。 - DFS 的兩個補救：depth-limited search 設深度上限 ℓ（知道最多幾步時好用，設錯會找不到或找到較差的解）；iterative deepening 把上限從 0、1、2 一路放寬，同時拿到 DFS 的省記憶體 O(bd) 和 BFS 的完整性，重複展開的浪費不大。 - Bidirectional search（雙向搜尋）從起點和目標兩端同時搜，兩邊 frontier 碰到就找到解，成本約 O(b^(d/2))，遠小於 O(b^d)。前提是算得出前一步是什麼：地圖、8-puzzle 可以，八皇后這種抽象目標就很難。 這章一直用、老師沒停下來解釋的詞，先在這裡講清楚： - O(…)（讀作 Big-O）：題目變大時，要花的時間或記憶體「大概長多快」，只看大方向。b 是每個節點有幾條岔路，d 是最近的答案在第幾層，m 是整棵樹最深到第幾層。O(b^d) 是 b 自己乘 d 次，層數一多就爆炸；O(bm) 只是 b 乘 m，小很多。 - complete（完備）：只要有解，就保證找得到。optimal（最佳）：找到的一定是成本最低的解。（[第 2 週 04 章](https://app.notion.com/p/3e6fc631b030811291c5ebaf18c949df)學過：這是評估搜尋法的四個指標中的兩個，另外兩個是時間和空間。） - 搜尋樹、root、state space：（[第 2 週 03 章](https://app.notion.com/p/3e6fc631b03081c8a7e0e152c12bbd25)學過：把「從起點能走的每一步」畫成往下分岔的樹，最上面的起點叫 root；所有可能狀態合起來叫 state space，狀態空間。） - frontier（[第 2 週 04 章](https://app.notion.com/p/3e6fc631b030811291c5ebaf18c949df)學過：已經看到、還沒走進去的待辦清單）。各種搜尋法的差別，就是待辦清單裡先拿誰。 - BFS 與 UCS（[第 2 週 04 章](https://app.notion.com/p/3e6fc631b030811291c5ebaf18c949df)學過：BFS 一層一層往外掃，第 1 層全看完才看第 2 層；UCS 每次挑目前累積成本最低的路往下走）。這章的 DFS 家族就是拿來跟它們比。 - 羅馬尼亞地圖、8-puzzle、八皇后（[第 2 週 03 章](https://app.notion.com/p/3e6fc631b03081c8a7e0e152c12bbd25)學過：課本的三個範例問題——在地圖上找路、九宮格滑塊拼圖、在棋盤上放 8 個互不攻擊的皇后）。 ## Exam-ready - **Depth-first search (DFS)**: "Expands the deepest node in the current frontier of the search tree."（Ch3 p.18） - 中文：DFS 在目前的 frontier（邊界，已生出但還沒展開的節點）裡，永遠挑最深的那一個來展開。白話：一路往下挖到底，不是目標才退回來換別的路。 - **DFS time**: "The time complexity of depth-first graph search is bounded by the size of the state space. A depth-first tree search, on the other hand, may generate all of the O(b^m) nodes in the search tree, where m is the maximum depth of any node. m can be much larger than d (the depth of the shallowest solution)."（Ch3 p.19） - 中文：DFS 樹搜尋最糟時會生出 O(b^m) 個節點（b：分支數 branching factor；m：整棵樹最深節點的深度）。m 可能遠比 d（最淺解的深度）大，因為 DFS 可能先把很深的錯誤分支走完，才輪到很淺的正解。白話：答案明明很近，DFS 卻可能先繞一大圈遠路。 - **DFS space**: "A depth-first tree search needs to store only a single path from the root to a leaf node, along with the remaining unexpanded sibling nodes for each node on the path. … DFS requires storage of only O(bm) nodes."（Ch3 p.20） - 中文：DFS 只需要記住從 root（根節點，起點）到目前節點的這一條路徑，再加上路徑上每個節點還沒展開的兄弟節點，總共只要 O(bm) 個節點。白話：不用整棵樹都記住，只要記「目前這條路」就好，比 BFS 省記憶體很多。 - **Depth-limited search**: "Supply depth-first search with a predetermined depth limit ℓ" · "Incompleteness" · "Nonoptimal" · "any city can be reached from any other city in at most 9 steps, i.e., ℓ = 9 leads to a more efficient depth-limited search."（Ch3 p.21） - 中文：給 DFS 一個事先定好的深度上限 ℓ（最多走幾層），到了就回頭換別的分支。缺點是「不完備」（incompleteness：解太深會永遠找不到）和「非最佳」（nonoptimal：找到的不一定最好）；如果知道任兩城市最多 9 步就能到，把 ℓ 設成 9 既不會漏解、又比亂設更有效率。 - **Iterative deepening**: "Iterative deepening search (or iterative deepening depth-first search) is a general strategy, often used in combination with depth-first tree search, that finds the best depth limit. It does this by gradually increasing the limit—first 0, then 1, then 2, and so on—until a goal is found. … Like DFS, its memory requirements are modest: O(bd) to be precise. Like BFS, it is complete when the branching factor is finite and optimal when the path cost is a nondecreasing function of the depth."（Ch3 p.22） - 中文：反覆用不同的深度上限重跑 depth-limited search：上限先設 0，找不到就設 1、再設 2……直到找到目標為止。它跟 DFS 一樣省記憶體（O(bd)）；也跟 BFS 一樣：分支數有限時一定找得到解，而且在每步成本不遞減（non­decreasing，越走越深成本不會變低）時能找到最佳解。白話：不知道解多深時，一層一層慢慢試，兼顧省記憶體跟找得到答案兩個優點。 - **When to use it**: "In general, iterative deepening is the preferred uninformed search method when the search space is large and the depth of the solution is not known."（Ch3 p.23，老師沒念） - 中文：搜尋空間很大、又不知道解在多深的地方時，iterative deepening 是最推薦的無資訊搜尋（uninformed search，除了問題定義沒有其他線索的搜尋）方法。白話：不知道要挖多深，就用這個方法最保險。 - **Repeated generation**: "Iterative deepening search may seem wasteful because states are generated multiple times. It turns out this is not too costly. The reason is that in a search tree with the same (or nearly the same) branching factor at each level, most of the nodes are in the bottom level, so it does not matter much that the upper levels are generated multiple times."（Ch3 p.24）【老師強調】(1:35:43) - 中文：Iterative deepening 每一輪都要從頭重新生成上面幾層的節點，看起來很浪費，其實代價不大。原因是同一層的分支數差不多時，大部分節點都集中在最底層，上面各層加起來也沒有很多，所以重複生成它們的成本相對很小。 - **Bidirectional search**: "Run two simultaneous searches—one forward from the initial state and the other backward from the goal—hoping that the two searches meet in the middle. The motivation is that b^(d/2) + b^(d/2) is much less than b^d" · "implemented by replacing the goal test with a check to see whether the frontiers of the two searches intersect"（Ch3 p.25） - 中文：同時跑兩個搜尋——一個從起點往前搜、一個從目標往回搜，希望兩邊在中間碰到。這樣做的理由是 b^(d/2) + b^(d/2) 遠比 b^d 小很多。實作上不是檢查有沒有到目標，而是改成檢查兩邊的 frontier 有沒有交集。白話：兩頭一起挖，比一頭挖到底快很多。 - **Predecessors**: "How to search backward? This is not easy. Let the predecessors of a state x be all those states that have x as a successor. Bidirectional search requires a method for computing predecessors. When all the actions in the state space are reversible, the predecessors of x are just its successors." · "For the 8-puzzle and for finding a route in Romania, there is just one goal state, so the backward search is very much like the forward search. If the goal is an abstract description, such as the goal that “no queen attacks another queen”, then bidirectional search is difficult to use."（Ch3 p.26） - 中文：往回搜需要算出一個狀態 x 的 predecessors（前驅：所有能走到 x 的狀態）。當所有動作都可逆（reversible，能走回去）時，x 的前驅就等於它的後繼，跟往前搜一樣容易。地圖和 8-puzzle（九宮格滑塊拼圖）只有一個明確目標盤面，往回搜跟往前搜差不多；但像八皇后這種目標只是一句抽象規則（沒有唯一盤面），就很難算出「前一步是什麼」，所以難用。 ## [1:23:14](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4994s) DFS：一條路走到底 DFS 每次都從 frontier（邊界：已經生出來、還沒展開的節點）裡挑最深的那一個來展開（expand：把它所有的下一步都生出來）。所以它從 root（根節點，也就是起點）沿著第一個分支一路往下，走到最底層；不是目標，就退回上一層，換下一個還沒走過的分支。下圖的目標是 M：DFS 先把左邊 B 底下全部走完，才輪到右邊的 C。 [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\ai_ch3_p018.png | DFS 在二元樹上找 M：先把 B 底下走到底，才回頭走 C（Ch3 p.18）]] 圖上重點： - Uninformed Search Strategies：無資訊搜尋策略（這頁講其中的 DFS）。 - Depth-first search (DFS)：深度優先搜尋。 - Expands the deepest node in the current frontier of the search tree：每次都展開 frontier 裡最深的那個節點。 - 圖怎麼看：12 小格照時間順序，從左到右、從上到下。三角形指著的是下一個要展開的節點；有外框的圓是 frontier（待辦清單）；灰色實心是已經展開過的；淡色虛線是還沒生出來的。 - 左邊子樹走完後，那些節點會從圖上消失，代表 DFS 不用再記它們，這就是 DFS 省記憶體的原因。 下面第一個摺疊用這棵樹把 DFS 一步一步走一遍。算出來的意思是：DFS 要拿 12 個節點才找到 M，而右邊的 C 一直被晾到最後。
在投影片那棵樹上手算一次，DFS 到底怎麼走？ DFS 的 frontier 是堆疊（stack，LIFO：最後放進去的最先拿出來）。每步從最前面拿一個節點，不是目標就把子節點放到最前面。每一步寫的是拿完之後的堆疊，左邊是最前面。 1. 拿 A，堆疊變成 B, C 2. 拿 B，堆疊變成 D, E, C 3. 拿 D，堆疊變成 H, I, E, C 4. 拿 H、I（第 3 層沒有子節點），剩 E, C 5. 拿 E，堆疊變成 J, K, C；再拿 J、K，剩 C 6. 拿 C，堆疊變成 F, G 7. 拿 F，堆疊變成 L, M, G；拿 L；拿 M：是目標，結束。 共拿了 12 個節點。右邊的 C 從第 1 步就在堆疊裡，一直等到左邊全部走完才輪到它。
老師原話是什麼？ 「我一條路走到黑」(1:23:26)
## [1:24:17](https://www.youtube.com/watch?v=hNZQIO0q74o&t=5057s) DFS 的代價：時間可能很差，空間很省 時間方面，最糟時 DFS 會生出 O(b^m) 個節點：b 是分支數，m 是整棵樹最深的深度。m 可能比 d（最淺的解的深度）大很多：解明明在右邊很淺處，DFS 卻先把左邊很深的樹掃完。空間方面，DFS 只要記目前這條路徑，加上路徑上每個節點還沒展開的兄弟，只要 O(bm) 個節點，遠比 BFS 的 O(b^d) 省。
要先懂什麼：b、d、m 和 Big-O 各代表什麼？ 老師說「這個理論上大家應該都學過了」(1:28:02)，這裡補短版： - Big-O（大 O 符號）：只看規模變大時成長得多快，不管常數。例如 3·b^d + 5 寫成 O(b^d)。 - b（branching factor，分支數）：每個節點有幾個子節點。d：最淺的解在第幾層。m：整棵樹最深到第幾層，可能無限深。 - b^d 是指數成長：b = 10 時，每深一層節點數乘 10。
下一個摺疊用小數字證明上面那段話。結論是：答案只在第 2 層時，DFS 可能先白走 1,023 個節點，BFS 只要約 6 個，所以時間可能差很多；但同一時間 DFS 只要記 7 個左右的節點，BFS 要記整層，所以空間省很多。
用例子各算一次，DFS 的時間和空間到底差多少？ 時間最糟的例子：b = 2 的樹，root 左邊的子樹一路長到第 10 層（m = 10），右邊子節點底下第 2 層就是解（d = 2）。DFS 先鑽左邊，要生完左子樹 1 + 2 + … + 512 = 1,023 個節點才輪到右邊；BFS 掃到第 2 層、約 6 個節點就找到。這就是 O(b^m) 對 O(b^d)：2^10 對 2^2。 空間的例子（上一段的樹，b = 2、m = 3）：DFS 剛展開 D 時，要記路徑 A、B、D 加上堆疊裡的 H、I、E、C，共 7 個，剛好是 b·m + 1。老師舉例時列了 A、B、D、I、E（1:27:09）；照 p.20 的定義，B 還沒展開的兄弟 C 也要記。 放大來看：用 p.15 的設定（b = 10、每個節點 1,000 bytes），深度 16 時 BFS 要 10 exabytes，DFS 只要約 160 個節點＝160 KB。
DFS 會不會永遠找不到？tree search 和 graph search 差在哪？ p.19 把 DFS 分成兩種版本： - tree search（樹搜尋）：不記得走過哪些狀態。在羅馬尼亞地圖上可能從 Arad 到 Sibiu、又回 Arad、再到 Sibiu……永遠繞圈，所以不 complete。 - graph search（圖搜尋）：多記一份已展開過的狀態（explored set），走過的不再走。狀態有限時終究會走完，時間上限就是狀態總數（p.19 的 "bounded by the size of the state space"），代價是空間不再只有 O(bm)。 狀態無限多時，兩種版本都可能一路往下走不回來。DFS 回傳最先碰到的解，所以也不 optimal。
老師原話是什麼？ 「你會花很多的時間去展開左邊很深的樹」(1:25:56) 「DFS呢至少不太花Memory」(1:27:01)
## [1:28:06](https://www.youtube.com/watch?v=hNZQIO0q74o&t=5286s) Depth-limited search：替 DFS 設深度上限 為了不讓 DFS 在很深的錯誤分支上白花時間，可以給它一個事先定好的深度上限 ℓ：照樣跑 DFS，但最多只往下走 ℓ 層，到了就回頭看別的分支。這叫 depth-limited search（深度受限搜尋）。老師用現在的 AI agent 比喻：agent 用 DFS 做事，會把第一種方法的細節全試完才換方法，跑很久甚至鬼打牆。
老師的 AI agent 比喻在說什麼？ 你交代 AI agent 一件工作：有 3 種方法；每種方法有 3 種子策略，每種子策略有 3 種 input 方式，每種 input 有 3 種參數設定。這是 b = 3、深度 4 的樹，光方法 1 底下就有 27 種組合。 笨笨地用 DFS，要把方法 1 的 27 種組合全部試完才會看方法 2；假如正解是方法 2 的第一種組合，前面 27 次都白做。老師說早期的 agent 常這樣鬼打牆（他也說不知道現在的產品實際怎麼做）。設深度上限，就是規定每條路最多試到第 ℓ 層就回頭。
老師原話是什麼？ 「你是跑DFS沒有錯 但是呢你給它一個限制 你往下搜尋 你最多就搜尋L這麼多層」(1:28:42) 「我相信你們應該很快就會覺得說 他怎麼跑那麼久」(1:30:22)
## [1:31:26](https://www.youtube.com/watch?v=hNZQIO0q74o&t=5486s) 深度上限的代價與領域知識 深度上限有兩個代價。第一，解比 ℓ 深就永遠找不到，所以不 complete（complete：只要有解就保證找得到）。第二，找到的不一定是最好的解，所以 nonoptimal。有領域知識時，就能把 ℓ 設得剛好：羅馬尼亞地圖上任兩個城市之間最多 9 步，設 ℓ = 9 就不會漏解，又比亂設有效率。 下一個摺疊用第一段那棵樹示範兩個代價：ℓ 設太小，明明有解卻回報找不到；ℓ 夠大，也可能先找到一條比較遠的解。
ℓ 設太小或設夠大時，各會出什麼問題？ 用第一段那棵樹： - ℓ 太小：目標 M 在第 3 層，設 ℓ = 2。DFS 走完 A, B, D, E, C, F, G 就停，回報找不到。明明有解卻找不到，這就是 incomplete。 - ℓ 夠大，解卻不是最好的：假設 J（第 3 層）和 C（第 1 層）都是目標，設 ℓ = 3。DFS 走 A, B, D, H, I, E, J 就停，回報 3 步的路；但到 C 只要 1 步，這就是 nonoptimal。
羅馬尼亞的 9 步是怎麼來的？ 地圖上有 20 個城市，任何不繞圈的路最多 19 步，所以 ℓ = 19 一定安全。但任兩城之間的最少步數其實最多只有 9，最遠的一對是 Lugoj 到 Neamt：Lugoj 經 Mehadia、Drobeta、Craiova、Pitesti、Bucharest、Urziceni、Vaslui、Iasi 到 Neamt，共 9 步（我用程式驗算過）。課本把這個數字叫做 state space 的 diameter（直徑）。
老師原話是什麼？ 「所以如果是Depth Limit Search 他就是Incomplete」(1:31:26) 「你就可以把你的深度的限制設定成9」(1:32:30)
## [1:32:49](https://www.youtube.com/watch?v=hNZQIO0q74o&t=5569s) Iterative deepening：上限一層一層放寬 不知道 ℓ 要設多少就不要猜：先設 ℓ = 0 跑一次 depth-limited search，找不到就設 ℓ = 1 從頭再跑，再設 ℓ = 2……直到找到為止。這叫 iterative deepening（逐步加深）。它像 DFS 一樣只要 O(bd) 的記憶體；又像 BFS 一樣，分支數有限就一定找得到，且在路徑成本是深度的非遞減函數時（最常見：每一步成本都一樣）找到最佳解。搜尋空間大、又不知道解多深時，它是首選。 **注意：老師口頭說上限從 1 開始（1:34:25），投影片 p.22 是從 0 開始（limit 0 只檢查 root）。老師把 "nondecreasing function of the depth" 解釋成多走一步成本就會增加（1:34:10），這樣太寬，見下方摺疊。考試寫投影片的版本。** [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\ai_ch3_p023.png | Iterative deepening 在二元樹上找 M：limit 0、1、2 都沒找到，limit 3 才找到（Ch3 p.23）]] 圖上重點： - Iterative deepening DFS：逐步加深的 DFS。 - 左邊那句：搜尋空間很大、又不知道解有多深時，iterative deepening 通常是最好的無資訊搜尋方法。 - Limit = 0、1、2、3：深度上限分別是 0、1、2、3 的四輪，每一輪都從 A 重新開始。 - Figure 3.19 Four iterations of iterative deepening search on a binary tree：在二元樹上跑四輪 iterative deepening。 - 圖怎麼看：黑色實心是這一輪已經走完、可以忘掉的節點；要到最後一列 Limit = 3 才碰到 M。 下面第一個摺疊把四輪一一數出來。算出來的意思是：總共碰了 23 個節點，比純 DFS 的 12 個多，多出來的全是前幾輪重做的上層，這就是下一段要談的「浪費」。第二個摺疊說明它什麼時候保證找到最佳解：每一步成本都一樣時最穩；用公里當成本時，步數最少的路不一定最便宜。
在同一棵樹上手算一次，iterative deepening 到底怎麼跑？ 目標 M 在第 3 層。每一輪都從 A 重新開始： - limit 0：A（1 個） - limit 1：A, B, C（3 個） - limit 2：A, B, D, E, C, F, G（7 個） - limit 3：A, B, D, H, I, E, J, K, C, F, L, M，找到了（12 個） 總共碰了 1 + 3 + 7 + 12 = 23 個節點，純 DFS 只要 12 個，多的是前三輪重做的部分。記憶體是 O(bd) 而非 O(bm)，因為最後一輪的上限就是 d，不會走到比 d 更深。
路徑成本是深度的非遞減函數，到底是什麼意思？ 意思是：越深的節點，路徑成本一定不比較淺的節點低。最常見的是每一步成本都一樣，這時步數最少就等於成本最低。 只要求每一步成本是正的還不夠。羅馬尼亞地圖用公里當成本時，limit 3 先找到 Arad 經 Sibiu、Fagaras 到 Bucharest（3 步，140 + 99 + 211 = 450 公里）；但最便宜的是 Arad 經 Sibiu、Rimnicu Vilcea、Pitesti 到 Bucharest（4 步，140 + 80 + 97 + 101 = 418 公里）。這裡多走一步成本確實會增加，但步數少的路反而貴，所以不保證最佳。
老師原話是什麼？ 「那就是我逐步的增加我的深度」(1:33:02) 「它其實這種做法呢 就有點混合了DFS跟BFS的好處」(1:33:38)
## [1:34:47](https://www.youtube.com/watch?v=hNZQIO0q74o&t=5687s) 重複展開其實不太浪費 Iterative deepening（IDS）每一輪都從 root 重做，上面幾層被生成好幾次，看似浪費。但每層分支數差不多時，大部分節點都在最底層，上面各層加起來還比最底層少，所以重做的成本不大。老師的例子：二元樹的上限從 2 提高到 3 時，重做的第 1、2 層只有 6 個節點，新的第 3 層就有 8 個；樹越深，差距越大。下表用 b = 10、d = 5 算一次（不算 root）：
深度這層節點數IDS 生成幾次IDS 小計BFS 小計
11055010
21004400100
31,00033,0001,000
410,000220,00010,000
5100,0001100,000100,000
合計**123,450****111,110**
IDS 只比 BFS 多生成約 11%，記憶體卻從 O(b^d) 降到 O(bd)。 怎麼讀這張表：每一列是一層。IDS 每加深一輪就從頭重做，所以越上層被生成越多次（第 1 層 5 次、最底層 1 次）；但上層節點很少，乘了好幾次加起來還是比最底層小。下一個摺疊說明為什麼最底層一定佔大多數：每往下一層，節點就乘 b 倍，所以最後一層比上面全部加起來還多。
為什麼最底層會佔大多數？ 每往下一層，節點數乘 b。第 d 層有 b^d 個；上面所有層加起來是 (b^d − 1)/(b − 1)，比 b^d 還少。 - b = 2、d = 3：最底層 8 個，上面 1 + 2 + 4 = 7 個，最底層剛好超過一半。 - b = 10、d = 5：最底層 100,000 個，上面加起來 11,111 個，最底層佔 90%。 一般公式：IDS 生成的節點數 = d·b + (d−1)·b^2 + … + 1·b^d，仍是 O(b^d)。樹越深，IDS 對 BFS 的倍數越接近 b/(b−1)：b = 10 約 1.11 倍，b = 2 最多約 2 倍。
老師原話是什麼？ 「對的確是有一點浪費 但是沒有到你想像中的那麼浪費」(1:35:43)
## [1:38:02](https://www.youtube.com/watch?v=hNZQIO0q74o&t=5882s) Bidirectional search：兩端同時挖 如果目標只有一個，也可以把目標當成另一個出發點：一邊從起點往前搜，一邊從目標往回搜，兩邊在中間碰到就把路接起來。老師用雪山隧道比喻：宜蘭、臺北兩端同時開挖，最後在中間接通。實作上，它不檢查是否抵達目標，而是檢查兩邊的 frontier 有沒有交集。每邊只要搜約 d/2 層，成本約 b^(d/2) + b^(d/2) = O(b^(d/2))，比單向的 O(b^d) 小非常多。但往回搜不一定容易：要算得出「上一步可能是什麼」。地圖和 8-puzzle 做得到，八皇后這種目標只是一句抽象描述的問題就很難用。 下一個摺疊在羅馬尼亞地圖上實際跑一次。算出來的意思是：兩邊各長一兩層就在 Fagaras 碰頭，只看了十幾個城市；換成大數字（b = 10、d = 6），雙向約 2,000 個節點、單向約 1,000,000 個。
從 Arad 到 Bucharest 手算一次，兩邊怎麼碰頭？ 兩邊各用 BFS，輪流長一層： 1. 往前第 1 層（Arad 的鄰居）：Zerind, Sibiu, Timisoara。 2. 往回第 1 層（Bucharest 的鄰居）：Fagaras, Pitesti, Giurgiu, Urziceni。沒有交集。 3. 往前第 2 層：Oradea, Fagaras, Rimnicu Vilcea, Lugoj。Fagaras 兩邊都有，碰到了。 4. 接起來：Arad 經 Sibiu、Fagaras 到 Bucharest，3 步。這是步數最少、不是公里數最少的路（418 公里那條要 4 步）。 數字放大：b = 10、d = 6 時，單向約 10^6 = 1,000,000 個節點，雙向約 2 × 10^3 = 2,000 個，差 500 倍。
往回搜為什麼不容易？ 往回搜要算得出一個狀態 x 的 predecessors（前驅：下一步可以走到 x 的所有狀態）。 - 羅馬尼亞地圖：路是雙向的，動作都能反過來做，x 的前驅就是 x 的鄰居，往回搜跟往前搜一樣。 - 8-puzzle（九宮格滑塊拼圖）：方塊可以滑回去，目標盤面只有一個，一樣容易。 - 八皇后（在西洋棋盤上放 8 個皇后）：目標只是一句抽象描述（沒有任何皇后互相攻擊），符合的盤面有 92 種，不知道從哪個盤面開始往回推，所以很難用。
老師原話是什麼？ 「我可不可以把目標也當成是一個出發點」(1:38:32) 「兩端同時從宜蘭往臺北方向 臺北往宜蘭方向 兩端同時蓋 然後最後接起來這樣子」(1:39:08) 「你從你的目的地出發 往回找這件事情 不見得容易」(1:40:28)
## [1:41:56](https://www.youtube.com/watch?v=hNZQIO0q74o&t=6116s) 前半總結：uninformed search 六種方法比一比 Ch3 前半到這裡講完，全是 uninformed search（無資訊搜尋：除了問題定義，沒有離目標還多遠的線索）。下半講 informed search：多知道一些額外資訊，找解的效率會高很多（下一章）。下課前老師回答分組：組員退選可以併到還沒滿 4 人的組，每組最多 4 人。下表把這章和上一章的方法放在一起比：
方法Complete?Optimal?TimeSpace
BFS是 (a)是 (c)O(b^d)O(b^d)
Uniform-cost是 (a)(b)是O(b^(1+⌊C*/ε⌋))同 Time
DFS否否O(b^m)O(bm)
Depth-limited否否O(b^ℓ)O(bℓ)
Iterative deepening是 (a)是 (c)O(b^d)O(bd)
Bidirectional是 (a)(d)是 (c)(d)O(b^(d/2))O(b^(d/2))
怎麼讀這張表：Complete 欄問「有解一定找得到嗎」，Optimal 欄問「找到的一定最便宜嗎」；Time、Space 欄的 O(…) 越小越好，次方上的字母（d、m、ℓ、d/2）越小越省。考試最常比的是：DFS 空間最省但不完備；iterative deepening 同時拿到 BFS 的完備、最佳和 DFS 的省空間；bidirectional 把次方砍一半。UCS 那格的 C*/ε 是「最佳解總成本 ÷ 最小一步成本」，大約等於最佳解要走幾步，看不懂可以略過。下一個摺疊說明表裡 (a)(b)(c)(d) 的成立條件。
表格裡的 (a)(b)(c)(d) 是什麼條件？ 整理自課本 Ch3 的比較表，投影片沒有這頁。(a) 分支數 b 有限；(b) 每一步成本至少是某個正數 ε；(c) 每一步成本都一樣；(d) 兩個方向都用 BFS。C* 是最佳解的成本。DFS 列的否，指 tree search 或狀態無限多的情況。
老師原話是什麼？ 「你如果知道一些額外的資訊的話 你的找到解答的這個效率會很高」(1:42:17) 「反正不管怎麼樣 變來變去動來動去 就是最多四個人一組」(1:43:32)
## Self-check
Q1. Explain why depth-first tree search needs only O(bm) memory while its time complexity is O(b^m). Why can m be much larger than d?（中文：為什麼 DFS 的樹搜尋只需要 O(bm) 的記憶體，時間複雜度卻是 O(b^m)？為什麼 m 可能遠大於 d？） **Answer**: DFS stores only a single path from the root to a leaf, plus the remaining unexpanded siblings of each node on the path: about b nodes per level for m levels, O(bm). In the worst case it generates all O(b^m) nodes, e.g. when a shallow solution lies in the branch explored last. m is the maximum depth of any node; one very deep branch makes m ≫ d. 中文：DFS 省空間，是因為它只需要記住從 root 到目前節點的一條路徑，再加上路徑上每個節點還沒展開的兄弟節點——每層大約 b 個、共 m 層，所以是 O(bm)。但最糟情況下，它可能把整棵樹的節點都生出來，也就是 O(b^m)，例如淺處的正解剛好在 DFS 最後才走到的分支裡。m 是整棵樹裡最深節點的深度，只要有一條路特別長，m 就會遠比最淺解的深度 d 大很多。
Q2. State two weaknesses of depth-limited search. How can knowledge of the problem help choose the limit? Use the Romania map as an example.（中文：說出 depth-limited search 的兩個缺點。知道問題的背景知識可以怎麼幫忙設定深度上限？用羅馬尼亞地圖當例子。） **Answer**: If ℓ < d, the goal is never found (incomplete); it may also return a deeper, more expensive solution first (nonoptimal). Since any city in Romania can be reached from any other in at most 9 steps, ℓ = 9 never misses a solution and is much smaller than the naive bound of 19. 中文：如果 ℓ 比解的深度 d 小，就永遠找不到解，這叫「不完備」；就算找到解，也可能不是最短的那一個，這叫「非最佳」。因為知道羅馬尼亞地圖上任兩個城市之間最多只要 9 步就能到，把 ℓ 設成 9 就一定不會漏掉答案，又比隨便設一個很大的上限（例如 19）有效率。
Q3. Iterative deepening generates upper-level nodes many times. Show that this is not too costly for b = 10 and d = 5, and state its space complexity, completeness and optimality.（中文：Iterative deepening 會把上面幾層的節點重複生成很多次。用 b = 10、d = 5 算出這樣做其實沒有很浪費，並說出它的空間複雜度、完備性和最佳性。） **Answer**: N(IDS) = 5·10 + 4·100 + 3·1,000 + 2·10,000 + 1·100,000 = 123,450 versus N(BFS) = 111,110, only about 11% more, because most nodes are in the bottom level. Memory O(bd) like DFS; complete when b is finite and optimal when path cost is a nondecreasing function of depth, like BFS. 中文：把每一輪重新生成的節點數加起來，IDS 總共要生成 5×10 + 4×100 + 3×1,000 + 2×10,000 + 1×100,000 = 123,450 個節點，而 BFS 只需要生成 111,110 個。IDS 只比 BFS 多了約 11%，因為大部分節點都集中在最底層，重複生成上面幾層的代價相對很小。它的記憶體是 O(bd)，跟 DFS 一樣省；分支數有限時一定找得到解（complete）；每一步成本不遞減時（最常見是每步成本相同）能找到最佳解（optimal），這兩點跟 BFS 一樣。
Q4. What is the motivation for bidirectional search, how is the goal test changed, and why is it difficult to use for the 8-queens problem?（中文：Bidirectional search 的動機是什麼？目標測試怎麼改？為什麼用在八皇后問題上很困難？） **Answer**: b^(d/2) + b^(d/2) is much less than b^d (b = 10, d = 6: 2,000 versus 1,000,000). The goal test is replaced by a check whether the frontiers of the two searches intersect. Searching backward requires computing predecessors: easy with reversible actions and one goal state (Romania, 8-puzzle), but the 8-queens goal is an abstract description with no single state to search back from. 中文：因為 b^(d/2) + b^(d/2) 遠比 b^d 小得多（例如 b = 10、d = 6 時，是 2,000 對 1,000,000），所以從起點和目標兩端同時搜尋可以省下大量時間。做法上不是檢查有沒有走到目標，而是檢查兩邊的 frontier 有沒有交集，交集到了就代表兩邊接上了。八皇后的目標只是一句抽象規則（沒有任何皇后互相攻擊），符合條件的盤面有 92 種，不知道該從哪個盤面開始往回推，所以很難算出「前一步是什麼」，也就很難做往回搜。
讀完了嗎？下一章：[06 Greedy 與 A* 搜尋（1:56–2:11）](https://app.notion.com/p/3e6fc631b03081f7acf6d56761c8225c)｜回到週頁：[W2（9/17）](https://app.notion.com/p/3e6fc631b0308175a433e5fa4bc500df)