# 章節包：人工智慧導論（AI）W2（9/17）第 04 章「BFS 與 UCS 搜尋」 影片 1:08:52–1:23:14，YouTube ID hNZQIO0q74o，逐字稿 C:\D槽\TAICA課程\人工智慧導論\第二周1150917\W2_人工智慧導論_朱威達.逐字稿.txt。Notion 章節頁 https://app.notion.com/p/3e6fc631b030811291c5ebaf18c949df（頁 ID 3e6fc631-b030-8112-91c5-ebaf18c949df），頁面標題「04 BFS 與 UCS 搜尋（1:08–1:23）」。 ## 1. 第一行（直接照抄，不要改） [人工智慧導論](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) ## 1b. 最後一行（直接照抄，放在 Self-check 後面，當全頁最後一行） 讀完了嗎？下一章：[05 DFS 家族與雙向搜尋（1:23–1:43）](https://app.notion.com/p/3e6fc631b03081bda674f874680e4a09)｜回到週頁：[W2（9/17）](https://app.notion.com/p/3e6fc631b0308175a433e5fa4bc500df) ## 2. 各段標題（照順序；每段一個 ## 標題，直接照抄連結） - `## [1:08:52](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4132s) 評估演算法的四個指標`　老師講什麼：Completeness（有解時一定找得到嗎）、optimality（找到的是最佳解嗎）、time complexity、space complexity；非電機資工背景要自己補複雜度觀念。 - `## [1:10:54](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4254s) Uninformed search 是什麼`　老師講什麼：Uninformed（blind）search 只知道問題定義，只能產生後繼節點、判斷是不是目標，不同策略差在展開順序；多知道哪個方向比較接近目標，就是 informed（heuristic）search。 - `## [1:12:54](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4374s) BFS 怎麼展開`　老師講什麼：先把 root 的所有分支都檢查一遍，再往下一層展開，一層一層往下。 - `## [1:14:22](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4462s) BFS 的複雜度 O(b^d)`　老師講什麼：每個節點有 b 個分支、深度 d，總共要產生 b + b² + … + b^d 個節點，時間複雜度 O(b^d)，記憶體需求也很大；沒學過 Big-O 要自己查。 - `## [1:15:53](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4553s) BFS 的時間與記憶體有多誇張`　老師講什麼：範例表：b=10、每秒 100 萬節點、每節點 1KB，深度 10 要 3 小時、10 TB，深度 16 要 350 年、10 EB。 - `## [1:17:21](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4641s) Uniform-cost search（Dijkstra）`　老師講什麼：AI 叫 uniform-cost search，理論資工叫 Dijkstra：每次展開 path cost g(n) 最小的節點，而且展開時才做 goal test；用 80+97+101=278 對比 99+211=310 示範。 - `## [1:21:07](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4867s) Uninformed 的意思，UCS 與 BFS 的差別`　老師講什麼：Uninformed 不是完全沒資訊，而是沒用到「離目標還多遠」的估計；UCS 一般是最佳的，依 path cost 展開而 BFS 依深度展開，步驟成本都一樣時 UCS 就像 BFS。 ## 3. 老師強調／會考／不考的地方（原句已驗證；寫進筆記時 ASR 錯字要改正） - (1:15:25) [強調] 「如果說你沒有學過BIG OF的話，同學你可能要自己去查一下，我們假設你來修正門課，你其實是有這些幾個素養的」 → Big-O 時間複雜度是前置知識，要自己補 - (1:21:07) [強調] 「所以這裡要釐清一個點，就是說Uninformed，你看字面上的意義」 → uninformed 不是沒有任何資訊，而是沒用到離目標多遠的估計（投影片 p.16 另附中文說明） ## 3b. 數學段候選（程式抓的，只是提示；寫「跳過提示」行用） 1:13:30–1:15:30 (120s, score 14) 分子 次方 展開 平方 是不是我的目的地不是那再回過來我把A可以走出去的所有分子都先走一次都走一次然後呢都不是我的目的地嘛那接下來我剛剛的第一個分子是S我再試試看我從S走出去的所有分子看看有沒有走到我的目的地就這樣依此類推一路這樣子往下展開所以底下這是另外一個示意圖從A先check一下B是不是目標 1 段候選（門檻 3.2 字／30 秒） ## 4. 這章摘要與重要度 先定義評估搜尋演算法的四個指標，再介紹無資訊搜尋裡的 BFS 與 uniform-cost search，比較兩者展開順序的差別。（核心） ## 5. 整堂課的提醒（ASR 錯字、老師口誤、投影片缺公式等；只用跟這章有關的） - 影片開頭缺幾分鐘：YouTube 標題 AI2026_0917_3。0:00:00–0:01:43 老師在設定直播畫面，0:01:46 起接著講到一半的 HW1 說明，HW1 前段不在影片裡。 - 1:02:22–1:02:52 約 30 秒逐字稿是 ASR 亂碼（重複「我用這個」「有一個」），剛好是八皇后問題的開場，寫筆記時以投影片 Ch3 p.7 為準。 - 兩次下課：0:40:28–0:53:20、1:43:47–1:56:41。下課時段的逐字稿時間戳有跳動（0:43:20→0:53:20、1:52:41→1:56:41 都剛好差整數分鐘），Ch3 與 informed search 的起點建議開影片確認。 - HW1 說明前段不在影片裡，本機投影片也沒有 HW1 說明頁（Lecture 0 只有一行 project proposal），研究動機之前講了什麼無法得知。 - 0:03:10「所以這邊會佔75%的比例」不確定指哪幾塊（introduction 加方法？），筆記建議只寫老師提到 75%，不要自行解讀。 - ASR 錯字（寫筆記時要改）：0:06:52「CPPR的格式」應為 CVPR；0:06:57「體驗報告」推測是「提案報告」；0:07:02「角角的期限」應為「繳交期限」；2:28:58「無極」應為 ridge（屋脊）；2:30:5x「8的84%17個million」應為 8^8 ≈ 17 million；另外多處 Asian=agent、Socastic=stochastic、Pass Cost=path cost、heel climbing=hill climbing、None=known、Amstrong Search/Active=A* search/optimal。 - 1:29:16「GPD-6 ASTRON」不確定原詞，大概是某個 GPT 的 agent 產品，筆記建議寫「現在的 AI agent」即可。 - 1:02:22–1:02:52 逐字稿亂碼約 30 秒（八皇后開場，老師好像在說買了一個小棋盤），內容以 Ch3 p.7 補。 - 時間戳疑似漂移：0:43:20「好接下來呢」→0:53:20、1:52:41「第二個部分」→1:56:41，都剛好差整數分鐘；章節起點採後者，建議開影片確認。 - 老師口誤或 ASR：1:12:54、1:17:25 把 BFS、UCS 說成「Informed Search」，投影片 p.12–17 標的是 Uninformed，筆記照投影片寫。 - 老師口頭說法跟投影片不同（筆記照投影片寫，並加「注意」）：(a) 1:21:5x 說「BFS 也可以找最佳解」，課本是步驟成本都一樣時才是；(b) 2:01:2x 說 greedy「有解一定會找到」，p.30 寫的是只在有限狀態空間才 complete；(c) 2:06 說 A* 要同時符合 admissible 與 consistent 才最佳，p.33 說 consistency 是稍強的條件，只有 graph search 才需要。 - 投影片內容有、老師沒明講的地方，Exam-ready 要補原句：Ch3 p.23（IDDFS 是搜尋空間大、解的深度未知時的首選）、Ch2 p.25（utility-based 能處理 stochastic／部分可觀察環境的不確定性）、Ch4 p.6 後半（有多個最好的鄰居時隨機挑）。 - 投影片 _text 缺公式（p.14、p.19、p.20、p.25 的 O(b^d)、O(b^m)、O(bm)、O(b^(d/2)) 都是空白），寫 Exam-ready 前要看投影片圖確認。 - 下課時段講台邊的對話（1:44:44–1:52:27）分不清誰是老師、誰是學生，例如 1:45:54「就是有自己的想法這才是那個重點」不確定是誰說的；「這週要記得」只用確定是老師回答的部分。 - 0:11:10「沒有點名」推測是回答 Slido 上「有沒有點名」的問題，但沒看到原問題，不確定。 ## 6. 投影片文字（這章範圍） **這幾頁的公式或內容只在圖裡（文字檔抓不到），寫 Exam-ready 與公式前先用 Read 看這幾張圖：** - Ch3 p.11 → C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\brief_Ch3_p011.png - Ch3 p.12 → C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\brief_Ch3_p012.png - Ch3 p.13 → C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\brief_Ch3_p013.png - Ch3 p.14 → C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\brief_Ch3_p014.png - Ch3 p.17 → C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\brief_Ch3_p017.png --- Ch3 p.11 --- We can evaluate an algorithm’s performance in four ways: • Completeness: Is the algorithm guaranteed to find a solution when there is one? • Optimality: Does the strategy find the optimal solution? • Time complexity: How long does it take to find a solution? • Space complexity: How much memory is needed to perform the search? Measuring Problem-Solving Performance 11 --- Ch3 p.12 --- • 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. • All search strategies are distinguished by the order in which nodes are expanded. • Strategies that know whether one non-goal state is “more promising” than another are called informed search or heuristic search strategies. Uninformed Search Strategies 12 --- Ch3 p.13 --- • Breadth-first search (BFS) • The root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. Uninformed Search Strategies 13 --- Ch3 p.14 --- • Breadth-first search (BFS) • Imagine searching a uniform tree where every state has b successors. The root of the search tree generates b nodes at the first level, each of which generates b more nodes, for a total of b2 at the second level. Each of these generates b more nodes, yielding b3 nodes at the third level, and so on. • Suppose that the solution is at depth d. The total number of nodes generated is Uninformed Search Strategies 14 --- Ch3 p.15 --- • Breadth-first search (BFS) Uninformed Search Strategies 15 --- Ch3 p.16 --- • 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 Uninformed Search Strategies 16 (1) expanded generated (2) expanded generated (3) expanded (1) 80+97=177 (2) 99+211=310 (3) 80+97+101=278 uninformed 的意思不是「完全沒有任何資 訊」，而是「沒有使用任何關於goal 還有多 遠的額外估計資訊」。 --- Ch3 p.17 --- • Uniform-cost search (AI) or Dijkstra’s algorithm (Theoretical CS) • Uniform-cost search is optimal in general. Uniform-cost search expands nodes in order of their optimal path cost. • 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. Uninformed Search Strategies 17 ## 7. 逐字稿（1:08:52 前後各多 1 分鐘，原始行） [01:07:53] 所以它的State [01:07:54] 就是代表一個盤面 [01:07:55] 它的Parent就是能夠造成 [01:07:57] 這個盤面的上一個動作 [01:08:00] 那它可以做的Action就是 [01:08:02] 我今天如果把這個空白 [01:08:04] 往下移 [01:08:05] 那就8號跑到最上面 [01:08:09] 如果往左移 [01:08:10] 就是4號馬來村右上角 [01:08:12] 空白跑到這裡 [01:08:14] 那PassCross的其實就是 [01:08:17] 你在這個Tree裡面行走 [01:08:20] 你多走一個分支 [01:08:22] 多走一次分支 [01:08:23] 就代表 [01:08:24] 我這個空格 [01:08:25] 多移動一次的意思 [01:08:27] 對不對 [01:08:28] 就好像說 [01:08:29] 剛剛這個 [01:08:30] 從A走到B的這個Tree [01:08:32] 我多走一個分支 [01:08:33] 我就要付出 [01:08:35] 我的里程數 [01:08:37] 那就是我的PassCross [01:08:42] 所以我們剛才有把問題 [01:08:44] 像這一類的問題 [01:08:46] 我們可以把它描述成 [01:08:48] 在一棵樹上面來找尋 [01:08:52] 剛剛講P.E.A.S [01:08:54] 我們要如何去評某一個演算法 [01:08:58] 我們還沒有跟大家講 [01:08:59] 你可以用什麼演算法 [01:09:01] 但是我們先來定義一下 [01:09:03] 我們如何去評判一個演算法 [01:09:05] 有幾種不同的指標 [01:09:09] 第一個Completeness [01:09:12] 它的意思是說 [01:09:14] 如果這個系統有解的話 [01:09:16] 如果這個問題是有Solution的話 [01:09:18] 它是不是一定能夠找到Solution [01:09:21] 比如說 [01:09:27] 我從A走到B [01:09:29] 可能我有很多種走法 [01:09:31] 對不對 [01:09:32] 我有好多種Solutions [01:09:35] 那評判一個演算法的第一種指標 [01:09:38] 可能是說 [01:09:39] 如果它有Solution [01:09:41] 你是不是一定就能夠找到Solution [01:09:44] 當然也有一些問題是沒有Solution的 [01:09:47] 那種就目前暫時 [01:09:49] 不在我們的考慮 [01:09:51] 如果它有Solution [01:09:52] 是不是一定能夠找到Solution [01:09:54] 這個叫做Completeness [01:09:57] 這叫Completeness [01:09:58] 第二個 [01:10:00] 如果它可以找到 [01:10:02] 找到了是不是最佳的Solution [01:10:06] 這個叫做Optimality [01:10:11] 這個搜尋的策略 [01:10:13] 是不是能夠找到最好的解 [01:10:15] 第三個Complicity [01:10:19] 實踐複雜度是怎麼樣 [01:10:23] 你要花多久的時間來找到 [01:10:26] 解答 [01:10:28] OK [01:10:29] 那這邊當然就會跟電機資工的同學 [01:10:33] 你可能會比較熟悉 [01:10:35] Time Completeness [01:10:36] 如果你不是電機資工的 [01:10:38] 可能你自己要補充一點背景知識 [01:10:42] 那再來就是Space Completeness [01:10:44] 就是你的這個演算法的運作 [01:10:47] 你要花多少Memory [01:10:50] 你可以從這幾個不同的角度 [01:10:52] 來去評判一個演算法 [01:10:54] 那我們先來講一種最簡單的 [01:10:57] 做法 [01:10:58] 叫做Uninformed Search [01:11:00] 又稱呼是Blind Search [01:11:03] 就是盲目的搜尋 [01:11:05] 有一大類的演算法 [01:11:07] 是這種所謂的盲目搜尋 [01:11:10] 這個的意思是說呢 [01:11:12] 這種策略是說 [01:11:13] 我除了告訴你原本問題的定義之外 [01:11:17] 比如說除了這個羅馬尼亞的地圖 [01:11:23] 我告訴你羅馬尼亞的地圖 [01:11:25] 然後ABCD到Z的都市的都市 [01:11:27] 以及它個別的道路的連結 [01:11:30] 還有道路連結上面的里程數 [01:11:34] 我除了告訴你這個之外 [01:11:35] 我其他全部不告訴你 [01:11:37] 那你就依賴我告訴你這些資訊 [01:11:40] 去找出如何從A找到B這樣子 [01:11:45] 這種叫做Uninformed Search的這個分類 [01:11:49] All they can do is to generate successors [01:11:54] and distinguish a goal state [01:11:56] from a non-goal state [01:11:58] 他能夠做的事情就是說 [01:11:59] 我從某個地方出發 [01:12:00] 然後往外走 [01:12:02] 然後走過去之後呢 [01:12:03] 判斷一下說 [01:12:04] 這是我的目的地 [01:12:06] 就這樣 [01:12:07] 他只能夠做這件事 [01:12:09] 那不同的搜尋策略 [01:12:14] 它如何進行不同的分類 [01:12:17] 我如果去區分它呢 [01:12:18] 那就跟我今天是用什麼樣子的順序 [01:12:22] 來搜尋這一棵樹是有差的 [01:12:26] 那相對來講呢 [01:12:28] 如果說我知道的比 [01:12:33] 剛剛問題的定義更多的話 [01:12:36] 比如說我大概知道 [01:12:39] 往哪個方向走 [01:12:41] 可能會離B這個城市更接近的話 [01:12:45] 如果我額外多知道這個資訊的話 [01:12:47] 那它就屬於是Informed Search [01:12:50] 或者是Heuristic Search的範圍 [01:12:52] 那這個我們等一下再講 [01:12:54] 我們先來講Informed Search [01:12:56] 其中一個最有名的 [01:12:58] 應該大家大一大二也都學過的演算法 [01:13:02] 就是BFS [01:13:04] Bread First Search [01:13:06] 寬度 [01:13:08] 廣度 [01:13:10] 廣度優先的搜尋演算法 [01:13:13] 那它其實概念很簡單 [01:13:16] 就是說呢 [01:13:17] 我就先從A [01:13:19] 我從A出發嘛 [01:13:20] 那我去走去B [01:13:22] 走去S看看 [01:13:23] 是不是我的目的地 [01:13:25] 如果不是 [01:13:26] 那我再去看 [01:13:27] 從A這邊我走去T [01:13:30] 是不是我的目的地 [01:13:31] 不是 [01:13:32] 那再回過來 [01:13:33] 我把A可以走出去的所有分子 [01:13:35] 都先走一次 [01:13:39] 都走一次 [01:13:40] 然後呢 [01:13:41] 都不是我的目的地嘛 [01:13:42] 那接下來 [01:13:43] 我剛剛的第一個分子是S [01:13:46] 我再試試看 [01:13:47] 我從S走出去的所有分子 [01:13:49] 看看有沒有走到我的目的地 [01:13:51] 就這樣 [01:13:52] 依此類推 [01:13:53] 一路這樣子往下展開 [01:13:54] 所以底下這是另外一個示意圖 [01:13:56] 從A [01:13:57] 先check一下B [01:13:59] 是不是目標 [01:14:00] 不是 [01:14:01] 回來 [01:14:02] 再走C [01:14:03] 是不是目的地 [01:14:04] 不是 [01:14:05] 回來 [01:14:06] 再從B繼續往下走 [01:14:07] 它的分子 [01:14:08] D是不是 [01:14:09] 不是 [01:14:10] E是不是 [01:14:11] 不是 [01:14:12] 那一路這樣子展開 [01:14:13] 所以它是屬於 [01:14:14] 廣度優先的搜尋策略 [01:14:18] OK [01:14:19] 就這麼簡單 [01:14:20] 它就這麼運作了 [01:14:22] 那BFS呢 [01:14:23] 你可以想像 [01:14:24] 稍微分析一下 [01:14:26] 假設啊 [01:14:27] 在這個tree裡面 [01:14:29] 每一個node [01:14:31] 都有B這麼多個successor [01:14:34] 也就是說都有B這麼多個分子可以走 [01:14:36] 好 [01:14:37] 所以呢 [01:14:38] 因你從root出發 [01:14:40] 你就有 [01:14:41] 在你往下的第一層 [01:14:43] 你就有B這麼多個分子 [01:14:45] 那每一個分子 [01:14:47] 另外又有B這麼多個分子 [01:14:49] 所以在第二層 [01:14:50] 就會有B平方 [01:14:51] 這麼多個node [01:14:53] 再往下一層 [01:14:54] 就會有B的三次方 [01:14:55] 這麼多個node [01:14:56] 因此 [01:14:58] 假設 [01:14:59] 你要把整顆tree [01:15:01] 假設這一顆tree [01:15:02] 它的深度是D [01:15:04] 也就是說有D這麼多層的話 [01:15:06] 你會展開出多少個node呢 [01:15:09] 就是B加上B平方 [01:15:11] 加B正方 [01:15:12] 加上B的D次方 [01:15:14] 對不對 [01:15:15] 好 [01:15:16] 那這個東西呢 [01:15:17] 就這個time complexity來講 [01:15:20] 它就是BIG OF B的D次方 [01:15:23] 好 [01:15:24] 那抱歉 [01:15:25] 如果說你沒有學過BIG OF的話 [01:15:27] 同學你可能要自己去查一下 [01:15:29] 我們假設你來修正門課 [01:15:32] 你其實是有這些幾個素養的 [01:15:35] 這其實是 [01:15:37] 子宮可能大二的時候 [01:15:39] 會介紹的對不對 [01:15:41] time complexity的一個說明 [01:15:45] 所以它其實它的time complexity [01:15:48] 以及它的memory的需求其實很大的 [01:15:51] 這是BFS [01:15:52] 好 [01:15:53] 那我們來看一下 [01:15:54] 這是一個範例 [01:15:55] 這個多大呢 [01:15:56] 有那麼嚴重嗎 [01:15:57] 假設今天 [01:15:58] 我平均每一個node都有十個分支 [01:16:04] 假設我走訪 [01:16:05] 我去check一個node [01:16:06] 我去generate一個node [01:16:08] 所需花的時間呢 [01:16:11] 是 [01:16:12] 假設我一秒鐘就可以check [01:16:14] 一百萬個node好了 [01:16:16] 一秒鐘 [01:16:17] 好 [01:16:18] 那假設每個node呢 [01:16:20] 是1K [01:16:23] 1千 [01:16:24] 對1K [01:16:25] 好 [01:16:26] 1千個byte [01:16:27] 好 [01:16:28] 那今天 [01:16:29] 你的這棵樹的深度 [01:16:31] 如果是兩層的話 [01:16:33] 你就為110個node [01:16:35] 你要花0.11個minisecond [01:16:37] 你要花107K kilobyte [01:16:41] 如果你的深度變成十層 [01:16:43] 你就為十個十次方個node [01:16:46] 你就要花三個小時 [01:16:49] 去generate這些node [01:16:51] 你所需的memory就會十個terabyte [01:16:53] 如果是十六層 [01:16:55] 你就要花三百五十年 [01:16:58] 去generate這些node [01:17:00] 然後呢 [01:17:01] 你的memory是十個exabyte [01:17:04] 所以事實上我們可以知道說 [01:17:06] 當你的這個tree的深度 [01:17:09] 增加的時候 [01:17:11] 你所需的時間跟所需的空間 [01:17:14] 會急劇的增加 [01:17:16] 這是BFS [01:17:18] 好 [01:17:20] 好 [01:17:21] 那 [01:17:23] 另外一個聰明一點 [01:17:24] 一樣是 [01:17:25] Informed Search的一個策略 [01:17:27] 大家 [01:17:28] 可能有一些同學也都學過了 [01:17:31] 就叫做Dijkstra Algorithm [01:17:34] 這個是在理論 [01:17:37] Theoretical Computer Science這個領域裡面 [01:17:39] 這個去稱呼它 [01:17:41] 在AI這個領域呢 [01:17:42] 其實因為當年幾十年前 [01:17:44] 大家其實都各自發展嘛 [01:17:45] 有時候 [01:17:46] 也搞不清楚別人已經提過同樣的東西了 [01:17:49] 在AI這個領域 [01:17:50] 當時提出來的時候 [01:17:51] 它叫做Uniform Cost Search [01:17:54] 但其實它跟Dijkstra Algorithm [01:17:56] 是一樣的意思 [01:17:58] 它的意思是說呢 [01:18:00] Uniform Cost Search [01:18:01] expand the node n with the lowest pass cost g n [01:18:07] 也就是說每次我在展開 [01:18:09] 我要決定我要往哪一個分子走的時候 [01:18:13] 像剛剛的BFS是 [01:18:15] 我管它的 [01:18:16] 我就每一個分子 [01:18:17] 我所有可以走的分子 [01:18:18] 我就走一遍嘛 [01:18:19] 對不對 [01:18:20] 好 [01:18:21] 那它現在有一個選擇性 [01:18:23] 它利用到 [01:18:25] 我走過去之後 [01:18:29] 需要花的里程這個資訊 [01:18:31] 因為這個也算是我一開始的問題 [01:18:35] 一開始問題在定義的時候 [01:18:36] 就已經有給過的資訊 [01:18:39] The algorithm tests for goals [01:18:41] only when you expand a node [01:18:43] not when you generate a node [01:18:45] 好 [01:18:46] 所以這裡舉個例子 [01:18:47] 假設我現在已經走到S了 [01:18:49] 我接下來可以走到R也可以走到F [01:18:52] 那我走到 [01:18:53] 走去哪裡呢 [01:18:54] 那我們看一下吧 [01:18:55] 我如果走到R [01:18:57] 我如果去走到R [01:19:03] 我會花80 [01:19:06] 那你從R再繼續往下走 [01:19:09] 你如果真的expand的時候 [01:19:11] 你expand [01:19:13] 你真的走過來的 [01:19:15] 你真的走過來 [01:19:16] 那接下來呢 [01:19:18] 你去check一下 [01:19:20] 這是我的目標 [01:19:21] 不是R [01:19:22] 這個都是不是我的目標 [01:19:23] 我的目標是 [01:19:24] ButcherRest這個嘛 [01:19:26] 所以呢 [01:19:27] 我走來這裡了 [01:19:29] 我花了80 [01:19:30] 然後呢 [01:19:31] 我去Generate [01:19:33] 它可以走出去的分支 [01:19:36] 它走出去的分支就P嘛 [01:19:39] 那P的話呢 [01:19:41] 其實我已經知道說 [01:19:42] 我如果是走P [01:19:43] 我如果走P這條路 [01:19:45] 我要再加97 [01:19:47] 這麼多個cost [01:19:48] 所以我就知道了 [01:19:50] 我走到這裡來呢 [01:19:52] 我的cost已經知道 [01:19:54] 就會是80加97啦 [01:19:57] 好 [01:19:58] 那接下來 [01:20:00] 我現在如果是走這一條的話 [01:20:02] 我會需要花177的cost [01:20:05] 那接下來我看一下 [01:20:06] 另外一個分支 [01:20:08] 我另外這個分支 [01:20:09] 這裡只要99耶 [01:20:11] 那我走過來看看 [01:20:13] 那我走過來了 [01:20:14] 但是因為這個過來之後呢 [01:20:17] 它接下來也只有一條路 [01:20:19] 這一條路我Generate出來是211 [01:20:21] 那我就知道說 [01:20:22] 99加21 [01:20:23] 所以其實我如果走這一條路啊 [01:20:25] 我要刷3110 [01:20:27] 那我就相較之下 [01:20:32] 那我就知道說 [01:20:33] 其實這個也不是那麼好 [01:20:35] 所以我就回過頭來走這個1 [01:20:38] 然後expand到P [01:20:40] 然後呢再Generate到101 [01:20:43] 那怎麼加起來呢 [01:20:44] 是278 [01:20:45] 所以相較之下呢 [01:20:47] 這個278 [01:20:49] 是一個比較好的一個路徑 [01:20:52] 所以它到現在 [01:20:55] 這個Gystra Algorithm呢 [01:20:56] 它就是一個 [01:20:58] 有利用到你的Cost [01:21:02] 有考慮到Pass Cost的一個演算法 [01:21:05] 這樣 [01:21:06] 好 [01:21:07] 所以這裡要釐清一個點 [01:21:08] 就是說Uninformed [01:21:10] 你看字面上的意義 [01:21:11] Uninformed的意思就是說 [01:21:13] 沒有被通知 [01:21:15] 沒有被告知的意思 [01:21:17] 所以這裡Uninformed的意思 [01:21:19] 不是說完全沒有任何資訊 [01:21:22] 它不是這個意思 [01:21:24] 就是說它沒有用到任何 [01:21:26] 關於目標有多元的額外資訊 [01:21:31] 好 [01:21:32] 好 [01:21:33] 那所以說呢這個Uniform Search [01:21:37] 基本上呢 [01:21:38] It's optimal in general [01:21:40] 什麼意思 [01:21:41] 回到剛剛我們講 [01:21:42] 評判一個演算法好不好 [01:21:43] 就是說 [01:21:44] 你如果可以找到解的話 [01:21:46] 你找到的是不是最佳解 [01:21:48] 好 [01:21:49] 他說呢這個Uniform Cost Search呢 [01:21:51] 基本上 [01:21:52] 可以找到最佳解 [01:21:54] 其實BFS也可以找最佳解啦 [01:21:57] 你去全部都掃一遍 [01:21:59] 然後找到Cost的最低那個 [01:22:01] 就是你的最佳解 [01:22:02] 好 [01:22:03] 那Uniform Cost Search呢 [01:22:06] Expand node in order of their optimal Pass Cost [01:22:10] 不過它在Expand node的時候 [01:22:12] 是有稍微聰明一點 [01:22:14] 稍微聰明一點 [01:22:16] 那他說呢它是Guided by Pass Cost [01:22:19] Relative Depth [01:22:20] 所以你在展開的時候啊 [01:22:23] 是根據你走到目前這邊為止 [01:22:27] 你所需花的Cost [01:22:29] 來進行展開的確定 [01:22:33] 跟BFS不一樣 [01:22:34] BFS是 [01:22:36] 我就先展開第一層 [01:22:38] 再來展開第二層 [01:22:40] 再來展開第三層 [01:22:42] 所以它是Order by Depth [01:22:44] BFS是Order by Depth [01:22:46] 然後呢Uniform Cost Search [01:22:48] 是Order by Pass Cost [01:22:52] OK [01:22:54] 這是最主要的一個差別 [01:22:56] 那到時候步驟 [01:22:58] 如果假設今天 [01:23:00] 你不管走哪一個分支 [01:23:02] 你的Cost都一模一樣的時候呢 [01:23:04] 其實Uniform Cost Search呢 [01:23:06] 就類似像是BFS一樣 [01:23:09] 這當然這是一個特例 [01:23:13] 好 [01:23:14] 那所以大家也算有學過BFS [01:23:17] 廣度優先的搜尋 [01:23:19] 那你也學過DFS啊 [01:23:21] 深度優先的搜尋 [01:23:23] 我想很多人也都知道了 [01:23:25] 那就是說呢 [01:23:26] 我一條路走到黑 [01:23:30] 我第一從Root出發 [01:23:32] 我展開第一層 [01:23:34] 那接下來呢 [01:23:35] 第一層的第一個Node [01:23:36] 我再展開它的分支 [01:23:39] 的第一個分支 [01:23:41] 然後呢 [01:23:42] 我再走第一個分支的 [01:23:44] 第一個分支的第一個分支 [01:23:45] 一路我把走到最深層為止 [01:23:49] 如果走到Edge這裡 [01:23:51] 不是我的目的地 [01:23:53] 那我就回過頭來到上一層 [01:23:55] 再走上一層的 [01:23:57] 另外一個分支 [01:23:58] 看一下I [01:23:59] I也不是我的目的地 [01:24:00] 那我再回到上面的D [01:24:02] 再回到上面的B [01:24:04] 然後再去展開這個E [01:24:06] 然後依此類推 [01:24:07] E再往下展開 [01:24:09] 然後呢 [01:24:10] K再展開 [01:24:12] 依此類推 [01:24:13] 這叫深度優先的搜尋 ## 8. 寫作規則 （這是 `_筆記SOP.md` 第 3.1、4、5、6 節的濃縮版。兩者衝突時以 SOP 為準。） 讀者：碩士生，兩門課期末是英文考試。要只看筆記就能學會，講得比老師好懂。畫面要簡潔。 **最高原則：Notion 是主教材，不是輔助（2026-10-04 主理人）**。主理人看不懂老師的英文簡報、數學和底層內容，**不看影片、不看投影片，只讀這一章也要學得會**。寫完用這三題自我檢查，任一題答「否」就補： 1. **數學段**：每個收起來的數學段，預設看得到的地方有沒有一句白話說明「這段公式想解決什麼問題、算出來代表什麼」？（例：「這段推導的目的是找出走哪個方向分數上升最快，結果就是梯度。」）只寫「可跳過」不算。 2. **英文圖**：每張投影片圖，下面有沒有把圖上的英文重點翻成中文（2–5 點）並說明這張圖在講什麼？ 3. **底層知識**：這章用到、但老師沒解釋的東西（數學名詞、程式名詞、前幾週的概念），有沒有用白話補上（一兩句或「要先懂什麼？」摺疊）？前幾週學過的概念，附一句提醒＋連結。 **概念優先（2026-09-26 主理人）**：主理人只想懂概念，不想補數學、不想看程式碼和座標圖。兩門課的考試也都是問答題、不考算式（AI W1 1:16:52；NLP W3 1:47:41、2:48:36）。所以： - 每段預設看得到的只有：白話摘要（2–4 句）＋**一句生活比喻**（例：模擬退火像投資理財，年輕時敢冒險、越老越保守）＋「考試可能怎麼問」一句。 - 數學推導、公式、手算、程式碼、座標圖，全部收進標題寫「（進階，可跳過）」的摺疊，例如「它到底怎麼運作？（進階，可跳過）」。每段最多一個進階摺疊，不要寫長篇計算。 - 演算法要能「用文字說出步驟」（考試可能要你描述），這一點放在預設看得到的地方，不用數字。 - **重心比例**：白話理論與概念模式（它在解決什麼問題、核心想法、跟別的方法差在哪、優缺點、生活比喻）占主要篇幅；數學與程式細節只用一兩句帶過，細節收進進階摺疊。 **圖文並茂（2026-09-26 主理人：不要只有文字）**： - 每章至少 2–3 個圖，放在**預設看得到**的地方，每個圖前後各用一兩句白話說明「這張圖在看什麼」。 - 流程、步驟、因果、比較 → 用 mermaid 流程圖（```mermaid，flowchart LR 或 TD；節點文字用中文、加雙引號；一張圖不超過 10 個節點）。 - 投影片上的示意圖、架構圖 → 用 [[IMG: …]] 放投影片圖。 - 仍守「每個 ## 段落最多一種視覺元素」。 ### 輸出兩個檔 1. `chNN.md`（Notion 寫法，不含頁面標題），結構固定： - 第一行：章節包第 1 節那行，原樣照抄。 - 第二行起（有數學段才寫）：**跳過提示**，每段一行，讓主理人看影片時知道從哪跳到哪。用章節包第 3b 節的候選當提示，對照第 7 節逐字稿確認（只標老師連續講公式、推導、矩陣、微積分、機率計算、程式細節超過約 1 分鐘的段落；概念講解和比喻不算）： `跳過提示：(1:31:02–1:35:40) 老師在推導梯度公式，聽不懂可以直接跳到 [1:35:40](YouTube 連結)，接著講「步長 α 怎麼選」。` - `## 重點`：三點中文，每點一到兩句。 - `## Exam-ready`：3–10 行英文，**從章節包的投影片文字逐字抄**，每行 `- **Term**: "原句"（Ch3 p.14）`。老師有明確證據才在行尾加 `【老師強調】(h:mm:ss)`。 **每一行下面一定要有一行縮排的中文解釋**（主理人英文不好，看不懂的英文等於沒用）： ``` - **Hill climbing**: "It keeps track of one current state and on each iteration moves to the neighboring state with highest value."（Ch4 p.5） - 中文：爬山法只記住「現在這一個狀態」，每一輪都移到分數最高的鄰居。白話：一直往比較高的地方走一步。 ``` 中文要先把句子意思講清楚，再補一句白話；最後用「英文（中文）」列出這句裡 1–3 個難字，例：sparse（稀疏）、distinct terms（不重複的字）。 **一行只放一句投影片原句**。同一頁有多句要考就拆成多行，每行各接一行中文；不要用分號串三句以上，不要把計算量 O(...) 塞進去。 - 章節包第 2 節的每一段：`## [h:mm:ss](連結) 標題`（照抄），下面 2–4 句白話摘要，其餘全部收進摺疊： ```
問句（例：用生活例子講，BFS 在做什麼？） 內容
``` 摺疊種類（需要才放）：用生活例子講？／它到底怎麼運作？／要先懂什麼？（老師假設你會的數學或概念，短版教學）／老師原話是什麼？（「原話」(h:mm:ss)，只放重要的，最多 5 句）。 - 「它到底怎麼運作？」要用一組小數字把這段的演算法**真的跑 1–3 步**（例：算出梯度、更新一次、比較兩個 α），不是只示範定義的加減乘除。全章盡量沿用同一組數字，讓前一段的答案能在下一段被驗證。 - 每段正文要回答讀者最可能卡住的一個「為什麼」。投影片公式方向跟題目相反、或投影片說「解不出來」時，用一兩句講出原因，自己補的標（我補充）。 - 投影片句子停在公式前（公式在圖裡）時：Exam-ready 在粗體詞條上補公式、引號內保持原句；正文寫出同一條式子。公式圖看章節包第 6 節列出的 PNG。 - `## Self-check`：2–4 題英文考題，答案收摺疊。**至少一題考老師強調的內容**；只出 explain／why／compare 這類問答題，**不出要代數字計算的題目**（考試不考算式）；不出「老師和投影片哪裡不同」這類不會考的題目。每題格式： ```
Q1. English question?（中文：中文題目） **Answer**: English answer. 中文：把答案完整講一遍（不是只翻一句），讓看不懂英文的人也知道要怎麼答。
``` - **最後一行**：章節包第 1b 節那行（下一章連結），原樣照抄。讓讀完的人直接點下一章。 - 不要把章節包或這份規則裡的指示句寫進筆記（例如「寫筆記時照投影片寫」「已改正 ASR 錯字」）。 - 長度：全文不超過 16,000 字元（跟 check_note.py 同一個數字）。**不要為了壓字數反覆刪改**（實測一章最多花 12 輪在刪字）；超過時只刪進階摺疊裡的第二組算例，比喻、比較表、圖說、「老師說不用背」的提醒都不刪。 - 預設看得到的正文不放計算量 O(...)、代號對照（例如 SMART 字母）、課本出處考據，一律移進進階摺疊。 2. `chNN.concepts.json`：JSON 陣列，4–12 個考試可能問的術語，每個物件： `name`（英文）、`zh`、`type`（概念／演算法／公式／人物事件／前置知識／行政）、`signal`（"老師說會考"／"老師強調"／"核心（我判斷）"／""）、`evidence`（有 signal 前兩種時必填：原句＋時間）、`definition_en`（投影片原句；沒有就註明 (textbook)／(lecture)／(my wording)）、`plain`（一句中文）、`a4`（≤150 字元英文，可夾極短中文；期末拼貼用的小方塊）、`time`、`slides`、`prereq`（英文名陣列）。 ### 風格鐵律 - 不用 emoji 或裝飾符號（✓✗★⚠ 都不要；→ 可以）。不用 callout。不用 `$`。時間不要用 code 樣式。 - 每個 `##` 段落最多一種視覺元素：一張圖、或一個表格、或一個 mermaid。 - 摺疊標題是問句，前面不加符號。 - 圖片最多 3 張，只放文字取代不了的圖。放法：單獨一行 `[[IMG: | 中文圖說]]`，PNG 用 `slides_to_png.py <圖片資料夾> <頁> --dpi=110` 產生。 - 考試訊號只在老師明確說時標。老師只說「不用背」「不講」就寫「注意：……」。 - 老師口誤或跟投影片不同：照投影片寫，加「注意：老師口頭說的是……」。 - 引用老師的話時，ASR 錯字改成正確的字。 ### 沒有投影片時 不要憑記憶逐字重現課本段落或數值表。英文定義用自己的話寫、句尾標 (my wording)；Exam-ready 每行標「（自擬，投影片待補）」。例子只用老師講的。 ### 寫完之後（只做一次） 跑檢查： `C:\Users\user\.cache\meeting-record\venv\Scripts\python.exe C:\Users\user\.claude\scripts\check_note.py --transcript <逐字稿> --slides <投影片 txt …> --start <起> --end <訖> --vid <影片 ID>` - STYLE／VISUAL／TIME／FORMAT：全部改掉。 - QUOTE：確認是不是你改正了 ASR 錯字（是就保留），不是就改成原文或拿掉引號。 - ENGLISH：確認是不是投影片斷行造成的（是就保留），不是就改成投影片原句。 **省額度守則**：章節包裡已經有你需要的全部資料。不要再去讀整份逐字稿、整份投影片、segments.json 或手冊。一次寫好整個檔（Write 一次），檢查後集中修改。