[人工智慧導論](https://app.notion.com/p/3e6fc631b0308131b213f0a3d93fe91d) › [W2（9/17）](https://app.notion.com/p/3e6fc631b0308175a433e5fa4bc500df) › 03｜影片 [0:53:20–1:08:52](https://www.youtube.com/watch?v=hNZQIO0q74o&t=3200s)｜投影片 Ch3 p.1–10｜上一章 [02 環境性質與五種 Agent（0:13–0:40）](https://app.notion.com/p/3e6fc631b03081da84a3de991c10424f)｜下一章 [04 BFS 與 UCS 搜尋（1:08–1:23）](https://app.notion.com/p/3e6fc631b030811291c5ebaf18c949df) ## 重點 - 這章只處理最單純的環境：解答一定是一串固定的動作。把這串動作找出來的過程叫 search（搜尋），會這樣解題的 agent 叫 problem-solving agent。 - 要讓電腦解題，先把問題寫成五個要素：initial state、actions、transition model、goal test、path cost。羅馬尼亞地圖、8-puzzle、8-queens 三個例子之後其他章還會用到。 - 把所有可能的動作序列畫成一棵 search tree（搜尋樹）：樹根是起點，分支是動作，節點是狀態。每個節點記四樣東西：STATE、PARENT、ACTION、PATH-COST（g(n)）。 ## Exam-ready - **Problem-solving agent**: "This chapter describes one kind of goal-based agent called a problem-solving agent." "we limit ourselves to the simplest kind of task environment (PEAS: Performance, Environment, Actuators, Sensors), for which the solution to a problem is always a fixed sequence of actions."（Ch3 p.2） - 中文：這章只討論一種目標導向的 agent，叫 problem-solving agent（解題型 agent）；先限定在最簡單的任務環境（PEAS：Performance 表現、Environment 環境、Actuators 動作機構、Sensors 感測器），在這種環境下解答一定是一串固定的動作。白話：先講最簡單的情況，答案就是一串照做的動作。 - **Search**: "The process of looking for a sequence of actions that reaches the goal is called search. A search algorithm takes a problem as input and returns a solution in the form of an action sequence. Once a solution is found, the actions it recommends can be carried out. This is called the execution phase."（Ch3 p.3，execution phase 老師沒講） - 中文：找出一串能到達目標的動作，這個過程叫 search（搜尋）；search algorithm（搜尋演算法）拿問題當輸入，輸出一個用動作序列表示的解答，找到後照著做的階段叫 execution phase（執行階段）。白話：先想好整條路線，再照著走。 - **Five components**: "A problem can be defined formally by five components" — "Initial state – In(Arad)", "A description of the possible actions -- Go(Sibiu), Go(Timisoara), Go(Zerind)", "A description of what each action does (transition model) -- RESULT(In(Arad), Go(Zerind)) = In(Zerind)", "The goal test, which determines whether a given state is a goal state -- In(Bucharest)", "A path cost function that assigns a numeric cost to each path"（Ch3 p.5） - 中文：一個問題可以用五個要素正式定義：initial state（起點，例如 In(Arad)）、actions（可能的動作，例如 Go(Sibiu)）、transition model（轉移模型：描述動作的後果，例如 RESULT(In(Arad), Go(Zerind)) = In(Zerind)）、goal test（目標檢查：判斷是不是到了目標狀態）、path cost function（路徑成本函式：給每條路徑算一個數字）。白話：要讓電腦解題，先把問題拆成這五樣東西。 - **Solution**: "A solution to a problem is an action sequence that leads from the initial state to a goal state. Solution quality is measured by the path cost function."（Ch3 p.5） - 中文：解答是一串從起點到目標狀態的動作序列，解答的好壞用 path cost function（路徑成本函式）衡量。白話：不只要有解，還要比哪個解比較省。 - **8-puzzle**: "States: A state description specifies the location of each of the eight tiles and the blank in one of the nine squares." "Initial state: Any state can be designated as the initial state. Note that any given goal can be reached from exactly half of the possible initial states." "Actions: The simplest formulation defines the actions as movements of the blank space Left, Right, Up, or Down." "Transition model: … if we apply Left to the start state …, the resulting state has the 5 and the blank switched." "Path cost: Each step costs 1, so the path cost is the number of steps in the path."（Ch3 p.6 圖中文字） - 中文：狀態（state）描述八塊方塊和空格分別在九個格子裡的哪一格；起始狀態可以是任何盤面，而且每個目標剛好能從一半的起始狀態到達；最簡單的動作定義是把空格往 Left、Right、Up、Down 移動；轉移模型舉例：對起始盤面套用 Left，結果會是 5 和空格互換位置；路徑成本是每一步算 1，也就是總步數。白話：把「移動哪塊方塊」想成「移動空格」比較好定義。 - **8-queens**: "A queen attacks any piece in the same row, column or diagonal." "States: Any arrangement of 0 to 8 queens on the board is a state." "Initial state: No queens on the board." "Actions: Add a queen to any empty square." "Transition model: Returns the board with a queen added to the specified square." "Goal test: 8 queens are on the board, none attacked."（Ch3 p.7，第一句以外是圖中文字） - 中文：皇后（queen）會攻擊同一列（row）、同一行（column）、同一條斜線（diagonal）上的棋子；狀態是棋盤上 0 到 8 個皇后的任何擺法；起始狀態是空棋盤；動作是把一個皇后加到任一空格；轉移模型回傳多加了皇后之後的棋盤；目標檢查是 8 個皇后都上了棋盤，且沒有互相攻擊。白話：一次放一個皇后，放滿又沒人被吃掉就是解。 - **Real-world problems**: "Touring problems – route-finding problem", "Traveling salesperson problem – route-finding problem", "VLSI layout problem", "Robot navigation -- – route-finding problem"（Ch3 p.8） - 中文：巡迴問題（touring problem）是路線規劃問題的一種；旅行推銷員問題（traveling salesperson problem，簡稱 TSP）也是路線規劃問題，要找最短的一圈路線；VLSI 佈局問題（晶片電路佈局）；機器人導航（robot navigation）也是一種路線規劃問題。白話：這些都是比玩具問題複雜、但一樣能用五要素定義的真實問題。 - **Search tree**: "Search algorithms work by considering various possible action sequences. The possible action sequences starting at the initial state form a search tree with the initial state at the root; the branches are actions and the nodes correspond to states in the state space of the problem."（Ch3 p.9） - 中文：搜尋演算法的做法是考慮各種可能的動作序列；從起點出發的所有可能動作序列，會形成一棵 search tree（搜尋樹），起點是樹根（root），分支（branch）是動作，節點（node）對應問題狀態空間裡的某個狀態。白話：把所有走法畫成一棵樹，樹根是起點。 - **Node**: "n.STATE: the state in the state space to which the node corresponds; n.PARENT: the node in the search tree that generated this node; n.ACTION: the action that was applied to the parent to generate the node; n.PATH-COST: the cost, traditionally denoted by g(n), of the path from the initial state to the node" "CHILD-NODE: … PATH-COST = parent.PATH-COST + problem.STEP-COST(parent.STATE, action)"（Ch3 p.10 圖中文字） - 中文：節點 n 的 STATE 是它對應的狀態；PARENT 是搜尋樹裡產生這個節點的那個節點；ACTION 是父節點做了什麼動作才產生這個節點；PATH-COST（傳統上寫成 g(n)）是從起點到這個節點的路徑成本。子節點的計算公式：PATH-COST = 父節點的 PATH-COST 加上 problem.STEP-COST(父節點的狀態, 動作)。白話：每個節點就是一筆記帳資料，記著自己從哪來、花了多少。 ## [0:53:20](https://www.youtube.com/watch?v=hNZQIO0q74o&t=3200s) Problem-solving agent：解答就是一串動作 第三章接著上一章的 goal-based agent（以目標為導向的 agent），先不管 utility-based 和 learning agent，只看最簡單的情況：解答一定是一串固定的動作（action sequence）。把這串動作找出來的過程叫 search（搜尋）。找到之後照著做，課本叫 execution phase（執行階段）。會這樣先想好整串、再照做的 agent，叫 problem-solving agent（解題型 agent）。 （上一章 [02 環境性質與五種 Agent](https://app.notion.com/p/3e6fc631b03081da84a3de991c10424f) 學過：goal-based agent 是心裡有一個目標的 agent，每次選動作都會想「做了之後離目標近不近」。）這章一直出現的 state（狀態），就是「世界現在長什麼樣子」的一張快照，例如人在哪個城市、拼圖盤面怎麼擺；action（動作）會把一個狀態變成另一個狀態。
用生活例子講，search 和 execution 差在哪？ 想像用 Google Maps 開車。按下「開始導航」前，它在所有可能的路線裡找出一條，這是 search。之後你照著一個一個轉彎，這是 execution。 能先整條規劃好再出發，是因為假設路不會突然消失、地圖是完整的。路況會變的情況，是後面章節的事。
要先懂什麼？ - Goal-based agent：上一章五種 agent 之一，會想：做了這個動作，離目標有沒有更近？ - PEAS：描述任務環境的四樣東西，Performance（怎樣算做得好）、Environment、Actuators（能動手的部位）、Sensors（感測器）。 - 投影片說的 simplest task environment，課本指四個條件（textbook）：fully observable（看得到全部）、discrete（選項數得出來）、known（知道動作的後果）、deterministic（結果是確定的）。 所以對這章的影響是：不會有意外，解答可以事先整串算好，照做就不會出錯。
老師原話是什麼？ 「那在這一章裡面呢，我們把我們的討論呢，侷限在最簡單的 PEAS」(0:54:23) 「我們去找一連串的動作來完成我們的目標，這件事情呢，我們稱呼它叫做 search」(0:54:54)
## [0:55:20](https://www.youtube.com/watch?v=hNZQIO0q74o&t=3320s) 羅馬尼亞地圖：定義問題的五個要素 題目：從 Arad 開車到首都 Bucharest，怎麼走最好？（課本挑這張圖，是因為城市名開頭幾乎從 A 排到 Z，好用字母代稱。）要讓電腦解，先把問題寫成五個要素：initial state（起點）、actions（能做的動作）、transition model（做了動作之後狀態變成什麼）、goal test（檢查到了沒）、path cost（整條路的花費）。老師順便複習上一章：這個環境是 deterministic（決定性的）還是 stochastic（隨機的）？答案是 deterministic：說要去 Zerind，就一定會到 Zerind，所以任何一個解答都能寫成一串 action。 （上一章學過：deterministic 是做了動作、結果一定一樣；stochastic 是結果有機率不一樣，像擲骰子。）投影片上的 In(Arad)、Go(Zerind)、RESULT(…) 是「函式」（function）寫法：括號裡放東西進去，得到一個結果。例如 RESULT(在 Arad, 去 Zerind) 的結果就是「在 Zerind」。看到這種寫法，照著念成中文句子就懂了。 [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\ai_ch3_p004.png | 羅馬尼亞簡化地圖（Ch3 p.4）：20 個城市，線上數字是公里數。這章和接下來的搜尋演算法都用這張圖]] 圖上重點：(1) 標題 Problem-Solving Agents＝解題型 agent。(2) An example problem: moving from Arad to Bucharest＝範例問題：從 Arad 移動到 Bucharest。(3) Figure 3.2 A simplified road map of part of Romania＝圖 3.2：羅馬尼亞部分地區的簡化道路圖。(4) 方塊是城市、線是道路、線旁的數字是兩城之間的距離（公里）。這張圖在講：起點 Arad 在左邊、終點 Bucharest 在右下，中間有很多條路可以選，電腦要從裡面找出一條。 下面第二個摺疊在做加法：把幾條路的公里數加總、比大小。它想讓你看到，到得了終點的路有很多條，加總最小（path cost 最低）的那條才是最佳解。
五個要素套在這張地圖上，各是什麼？ - Initial state：In(Arad)，人在 Arad。 - Actions：在 Arad 能做 Go(Sibiu)、Go(Timisoara)、Go(Zerind)，就是從 Arad 伸出去的三條路。在不同城市，能做的動作就不同。 - Transition model：RESULT(In(Arad), Go(Zerind)) = In(Zerind)。RESULT(s, a) 讀作「在狀態 s 做動作 a 之後的狀態」。 - Goal test：現在是不是 In(Bucharest)。 - Path cost：走過每一段路的公里數加起來；每一段的花費叫 step cost（步驟成本）。越小越好，老師說就是省油錢、省時間。 課本補充（textbook）：前三個要素合起來，決定了 state space（狀態空間：從起點出發能到達的所有狀態）。這張地圖的 state space 就是 20 個城市。
老師舉的兩條路，手算起來哪一條比較好？ - A–Z–O–S–F–B：75 + 71 + 151 + 99 + 211 = 607 公里 - A–S–R–P–B（經 Rimnicu Vilcea、Pitesti）：140 + 80 + 97 + 101 = 418 公里 - 再多算一條 A–S–F–B：140 + 99 + 211 = 450 公里 三條都是 solution（都到得了 Bucharest），品質用 path cost 比。我用程式把整張圖算過，418 就是 optimal solution（最佳解：path cost 最低的解答）。 第三條只走 3 段，比 418 那條少一段，卻比較遠。步數少不等於成本低，下一章 BFS 和 UCS 的差別就在這裡。
老師原話是什麼？ 「一旦我們說要從 A 走到 Z，我們的下一個狀態就是我們真的會到 Z，這是一定的，所以它是 Deterministic」(0:57:54) 「我希望我走的里程是越小越好」(0:58:35) 「任何的一個解答，都可以用一連串的 Action 來表達」(0:59:29)
## [0:59:42](https://www.youtube.com/watch?v=hNZQIO0q74o&t=3582s) 8-puzzle：狀態是盤面，動作是移動空格 老師先提醒：地圖、8-puzzle、8-queens 這三個例子，之後其他章也可能會用到 (0:59:43)。8-puzzle（八格拼圖）是 3×3 九宮格裡 1 到 8 八塊方塊加一個空格，要把打亂的盤面滑回目標盤面（空格在左上，1 到 8 依序排）。每一種擺法是一個 state。動作的定義很聰明：不說移動哪一塊方塊（常常好幾塊都能動），而是想成空格往上下左右移，動作最多就 Left、Right、Up、Down 四種。空格往哪移，結果就一定是那樣，所以這也是 deterministic 環境。每移一次成本 1，path cost 就是移動次數。 下面兩個摺疊有一點算數。第一個實際把空格移一步，看盤面會變成什麼樣子；第二個說明為什麼有一半的盤面永遠排不回目標，結論只要記：隨便亂擺的 8-puzzle 有一半根本無解。裡面的 9!（讀作「9 階乘」）就是 9 × 8 × 7 × … × 1，意思是把 9 樣東西排成一排一共有幾種排法。
從投影片的起始盤面走一步，手算會變成什麼？ 寫法：三列用斜線隔開，□ 是空格。起始盤面（Ch3 p.6）是 7 2 4 / 5 □ 6 / 8 3 1，目標是 □ 1 2 / 3 4 5 / 6 7 8。
動作（空格往哪移）結果盤面實際上是哪塊方塊在動
Up7 □ 4 / 5 2 6 / 8 3 12 往下
Down7 2 4 / 5 3 6 / 8 □ 13 往上
Left7 2 4 / □ 5 6 / 8 3 15 往右（投影片的例子：5 和空格交換）
Right7 2 4 / 5 6 □ / 8 3 16 往左
空格在正中間才有四個動作，在邊上 3 個，在角落只有 2 個。 我用程式跑過：這個起始盤面最少要移 26 步才能排好，用的方法就是下一章的 BFS。
投影片說任何目標只能從一半的起始盤面到達，是什麼意思？ 九格的擺法一共 9! = 362,880 種。但滑動方塊永遠改變不了盤面的某種「奇偶性」（parity），所以所有盤面分成兩群，兩群之間互相到不了。 最好懂的例子：把目標盤面的 1 和 2 拿起來對調再放回去。這個盤面看起來只差一點，但不管怎麼滑，都滑不回目標。 從一個盤面出發，能到達的剛好一半：9!/2 = 181,440 種（課本數字，我用程式從起始盤面走遍驗證過）。 所以對你的影響是：隨便亂擺一個 8-puzzle 給電腦解，有一半的機率根本無解。
老師原話是什麼？ 「這是一個我們之後會用的例子，我們順便也介紹其他，在往後不只這一章，在往後其他 Chapter 也可能會用到的例子」(0:59:43) 「我們把空格這個也想成是一個方塊」(1:01:16) 「比如說你這個空格往上移，就等於是你二號往下移的意思嘛」(1:01:28) 「我們把它定義成你要移多少次，我希望你移越少次」(1:02:08)
## [1:02:21](https://www.youtube.com/watch?v=hNZQIO0q74o&t=3741s) 8-queens：一次放一個皇后 西洋棋的皇后會攻擊同一列（row）、同一行（column）、同一條斜線（diagonal）上的棋子。8-queens（八皇后）要在 8×8 棋盤放 8 個皇后，彼此都不互相攻擊。投影片用一次放一個的定義：state 是盤上 0 到 8 個皇后的任何擺法，從空棋盤開始，每個 action 放一個皇后到空格，放滿 8 個且沒人被攻擊就達成目標。 下面第二、三個摺疊有算式。第二個用「兩個皇后的列差等於行差，就在同一條斜線上」來檢查投影片的盤面為什麼不是解；第三個算出「隨便放」的放法多到 10 的 14 次方這個等級，用來說明：同一個問題定義得好不好，電腦要找的量會差非常多。摺疊裡兩條直線夾住一個數（例如 1 − 8 夾起來）叫絕對值，意思是不管正負、只看差多少，所以結果是 7。10 的 14 次方就是 1 後面接 14 個零（一百兆）。
三個例子的五個要素，放在一起長怎樣？
要素羅馬尼亞地圖8-puzzle8-queens
States人在哪個城市（20 個）8 塊方塊和空格各在哪一格棋盤上 0 到 8 個皇后的任何擺法
Initial stateIn(Arad)任何盤面都可以空棋盤
ActionsGo(相鄰城市)空格 Left、Right、Up、Down放一個皇后到任一空格
Transition modelRESULT(In(Arad), Go(Zerind)) = In(Zerind)空格和旁邊的方塊交換回傳多放了一個皇后的棋盤
Goal testIn(Bucharest)是否等於目標盤面8 個皇后、互不攻擊
Path cost公里數加總每步 1，等於步數投影片沒列：只在乎最後盤面，怎麼放上去不重要（textbook）
投影片 p.7 那個盤面，手算看看為什麼不是解？ 用（列, 行）記位置，列由上往下、行由左往右數。圖上的皇后在：(1,1)、(2,5)、(3,2)、(4,6)、(5,3)、(7,4)、(8,8)，一共 7 個，第 6 列是空的。 - 同列、同行：7 個皇后的列都不同、行也都不同。 - 同斜線的判斷法：(r1,c1) 和 (r2,c2) 如果 |r1 − r2| = |c1 − c2|，就在同一條斜線上。 - (1,1) 和 (8,8)：|1 − 8| = 7 = |1 − 8|，左上角和右下角互相攻擊。其他 20 對都不相等。 老師說「這一個會打到這一個」就是這一對。就算第 8 個皇后放到唯一不撞列也不撞行的 (6,7)，這一對還是互打，所以不是解。8 皇后的正確解一共 92 種（我用程式數過）。
隨便放一個皇后這種定義，有什麼缺點？ 每一步都能放在任何空格，要檢查的放法有 64 × 63 × … × 57 ≈ 1.8 × 10^14 種（課本數字，我用程式驗算過）。 課本給了一個改良版（textbook）：規定第 k 個皇后只能放在第 k 行，而且只能放在不會被攻擊的格子。這樣狀態只剩 2,057 個（我也用程式數過）。 所以對你的影響是：同一個問題換個定義，搜尋空間可以差到將近 900 億倍（1.8 × 10^14 ÷ 2,057 ≈ 8.7 × 10^10）。「怎麼定義問題」本身就是解題的一部分。
老師原話是什麼？ 「所以所謂的八皇后問題的目標就是，你這八隻皇后應該要怎麼擺，會讓我最後擺完，然後盤面上的八隻皇后不會互相攻擊」(1:03:44) 「這一個會打到這一個，因為這是同一個對角線」(1:03:33) 「它的 State 就是一個盤面，你可能放 0 隻皇后到 8 隻皇后」(1:03:59)
## [1:04:42](https://www.youtube.com/watch?v=hNZQIO0q74o&t=3882s) 真實世界的搜尋問題 投影片 p.8 列了幾個真實問題：touring problem（巡迴問題）、traveling salesperson problem（TSP，旅行推銷員問題）、VLSI layout（晶片佈局）、robot navigation（機器人導航）。老師說資工系大二的演算法課多半碰過這些題目，做電路設計會遇到 layout，做自駕車會遇到 robot navigation；沒修過也沒關係，下面摺疊有每個問題在找什麼。它們複雜得多，但骨架一樣：都能用同樣五個要素定義，本質上都是在建 problem-solving agent。課本把 8-puzzle、8-queens 這類例子叫 toy problem（玩具問題：規則乾淨，拿來比較演算法），和這些 real-world problem 對照。
這幾個真實問題，各在找什麼？ - Touring problem：每個城市至少去一次（課本例：從 Bucharest 出發走遍每個城市再回來）。所以 state 除了現在在哪，還要記去過哪些城市。 - TSP：每個城市剛好去一次，找最短的一圈路線。演算法課的經典難題。 - VLSI layout：在晶片上擺放數百萬個元件和連線，讓面積、電路延遲盡量小。 - Robot navigation：找路問題的推廣，但機器人在連續空間移動，動作和狀態理論上有無限多個。
老師原話是什麼？ 「當然我們上課我們就先從最簡單的開始講起」(1:05:32)
## [1:05:45](https://www.youtube.com/watch?v=hNZQIO0q74o&t=3945s) 把問題展開成搜尋樹 問題定義好了，怎麼找解答？把所有可能的動作序列畫成一棵 search tree（搜尋樹）：root（樹根）是起點 Arad，每條 branch（分支）是一個動作，每個 node（節點）對應一個狀態。從 Arad 長出 Sibiu、Timisoara、Zerind，這叫 expand（展開：一次產生某節點的所有子節點）Arad。再展開 Sibiu，又長出 Arad、Fagaras、Oradea、Rimnicu Vilcea。搜尋演算法真正在決定的，是下一個要展開哪個節點，直到展開到 Bucharest。 [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\ai_ch3_p009.png | 搜尋樹一層一層長出來（Ch3 p.9）：(a) 只有起點 Arad；(b) 展開 Arad；(c) 再展開 Sibiu。灰底是已經展開過的節點，實線框是已產生、還沒展開的，淡色虛線是還沒產生的]] 圖上重點：(1) 標題 Searching for Solutions＝尋找解答。(2) 上面那句：搜尋演算法會考慮各種可能的動作序列；從起點出發的所有序列形成一棵 search tree（搜尋樹），起點是 root（樹根），branches（分支）是 actions（動作），nodes（節點）對應 state space（狀態空間）裡的 states（狀態）。(3) (a) The initial state＝只有起點；(b) After expanding Arad＝展開 Arad 之後；(c) After expanding Sibiu＝再展開 Sibiu 之後。這張圖在講：搜尋就是讓這棵樹一層一層長出來，直到長出終點 Bucharest。
要先懂什麼？ 樹（tree）的基本名詞： - Root（根）：最上面那個節點，這裡是起點。 - Parent／child（父節點／子節點）：A 展開後長出 B，A 就是 B 的 parent，B 是 A 的 child。 - Leaf（葉節點）：還沒有子節點的節點。 - Depth（深度）：從 root 往下走了幾層。root 的深度是 0。 - Frontier（邊界，textbook）：所有已產生、還沒展開的節點。下一章的演算法都在決定先從 frontier 拿哪一個出來展開。
地圖只有 20 個城市，樹為什麼會無限大？ 看圖 (c)：展開 Sibiu 時又長出了 Arad，也就是走回頭路。這個 Arad 又能長出 Sibiu，可以無限繞下去。課本叫 loopy path（繞圈的路徑），Arad 在樹上是 repeated state（重複狀態）。 所以 state space 只有 20 個狀態，search tree 卻可以無限大。後面講 DFS 和 A* 時，投影片會分 tree search（不記得走過哪裡）和 graph search（記住展開過的狀態），就是為了處理這件事。
老師原話是什麼？ 「整體而言表達成一個 Search Tree，表達成一棵樹，這棵樹的 Root，出發點就是 A 這個都市」(1:06:04)
## [1:07:03](https://www.youtube.com/watch?v=hNZQIO0q74o&t=4023s) 樹上每個節點記了什麼 樹上每個節點 n 是一個小資料結構，存四樣東西：n.STATE（對應哪個狀態，例如哪個盤面）、n.PARENT（哪個節點產生了我）、n.ACTION（父節點做了什麼動作才產生我）、n.PATH-COST（從起點到我的總成本，寫成 g(n)）。每多走一個分支就多付一步成本：8-puzzle 加 1，地圖加那段的公里數。找到目標節點後，沿 PARENT 往回走到 root，就拼出整串動作，也就是解答。 資料結構（data structure）是程式裡把幾樣相關資料綁在一起存的格子，像一張固定欄位的表單。n.STATE 中間那個點，意思是「節點 n 的 STATE 這一欄」。 **注意：老師口頭說這個節點的 parent「有兩種可能」(1:07:42)，並用空格往下、往左來說明 action。投影片的定義是：PARENT 是產生這個節點的那一個節點，只有一個；ACTION 是父節點做了哪個動作才產生它，圖中是 Right。考試寫投影片的版本。** [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\ai_ch3_p010.png | 節點的四個欄位（Ch3 p.10）：左邊盤面是 STATE，往上的箭頭是 PARENT；ACTION = Right 表示父節點把空格往右移才得到它，PATH-COST = 6 表示從起點已經移了 6 步]] 圖上重點：(1) 標題 Infrastructure for Search Algorithms＝搜尋演算法的基本零件。(2) For each node n of the tree, we have a structure containing four components＝樹上每個節點 n 都是一個有四個欄位的結構。(3) PATH-COST 傳統上寫成 g(n)，是沿著 parent pointers（指向父節點的連結）從起點一路算過來的成本。(4) 右上方框 function CHILD-NODE(problem, parent, action) returns a node＝「產生子節點」的函式：新節點的 STATE 是父節點狀態做這個動作後的結果，PARENT 是父節點，ACTION 是這個動作，PATH-COST 是父節點的成本加上這一步的成本。這張圖在講：每個節點就是一筆記帳資料，每長出一個子節點就把成本往下累加。 下面第二個摺疊的公式 g(子) = g(父) + 這一步的成本，就是把每段路的花費一路加起來。用它算出走到每個城市累計花了多少，最後沿 PARENT 倒著讀，就得到整條路線。
老師說的「兩種可能」和投影片差在哪？ 圖中節點的盤面是 5 4 □ / 6 1 8 / 7 3 2。在 state space 裡，有兩個鄰居盤面可以一步變成它：5 □ 4 / 6 1 8 / 7 3 2（空格往右）和 5 4 8 / 6 1 □ / 7 3 2（空格往上）。老師說的兩種可能是這兩個鄰居。 但搜尋樹上的節點只記真正產生它的那一個。ACTION = Right 就告訴我們，父節點是 5 □ 4 / 6 1 8 / 7 3 2。 如果兩條路都走到同一個盤面，樹上會有兩個不同的節點：STATE 一樣，PARENT 不一樣。這就是課本強調的 node ≠ state（textbook）：state 是世界長什麼樣，node 是搜尋時記帳用的資料結構。 老師講的空格往下（8 到右上角）、往左（4 到右上角），是從這個節點產生子節點的動作。往左會回到父節點的盤面，又是一個重複狀態。
沿著 PARENT 往回走，手算怎麼拼出解答？ 子節點的成本公式（投影片 p.10 的 CHILD-NODE）：PATH-COST = parent.PATH-COST + STEP-COST(parent.STATE, action)。也就是 g(子) = g(父) + 這一步的成本。 - Arad：沒有 PARENT、沒有 ACTION，g = 0 - Sibiu：PARENT = Arad，ACTION = Go(Sibiu)，g = 0 + 140 = 140 - Rimnicu Vilcea：PARENT = Sibiu，g = 140 + 80 = 220 - Pitesti：PARENT = Rimnicu Vilcea，g = 220 + 97 = 317 - Bucharest：PARENT = Pitesti，g = 317 + 101 = 418 從 Bucharest 沿 PARENT 往回，依序經過 Pitesti、Rimnicu Vilcea、Sibiu，回到 Arad。倒過來讀就是解答 Go(Sibiu)、Go(Rimnicu Vilcea)、Go(Pitesti)、Go(Bucharest)，總成本 418。 g(n) 這個符號之後一直用：下一章 UCS 先展開 g(n) 最小的節點，A* 的 f(n) = g(n) + h(n) 也從這裡來。
老師原話是什麼？ 「所以它的 Parent 有兩種可能」(1:07:42) 「我多走一個分支，我就要付出我的里程數」(1:08:32) 「我們可以把它描述成在一棵樹上面來找尋」(1:08:46)
## Self-check
Q1. List the five components that formally define a problem, and give each one for the route-finding problem from Arad to Bucharest.（中文：列出正式定義一個問題的五個要素，並套用在從 Arad 到 Bucharest 的路線問題上。） **Answer**: (1) Initial state: In(Arad). (2) Actions: in Arad, Go(Sibiu), Go(Timisoara), Go(Zerind). (3) Transition model: RESULT(In(Arad), Go(Zerind)) = In(Zerind). (4) Goal test: is the state In(Bucharest)? (5) Path cost: sum of road distances along the path. A solution is an action sequence from the initial state to a goal state; the optimal one has the lowest path cost (Arad–Sibiu–Rimnicu Vilcea–Pitesti–Bucharest, 418 km). 中文：五個要素是：(1) 起點：人在 Arad。(2) 動作：在 Arad 可以做 Go(Sibiu)、Go(Timisoara)、Go(Zerind)。(3) 轉移模型：RESULT(In(Arad), Go(Zerind)) = In(Zerind)，表示在 Arad 做了 Go(Zerind) 之後會到 Zerind。(4) 目標檢查：現在的狀態是不是 In(Bucharest)。(5) 路徑成本：把走過的公里數加總。解答是一串從起點到目標的動作，其中最佳解是路徑成本最低的那個，就是 Arad–Sibiu–Rimnicu Vilcea–Pitesti–Bucharest 這條路，總共 418 公里。回答這題要把五個要素一個一個對應著地圖上的例子講出來，不能只背名詞。
Q2. Formulate the 8-puzzle as a search problem. What state results from applying Left to the start state 7 2 4 / 5 □ 6 / 8 3 1?（中文：把 8-puzzle 定義成一個搜尋問題，並算出起始盤面 7 2 4 / 5 □ 6 / 8 3 1 套用 Left 之後會變成什麼盤面。） **Answer**: States: locations of the eight tiles and the blank. Initial state: any state. Actions: move the blank Left, Right, Up, or Down. Transition model: returns the resulting state. Goal test: matches the goal configuration. Path cost: each step costs 1 (number of steps). Left gives 7 2 4 / □ 5 6 / 8 3 1 (the 5 and the blank switched). 中文：狀態是八塊方塊和空格分別在哪一格；起始狀態可以是任何盤面；動作是把空格往 Left、Right、Up、Down 移動；轉移模型回傳移動後的新盤面；目標檢查是有沒有排成目標盤面；路徑成本是移動次數，每步算 1。套用 Left 在起始盤面 7 2 4 / 5 □ 6 / 8 3 1 上，會變成 7 2 4 / □ 5 6 / 8 3 1，也就是 5 和空格互換位置。回答這題要先把六個要素講完整，再實際算一步當範例，不能只寫定義。
Q3. What is the difference between a state and a node? List the four components of a search-tree node.（中文：state 和 node 有什麼不同？搜尋樹的節點有哪四個欄位？） **Answer**: A state is a configuration of the world; a node is a bookkeeping data structure in the search tree. A node n has n.STATE, n.PARENT (the node that generated it), n.ACTION (the action applied to the parent), and n.PATH-COST g(n) (cost from the initial state to n). Two nodes can hold the same state if it is reached by different paths (Arad reappears after expanding Sibiu). Following parent pointers from a goal node gives the solution. 中文：state（狀態）是這個世界實際長什麼樣子；node（節點）是搜尋樹裡用來記帳的資料結構，不是狀態本身。一個節點 n 有四個欄位：n.STATE（對應哪個狀態）、n.PARENT（哪個節點產生了它）、n.ACTION（父節點做了什麼動作才產生它）、n.PATH-COST（也寫成 g(n)，從起點到這個節點的成本）。同一個狀態可以出現在不同的節點上，例如展開 Sibiu 之後又長出 Arad，這個 Arad 節點和樹根的 Arad 節點狀態一樣，卻是不同節點。找到目標節點之後，沿著 PARENT 一路往回走到樹根，就能拼出整條解答。回答這題要先講清楚 state 和 node 的差別，再把四個欄位名稱和作用都講出來。
讀完了嗎？下一章：[04 BFS 與 UCS 搜尋（1:08–1:23）](https://app.notion.com/p/3e6fc631b030811291c5ebaf18c949df)｜回到週頁：[W2（9/17）](https://app.notion.com/p/3e6fc631b0308175a433e5fa4bc500df)