# 章節包：人工智慧導論（AI）W2（9/17）第 05 章「DFS 家族與雙向搜尋」
影片 1:23:14–1:43:47，YouTube ID hNZQIO0q74o，逐字稿 C:\D槽\TAICA課程\人工智慧導論\第二周1150917\W2_人工智慧導論_朱威達.逐字稿.txt。Notion 章節頁 https://app.notion.com/p/3e6fc631b03081bda674f874680e4a09（頁 ID 3e6fc631-b030-81bd-a674-f874680e4a09），頁面標題「05 DFS 家族與雙向搜尋（1:23–1:43）」。
## 1. 第一行（直接照抄，不要改）
[人工智慧導論](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)
## 1b. 最後一行（直接照抄，放在 Self-check 後面，當全頁最後一行）
讀完了嗎？下一章：[06 Greedy 與 A* 搜尋（1:56–2:11）](https://app.notion.com/p/3e6fc631b03081f7acf6d56761c8225c)｜回到週頁：[W2（9/17）](https://app.notion.com/p/3e6fc631b0308175a433e5fa4bc500df)
## 2. 各段標題（照順序；每段一個 ## 標題，直接照抄連結）
- `## [1:23:14](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4994s) DFS 一條路走到底` 老師講什麼：從 root 沿第一個分支一路走到最深，不是目標就退回上一層換另一個分支。
- `## [1:24:17](https://www.youtube.com/watch?v=hNZQIO0q74o&t=5057s) DFS 時間差、空間省` 老師講什麼：最糟時間 O(b^m)，m 是最大深度，可能遠大於最淺解的深度 d；但只要記目前這條路徑和沿途還沒展開的兄弟節點，空間只要 O(bm)，遠低於 BFS。
- `## [1:28:06](https://www.youtube.com/watch?v=hNZQIO0q74o&t=5286s) Depth-limited search 與 AI agent 類比` 老師講什麼：替 DFS 加一個深度上限 L，避免在很深的子樹白花時間；老師用現在的 AI agent 做事時若一路 DFS 會跑很久、鬼打牆來比喻。
- `## [1:31:26](https://www.youtube.com/watch?v=hNZQIO0q74o&t=5486s) 深度上限的代價與領域知識` 老師講什麼：設了上限可能找不到解（incomplete），也不保證最佳；若有領域知識（羅馬尼亞任兩城最多 9 步）就能把 L 設成 9。
- `## [1:32:49](https://www.youtube.com/watch?v=hNZQIO0q74o&t=5569s) Iterative deepening DFS` 老師講什麼：不知道 L 怎麼設時，從小到大逐步放寬深度上限；兼有 DFS 的低記憶體與 BFS 的完整性，路徑成本隨深度不減時也是最佳的。
- `## [1:34:47](https://www.youtube.com/watch?v=hNZQIO0q74o&t=5687s) 重複展開其實不太浪費` 老師講什麼：上層會被重複展開看似浪費，但大部分節點都在最底層（例：底層 8 個、上面兩層共 6 個），樹越深差距越大，所以浪費沒有想像中大。
- `## [1:38:02](https://www.youtube.com/watch?v=hNZQIO0q74o&t=5882s) Bidirectional search` 老師講什麼：從起點和目標兩端同時搜，兩邊 frontier 交會就找到解（像雪隧兩端同時開挖），約 O(b^(d/2))；要能往回推前一步，地圖與 8-puzzle 容易，8-queens 這種抽象目標就難。
- `## [1:41:56](https://www.youtube.com/watch?v=hNZQIO0q74o&t=6116s) 前半總結與分組問答` 老師講什麼：Ch3 前半是 uninformed search，後半要講 informed search；回答問題：組員退選可以併到別組，但不管怎麼變最多四人一組。
## 3. 老師強調／會考／不考的地方（原句已驗證；寫進筆記時 ASR 錯字要改正）
（無）
## 3b. 數學段候選（程式抓的，只是提示；寫「跳過提示」行用）
0 段候選（門檻 3.0 字／30 秒）
## 4. 這章摘要與重要度
DFS 一路走到底、省記憶體卻可能白走深樹，因此有 depth-limited 與 iterative deepening 兩種折衷，最後介紹從兩端同時搜的 bidirectional 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.19 → C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\brief_Ch3_p019.png
- Ch3 p.21 → C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\brief_Ch3_p021.png
- Ch3 p.22 → C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\brief_Ch3_p022.png
- Ch3 p.23 → C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\brief_Ch3_p023.png
- Ch3 p.24 → C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\brief_Ch3_p024.png
- Ch3 p.26 → C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\brief_Ch3_p026.png
--- Ch3 p.18 ---
• Depth-first search (DFS)
• Expands the deepest node in the current frontier of the search tree.
Uninformed Search Strategies
18
--- Ch3 p.19 ---
• Depth-first search (DFS)
• Time complexity: 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
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).
Uninformed Search Strategies
19
--- Ch3 p.20 ---
• Depth-first search (DFS)
• Space complexity: 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.
• For a state space with branching factor b and maximum
depth m, DFS requires storage of only nodes.
Uninformed Search Strategies
20
--- Ch3 p.21 ---
• Depth-limited search
• Supply depth-first search with a predetermined depth limit
• Incompleteness
• Nonoptimal
• Sometimes, depth limits can be based on knowledge of the problem.
For example, if we check carefully, we would discover that any city
can be reached from any other city in at most 9 steps, i.e.,
leads to a more efficient depth-limited search.
Uninformed Search Strategies
21
--- Ch3 p.22 ---
• Iterative deepening DFS
• 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.
• Iterative deepening combines the benefits of depth-first and breadth-
first search. 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.
Uninformed Search Strategies
22
--- Ch3 p.23 ---
• Iterative deepening DFS
• 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.
Uninformed Search Strategies
23
--- Ch3 p.24 ---
• Iterative deepening DFS
• 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.
Uninformed Search Strategies
24
--- Ch3 p.25 ---
• 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 is much less than
• Bidirectional search is implemented by replacing the goal test with a
check to see whether the frontiers of the two searches intersect; if they
do, a solution has been found.
Uninformed Search Strategies
25
--- Ch3 p.26 ---
• Bidirectional search
• 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.
Uninformed Search Strategies
26
## 7. 逐字稿（1:23:14 前後各多 1 分鐘，原始行）
[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] 這叫深度優先的搜尋
[01:24:17] 那DFS呢
[01:24:20] 它的Time Complexity呢
[01:24:23] 是Bounded by the Size of
[01:24:25] State Space
[01:24:30] In general may generate all of the
[01:24:32] big ol' B的M字吧
[01:24:34] 其中M呢是Mesmer Depth
[01:24:38] M呢
[01:24:39] 對
[01:24:40] 就是說假設今天
[01:24:42] 你每一個Node
[01:24:44] 都有B這麼多個分支
[01:24:48] 然後假設你的深度
[01:24:51] 是
[01:24:52] 深度是
[01:24:56] 最深的那個
[01:24:59] 最深的那個層數
[01:25:04] 比如說
[01:25:05] 我今天這個數可能長得歪歪的
[01:25:07] 雖然我們這裡的數
[01:25:08] 看起來都好像是左右非常的平衡
[01:25:11] 但是其實有可能是
[01:25:13] 左邊這個數啊
[01:25:14] 一路往下長
[01:25:15] 長十層
[01:25:16] 然後右邊這個分支的數
[01:25:18] 可能只長三層
[01:25:20] 所以呢
[01:25:21] 這裡的M指的是
[01:25:23] 最深的那一層的深度
[01:25:26] 這樣
[01:25:27] 在最糟的情況之下呢
[01:25:29] DFS呢
[01:25:30] 有可能會生出
[01:25:31] big ol' B的M字吧
[01:25:36] 其中呢
[01:25:37] M可能遠大過於D
[01:25:40] D指的是
[01:25:41] The Depth of the Shadowless Solution
[01:25:43] 你說不定啊
[01:25:44] 你真正的正解
[01:25:46] 是在右邊的那個指數的一個比較淺的地方
[01:25:50] 就已經是你的解了
[01:25:52] 可是你
[01:25:53] 如果你是深度優先的展開的話
[01:25:56] 你會花很多的時間
[01:25:58] 去展開左邊很深的數
[01:26:01] 好
[01:26:03] 然後
[01:26:04] 殊不知
[01:26:05] 展開完之後
[01:26:08] 這個根本就是
[01:26:11] 你真正要的解答
[01:26:13] 其實就是在
[01:26:14] 右邊的這個指數的一個很淺的地方就有了
[01:26:18] OK
[01:26:20] 那
[01:26:21] 這個就是最糟的情況
[01:26:23] 這DFS
[01:26:25] 但是DFS的
[01:26:27] 優點是說
[01:26:28] 它的Space Complexity
[01:26:31] 是比較低的
[01:26:32] 比如說
[01:26:33] 它只需要儲存
[01:26:34] 它目前展開維持的
[01:26:36] 這一條路徑上面的這些Node就好了
[01:26:40] 其他都不用記
[01:26:42] 其他都不用記
[01:26:44] 當然要記一下
[01:26:45] 我目前展開的最深的這個
[01:26:47] 它的兄弟的Node是誰吧
[01:26:51] 所以它的Space Complexity是
[01:26:53] 遠低於BFS的
[01:26:55] 我們剛剛說過說
[01:26:57] 那個廣度優先的搜尋
[01:26:59] 又花時間又花Memory
[01:27:01] 那DFS呢
[01:27:03] 至少不太花Memory
[01:27:04] 因為你光看這個
[01:27:05] 其實它在展開左邊的指數到最深的時候
[01:27:09] 它只需要記錄下這個啦
[01:27:11] A B D I
[01:27:13] 還有這個E
[01:27:15] 這裡而已啊
[01:27:17] 右邊的這個
[01:27:18] 這個這裡都不需要記啊
[01:27:20] 這裡都不需要記
[01:27:22] 那反正這個如果不是我的目標
[01:27:24] 我就回過頭來
[01:27:26] 我只要
[01:27:27] 這都丟掉了嘛
[01:27:28] 這反正不是我的目的地嘛
[01:27:30] 所以它一次只要處理一個Pack
[01:27:33] 幾乎是一個Path
[01:27:35] 上面的Node就好
[01:27:37] 我只要記這些就好
[01:27:39] 這是DFS的優勢
[01:27:42] 所以理論上來講呢
[01:27:44] State Space
[01:27:46] 它的Branch是B
[01:27:48] 然後呢它最高深度是M的話呢
[01:27:50] 它大約只需要儲存
[01:27:52] Big O BxM
[01:27:57] 所以它所需的Memory是小很多的
[01:28:00] OK
[01:28:01] 好
[01:28:02] 這個理論上大家應該都學過了
[01:28:04] 都應該學過了
[01:28:06] 好那當然我們知道啦
[01:28:08] 這個DFS呢
[01:28:09] 它有它的缺點嘛
[01:28:10] 如果說今天要是很衰
[01:28:12] 我左邊的指數很深
[01:28:15] 那但是我根本我的解答
[01:28:17] 就在右邊指數的很淺的地方
[01:28:19] 那就很衰嘛
[01:28:20] 我花那麼多時間在展開左邊指數
[01:28:24] 那所以要如何取得一個平衡呢
[01:28:27] 有一種做法叫做
[01:28:29] Depth Limit Search
[01:28:32] Depth Limit Search
[01:28:34] 意思是說
[01:28:42] 你是跑DFS沒有錯
[01:28:44] 但是呢你給它一個限制
[01:28:48] 你往下搜尋
[01:28:50] 你最多就搜尋L這麼多層
[01:28:54] 你在左邊指數你搜尋最深到L這麼多層
[01:28:58] 搜尋不到你就要回來了
[01:29:00] 你要去看一下右邊的指數
[01:29:03] 這樣大家懂我意思嗎
[01:29:05] 其實這樣子的邏輯
[01:29:07] 我剛剛突然想到
[01:29:09] 這到現在這個邏輯
[01:29:12] 一樣是通的喔
[01:29:14] 我們現在不是你跑過
[01:29:16] 那個GPD-6 ASTRON沒有
[01:29:19] 他幫你做一些工作嘛對不對
[01:29:22] 所以你假設你今天交付給他一個工作
[01:29:25] 這個工作可能有幾種方法可以完成
[01:29:31] 但是哪一種方法可以完成他不知道
[01:29:33] 好有三種方法可以完成
[01:29:36] 如果今天他是用類似
[01:29:38] 比如說第一個方法
[01:29:41] 又可以拆開成三種不同的策略或子方法
[01:29:47] 那每一個子方法又有三種不同的input方式對不對
[01:29:51] 然後呢每一個input方式又有三種不同的參數設定
[01:29:55] 所以你看你想像一下
[01:29:58] even到今天你在跑GPD-6 ASTRON
[01:30:03] 你叫他做代理
[01:30:05] 他如果是笨笨的
[01:30:07] 一路都把
[01:30:09] 第一個方法裡面的
[01:30:11] 第一種input方式裡面的
[01:30:13] 第一種參數設定完再怎麼樣
[01:30:16] 都弄完了
[01:30:18] 然後再回過頭來看一下第二個方法
[01:30:20] DFS的話
[01:30:22] 我相信你們應該很快就會覺得說
[01:30:25] 他怎麼跑那麼久
[01:30:27] 所以我相信呢
[01:30:28] 當然我不知道他是怎麼做的
[01:30:30] 但是他們一定有某些策略是讓
[01:30:33] 有效尤其在之前比較早期
[01:30:37] 在我們A群
[01:30:38] 會產生鬼搭牆
[01:30:40] 一直跑步不斷的
[01:30:42] 在那邊繞
[01:30:43] 然後走進一個死胡桃
[01:30:44] 所以這裡就有點類似像這樣
[01:30:48] 你可以做所謂的Depth Limit Search
[01:30:51] 你讓他深度最多
[01:30:53] 你要求他最多就是走到L位置
[01:30:57] 那你也許可以避免掉
[01:31:00] 那麼衰
[01:31:01] 花很多時間在
[01:31:03] 處理左邊的某一個指數
[01:31:06] 明明答案就在右邊的一個比較淺的地方
[01:31:11] 但是這裡有另外一個問題
[01:31:13] 那說不定我真正的答案
[01:31:15] 就是在左邊指數很深的地方
[01:31:18] 對不對
[01:31:19] 所以你如果只限定他說
[01:31:21] 我的深度最多可以到L
[01:31:23] 那他可能就找不到解了
[01:31:26] 所以如果是Depth Limit Search
[01:31:29] 他就是Incomplete
[01:31:31] Complete的定義就是說
[01:31:34] 如果這個問題有解的話
[01:31:36] 你一定可以找得到解
[01:31:39] 那如果你設定了一個
[01:31:41] Upper bound L的話
[01:31:43] 那有可能找不到解
[01:31:45] 然後你找到的解
[01:31:46] 也有可能不是最佳解
[01:31:49] 那他說有的時候
[01:31:52] 這個Depth Limit的演算法
[01:31:55] 其實如果你對於這個問題
[01:31:58] 你有一個整體的
[01:32:00] Extra的Prior Knowledge的話
[01:32:03] 有一些事前的領域知識的話
[01:32:07] 其實搭配起來
[01:32:10] 可能是可以更有效率來解決你的問題的
[01:32:12] 比如說
[01:32:13] 在這個羅馬尼亞的地圖裡面
[01:32:16] Somehow你知道說
[01:32:19] 從任何某一個都市走到另外一個都市
[01:32:22] 絕對不會走超過9條
[01:32:25] 不同的
[01:32:26] 超過9步
[01:32:28] 那你如果是這樣的話
[01:32:30] 你就可以把你的深度的限制設定成9
[01:32:35] 因為你最多不可能走超過9步
[01:32:41] 如果你有這個知識的話
[01:32:43] 你就可以設定這個L
[01:32:44] 那既然L
[01:32:49] 你設定了一個L
[01:32:51] 你怎麼知道這個L要怎麼設定呢
[01:32:53] 除非你有這個知識
[01:32:55] 那你如果沒有這個事先的領域知識的話
[01:32:58] 有另外一種策略叫做
[01:33:00] Iterative Depth DFS
[01:33:02] 那就是我逐步的增加我的深度
[01:33:06] 所以一開始我允許你展開一層
[01:33:12] DFS做一層
[01:33:14] 最多
[01:33:15] 往下深入一層
[01:33:17] 如果都沒有找到解答
[01:33:19] 那我就允許你最多深入兩層
[01:33:23] 再沒有找到答案
[01:33:24] 我最多允許深入三層
[01:33:27] 一步一步的增加我的那個Libid L
[01:33:31] 逐步的增加那個L
[01:33:33] 這樣
[01:33:35] 好
[01:33:36] 那如果是這樣子的話呢
[01:33:38] 它其實這種做法呢
[01:33:40] 就有點混合了DFS跟BFS的好處
[01:33:45] 那比如說就像DFS
[01:33:47] 它的Memory Requirement是低的啊
[01:33:51] 所需的Memory是低的啊
[01:33:53] 那就好像BFS
[01:33:54] 它在限定之內
[01:33:56] 它真的是把所有可能的狀況都掌握了啊
[01:34:01] 好
[01:34:02] The branch factors is finite and optimal
[01:34:05] when pass cost is a non-decreasing function of depth
[01:34:08] 當然你的pass cost是
[01:34:10] 你多走一步你的cost就會增加
[01:34:12] 它是一個non-decreasing
[01:34:14] 就是不會多走一步
[01:34:16] 你的cost不會降低
[01:34:17] 一定是往上增加的
[01:34:18] 這叫non-decreasing
[01:34:20] 好
[01:34:21] 好所以這個概念就像這樣啊
[01:34:23] 我允許你一開始呢
[01:34:25] 我的深度限制是1
[01:34:27] 那你就是一次
[01:34:28] 你一定就是展開一層
[01:34:30] 沒找到答案
[01:34:32] 我讓你深度限制是2
[01:34:35] 沒找到答案
[01:34:36] 我讓你深度限制是3
[01:34:38] 這樣
[01:34:39] 一步一步的放鬆我的管制
[01:34:43] 直到你找到你的答案為止
[01:34:45] 這樣子
[01:34:46] 好
[01:34:47] 可是你聽到這裡
[01:34:49] 有沒有覺得
[01:34:50] 這樣好嗎
[01:34:52] 你不會覺得說這樣子好像
[01:34:55] 浪費了很多
[01:34:57] 有些地方好像重複的去展開啦
[01:35:01] 比如說你看啊
[01:35:02] 我假設允許
[01:35:04] 你的深度最多到三層
[01:35:08] 你看啊
[01:35:09] 在展開到第三層之前
[01:35:11] 這裡
[01:35:12] 四層相似
[01:35:16] 這裡不是剛剛這裡有做過嗎
[01:35:18] 包括這裡有做過嗎
[01:35:20] 所以你會覺得說
[01:35:22] 當你把你的limit提升到三層的時候
[01:35:25] 感覺從這裡到這裡的這個動作
[01:35:28] 這裡到這裡的動作
[01:35:30] 剛剛這裡有做過啊
[01:35:32] 那我不就浪費了很多的時間
[01:35:35] 我浪費時間在重複做同樣的動作
[01:35:37] 會有這種感覺
[01:35:39] 的確
[01:35:40] 直觀上你會有這種感覺
[01:35:42] 但他這裡告訴你
[01:35:43] 對的確是有一點浪費
[01:35:46] 但是沒有到你想像中的那麼浪費
[01:35:49] 好
[01:35:50] It turns out this is not too costly
[01:35:53] 為什麼呢
[01:35:54] 因為啊
[01:35:55] 這個樹呢
[01:35:57] 他大部分的node
[01:35:59] 甚至超過一半以上的node
[01:36:03] 其實都是在
[01:36:05] 你展開的最深的那一層
[01:36:08] 這裡
[01:36:11] 也就是說
[01:36:12] 雖然你今天你的limit從二
[01:36:15] 提升到三
[01:36:17] 可是你如果仔細看一下
[01:36:19] 你limit如果是二
[01:36:20] 你這裡展開的node分別幾個
[01:36:21] 一二三四五六
[01:36:22] 如果不算 root的話
[01:36:24] 就六個嘛
[01:36:25] 可是你如果今天展開到三層
[01:36:28] 你看三層的最底端
[01:36:30] 就有一二三四五六七八
[01:36:33] 光這裡就有八個node耶
[01:36:35] 所以呢
[01:36:37] 你不要那麼在意
[01:36:39] 三層以前的
[01:36:43] 這裡一二三四五六
[01:36:45] 這才六個node
[01:36:48] 對
[01:36:49] 你可以說
[01:36:50] 欸那我第二層
[01:36:51] 第一層到第二層的
[01:36:53] 這六個node
[01:36:54] 我是又重複展開一次啦
[01:36:56] 對不對
[01:36:57] 對這部分的確是有一點浪費
[01:37:00] 但他的浪費沒有浪費到你
[01:37:02] 你覺得超浪費耶
[01:37:05] 我在講什麼
[01:37:06] 因為為什麼
[01:37:07] 原因就在於說
[01:37:08] 你越
[01:37:09] 如果你這個tree越深
[01:37:11] 你最底層的
[01:37:13] 最細的最底層的這些node的數量
[01:37:17] 一下子就會遠遠超過
[01:37:19] 往上一層的所有的總和
[01:37:22] in this case
[01:37:23] 他就是超過的嘛
[01:37:24] 像這個就已經是包含了
[01:37:26] 一二三四五六七八
[01:37:28] 八個node
[01:37:29] 而
[01:37:31] 第二層加第一層的
[01:37:32] 總共展開的node也才六個
[01:37:35] 這件事情在你深入越深的時候
[01:37:38] 那個差距會越大
[01:37:40] 所以
[01:37:41] 的確有點浪費
[01:37:42] 但沒有浪費到
[01:37:44] 你想像中
[01:37:45] 你直覺想的
[01:37:46] 那麼誇張
[01:37:48] 這個就是所謂的
[01:37:49] Iterative Dimple DFS
[01:37:56] 那我們把這部分講完
[01:37:58] 我們再講下一個
[01:38:00] 再休息
[01:38:01] 好啦
[01:38:02] 那所以呢
[01:38:03] 我們剛剛前面講過BFS跟DFS
[01:38:06] 對不對
[01:38:07] 好
[01:38:08] 那聰明的人就想說
[01:38:09] 那我要
[01:38:10] 我其實在搜尋的時候
[01:38:12] 我當然目標就是說
[01:38:14] 最好是
[01:38:15] 越快找到答案越好
[01:38:18] 那我所說的
[01:38:19] 我需要的
[01:38:20] 記憶體能夠越少越好
[01:38:22] 好那所以呢
[01:38:23] 就有人想說
[01:38:24] 欸
[01:38:25] 反正我從一個地方出發
[01:38:28] 我要走到我的目標也
[01:38:30] 如果只有一個的話
[01:38:32] 我可不可以把目標
[01:38:34] 也當成是一個出發點
[01:38:36] 對不對
[01:38:37] 我從A要走到B嘛
[01:38:40] 我從A出發一路這樣展開
[01:38:43] 然後呢我也從B這個地方出發
[01:38:45] 一路往回推
[01:38:47] 欸要是走走走走走走到中間
[01:38:49] 某一個地方
[01:38:50] 剛好交匯到了
[01:38:51] 我就把它整個串起來
[01:38:53] 好不好
[01:38:58] 對不對
[01:38:59] 這就好像說這個
[01:39:00] 我們在蓋那個血稅的時候
[01:39:02] 臺北到宜蘭血稅的時候
[01:39:04] 當時蓋啦
[01:39:05] 是兩端同時
[01:39:08] 兩端同時
[01:39:09] 從宜蘭往臺北方向
[01:39:10] 臺北往宜蘭方向
[01:39:11] 兩端同時蓋
[01:39:12] 然後最後接起來這樣子
[01:39:15] 欸
[01:39:16] 對嘛
[01:39:17] 這個現實
[01:39:18] 這個概念上是這樣沒有錯
[01:39:20] 你可以從start
[01:39:21] 出發點
[01:39:22] 一路往外展開
[01:39:23] 然後呢
[01:39:24] 目的地一路往外展開
[01:39:27] 那在完美的情況下呢
[01:39:29] 概念上呢
[01:39:30] 你可能只需要
[01:39:32] 展開
[01:39:34] Big O B的二分之D次方
[01:39:36] D是指深度
[01:39:39] 那你有兩個Big O二的
[01:39:41] 二分之D次方
[01:39:42] 其實就是Big O
[01:39:45] B的二分之D次方
[01:39:48] 這個數值呢
[01:39:49] 遠遠小於B的D次方
[01:39:54] 這個叫Bidirectional Search
[01:39:56] 雙向的搜尋
[01:39:58] 那Bidirectional Search
[01:39:59] Is implemented by
[01:40:00] repressing the goal test
[01:40:01] with the check
[01:40:02] to see whether
[01:40:03] the frontier of two search
[01:40:05] interact
[01:40:06] intercept
[01:40:08] 它不是在找說
[01:40:09] 欸
[01:40:10] 我是不是已經抵達
[01:40:11] 某一個目的地了
[01:40:12] 它反而是在確認說
[01:40:13] 欸
[01:40:14] 我兩條支線
[01:40:16] 有沒有交匯
[01:40:18] 有沒有交匯
[01:40:19] 如果有交匯
[01:40:20] 那我就找到一個解答了
[01:40:22] 那這裡面呢
[01:40:25] 真的要做到這件事
[01:40:27] 其實並不容易啊
[01:40:28] 因為你從
[01:40:30] 你的目的地出發
[01:40:32] 往回找這件事情
[01:40:34] 不見得容易
[01:40:36] 好 不見得容易
[01:40:37] 以這個地圖來講
[01:40:40] 相對是容易的
[01:40:43] 因為
[01:40:44] 你就看著那個地圖嘛
[01:40:45] 對不對
[01:40:46] 你從B這個城市出發
[01:40:48] 你往外可以走哪裡
[01:40:50] 是很明確的
[01:40:51] OK
[01:40:52] 所以你如果以
[01:40:53] 羅馬尼亞的這個問題來講
[01:40:55] 你可以用白的Rational Search
[01:40:57] 好
[01:40:58] 可是呢
[01:40:59] 你如果
[01:41:00] 然後你如果是從
[01:41:02] A puzzle problem
[01:41:04] 就是那個
[01:41:05] 從那個
[01:41:11] 九宮格的那個問題
[01:41:13] 也相對容易
[01:41:15] 你的目的地在哪裡
[01:41:16] 然後呢
[01:41:17] 一路你去移動你那個空格
[01:41:19] 好
[01:41:20] 所以往回找上一步是什麼
[01:41:22] 這是相對容易的
[01:41:23] 但是如果說
[01:41:25] 你的目標是一個
[01:41:26] 比較抽象的描述
[01:41:28] 比如說八皇後的問題
[01:41:30] 八皇後的問題是什麼
[01:41:31] 就是沒有任何一隻皇后
[01:41:33] 會攻擊其他皇后
[01:41:36] 你的目標組是這一種的話
[01:41:39] 那白的Rational Search
[01:41:41] 就很難implement
[01:41:43] 就很難說
[01:41:47] 某一個盤面的前一個動作
[01:41:50] 一定是怎麼樣
[01:41:52] 那這是白的Rational Search
[01:41:54] OK
[01:41:56] 好
[01:41:57] 那所以呢
[01:41:58] 第三章這裡呢
[01:41:59] 其實我們講完一半了
[01:42:01] 它主要就分兩個
[01:42:03] 兩大塊
[01:42:05] 一塊叫做On Informed Search
[01:42:08] 就是沒有額外知道
[01:42:10] 目標資訊的搜尋法
[01:42:13] 那下一個
[01:42:14] 下半部分我們要講的就是
[01:42:16] Informed Search
[01:42:17] 你如果知道
[01:42:19] 一些額外的資訊的話
[01:42:21] 你的找到解答的
[01:42:23] 這個效率會很高
[01:42:25] OK
[01:42:26] 好 講到這邊
[01:42:27] 有沒有什麼問題
[01:42:32] 我們看一下線上
[01:42:33] 請好好上課
[01:42:46] 這個我也
[01:42:48] 獨宗家族園可以嗎
[01:42:59] 只要不要超過四位
[01:43:01] 是可以的
[01:43:02] 我們過去也曾經遇到過
[01:43:04] 就是說
[01:43:05] 誒 本來比如說
[01:43:07] 三個人一組好了
[01:43:09] 後來
[01:43:11] 這個課修到一半的時候
[01:43:13] 撐不下去
[01:43:14] 退選了
[01:43:15] 落跑了
[01:43:17] 然後就只剩下一個人
[01:43:19] 自己一個人一組
[01:43:20] 那他就覺得他撐不住
[01:43:22] 他就問說
[01:43:23] 那我可不可以去救命其他組
[01:43:25] 這樣子
[01:43:26] 那如果你找得到
[01:43:27] 的話
[01:43:28] 是可以的
[01:43:29] 當然了前提是
[01:43:30] 另外那一組
[01:43:31] 還沒有滿四個人
[01:43:32] 反正不管怎麼樣
[01:43:34] 變來變去動來動去
[01:43:35] 就是最多四個人一組
[01:43:37] 好
[01:43:38] OK
[01:43:40] 還沒有其他問題
[01:43:41] 我的話我們休息一下
[01:43:47] 再回來
[01:43:48] 這對這個作業
[01:44:44] 有一點問題
[01:44:45] 因為就是
[01:44:46] 我感覺上整個作業
[01:44:47] 它就是有一點像
## 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 一次），檢查後集中修改。