[人工智慧導論](https://app.notion.com/p/3e6fc631b0308131b213f0a3d93fe91d) › [W2（9/17）](https://app.notion.com/p/3e6fc631b0308175a433e5fa4bc500df) › 04｜影片 [1:08:52–1:23:14](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4132s)｜投影片 Ch3 p.11–17｜上一章 [03 搜尋問題的定義（0:53–1:08）](https://app.notion.com/p/3e6fc631b03081c8a7e0e152c12bbd25)｜下一章 [05 DFS 家族與雙向搜尋（1:23–1:43）](https://app.notion.com/p/3e6fc631b03081bda674f874680e4a09) 跳過提示：(1:14:34–1:17:20) 老師在算 BFS 的時間與記憶體複雜度公式和具體數字範例，聽不懂可以直接跳到 [1:17:20](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4640s)，接著講「Dijkstra Algorithm（Uniform Cost Search）這個演算法的名字」。 跳過的這段在做什麼（白話）：老師在估算 BFS 要看多少個節點、要記住多少個節點。結論只有一句：答案每深一層，工作量和記憶體都乘上 b 倍，層數一多電腦就撐不住。 跳過提示：(1:19:00–1:20:50) 老師在算 Uniform Cost Search 的路徑成本數字範例，聽不懂可以直接跳到 [1:20:50](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4850s)，接著講「Uniform Cost Search 的特點：會把已經走的成本考慮進去」。 跳過的這段在做什麼（白話）：老師在地圖上把兩條路線的里程加起來比大小（經 Fagaras 是 310，經 Rimnicu Vilcea 和 Pitesti 是 278），說明 UCS 最後會挑累積里程較少的 278 那條。 ## 重點 - 評一個搜尋演算法看四件事：completeness（有解時保證找得到嗎）、optimality（找到的是不是最好的解）、time complexity（要花多久）、space complexity（要佔多少記憶體）。 - Uninformed search（無資訊搜尋）只知道題目給的資訊，各種方法只差在「先展開哪個節點」。BFS 一層一層展開，時間和空間都是 O(b^d)（b 是每個節點的分支數，d 是最淺的解在第幾層），記憶體通常比時間先撐不住。 - Uniform-cost search（UCS，理論資工叫 Dijkstra's algorithm）每次展開累積成本 g(n) 最小的節點，展開時才檢查目標，所以找得到最便宜的路；每步成本都一樣時就跟 BFS 一樣。 ## Exam-ready - **Completeness**: "Is the algorithm guaranteed to find a solution when there is one?"（Ch3 p.11） - 中文：Completeness（完備性）問的是——只要問題有解，這個演算法保證找得到嗎？白話：不保證一定找到解的方法，就不算 complete。 - **Optimality**: "Does the strategy find the optimal solution?"（Ch3 p.11） - 中文：Optimality（最佳性）問的是——這個策略找到的解，是不是成本最低的那一個？白話：光找得到還不夠，還要是最好的那個。 - **Time / space complexity**: "How long does it take to find a solution?" / "How much memory is needed to perform the search?"（Ch3 p.11） - 中文：Time complexity（時間複雜度）問要花多久才找得到解；space complexity（空間複雜度）問過程中最多要同時記住多少節點。白話：一個看花多少時間，一個看佔多少記憶體。 - **Uninformed search**: "Uninformed search (also called blind search) … The strategies have no additional information about states beyond that provided in the problem definition. All they can do is generate successors and distinguish a goal state from a non-goal state."（Ch3 p.12）【老師強調】(1:21:07) - 中文：Uninformed search（無資訊搜尋，也叫 blind search 盲目搜尋）手上只有題目定義給的資訊，能做的只有兩件事：產生下一步的節點（generate successors）、判斷是不是終點（goal test）。白話：完全不知道哪個方向比較接近目標，只能按規則展開。 - **Search order**: "All search strategies are distinguished by the order in which nodes are expanded."（Ch3 p.12） - 中文：所有搜尋策略的差別，只在於「展開節點的順序」不一樣。白話：方法不同，比的就是先看誰、後看誰。 - **Informed search**: "Strategies that know whether one non-goal state is “more promising” than another are called informed search or heuristic search strategies."（Ch3 p.12） - 中文：Informed search（有資訊搜尋，也叫 heuristic search 啟發式搜尋）多了一份額外資訊，知道哪個非目標狀態「比較有希望」。白話：比 uninformed 多了一個「感覺離目標比較近」的線索。 - **Breadth-first search**: "The root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on."（Ch3 p.13） - 中文：BFS 先展開根節點（root），再展開 root 所有子節點，然後才輪到孫節點，一層一層往外展開。白話：像剝洋蔥，這一層剝完才剝下一層。 - **Branching factor**: "Imagine searching a uniform tree where every state has b successors."（Ch3 p.14） - 中文：想像一棵每個節點都有 b 個子節點的樹，這個 b 就叫 branching factor（分支因子）。白話：b 是「每一步能往幾個方向走」。 - **BFS complexity**: "Suppose that the solution is at depth d. The total number of nodes generated is b + b² + b³ + ··· + b^d = O(b^d)"（Ch3 p.14，公式只在投影片圖上） - 中文：假設解在第 d 層，總共會產生 b + b² + b³ + ··· + b^d 個節點，寫成大 O 就是 O(b^d)。白話：每往下一層，節點數就乘上 b 倍，長得非常快。 - **Uniform-cost search**: "Uniform-cost search (AI) or Dijkstra’s algorithm (Theoretical CS) … Uniform-cost search expands the node n with the lowest path cost g(n). The algorithm tests for goals only when it expands a node, not when it generates a node"（Ch3 p.16） - 中文：UCS（一致成本搜尋）在理論資工領域就是 Dijkstra's algorithm（戴克斯特拉演算法）。它每次展開累積成本 g(n) 最小的節點，而且是展開時才檢查是不是終點，不是產生時就檢查。白話：永遠先走目前最便宜的那條路，走到才確認是不是終點。 - **UCS optimality**: "Uniform-cost search is optimal in general. Uniform-cost search expands nodes in order of their optimal path cost."（Ch3 p.17） - 中文：UCS 通常是最佳的，因為它是照「最佳路徑成本」的順序展開節點。白話：每次都挑目前最便宜的先展開，所以停下來時一定是最便宜的解。 - **UCS vs BFS**: "Uniform-cost search is guided by path costs rather than depths. When all step costs are the same, uniform-cost search is similar to breadth-first search."（Ch3 p.17） - 中文：UCS 是照路徑成本（path cost）排序，不是照深度排序；當每一步成本都一樣時，UCS 就跟 BFS 一樣。白話：成本都相同時，「最便宜」跟「步數最少」剛好是同一件事。 ## [1:08:52](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4132s) 評估搜尋演算法的四個指標 還沒介紹任何演算法之前，老師先定好評分標準。Completeness（完備性）問：只要問題有解，這個方法保證找得到嗎？Optimality（最佳性）問：找到的是不是成本最低的那個解？Time complexity（時間複雜度）和 space complexity（空間複雜度）分別問：要花多久、要佔多少記憶體。實際算的時候，時間看「總共產生幾個節點」，空間看「同時要記住幾個節點」，兩者都用 Big-O 表示。後面每種搜尋法都用這四項比較，本章最後一段有對照表。老師提醒非電機資工背景要自己補複雜度的觀念 (1:10:36)，Big-O 的短版教學放在「BFS 的複雜度」那段。 要先懂的前置概念（第 2 週第 03 章學過：[搜尋問題的定義](https://app.notion.com/p/3e6fc631b03081c8a7e0e152c12bbd25)）：搜尋時會把所有可能的走法畫成一棵 search tree（搜尋樹）。樹上每個 node（節點）代表一個狀態，例如「人在 Arad」；最上面的起點叫 root（根節點），從它往下長出的節點叫 successors（子節點，也就是下一步能到的地方）。path cost（路徑成本）是從起點走到這個節點累積花掉的成本，例如里程加總。
用生活例子講，這四個指標在問什麼？ 想像你要找一條從家裡到台北車站的路線。 - Completeness：只要路存在，這套找法保證能找到一條嗎？會不會一直繞圈圈？ - Optimality：找到的那條，是不是最省時（或最省錢）的？ - Time complexity：為了找路，你總共查看了幾個路口？ - Space complexity：找路的過程中，你的紙上最多同時要記幾條「還沒走完的候選路線」？
完備和最佳差在哪？可以只有其中一個嗎？ 可以。完備只保證「找得到一個解」，不保證是最好的。本章最後一段的小例子裡，BFS 找到成本 10 的路，但其實有成本 3 的路：BFS 完備，卻不最佳。老師也說，沒有解的問題暫時不在考慮範圍 (1:09:44)。
老師原話是什麼？ 「如果這個問題是有 Solution 的話，它是不是一定能夠找到 Solution」(1:09:16) 「找到了是不是最佳的 Solution，這個叫做 Optimality」(1:10:02)
## [1:10:54](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4254s) Uninformed search：只知道題目給的資訊 Uninformed search（無資訊搜尋，也叫 blind search 盲目搜尋）手上只有問題定義。以羅馬尼亞地圖為例，只知道城市、道路和每段路的里程。它能做的只有兩件事：從目前的節點產生下一步能到的節點（generate successors），以及判斷某個節點是不是終點（goal test）。所以各種 uninformed 方法的差別只有一個：**展開節點的順序**。如果還多知道「哪個方向比較可能接近目標」，就叫 informed search（有資訊搜尋，也叫 heuristic search 啟發式搜尋），第 06 章會講。
要先懂什麼？generate、expand、frontier 是什麼？ 後面每種搜尋法都用這幾個詞描述： - **Generate（產生）**：幫某個節點的鄰居建立新節點，放進待辦清單。這時還沒「走過去」。 - **Expand（展開）**：從待辦清單拿出一個節點，把它所有鄰居都 generate 出來。 - **Frontier（邊界，也就是待辦清單）**：已經產生、但還沒展開的節點。各種搜尋法的差別，就是 frontier 裡「下一個先拿誰」。 - **Goal test（目標檢查）**：問這個節點是不是終點。
用生活例子講，uninformed 和 informed 差在哪？ 你在沒去過的城市找一家店，手機沒電。站在路口，你只看得到「這個路口可以往哪幾條路走」，走到店門口才知道是不是它，這就是 uninformed。 如果你遠遠看得到那家店的招牌，知道「大概在東北方」，就能優先往東北走，這就是 informed：多了一份「離目標還多遠」的估計。
老師原話是什麼？ 「我除了告訴你這個之外，我其他全部不告訴你」(1:11:34) 「跟我今天是用什麼樣子的順序來搜尋這一棵樹是有差的」(1:12:18)
## [1:12:54](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4374s) BFS：一層一層往外展開 BFS（breadth-first search，廣度優先搜尋）先展開起點（root），再把 root 的所有子節點都展開，然後才輪到孫子那一層，依此類推。frontier 用 FIFO queue（先進先出佇列，像排隊：先產生的先展開），所以淺的節點一定先處理。老師用下圖上半的羅馬尼亞地圖講：從 Arad 出發，先把 Sibiu、Timisoara、Zerind 三個鄰居都產生出來、逐一檢查是不是目的地，都不是，才回頭展開第一個鄰居 Sibiu 的所有分支 (1:13:17)。下圖下半的二元樹，展開順序是 A、B、C、D、E、F、G。 二元樹（binary tree）就是每個節點最多只分出 2 個子節點的樹，課本拿它當最簡單的例子。羅馬尼亞地圖是課本從第 03 章就一直用的例子（第 2 週第 03 章學過：城市是狀態，道路是動作，每段路的里程是成本）。 **注意：老師口頭說「我們先來講 Informed Search」(1:12:54)，是口誤；投影片 p.13 的標題是 Uninformed Search Strategies，BFS 屬於 uninformed。考試寫投影片的版本。** [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\ai_ch3_p013.png | 投影片 Ch3 p.13：BFS 在羅馬尼亞地圖和二元樹上的展開順序，三角形標記的是下一個要展開的節點]] 圖上重點： - Breadth-first search (BFS)：廣度優先搜尋。 - The root node is expanded first, then all the successors…：先展開根節點，再展開它的所有子節點，然後才輪到子節點的子節點。 - (a) The initial state／(b) After expanding Arad／(c) After expanding Sibiu：上半是羅馬尼亞地圖的搜尋樹，依序是「剛開始只有 Arad」「展開 Arad 之後」「展開 Sibiu 之後」；灰底是已展開，實線是已產生，淡色虛線是還沒產生。 - Figure 3.12：下半是二元樹，三角形標記（marker）指「下一個要展開的節點」，四格依序指向 A → B → C → D。 這張圖在講：BFS 一定把同一層全部處理完，才往下一層走。
在 5 個節點的小圖上，BFS 一步一步怎麼跑？ 小圖：起點 S，終點 G。S 連到 A（成本 1）和 B（成本 5）；A 連到 C（成本 1）；C 連到 G（成本 1）；B 連到 G（成本 5）。BFS 不看成本，只看層數。這裡照課本的做法，節點一產生就做 goal test。 1. frontier = [S]。展開 S，產生 A、B，都不是 G。frontier = [A, B]。 2. 從隊伍最前面拿 A 展開，產生 C，不是 G。frontier = [B, C]。 3. 拿 B 展開，產生 G，是目標，停。 結果：S → B → G，走 2 步，成本 5 + 5 = 10。BFS 保證找到「步數最少」的解，但本章最後一段會看到，這條不是最便宜的。
老師原話是什麼？ 「我把 A 可以走出去的所有分支都先走一次」(1:13:33)
## [1:14:22](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4462s) BFS 的複雜度：O(b^d) 假設每個節點都有 b 個子節點（b 叫 branching factor，分支因子），最淺的解在第 d 層。root 產生第 1 層 b 個節點，每個再產生 b 個，第 2 層就有 b² 個，第 3 層 b³ 個，到第 d 層總共產生 b + b² + b³ + ··· + b^d 個節點，所以時間複雜度是 O(b^d)。BFS 要一層做完才進下一層，處理第 d 層時 frontier 裡同時放著約 b^d 個節點，所以空間複雜度同樣是 O(b^d)（課本）。老師兩次提醒：Big-O 是修這門課預設你已經會的，非電機資工背景要自己補 (1:10:36、1:15:25)。 **注意：老師口頭說「假設這一顆 tree 它的深度是 D，也就是說有 D 這麼多層」(1:15:01)；投影片 p.14 寫的是 "the solution is at depth d"，也就是最淺的那個解所在的深度，不是整棵樹的深度。考試寫投影片的版本。** 這段數學想回答的問題是：BFS 為了找到答案，總共要看多少個節點、同時要記住多少個節點？算出來的 O(b^d) 意思是「答案每深一層，工作量和記憶體都要乘上 b 倍」。下面兩個摺疊，一個補 Big-O 是什麼，一個用小數字驗算這個加總；記住這句結論就夠了。
要先懂什麼？Big-O 在說什麼？ Big-O 描述「問題變大時，工作量長多快」，只看成長最快的那一項，忽略常數倍數。 - 只留最大項：10 + 100 + 1,000 裡，1,000 就佔九成，所以只看最大那一項。 - 常數不管：2n 和 n 都是 O(n)。 - 常見的成長速度由慢到快：O(1)、O(log n)、O(n)、O(n²)、O(b^n)。 - O(b^d) 是指數成長：d 每多 1，工作量就乘上 b。b = 10 時，多一層就是十倍。 正式定義（標準寫法）：如果存在常數 k 和 n₀，讓所有 n > n₀ 都有 T(n) ≤ k·f(n)，就說 T(n) 是 O(f(n))。
手算一次，b + b² + ··· + b^d 到底有多大？ - b = 2、d = 3：2 + 4 + 8 = 14 個節點。 - b = 10、d = 3：10 + 100 + 1,000 = 1,110 個節點，最後一層佔 90%。 前面所有層加起來，還不到最後一層的 1/(b−1)。所以總數跟 b^d 是同一個等級，寫成 O(b^d)。
老師原話是什麼？ 「如果你不是電機資工的，可能你自己要補充一點背景知識」(1:10:36) 「如果說你沒有學過 Big O 的話，同學你可能要自己去查一下」(1:15:25) 「所以它其實它的 time complexity 以及它的 memory 的需求其實很大的」(1:15:45)
## [1:15:53](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4553s) BFS 的時間與記憶體有多誇張 投影片 p.15（課本 Figure 3.13）假設 b = 10、每秒產生 100 萬個節點、每個節點佔 1000 bytes。深度每加 2，節點數就乘 100，深度 16 要 350 年、10 EB。再看深度 12：13 天咬牙還等得到，1 petabyte 記憶體卻買不起。課本的結論是，BFS 的記憶體比時間更早出問題。
DepthNodesTimeMemory
21100.11 milliseconds107 kilobytes
411,11011 milliseconds10.6 megabytes
610^61.1 seconds1 gigabyte
810^82 minutes103 gigabytes
1010^103 hours10 terabytes
1210^1213 days1 petabyte
1410^143.5 years99 petabytes
1610^16**350 years****10 exabytes**
表格單位白話版：milliseconds 是毫秒（千分之一秒）；記憶體由小到大是 kilobytes（KB）、megabytes（MB）、gigabytes（GB）、terabytes（TB，約 1,000 GB）、petabytes（PB，約 1,000 TB）、exabytes（EB，約 1,000 PB）。下面「這些數字怎麼算出來的？」只是在驗算表格：時間＝節點數 ÷ 每秒能產生的節點數，記憶體＝節點數 × 每個節點的大小。不看也不影響理解，重點是最後一列的 350 年和 10 EB。
這些數字怎麼算出來的？ 以深度 10 為例： 1. 節點數：10 + 100 + ··· + 10^10 = 11,111,111,110，約 1.11 × 10^10。 2. 時間：1.11 × 10^10 ÷ 每秒 10^6 個 = 11,111 秒，約 3.1 小時。 3. 記憶體：1.11 × 10^10 × 1000 bytes，約 1.11 × 10^13 bytes。課本用 1024 進位（1 TB = 1024⁴ bytes），算出來約 10.1 TB。
用生活例子講，指數成長有多可怕？ 像連鎖訊息：你傳給 10 個人，每人再傳 10 個人，第 6 輪就是 100 萬人，第 10 輪 100 億人，超過全世界人口。BFS 每往下一層也是這樣乘 10。課本的說法是：指數複雜度的搜尋問題，除了最小的例子，uninformed 方法都解不了。
老師原話是什麼？ 「當你的這個 tree 的深度增加的時候，你所需的時間跟所需的空間會急劇的增加」(1:17:06)
## [1:17:21](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4641s) Uniform-cost search：每次展開目前最便宜的節點 Uniform-cost search（UCS，一致成本搜尋）在理論資工叫 Dijkstra's algorithm（戴克斯特拉演算法），兩者是同一個方法，只是兩個領域當年各自發展、各自取名。規則有兩條。第一，每次從 frontier 挑 path cost g(n)（從起點走到 n 的累積成本）最小的節點展開，所以 frontier 要用 priority queue（優先佇列：每次拿出數值最小的那個）。第二，節點被「展開」時才做 goal test，不是一被「產生」就檢查。 **注意：老師口頭說 UCS「一樣是 Informed Search 的一個策略」(1:17:24)，是口誤；投影片 p.16 的標題是 Uninformed Search Strategies。考試寫投影片的版本。** [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\ai_ch3_p016.png | 投影片 Ch3 p.16：UCS 從 Sibiu 找到 Bucharest，紅色 (1)(2)(3) 是依序展開的路段，最後選 278 的路線而不是 310]] 圖上重點： - Uniform-cost search (AI) or Dijkstra's algorithm (Theoretical CS)：UCS 是 AI 領域的名字，理論資工叫 Dijkstra 演算法，兩個是同一個方法。 - expands the node n with the lowest path cost g(n)：每次展開累積成本 g(n) 最低的節點。 - tests for goals only when it expands a node, not when it generates a node：展開時才檢查是不是終點，產生時不檢查。 - 地圖上的 expanded 是「已展開」，generated 是「已產生」：Bucharest 旁寫 generated，表示它一開始只是被產生、還沒被確認是終點。右邊三個算式是累積里程：80+97=177、99+211=310、80+97+101=278。 這張圖在講：UCS 不會一看到終點就停，而是等經 Pitesti 那條更便宜的 278 出現、輪到它展開時才停。下面摺疊把這個過程一步一步跑一次。
投影片的 Sibiu 到 Bucharest，UCS 一步一步怎麼跑？ 只看投影片畫出來的五個城市，括號裡是 g(n)。 1. frontier = [Sibiu 0]。展開 Sibiu（不是目標），產生 Rimnicu Vilcea 80、Fagaras 99。 2. 最小的是 Rimnicu Vilcea 80。展開它，產生 Pitesti 80 + 97 = 177。frontier = [Fagaras 99, Pitesti 177]。 3. 最小的是 Fagaras 99。展開它，產生 Bucharest 99 + 211 = 310。Bucharest 是目標，但它只是被「產生」，先不檢查。frontier = [Pitesti 177, Bucharest 310]。 4. 最小的是 Pitesti 177。展開它，又產生 Bucharest 177 + 101 = 278，比 frontier 裡的 310 便宜，換成 278。frontier = [Bucharest 278]。 5. 展開 Bucharest 278，這時才做 goal test，通過。答案：Sibiu → Rimnicu Vilcea → Pitesti → Bucharest，成本 80 + 97 + 101 = 278。
為什麼一定要等到展開才檢查目標？ 看上面第 3 步：Bucharest 第一次出現時走的是 310 那條。如果一產生就檢查，會立刻回答 310，錯過 278。 等到展開才檢查，代表 Bucharest 已經是整個 frontier 裡最便宜的。其他路線現在都不比它便宜，之後只會再加正的成本，不可能變得更便宜，所以停下來一定是最佳解。這就是 UCS 最佳的原因（前提：每步成本都是正的）。
老師原話是什麼？ 「在 AI 這個領域，當時提出來的時候，它叫做 Uniform Cost Search，但其實它跟 Dijkstra Algorithm 是一樣的意思」(1:17:49) 「所以相較之下呢，這個 278 是一個比較好的一個路徑」(1:20:45)
## [1:21:07](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4867s) Uninformed 的真正意思，UCS 與 BFS 差在哪 【老師強調】(1:21:07) UCS 明明就用了里程，為什麼還算 uninformed？投影片 p.16 左下角的中文說明講得很清楚：uninformed 的意思不是「完全沒有任何資訊」，而是「沒有使用任何關於 goal 還有多遠的額外估計資訊」。里程本來就寫在題目定義裡，老師講 UCS 時也提到這點 (1:18:31)。換句話說，UCS 用的 g(n) 是「已經走了多少」，不是「離終點還剩多少」；後者要到第 06 章的 informed search 才會用。UCS 一般是最佳的，因為它照最佳 path cost 的順序展開。根本差別：BFS 照深度（步數）展開，UCS 照 path cost 展開。每步成本都一樣時，path cost＝步數 × 固定成本，兩種順序一致，UCS 就跟 BFS 一樣。 **注意：老師口頭說「其實 BFS 也可以找最佳解啦，你去全部都掃一遍，然後找到 Cost 的最低那個」(1:21:54)。照課本，BFS 只有在每一步成本都一樣時才保證最佳：BFS 找到第一個目標就停，給的是步數最少、不一定是成本最低的解。考試寫課本的版本。** 下表的 complete、optimal 和 UCS 的複雜度來自課本（AIMA）的比較表，投影片只寫了 BFS 的 O(b^d)。
BFSUCS
展開順序最淺的先（order by depth）g(n) 最小的先（order by path cost）
FrontierFIFO queuepriority queue（依 g(n) 排）
Goal test產生時就檢查（課本）展開時才檢查（投影片 p.16）
Complete?Yes，只要 b 有限Yes，只要 b 有限且每步成本 ≥ 某個正數 ε
Optimal?只有每步成本都一樣時才是**Yes**
TimeO(b^d)O(b^(1+floor(C∗/ε)))
SpaceO(b^d)O(b^(1+floor(C∗/ε)))
表格最後兩列 UCS 的式子看起來很嚇人，意思其實很簡單：UCS 只看成本、不看步數，如果路上有很多很便宜的小步，它可能往下挖得比 BFS 更深，所以最壞情況下可能比 BFS 更花時間和記憶體。式子裡的 ε 是希臘字母 epsilon，數學上常用來代表「一個很小的正數」，這裡指最便宜的一步要花多少；C∗ 和 ε 的完整說明收在下面摺疊，不用背這條式子。
同一張小圖，BFS 和 UCS 會找到不同答案嗎？ 會。用 BFS 那段的小圖（S→A 1、S→B 5、A→C 1、C→G 1、B→G 5）： - BFS：第 2 層就碰到 G，回答 S → B → G，2 步，成本 10。 - UCS：依序展開 S(0)、A(1)、C(2)。這時 frontier 是 [G 3, B 5]，展開 G(3) 時檢查通過，回答 S → A → C → G，3 步，成本 3。 BFS 找的是「最少步」，UCS 找的是「最便宜」。如果每條路成本都是 1，最少步就是最便宜，兩者答案就一樣。
表格裡 UCS 的 C∗ 和 ε 是什麼？ C∗ 是最佳解的總成本，ε 是最小的單步成本。UCS 不看步數，只要路夠便宜就一直往下挖，最壞可能挖到 C∗/ε 層深（每步都只花 ε），所以用 1 + floor(C∗/ε) 取代 BFS 的 d（floor 是無條件捨去成整數）。每步成本都一樣時 C∗/ε = d，複雜度是 O(b^(d+1))，比 BFS 多一層，因為 UCS 等到展開才檢查目標。
用生活例子講，BFS 和 UCS 差在哪？ 查捷運加公車的路線。BFS 像「轉乘次數最少」：先看搭一段車能到的地方，再看搭兩段的。UCS 像「票價最便宜」：永遠先延伸目前累計花費最少的路線，就算它轉了好幾次車。每段車資都一樣時，兩種找法結果相同。
別人怎麼教這個？ Red Blob Games 的 [Introduction to the A∗ Algorithm](https://www.redblobgames.com/pathfinding/a-star/introduction.html)：用可以拖拉的格子地圖，示範 Breadth First Search 和 Dijkstra's Algorithm 展開順序的差別，第 06 章的 A∗ 也在同一頁。
老師原話是什麼？ 「所以這裡要釐清一個點」(1:21:07) 「Uninformed 的意思不是說完全沒有任何資訊」(1:21:17) 「它沒有用到任何關於目標有多遠的額外資訊」(1:21:24) 「BFS 是 Order by Depth，然後呢 Uniform Cost Search 是 Order by Path Cost」(1:22:44)
## Self-check
Q1. List and define the four criteria used to evaluate the performance of a search algorithm.（中文：列出並定義評估搜尋演算法效能的四個指標。） **Answer**: Completeness: is the algorithm guaranteed to find a solution when there is one? Optimality: does the strategy find the optimal (lowest path cost) solution? Time complexity: how long does it take to find a solution? Space complexity: how much memory is needed to perform the search? 中文：完備性（completeness）——只要問題有解，這個演算法保證找得到嗎？最佳性（optimality）——找到的解是不是成本最低的那一個？時間複雜度（time complexity）——要花多久才能找到解？空間複雜度（space complexity）——過程中最多要同時記住多少節點？回答這題要四項都講到，並說明完備跟最佳是兩件不同的事：找得到解不代表找到的就是最好的解。
Q2. With branching factor b = 10 and the shallowest solution at depth d = 3, how many nodes does BFS generate? Give its time and space complexity. Which is the bigger problem in practice?（中文：分支因子 b = 10、最淺的解在第 3 層時，BFS 會產生多少節點？時間和空間複雜度各是多少？實際上哪一個問題更大？） **Answer**: 10 + 100 + 1,000 = 1,110 nodes. In general BFS generates b + b² + ··· + b^d = O(b^d) nodes, so its time complexity is O(b^d). Its space complexity is also O(b^d), because the whole frontier must be kept in memory. Memory is the bigger problem: at depth 12 (b = 10), BFS takes 13 days but needs 1 petabyte. 中文：10 + 100 + 1,000 = 1,110 個節點。一般來說 BFS 會產生 b + b² + ··· + b^d = O(b^d) 個節點，所以時間複雜度是 O(b^d)。空間複雜度也是 O(b^d)，因為整個 frontier（待展開清單）都要留在記憶體裡。實際上記憶體先出問題：深度 12（b = 10）時，BFS 要花 13 天，但需要 1 petabyte 記憶體，記憶體比時間更早撐不住。
Q3. Trace uniform-cost search from Sibiu to Bucharest (Sibiu–Rimnicu Vilcea 80, Sibiu–Fagaras 99, Rimnicu Vilcea–Pitesti 97, Fagaras–Bucharest 211, Pitesti–Bucharest 101). Why does UCS apply the goal test when a node is expanded rather than when it is generated?（中文：示範一致成本搜尋（UCS）從 Sibiu 走到 Bucharest 的過程。為什麼 UCS 要等到節點被展開時才檢查目標，而不是產生時就檢查？） **Answer**: Nodes are expanded in the order Sibiu (0), Rimnicu Vilcea (80), Fagaras (99), Pitesti (177), Bucharest (278). Bucharest is first generated via Fagaras with cost 310; a goal test at generation would return this suboptimal path. Testing on expansion means Bucharest is chosen only when its cost 278 is the lowest in the frontier, so the path via Rimnicu Vilcea and Pitesti is optimal. 中文：節點展開順序是 Sibiu(0)、Rimnicu Vilcea(80)、Fagaras(99)、Pitesti(177)、Bucharest(278)。Bucharest 第一次是經 Fagaras 產生，成本 310；如果一產生就檢查目標，就會馬上回答這條 310 的次佳路徑。等到展開才檢查，代表 Bucharest 是等到經 Rimnicu Vilcea、Pitesti 這條路、成本降到 278、成為 frontier 裡最小的，才被選中、展開、確認是目標，所以能保證找到的是最便宜的路徑。
Q4. Uniform-cost search uses path costs. Why is it still an uninformed search strategy, and when does it behave like breadth-first search?（中文：一致成本搜尋（UCS）用了路徑成本，為什麼它仍然算是無資訊搜尋（uninformed search）？它什麼時候會跟廣度優先搜尋（BFS）表現一樣？） **Answer**: Step costs are part of the problem definition, and UCS uses no estimate of how far a state is from the goal, so it has no additional information beyond the problem definition. When all step costs are the same, ordering by path cost equals ordering by depth, so uniform-cost search is similar to breadth-first search. 中文：每一步的成本本來就寫在題目定義裡，UCS 用的 g(n) 是「已經走了多少」，並沒有用到任何「離目標還有多遠」的額外估計，所以沒有超出題目定義給的資訊，仍然算 uninformed。當每一步成本都相同時，照路徑成本排序就等於照深度排序，這時 UCS 的展開順序就跟 BFS 一樣。
讀完了嗎？下一章：[05 DFS 家族與雙向搜尋（1:23–1:43）](https://app.notion.com/p/3e6fc631b03081bda674f874680e4a09)｜回到週頁：[W2（9/17）](https://app.notion.com/p/3e6fc631b0308175a433e5fa4bc500df)