[人工智慧導論](https://app.notion.com/p/3e6fc631b0308131b213f0a3d93fe91d) › [W2（9/17）](https://app.notion.com/p/3e6fc631b0308175a433e5fa4bc500df) › 06｜影片 [1:56:41–2:11:49](https://www.youtube.com/watch?v=hNZQIO0q74o&t=7001s)｜投影片 Ch3 p.27–35（地圖在 p.4）｜上一章 [05 DFS 家族與雙向搜尋（1:23–1:43）](https://app.notion.com/p/3e6fc631b03081bda674f874680e4a09)｜下一章 [07 局部搜尋與爬山演算法（2:11–2:35）](https://app.notion.com/p/3e6fc631b03081e896bdc677065a3376) 跳過提示：(2:02:50–2:05:30) 老師在算 A* 搜尋的數字範例，把已經走的距離跟到終點的直線距離估計加起來比大小，聽不懂可以直接跳到 [2:05:30](https://www.youtube.com/watch?v=hNZQIO0q74o&t=7530s)，接著講「為什麼 A* 比貪婪搜尋更好」。 跳過的這段在做什麼（白話）：老師替每個城市算「已經開了幾公里」加上「到終點的直線距離」，每次挑總和最小的城市往下走，一路走到 Bucharest。下面「A* 走一次羅馬尼亞」那段的表格就是同一個過程，看懂表格就不必看這段影片。 跳過提示：(2:07:40–2:10:20) 老師在證明 Heuristic 的 Consistency 條件（三角不等式），聽不懂可以直接跳到 [2:10:20](https://www.youtube.com/watch?v=hNZQIO0q74o&t=7820s)，接著講「第三章結束，準備進入第四章」。 跳過的這段在做什麼（白話）：老師畫一個三角形說明 consistency：從某個點直接猜到終點的距離，不能比「先走一步、再從下一個點猜」還遠。重點已寫在最後一段「Consistency 就是三角不等式」，詳細證明老師說不講。 ## 重點 - Informed search（有資訊搜尋）比 BFS、UCS 多知道一個估計值：heuristic function h(n)（從節點 n 到目標，最便宜的路估計要花多少）。羅馬尼亞例子用各城市到 Bucharest 的直線距離當 h。 - Greedy best-first search 只看 h(n)，每次走看起來離終點最近的那個。很快，但找到的路線 450 公里，比最短的 418 公里多 32 公里，不是最佳解。 - A* search 看 f(n) = g(n) + h(n)：已經走了多少，加上估計還剩多少。h 是 admissible（永遠不高估）時 A* 保證找到最佳解，用在 graph search 還要 consistent（三角不等式）；羅馬尼亞例子找到 418 公里的最短路線。 ## Exam-ready - **Informed search**: "Informed search strategy—one that uses problem-specific knowledge hints about the location of goals—can find solutions more efficiently than can an uninformed strategy."（Ch3 p.27） - 中文：Informed search（有資訊搜尋）策略，會用跟這個問題有關的知識線索去提示目標大概在哪裡，比 uninformed strategy（無資訊策略）更有效率地找到解。白話：多知道一點「目標大概在哪」的線索，就能少走冤枉路。 - **Heuristic function**: "The hints come in the form of a heuristic function, denoted h(n)" "h(n) = estimated cost of the cheapest path from the state at node n to a goal state."（Ch3 p.27） - 中文：這個線索的形式就是 heuristic function（啟發函數），記成 h(n)；h(n) 是「從節點 n 到目標狀態，最便宜路徑的估計成本」。白話：h(n) 就是「從這裡到終點大概還要花多少」的猜測值，不是真正算出來的。 - **Greedy best-first search**: "Expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function; that is, f(n) = h(n)." "In this example, use the straight-line distance heuristic"（Ch3 p.28） - 中文：展開離目標最近的節點，理由是這樣比較快找到解；所以它只用 heuristic function（啟發函數）評估節點，也就是 f(n) = h(n)。這個例子用直線距離當 heuristic。白話：greedy（貪婪）每一步都只挑「看起來離終點最近」的路走，不管已經走了多遠。 - **Greedy search cost**: "Greedy best-first search using hSLD finds a solution without ever expanding a node that is not on the solution path; hence, its search cost is minimal." "However, this solution is not optimal"（Ch3 p.29） - 中文：用 hSLD（直線距離）的 greedy best-first search 找到解時，完全沒展開答案路線以外的節點，所以 search cost（搜尋成本，找路花的工夫）最小；但這個解不是 optimal（最佳解）。白話：找得快不代表找得好，展開的節點少，但走的路線不是最短的。 - **Greedy properties**: "the path via Sibiu and Fagaras to Bucharest is 32 kilometers longer than the path through Rimnicu Vilcea and Pitesti." "Greedy best-first tree search is complete in finite state spaces, but not in infinite ones." "With a good heuristic function, the complexity can be reduced substantially."（Ch3 p.30） - 中文：經過 Sibiu、Fagaras 到 Bucharest 的路線，比經過 Rimnicu Vilcea、Pitesti 的路線多 32 公里。Greedy best-first tree search（貪婪最佳優先樹搜尋）在 finite state spaces（有限狀態空間）裡是 complete（一定找得到解），在無限狀態空間裡不是。用好的 heuristic function，複雜度可以大幅降低。白話：greedy 快是快，但可能繞遠路；狀態空間夠有限一定有解，好的猜測值能省下大量工夫。 - **A-star search**: "The most widely known form of best-first search" "g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the cheapest path from n to the goal." "f(n) = g(n) + h(n) is the estimated cost of the cheapest solution through n."（Ch3 p.31） - 中文：A* 是最有名的 best-first search（最佳優先搜尋）。g(n) 是從起點到節點 n 的實際路徑成本；h(n) 是從 n 到目標，最便宜路徑的估計成本。f(n) = g(n) + h(n) 就是「經過 n 的最便宜解」的估計成本。白話：A* 把「已經走的」和「還要走的估計」加起來一起比較，兩邊都顧到。 - **Admissible heuristic**: "The first condition we require for optimality is that h(n) be an admissible heuristic. An admissible heuristic is one that never overestimates the cost to reach the goal." "Example: straight-line distance that we used in getting to Bucharest"（Ch3 p.32） - 中文：要保證找到最佳解，第一個條件是 h(n) 是 admissible heuristic（可採納的啟發函數）：這種啟發函數永遠不會高估到達目標的真實成本。例子：到 Bucharest 用的直線距離。白話：這個猜測值可以猜少，但絕對不能猜多。 - **Consistency**: "A second, slightly stronger condition called consistency (or sometimes monotonicity) is required only for applications of A* to graph search."（Ch3 p.33） - 中文：第二個、稍微更嚴格的條件叫 consistency（一致性，有時稱 monotonicity／單調性），只有把 A* 用在 graph search（圖搜尋，會記住走過的狀態）時才需要。白話：只是「不亂猜太多」還不夠，用在 graph search 上還要「前後猜的值不能自相矛盾」。 - **Consistent heuristic**: "A heuristic h(n) is consistent if, for every node n and every successor n’ of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n’ plus the estimated cost of reaching the goal from n’": h(n) ≤ c(n, a, n′) + h(n′). "This is a form of the general triangle inequality."（Ch3 p.33，公式看投影片圖） - 中文：h(n) 是 consistent（一致的），代表對任何節點 n，和它經過任一動作 a 產生的下一個節點 n′，從 n 直接估計到目標的成本，都不會大於「走到 n′ 的實際成本」加上「從 n′ 估計到目標的成本」：h(n) ≤ c(n, a, n′) + h(n′)。這其實就是三角不等式（triangle inequality）的一種形式。白話：直接猜的值不能比「先走一步再猜」還大，這個條件保證猜測值前後穩定、不矛盾。 ## [1:56:41](https://www.youtube.com/watch?v=hNZQIO0q74o&t=7001s) Informed search 與 heuristic h(n) BFS、UCS、DFS 都是 uninformed search（無資訊搜尋）：只知道問題的定義，不知道離終點還有多遠。Informed search（又叫 heuristic search）多知道一個估計值 h(n)，叫 heuristic function（啟發函數）：從節點 n 到目標，最便宜的路估計要花多少。羅馬尼亞例子的 h 是各城市到 Bucharest 的直線距離 hSLD（SLD＝straight-line distance，數值表在 p.28），老師比喻成在空照圖上兩城之間畫一條直線。 [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\ai_ch3_p004.png | 羅馬尼亞地圖（Ch3 p.4）：線上數字是實際道路里程（step cost）]] 圖上重點： - 標題 Problem-Solving Agents（會解題的 agent）；小字 An example problem: moving from Arad to Bucharest（例題：從 Arad 移動到 Bucharest）。 - 方塊是城市，線是道路，線上的數字是兩城之間的實際道路里程（公里）。 - 下方 Figure 3.2 A simplified road map of part of Romania：羅馬尼亞部分地區的簡化道路圖。 - 這張圖在講：起點是左邊的 Arad，終點是中下方的 Bucharest。圖上只有道路里程，沒有直線距離；直線距離在另一張表（p.28），數字列在下面第一個摺疊。 下面「拿 Sibiu 算一次」的摺疊在做什麼（白話）：用 Sibiu 一個城市示範，g 是已經開過的里程（算得出來），h 是到終點的直線距離（用猜的），而且猜的 253 比真正要走的 278 少。
要先懂什麼？節點、path cost、BFS／UCS／DFS - state（狀態）就是「現在在哪個城市」；node（節點）是搜尋樹上的一個點，記著這個城市和怎麼走到這裡。（本週第 03 章學過：[03 搜尋問題的定義](https://app.notion.com/p/3e6fc631b03081c8a7e0e152c12bbd25)） - step cost（步驟成本）是走一段路的里程；path cost（路徑成本）是從起點一路走過來的里程加總，越小越好。（本週第 03 章學過） - BFS 一層一層往外找；UCS 每次挑「已走里程最少」的節點展開（本週第 04 章學過：[04 BFS 與 UCS 搜尋](https://app.notion.com/p/3e6fc631b030811291c5ebaf18c949df)）；DFS 一條路走到底再回頭（本週第 05 章學過：[05 DFS 家族與雙向搜尋](https://app.notion.com/p/3e6fc631b03081bda674f874680e4a09)）。 - 這三種都叫 uninformed search：手上有地圖和里程，但不會去猜「離終點還有多遠」。這章的新東西就是多了這個猜測值。
這章會用到哪些直線距離？ 投影片 p.28 的表是各城市到 Bucharest 的直線距離（公里）。這章用到的有：Arad 366、Zerind 374、Timisoara 329、Sibiu 253、Oradea 380、Fagaras 176、Rimnicu Vilcea 193、Pitesti 100、Craiova 160、Bucharest 0。 老師口頭舉例時，逐字稿是 Arad 360、Craiova 160、Drobeta 242 (1:58:25)。Arad 以表上的 366 為準。
h(n) 和 g(n) 差在哪？拿 Sibiu 算一次 - g(n)：從起點到 n 實際花掉的里程，算得出來。Arad 到 Sibiu 是 140，g(Sibiu) = 140。 - h(n)：從 n 到終點估計還要多少，是猜的。Sibiu 到 Bucharest 直線 253，h(Sibiu) = 253。 - 真實答案：Sibiu 走道路到 Bucharest 最短 80 + 97 + 101 = 278。h 少估了 25；直線距離只會少估或剛好。終點的 h 一定是 0。 老師口頭用首字母 A、S、F、R、P、B 代稱各城市。 **注意：老師口頭把 h(n) 說成到目的地「的最小的path cost」(1:57:32)。投影片的定義是 estimated cost of the cheapest path：h 是估計值，不是真正的最短里程。考試寫投影片的版本。**
用生活例子講，heuristic 是什麼？ 在陌生城市走去台北 101，沒有地圖，但抬頭看得到大樓。每個路口你都挑看起來離 101 比較近的方向。這個目測距離就是 heuristic：便宜、馬上知道、方向大致對，但不一定準，中間可能隔著河。 uninformed 也不是什麼都不知道：p.16 的補充說，它只是沒用離 goal 還有多遠的估計；地圖、里程它都知道。
老師原話是什麼？ 「除了原本問題的該給的資訊之外，他還額外多知道了一些離目標有多遠的資訊」(1:56:49) 「它不見得真的有一條路啊，它只是在地圖上的直線距離而已啊」(1:58:18)
## [1:58:47](https://www.youtube.com/watch?v=hNZQIO0q74o&t=7127s) Greedy best-first search Greedy best-first search（貪婪最佳優先搜尋）只用 h(n) 評估節點，也就是 f(n) = h(n)：每一步都挑直線距離最短的展開。從 Arad 出發，鄰居 Sibiu 253、Timisoara 329、Zerind 374，挑 Sibiu；Sibiu 的鄰居 Arad 366、Fagaras 176、Oradea 380、Rimnicu Vilcea 193，Fagaras 最小，挑 Fagaras；Fagaras 下一步就是 Bucharest。路線 Arad → Sibiu → Fagaras → Bucharest，很快就找到了。 [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\ai_ch3_p029.png | Greedy 的搜尋樹（Ch3 p.29）：節點下的數字是 hSLD，灰色是已展開，三角形指向下一個要展開的]] 圖上重點： - 左邊文字：Greedy best-first search using hSLD finds a solution without ever expanding a node that is not on the solution path; hence, its search cost is minimal（用直線距離的 greedy 找到解時，從沒展開答案路線以外的節點，所以找路花的工夫最少）。However, this solution is not optimal（但這個解不是最佳解）。 - (a) The initial state（起始狀態）：只有 Arad，下面的 366 是它到終點的直線距離。 - (b) After expanding Arad（展開 Arad 之後）：長出 Sibiu 253、Timisoara 329、Zerind 374，三角形指著最小的 Sibiu。 - (c) After expanding Sibiu（展開 Sibiu 之後）：長出 Arad 366、Fagaras 176、Oradea 380、Rimnicu Vilcea 193，三角形指著最小的 Fagaras。 - (d) After expanding Fagaras（展開 Fagaras 之後）：長出 Sibiu 253、Bucharest 0，到達終點。 這張圖在講：greedy 每一層都只挑直線距離最小的節點往下長，展開三次就到終點，又快又省工；但下一段會看到，這條路不是最短的。
要先懂什麼？frontier、展開、best-first search - frontier（邊界）：已經產生、還沒展開的候選節點。expand（展開）：拿出一個節點，把它的下一步都放進 frontier。 - best-first search：每次拿 f(n) 最小的節點展開，用 priority queue（隨時能取出最小值的資料結構）實作。UCS 是 f(n) = g(n) 的 best-first search；greedy 和 A* 也是，只差在 f(n) 怎麼算。
p.29 說它的 search cost 最小，那為什麼不是最佳解？ 兩個 cost 不一樣。search cost 是找路花的工夫：greedy 只展開 Arad、Sibiu、Fagaras，全在答案路線上，工夫最少。path cost 是路線本身的里程：450，不是最短。
老師原話是什麼？ 「哪一個離目標最近，直線距離最近，S最近，所以我就決定我走到S」(1:59:26)
## [2:00:15](https://www.youtube.com/watch?v=hNZQIO0q74o&t=7215s) Greedy 找到的不是最佳解 Greedy 的路線實際里程 140 + 99 + 211 = 450；走 Rimnicu Vilcea、Pitesti 是 140 + 80 + 97 + 101 = 418，greedy 多 32 公里，不是 optimal（最佳）。老師說雖不中亦不遠矣；而且 heuristic 越好，complexity 越能大幅下降，不用像 BFS、DFS 慢慢找。 **注意：老師口頭說「如果有解的話，他一定會找到解」(2:01:27)。投影片 p.30 寫的是 greedy best-first tree search 只在有限狀態空間（finite state spaces）complete，無限的不是。考試寫投影片的版本。** 下面「為什麼 greedy 會選錯？」在做什麼（白話）：只是把里程加一加，結論是 greedy 在 Sibiu 只看直線距離選了 Fagaras，沒算到「走過去比較遠」和「Fagaras 的實際道路比直線繞很多」，兩個加起來就多走了 32 公里。
為什麼 greedy 會選錯？ 關鍵在 Sibiu：Fagaras 的 h 176 比 Rimnicu Vilcea 的 193 小，greedy 就選了 Fagaras。它沒看到兩件事： 1. 走過去的成本：Sibiu 到 Fagaras 要 99，到 Rimnicu Vilcea 只要 80。 2. 直線和道路的落差：Fagaras 到 Bucharest 的路 211，比直線多 35；Rimnicu Vilcea 走道路 198，只比直線多 5。 從 Sibiu 算起，99 + 211 = 310 對上 80 + 97 + 101 = 278，差的就是 32。
什麼時候 greedy 會找不到解？ 課本的例子：從 Iasi 走到 Fagaras（地圖右上角）。Neamt 直線較近，greedy 先走 Neamt，但那是死路；展開 Neamt 又把 Iasi 放回 frontier，Iasi 又比 Vaslui 近，於是在 Iasi、Neamt 之間來回，永遠不走正確的 Vaslui。 所以要記得走過的狀態（graph search），有限狀態空間才保證找得到；無限的可能一路走下去。 **注意：這個例子說明不記得走過狀態的 tree search 在有限空間也會繞圈，課本說有限空間 complete 的是 graph search 版本；投影片 p.30 原句寫的是 tree search。考試引用時照投影片原句寫。**
老師原話是什麼？ 「雖然很開心，很快就找到解了，但是它的解可能不是最佳解」(2:00:39) 「雖不中亦不遠矣嘛」(2:01:39)
## [2:02:15](https://www.youtube.com/watch?v=hNZQIO0q74o&t=7335s) A*：f(n) = g(n) + h(n) A* search（念 A-star）是最有名的 best-first search，把兩個數相加：g(n) 是從起點到 n 已經花掉的 path cost，h(n) 是從 n 到目標的估計成本。f(n) = g(n) + h(n) 就是：如果解經過 n，總共估計要花多少。每次展開 f 最小的節點。h 全設成 0 就變回 UCS；只留 h 就是 greedy。 表格裡兩個詞先說明：complete（完備）＝只要有解，保證找得到；optimal（最佳）＝找到的一定是成本最低的那條路。（本週第 04 章學過：評估搜尋演算法的四個指標，[04 BFS 與 UCS 搜尋](https://app.notion.com/p/3e6fc631b030811291c5ebaf18c949df)）
演算法f(n)CompleteOptimal羅馬尼亞例子
UCSg(n)，只看過去是（每步成本為正時，課本）是（p.17）418，展開 12 個城市
Greedy best-firsth(n)，只看未來有限狀態空間是，無限的不是（p.30）否（p.29–30）450，展開 3 個城市
A*g(n) + h(n)，兩個都看是是，h 要 admissible；graph search 還要 consistent（p.32–33）418，展開 5 個城市
展開城市數是我用程式在同一張地圖跑的。課本另外提到：greedy 最壞的時間和空間是 O(b^m)（b 是每個節點的分支數，m 是最大深度）；A* 要存下所有產生過的節點，通常記憶體比時間先用完。 O(b^m) 的白話：這是計算量的寫法（本週第 04 章學過 BFS 的 O(b^d)），意思是最壞情況下，要看的節點數每深一層就乘上 b 倍，會暴增。所以 greedy 快不快全看 heuristic 準不準：猜得好就很快，猜不好可能跟地毯式搜尋一樣慢。
老師原話是什麼？ 「A star search，它是最著名的best first search」(2:02:29)
## [2:03:17](https://www.youtube.com/watch?v=hNZQIO0q74o&t=7397s) A* 走一次羅馬尼亞 從 Arad 出發，三個鄰居的 f 是 Sibiu 140 + 253 = 393、Timisoara 118 + 329 = 447、Zerind 75 + 374 = 449，展開最小的 Sibiu。接著 Rimnicu Vilcea 220 + 193 = 413 最小。一路比下去，得到 Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest，總里程 418，就是最短路線。A* 贏 greedy，是因為同時考慮過去已花的成本和未來的估計。 **注意：老師口頭從 Rimnicu Vilcea 直接接到 Pitesti。投影片 p.34–35 中間還展開了 Fagaras（415 比 Pitesti 的 417 小），並產生 f = 450 的 Bucharest，但演算法沒有停。考試照投影片的步驟寫。**
步驟展開（f 最小）新加入 frontier，f = g + h
1Arad 366Sibiu 393 = 140 + 253、Timisoara 447 = 118 + 329、Zerind 449 = 75 + 374
2Sibiu 393Arad 646 = 280 + 366、Fagaras 415 = 239 + 176、Oradea 671 = 291 + 380、Rimnicu Vilcea 413 = 220 + 193
3Rimnicu Vilcea 413Craiova 526 = 366 + 160、Pitesti 417 = 317 + 100、Sibiu 553 = 300 + 253
4Fagaras 415Sibiu 591 = 338 + 253、**Bucharest 450 = 450 + 0**
5Pitesti 417**Bucharest 418 = 418 + 0**、Craiova 615 = 455 + 160、Rimnicu Vilcea 607 = 414 + 193
6Bucharest 418是目標，結束。Timisoara 447、Zerind 449 從第 1 步等到最後都沒輪到
表裡同一城市會出現好幾次（Sibiu 三次）：投影片用 tree search，不記得走過哪裡，從不同的路走到同一城市都算一個新節點。這些重複節點的 f 都比較大，到結束都沒輪到。
第 4 步已經產生 Bucharest 了，為什麼不停？ A* 跟 UCS 一樣，展開時才檢查是不是目標，產生時不檢查（p.16：tests for goals only when it expands a node, not when it generates a node）。 第 4 步的 Bucharest 是 450，但 frontier 裡還有 Pitesti 417，經過它可能有更便宜的解，要先看。果然第 5 步找到 418。一產生就停的話，會交出 450，跟 greedy 一樣錯。
A* 真的比 UCS 省工嗎？ UCS 只看 g，要把 g 小於 418 的城市全部展開才敢確定：Arad、Zerind、Timisoara、Sibiu、Oradea、Rimnicu Vilcea、Lugoj、Fagaras、Mehadia、Pitesti、Craiova、Drobeta，共 12 個，其中 Lugoj、Mehadia、Drobeta 根本在反方向。 A* 只展開 5 個。h 讓 A* 不往錯的方向浪費時間。
別人怎麼教這個？ - [Red Blob Games：Introduction to the A* Algorithm](https://www.redblobgames.com/pathfinding/a-star/introduction.html)：互動圖比較 BFS、Dijkstra（即 UCS）、greedy、A* 的搜尋範圍。 - [Computerphile：A* (A Star) Search Algorithm](https://www.youtube.com/watch?v=ySN5Wnu88nE)：英文影片，在紙上手算。
老師原話是什麼？ 「就是考慮了我過去的歷史，我的path cost，以及我預估未來我要走的cost有多少，兩個一起合併考量」(2:05:26)
## [2:05:50](https://www.youtube.com/watch?v=hNZQIO0q74o&t=7550s) A* 最佳的條件：admissible A* 真的保證最佳嗎？可以證明：heuristic 符合 admissibility 和 consistency 時，A* 是 complete 而且 optimal。第一個條件 admissible（可採納的）：h 永遠不高估（never overestimates）到目標的真實成本，即 h(n) ≤ 從 n 到目標的真正最小成本。直線距離就是例子：兩點之間直線最短，道路只會一樣長或更長。 **注意：最佳性的詳細證明老師不講（「當然我們不會講仔細的證明啦」(2:06:01)），只講 admissible、consistent 兩個條件是什麼。** **注意：老師口頭說 h 要同時符合 admissible 和 consistent 才保證 optimal (2:06:32)。投影片 p.32–33 寫的是：consistency 是稍強的第二個條件，只有用在 graph search 時才需要。考試寫投影片的版本。** 下面兩個進階摺疊在做什麼（白話）：「手算一次」用一張五個點的小地圖示範，h 只要高估一個點，A* 就會交出比較貴的路線；「為什麼不高估就能保證」用四步推理說明，只要 h 不猜多，最短路線上的城市分數一定比較低，會先被拿出來，貴的路輪不到被交出去。
用生活例子講，為什麼不能高估？ 導航說最快 20 分鐘，實際只會更久，這是樂觀的估計，照它比較不會錯過好路線。如果導航把一條其實 30 分鐘的路說成要 2 小時（高估），你看都不看就改走 50 分鐘的路。高估讓好路線看起來很貴，A* 還沒去看它，就先把差的解交出去了。
如果 h 高估了會怎樣？手算一次 小地圖：起點 S、終點 G。路有 S→A 1、A→G 5、S→B 2、B→C 1、C→G 1。最短路線 S→B→C→G，成本 4。A 像在終點的河對岸，直線很近、橋很遠。 h 設成 S 2、A 1、B 2、C 1、G 0，都不超過真實成本（S 4、A 5、B 2、C 1），是 admissible。 1. 展開 S：A 的 f = 1 + 1 = 2，B 的 f = 2 + 2 = 4。 2. 展開 A：產生 G，f = 6。frontier 剩 B 4、G 6。 3. 展開 B 產生 C（f = 3 + 1 = 4），展開 C 產生 G（f = 4）。frontier 剩 G 4、G 6。 4. 拿出 G 4，結束。成本 4，正確。 把 h(B) 改成 6（真實只有 2，高估）：展開 S 後 A 是 2、B 是 2 + 6 = 8；展開 A 產生 G 6；G 6 比 B 8 小，直接拿出 G，交出 S→A→G，成本 6，錯了。 同一張圖用 greedy（第一組 h）：A 的 h = 1 比 B 的 2 小，走 A 再走 G，也是 6。所以 greedy 就算 h 是 admissible 也不保證最佳。
為什麼不高估就能保證 A* 最佳？ 老師不講證明，這裡只給直覺（tree search 版），不必背。設最短路線的成本是 C*。 1. 假設 A* 快要交出一條比較貴的解 G2，成本 C2 大於 C*。終點的 h 是 0，所以 f(G2) = C2。 2. 這時最短路線上一定還有某個節點 n 在 frontier 排隊。 3. h 不高估，所以 f(n) = g(n) + h(n) ≤ g(n) + n 到終點的真實成本 = C*。 4. f(n) ≤ C* 小於 C2，n 會先被拿出來，G2 輪不到。最後第一個被拿出來的終點，就是最短路線。 羅馬尼亞例子：Bucharest 450 在排隊時，最短路線上的 Pitesti 是 417，比 450 小，所以先展開 Pitesti。
老師原話是什麼？ 「如果你可以證明你的Heuristic Function符合Admissible跟Consistent，你就一定能夠說A Star Search是Optimal」(2:06:32) 「你這個Heuristic呢，永遠不會過度估計了某一個State走到目標那個State所需花的Cost」(2:07:04)
## [2:08:07](https://www.youtube.com/watch?v=hNZQIO0q74o&t=7687s) Consistency 就是三角不等式 第二個條件 consistency（一致性，有時叫 monotonicity）：對每個節點 n，和 n 做任何動作 a 產生的下一個節點 n′，都要 h(n) ≤ c(n, a, n′) + h(n′)。白話：從 n 直接估的剩餘成本，不大於先走一步的實際成本加上從 n′ 估的剩餘成本。老師說像繞口令，畫成三角形就懂：n 到終點 G 這一邊，不會比 n → n′ → G 兩邊加起來長，就是三角不等式。第三章到這裡結束。 ```mermaid graph LR N["n"] -->|"c 實際走一步的成本"| N2["n′ 下一步"] N2 -.->|"h(n′)"| G["G 終點"] N -.->|"h(n) 直接估"| G ``` 這張圖在講：從 n 到終點 G 有兩種估法。實線是真的走一步的成本，虛線是猜的；直接猜（下面那條虛線）不能比「先走一步再猜」（上面兩條加起來）還長。 下面兩個進階摺疊在做什麼（白話）：「拿羅馬尼亞驗算」把地圖上的數字代進去，確認直線距離真的符合這個條件；「為什麼 graph search 需要 consistency」說明它的好處：A* 第一次走到某個城市時，走的一定是到那裡最便宜的路，不用回頭改。
它到底怎麼運作？拿羅馬尼亞驗算 每條路檢查 h(出發城市) ≤ 道路里程 + h(到達城市)： - Rimnicu Vilcea → Pitesti：193 ≤ 97 + 100 = 197，成立。 - Pitesti → Bucharest：100 ≤ 101 + 0 = 101，成立（全圖最緊，只差 1）。 我用程式檢查了地圖上 23 條路的兩個方向，全部成立。這不是巧合：直線距離本身滿足三角不等式，道路又不比直線短，所以一定 consistent。
要先懂什麼？三角不等式、tree search 和 graph search 三角不等式：三角形任兩邊加起來大於或等於第三邊。生活版：從家直接去學校，不會比先繞去便利商店再去學校遠。 Tree search 不記得走過哪些狀態，同一城市可出現很多次（A* 表裡 Sibiu 出現三次）。Graph search 多一張已展開清單（explored set），同一狀態只展開一次。
為什麼 graph search 需要 consistency？為什麼說它稍強？ Graph search 第一次展開某個狀態就定案，之後找到更便宜的路也不理，所以第一次走的必須就是最便宜的路。 Consistent 保證沿著任何路 f 不會變小：f(n′) = g(n) + c + h(n′) ≥ g(n) + h(n) = f(n)。A* 照 f 由小到大展開，第一次拿到某個狀態就是最便宜的路。只有 admissible 的話，可能先用較貴的路定案。 稍強的意思（課本）：consistent（且終點 h 為 0）就一定 admissible，沿最佳路線把不等式一路加起來就證得出來；反過來不一定。
老師原話是什麼？ 「好像在繞口令，其實很簡單」(2:08:54) 「但事實上這件事情就是三角不等式」(2:09:25) 「那詳細的證明我們就不講了，我們只講它的特性是怎樣」(2:10:37)
## Self-check
Q1. What evaluation function f(n) do greedy best-first search and A* search use? From Arad to Bucharest with hSLD, which route does each find?（中文：greedy best-first search 和 A* search 各用什麼評估函數 f(n)？用 hSLD 從 Arad 走到 Bucharest，各找到哪條路線？） **Answer**: Greedy uses f(n) = h(n); A* uses f(n) = g(n) + h(n), where g(n) is the path cost from the start to n. Greedy finds Arad → Sibiu → Fagaras → Bucharest (450), 32 km longer than optimal; A* finds Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest (418), the optimal route. 中文：Greedy best-first search 只用 f(n) = h(n) 評估節點，只看「還剩多少」；A* 用 f(n) = g(n) + h(n)，同時看「已經走了多少」和「還剩多少」。用 hSLD 從 Arad 走到 Bucharest 時，greedy 找到 Arad → Sibiu → Fagaras → Bucharest，里程 450 公里，比最短路線多 32 公里，不是最佳解；A* 找到 Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest，里程 418 公里，就是最佳解。
Q2. Define an admissible heuristic. Why is the straight-line distance admissible?（中文：什麼是 admissible heuristic〔可採納的啟發函數〕？為什麼直線距離是 admissible 的？） **Answer**: An admissible heuristic never overestimates the cost to reach the goal. A straight line is the shortest distance between two points and any road is at least as long, so hSLD never overestimates (e.g., h(Sibiu) = 253, true cost 278). 中文：admissible heuristic 是指這個啟發函數永遠不會高估到達目標的真實成本。直線距離是 admissible 的，因為兩點之間直線最短，任何實際道路都只會一樣長或更長，所以直線距離永遠不會比真實成本大，例如 h(Sibiu) = 253，真實成本卻是 278，猜的比真的少。
Q3. State the consistency condition, check it for Rimnicu Vilcea → Pitesti (step cost 97, h = 193 and 100), and say when it is required.（中文：寫出 consistency〔一致性〕條件，用 Rimnicu Vilcea → Pitesti 這一步〔實際成本 97，h 分別是 193 和 100〕驗算一次，並說明什麼時候才需要這個條件。） **Answer**: h(n) ≤ c(n, a, n′) + h(n′) for every node n and every successor n′; it is a form of the triangle inequality. Check: 193 ≤ 97 + 100 = 197, so it holds. Consistency is slightly stronger than admissibility and is required only when A* is applied to graph search. 中文：consistency 條件是 h(n) ≤ c(n, a, n′) + h(n′)，對每個節點 n 和它的每個後繼節點 n′ 都要成立，本質上就是三角不等式。驗算：193 ≤ 97 + 100 = 197，成立。Consistency 比 admissibility 稍微嚴格一點，只有把 A* 用在 graph search（會記住走過的狀態、每個狀態只展開一次）時才需要，用 tree search 不需要。
Q4. In A* on the Romania map, Bucharest is generated with f = 450 after Fagaras is expanded. Why is this path not returned?（中文：在羅馬尼亞地圖上用 A*，展開 Fagaras 之後產生了 f = 450 的 Bucharest，為什麼這條路不會直接被交出去？） **Answer**: A* tests for the goal only when a node is expanded, not when it is generated. Pitesti is still on the frontier with f = 417 < 450, so A* expands it next, generates Bucharest with f = 418, and returns that optimal path. 中文：A* 只有在節點被「展開」時才檢查是不是目標，產生（generate）出來的時候不檢查。這時 frontier 裡還有 Pitesti，f = 417，比 450 小，所以 A* 會先展開 Pitesti，展開後又產生一個 f = 418 的 Bucharest，這次輪到它被展開、檢查是目標，才交出這條最佳路線。
讀完了嗎？下一章：[07 局部搜尋與爬山演算法（2:11–2:35）](https://app.notion.com/p/3e6fc631b03081e896bdc677065a3376)｜回到週頁：[W2（9/17）](https://app.notion.com/p/3e6fc631b0308175a433e5fa4bc500df)