[人工智慧導論](https://app.notion.com/p/3e6fc631b0308131b213f0a3d93fe91d) › [W2（9/17）](https://app.notion.com/p/3e6fc631b0308175a433e5fa4bc500df) › 07｜影片 [2:11:49–2:35:52](https://www.youtube.com/watch?v=hNZQIO0q74o&t=7909s)｜投影片 Ch4 p.1–9｜上一章 [06 Greedy 與 A* 搜尋（1:56–2:11）](https://app.notion.com/p/3e6fc631b03081f7acf6d56761c8225c)｜下一章 無 跳過提示：(2:14:52–2:16:24) 老師在用線性代數 AX=B 求解（矩陣求反矩陣、最小平方解）來比喻找最佳解的概念，聽不懂可以直接跳到 [2:16:24](https://www.youtube.com/watch?v=hNZQIO0q74o&t=8184s)，接著講「回到 Local Search 演算法的基本做法」。 跳過的這段在做什麼（白話）：老師拿解方程式來比喻——找不到剛好成立的答案時，就退一步找「誤差最小」的答案。重點只有一句：local search 也一樣，不求完美，而是在一大堆候選解裡找分數最好的。 ## 重點 - Ch3 的搜尋要找出一條「路徑」。八皇后這類問題只在乎最後怎麼擺，不在乎怎麼擺到那裡，所以改用 local search（局部搜尋：手上只拿一個完整的解，每次跟旁邊的「鄰居」比，往更好的方向挪）。 - 最基本的 local search 是 hill climbing（爬山演算法）：看遍所有鄰居，走到最好的那個；沒有鄰居比自己好就停。記憶體只要固定一點點，但常卡在 local maximum（小山頂）、ridge（屋脊）、plateau（高原）。 - 八皇后實驗：原版只有 14% 解得出來；允許 sideways move（走到一樣好的鄰居）升到 94%，但步數變多。另有 stochastic、first-choice、random-restart 三種變形，成敗很看地形。 ## Exam-ready - **Why local search**: "The search algorithms that we have seen so far are designed to explore search spaces systematically. When a goal is found, the path to that goal also constitutes a solution to the problem." / "In many problems, however, the path to the goal is irrelevant. In the 8-queens problem, what matters is the final configuration of queens, not the order in which they are added." / "We need algorithms not worrying about paths at all."（Ch4 p.2） - 中文：老師說前面教的搜尋都在找「一條路徑」，但八皇后這種問題只在乎最後擺法對不對，不管怎麼擺到那裡，所以要換一種不管路徑、只看最後解好不好的演算法。 - **Local search**: "Local search algorithms operate using a single current node and generally move only to neighbors of that node." / "They use very little memory—usually a constant amount" / "They can often find reasonable solutions in large or infinite (continuous) state spaces for which systematic algorithms are unsuitable."（Ch4 p.3） - 中文：Local search 手上永遠只留「一個目前的解」（current node），每次只看它旁邊的鄰居（neighbor：稍微改一點的解），不像前面的搜尋要記住整棵樹，所以只要很少的記憶體，連很大甚至無限大的空間都能處理。 - **Optimization**: "Local search algorithms are useful for solving pure optimization problems, in which the aim is to find the best state according to an objective function."（Ch4 p.3） - 中文：Local search 適合用在「純最佳化問題」（pure optimization problem）——不用找路徑，只要用一個目標函數（objective function：幫每個解打分數的公式）找分數最好的那個解。 - **Hill climbing**: "The hill-climbing search algorithm (steepest-ascent version) is simply a loop that continually moves in the direction of increasing value. It terminates when it reaches a “peak”." / "Does not maintain a search tree … need only record the state and the value of the objective function."（Ch4 p.5） - 中文：爬山法（hill climbing，steepest-ascent 版）就是不斷往分數變高的方向移動，走到「山頂」（沒有鄰居比自己好）就停；它不像前面的搜尋要存整棵樹，只要記住目前狀態和它的分數就好。 - **8-queens formulation**: "The successors of a state are all possible states generated by moving a single queen to another square in the same column. The heuristic cost function h is the number of pairs of queens that are attacking each other." / "Hill-climbing algorithms typically choose randomly among the set of best successors if there is more than one."（Ch4 p.6） - 中文：八皇后的「鄰居」（successor）是把某一隻皇后移到同一欄的別的格子；h（分數，越小越好）是互相攻擊的皇后對數；如果好幾個鄰居一樣好，就隨機挑一個。 - **Greedy local search**: "Hill climbing is sometimes called greedy local search because it grabs a good neighbor state without thinking ahead about where to go next." / "It turns out that greedy algorithms often perform quite well" / "Hill climbing often gets stuck for the following reasons: Local maxima, Ridges, Plateaux (can be flat local maximum or a shoulder)"（Ch4 p.7） - 中文：爬山法又叫「貪婪局部搜尋」（greedy local search），因為它只抓眼前最好的鄰居，不會想之後會走到哪；這種貪婪做法通常表現不差，但容易卡在小山頂（local maxima）、屋脊（ridges）、高原（plateaux）這三種地形。 - **Ridge**: "a ridge rising from left to right, creating a sequence of local maxima that are not directly connected to each other. From each local maximum, all the available actions point downhill."（Ch4 p.7 Figure 4.4 圖說） - 中文：屋脊（ridge）是一條斜斜往上升的稜線，線上有一串「小山頂」彼此不是直接相連的；站在每一個小山頂，四周能走的方向都是往下，所以會被卡住，即使整條稜線其實還在往上升。 - **8-queens results**: "steepest-ascent hill climbing gets stuck 86% of the time, solving only 14% of problem instances. It works quickly, taking just 4 steps on average when it succeeds and 3 when it gets stuck—not bad for a state space with 8^8 ≈ 17 million states."（Ch4 p.8） - 中文：原版爬山法對八皇后只有 14% 能解出來，86% 會卡住；但跑得很快，成功平均只要 4 步、卡住平均 3 步，對一個有 8 的 8 次方（約 1700 萬）種狀態的空間來說算是很省。 - **Sideways move**: "to allow a sideways move in the hope that the plateau is really a shoulder … This raises the percentage of problem instances solved by hill climbing from 14% to 94%. Success comes at a cost: the algorithm averages roughly 21 steps for each successful instance and 64 for each failure."（Ch4 p.8） - 中文：允許「橫著走」（sideways move：走到跟自己一樣好的鄰居），賭這片平地其實是還能往上的 shoulder；這樣把成功率從 14% 拉高到 94%，但代價是步數變多，成功平均要走 21 步、失敗平均要走 64 步。 - **Variants**: "Stochastic hill climbing chooses at random from among the uphill moves; the probability of selection can vary with the steepness of the uphill move." / "First-choice hill climbing implements stochastic hill climbing by generating successors randomly until one is generated that is better than the current state." / "Random-restart hill climbing conducts a series of hill-climbing searches from randomly generated initial states until a goal is found." / "The success of hill climbing depends very much on the shape of the state-space landscape."（Ch4 p.9） - 中文：除了原版還有三種變形：stochastic（在比自己好的鄰居裡隨機挑，坡度越陡越容易被挑到）、first-choice（隨機生出鄰居，第一個比自己好就走）、random-restart（從不同隨機起點重跑很多次，直到找到目標）。哪一種會成功，很看地形長什麼樣子。 ## [2:11:49](https://www.youtube.com/watch?v=hNZQIO0q74o&t=7909s) 路徑不重要的問題 Ch3 的問題都能畫成一棵搜尋樹，走到目標的那條路徑就是答案，例如從 Arad 開到 Bucharest 的路線。可是八皇后只要最後 8 隻皇后互不攻擊，先放哪隻、後放哪隻都無所謂，就像排婚宴座位只在乎最後的座位表。這種問題需要完全不管路徑的演算法，老師說其中最重要的做法是 local search (2:14:09)。這裡的 search 不是 Google 查文件，而是在所有可能的解裡面找最好的那一個。 （Arad 到 Bucharest 是本週 [03 搜尋問題的定義](https://app.notion.com/p/3e6fc631b03081c8a7e0e152c12bbd25) 學過的羅馬尼亞地圖例子：在地圖上找一條從 Arad 開到 Bucharest 的路線。） 下面「最小平方解」的摺疊是數學，在講：方程式沒有完美解時，改找最接近的解。它只是老師的比喻，看不懂也不影響這章。
要先懂什麼？老師比喻的「最小平方解」是什麼？ 解 Ax = b 時，沒有 x 能讓等式剛好成立，就退一步找「誤差最小」的 x，叫 least squares solution（最小平方解）。 小例子：同時要 x = 1 又要 x = 3，不可能。改成讓 (x − 1)² + (x − 3)² 最小：x = 2 時是 1 + 1 = 2，x = 1 時是 0 + 4 = 4，所以取 x = 2。 補充：老師說 A 有反矩陣才有解；精確說法是有反矩陣時剛好一個解，沒有時可能無解或無限多解。 所以對這章的影響是：local search 同一個精神，不求完美，只在一大堆候選解裡找分數最好的。
老師原話是什麼？ 「跟你擺的順序基本上沒有關係」(2:13:25) 「最重要的一種做法，就叫做Local Search」(2:14:09)
## [2:16:03](https://www.youtube.com/watch?v=hNZQIO0q74o&t=8163s) Local search 的基本原則 Local search 手上只拿一個 current node（目前的解），只看它的鄰居（把目前的解稍微改一點）；有鄰居比較好就換過去，再從新位置看鄰居，一直重複。這裡的 node 不是「路徑上的一站」，而是「一個完整的候選解」。它適合 pure optimization problem（純最佳化問題：每個解都能用 objective function 目標函數打分數）。 先懂兩個詞：state（狀態：問題在某一刻的樣子，例如棋盤上皇后現在怎麼擺）；neighbor／successor（鄰居：從目前狀態只做一個小改動就能變成的狀態）。本週 [03 搜尋問題的定義](https://app.notion.com/p/3e6fc631b03081c8a7e0e152c12bbd25) 學過：用 state 和 action（動作）來描述一個搜尋問題。 下表用到幾個前面的詞：BFS、A*（本週 04、06 章學過的兩種搜尋法）；frontier（待展開清單：已經看到、還沒走進去的節點）。O(…) 是「問題變大時，記憶體會長多快」的寫法：O(1) 表示永遠只要固定一點點；O(b^d) 表示每多深一層就乘 b 倍，很快就爆掉。complete 是「有解就一定找得到」，optimal 是「找到的一定是最好的」。
Ch3 系統性搜尋（BFS、A* 等）Ch4 local search
答案是什麼一條從起點到目標的路徑一個狀態（最後的擺法）
要記住什麼搜尋樹和 frontier（待展開清單），常是指數級，例如 BFS 的 O(b^d)（b＝分支數、d＝解的深度）只有目前狀態和分數，通常是常數 O(1)：八皇后只存 8 個數字加一個分數
適合的空間能一格一格列舉的有限空間很大、甚至無限（連續）的空間
保證有些演算法 complete、optimal不保證，找到「還不錯」的解
老師原話是什麼？ 「我之所以講還不錯，就代表它不見得是最好」(2:17:41) 「有一個Objective Function，有一個目標函數，來去評判你這個Solution有多棒」(2:18:02)
## [2:18:08](https://www.youtube.com/watch?v=hNZQIO0q74o&t=8288s) State-space landscape 把所有狀態排在 x 軸、每個狀態的 objective function 值畫在 y 軸，就得到一張「地形圖」，叫 state-space landscape（狀態空間地形）。目標是找到最高點 global maximum（全域最大值）。拿 8-puzzle（九宮格滑塊拼圖）來說：越接近排好 1 到 8 的盤面分數越高；空格往上下左右移一格得到的盤面，就是目前盤面的鄰居。 [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\ai_ch4_p004.png | Ch4 p.4 Figure 4.1：一維的狀態空間地形。x 軸是狀態，y 軸是 objective function，箭頭是 hill climbing 從 current state 往上爬。]] 圖上重點： - objective function（目標函數）是縱軸，越高代表這個解越好；state space（狀態空間）是橫軸，代表所有可能的解。 - global maximum（全域最大值）：整張圖最高的山頂，這是我們要找的。 - local maximum（區域最大值）：比左右都高、但不是最高的小山頂。 - "flat" local maximum（平的區域最大值）：山頂是一片平地；shoulder（肩膀）：山腰上的平台，走過去還能往上。 - current state（目前狀態）：灰色圓點，箭頭表示爬山法從這裡往上爬。 這張圖在講：把所有解排成一條線、分數畫成高度，找最好的解就像在地形上找最高峰，而路上有很多會讓人誤以為「到頂了」的地方。
有時候說「往上爬」，有時候說「往下走」，是同一件事嗎？ 是同一件事，只差在分數怎麼定義。 - objective function（越高越好）：找最高點，所以叫「爬山」。 - cost function（越低越好），例如八皇后的 h＝互相攻擊的對數：找最低點。投影片 p.5 圖說寫：用 heuristic cost h 時，改找 h 最小的鄰居。 把分數定成 −h，最小化 h 就等於最大化分數。所以老師講八皇后時說「卡在local minimum」(2:29:49)，跟投影片的 local maximum 是同一種狀況。
老師原話是什麼？ 「X軸是我各式各樣不同的State，Y軸是我某一種狀態之下有多高的分數」(2:19:40) 「這個你往上移一格所造成的狀態，就叫做你的鄰居」(2:20:58)
## [2:21:46](https://www.youtube.com/watch?v=hNZQIO0q74o&t=8506s) 會卡住的地方 一路往高處走，總會走到「每個鄰居都不比我好」的地方停下來，但那裡不一定是最高點。老師在 Figure 4.1 上指出三種：local maximum、flat local maximum、shoulder；後兩種是平的一片，合稱 plateau（高原）。更麻煩的是，解題時你看不到整張圖，永遠不知道最高點在哪，只能邊走邊看。第四種 ridge 老師到 (2:28:58) 才講，一起放在下表。 表格後面有一個手算摺疊（數學）：用一條 11 格的小地形，從四個不同起點爬，只有一個爬到最高點。它要說明的是：爬山法停下來時，自己分不出是真的到頂，還是卡在假山頂。
地形長什麼樣為什麼會卡怎麼救
**Local maximum**比所有鄰居高、但比全域最高點低的小山頂四周都是下坡換起點重爬（random restart）
**Flat local maximum**山頂是一片平地，兩側更低鄰居一樣高，沒有「更好」可選換起點；sideways move 救不了
**Shoulder**山腰上的平台，走過去還能往上平台上鄰居都一樣高，看不出哪邊會上坡sideways move
**Ridge**斜斜往上的山脊，兩側陡降往上要斜著走，但每個動作都偏離山脊換起點、其他變形
用一條 11 格的小地形手算，爬山會停在哪裡？ 位置 x = 0 到 10，分數 f 依序是：2, 4, 6, 6, 9, 5, 7, 3, 4, 4, 2。鄰居是左右各一格。規則：有鄰居「嚴格比我高」就走到最高的那個，否則停。 - 從 x = 0：分數 2、4、6，爬到 x=2。鄰居是 4 和 6，沒有比 6 高，停。這是 shoulder：x=3 也是 6，再過去就是 9。 - 從 x = 5：分數 5、9，爬到 x=4。鄰居 6 和 5 都較低，停。這次是 global maximum。 - 從 x = 7：分數 3、7，爬到 x=6。鄰居 5 和 3 都較低，停。這是 local maximum。 - 從 x = 10：分數 2、4，爬到 x=9。鄰居 4 和 2，停。這是 flat local maximum（x=8、x=9 都是 4）。 四個起點只有一個爬到 9。而且停下來那一刻，演算法「看起來」跟找到最高點一模一樣：它只知道鄰居都不比自己好。
用生活例子講，ridge 是什麼？ 想像一條從西南往東北斜斜升高的稜線，兩邊是懸崖，你每步只能往正東、正西、正南、正北走。沿稜線往上要「往東北」斜走，可是往正東或正北一步都會踩出稜線往下掉。所以每一點四個方向都是下坡，你就停了，儘管稜線還在往上。這就是 Figure 4.4：稜線上一串 local maximum 彼此不直接相連。 **注意：老師口頭說 ridge 是沿某個方向的鄰居都跟自己一樣好、其他方向都比較差 (2:29:11)；投影片 Figure 4.4 是往上升的稜線，每個可走的動作都往下。考試寫投影片的版本。**
老師原話是什麼？ 「就目前我能夠看到的範圍內，我能夠找到的最佳解法，就是在這裡」(2:22:39) 「你只能夠邊走邊看」(2:23:53)
## [2:23:55](https://www.youtube.com/watch?v=hNZQIO0q74o&t=8635s) Hill climbing 演算法 Hill climbing 像被隨機丟進一片山區：看看方圓 100 公尺內（鄰居）哪裡最高，就走過去；再以新位置為中心看一次；直到四周沒有比腳下更高的地方，就把腳下當答案。投影片寫的是 steepest-ascent（最陡上升）版本：每次選「最好的」鄰居，不是隨便一個比較好的。它不保留搜尋樹，只記目前的狀態和它的分數。 下面兩個摺疊：第一個是課本的 pseudocode（虛擬碼：用接近英文的步驟寫的程式草稿），意思就是上面這段話——從起點開始、挑最好的鄰居、不比自己好就停，否則搬過去再來一輪。第二個用 4 皇后小棋盤實際走兩步，示範互相攻擊的對數 h 從 4 降到 1、再降到 0，就是解。
課本的虛擬碼怎麼讀？ ``` function HILL-CLIMBING(problem) returns a state that is a local maximum current = MAKE-NODE(problem.INITIAL-STATE) // 從初始狀態開始 loop do neighbor = a highest-valued successor of current // 所有鄰居裡挑分數最高的 if neighbor.VALUE ≤ current.VALUE then return current.STATE // 最好的鄰居不比我高就停 current = neighbor // 否則搬過去，再看一輪 ``` 停止條件是「≤」：鄰居跟我一樣高也會停，所以走到平地就停，這正是 sideways move 要改的地方。函式名稱寫 returns a state that is a local maximum，本身就承認只保證區域最高。
4 皇后用爬山法怎麼一步步解？ 4×4 棋盤，每欄一隻皇后，只能在自己那欄上下移動。列由上往下編 1–4，欄由左往右編 A–D。h＝互相攻擊的對數（同列或同斜線），目標 h = 0。每個狀態有 4 × 3 = 12 個鄰居。 起點 A1、B1、C1、D2：A-B、A-C、B-C 同在第 1 列，C-D 在斜線上，h = 4。 第一步：算出 12 個鄰居的 h。格子數字＝把那一欄的皇后移到這格後的 h；Q＝皇后現在的位置。
ABCD
列 1QQQ6
列 2453Q
列 33234
列 423**1**4
最小是 1（C 移到列 4），比 4 好，走過去。新狀態 A1、B1、C4、D2，只剩 A-B 同列，h = 1。 第二步：再算 12 個鄰居，最好的是 A 移到列 3，h = 0（其他都 ≥ 1）。A3、B1、C4、D2 任兩隻都不同列、不同斜線，找到解。
老師原話是什麼？ 「方圓100公尺內，哪一個地方是最高的」(2:24:30) 「我永遠都會走到我最強的那個鄰居那裡」(2:25:52)
## [2:26:12](https://www.youtube.com/watch?v=hNZQIO0q74o&t=8772s) 八皇后例子與 greedy local search 投影片把八皇后寫成 local search：一個狀態是 8 隻皇后各占一欄的完整盤面；鄰居＝挑一隻皇后在同一欄裡移到別格，所以有 8 × 7 = 56 個鄰居；h＝互相攻擊的皇后對數，越少越好。Hill climbing 又叫 greedy local search（貪婪局部搜尋），因為它只抓眼前最好的鄰居，不想之後會走到哪；跟上一章 greedy best-first 不同的是，它連 frontier 都不留，走過就回不去。這麼簡單的方法常常表現不錯，但會卡在 local maximum、ridge、plateau。 這裡的 h 借用 heuristic 的符號（本週 [06 Greedy 與 A* 搜尋](https://app.notion.com/p/3e6fc631b03081f7acf6d56761c8225c) 學過：heuristic 是「估計離目標還有多遠」的分數）；在八皇后裡 h 越小越好，h = 0 就代表 8 隻皇后互不攻擊、解好了。greedy best-first 也是 06 章學的：每次展開看起來離目標最近的節點，但會把其他候選留在 frontier 裡，走錯還能回頭。 [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w2\img\ai_ch4_p006.png | Ch4 p.6 Figure 4.3：(a) h = 17 的盤面與每個鄰居的 h。(b) h = 1 卻卡住的盤面。]] 圖上重點： - 圖 (a)：8×8 棋盤，皇后圖示是目前位置；每個空格的數字是「把那一欄的皇后移到這格後，還剩幾對互相攻擊」。 - 有框的格子（數字 12）是最好的走法，共 8 格，平手就隨機挑一個。 - 圖 (b)：只剩 1 對互相攻擊（h = 1），但動哪一隻都會變更差，爬山法卡在這裡。 - 圖說英文：heuristic cost estimate（估計的代價，就是 h）、successor（鄰居）、local minimum（區域最小值：h 越小越好時的「小山谷」）。 這張圖在講：爬山法每一步就是看完所有鄰居的分數、挑最好的；但也可能停在離答案只差一點、卻再也走不動的盤面。
這張圖怎麼讀？ - 圖 (a) 目前盤面有 17 對皇后互相攻擊（h = 17）；每個空格的數字：只把那一欄的皇后移到這格、其他不動，新盤面的 h。例如左數第 2 欄的皇后移到最上面，h 變 12。 - 最小是 12，共 8 格（有框的）。平手時隨機挑一個（p.6 第三點，老師沒講）。 - 圖 (b)：h = 1，但 56 個鄰居的 h 都至少是 2，hill climbing 停在這裡。以 h 來說是 local minimum，等同 objective 的 local maximum。 **注意：老師口頭舉的 14、14、12 組是第 2 欄幾個格子上的數字（移過去之後的 h），聽起來像目前盤面是 14；投影片圖說寫目前盤面 h = 17，考試寫投影片的版本。**
要先懂什麼？八皇后在 Ch3 和 Ch4 的寫法差在哪？ Ch3（本週 1:03:57）：從空棋盤開始，一個 action 放一隻皇后，狀態是放了 0 到 8 隻的盤面，是在「長出一個解」。 Ch4：每個狀態一開始就有 8 隻皇后，只是位置可能不對；動作是挪一隻，是在「修改一個解」。課本稱為 complete-state formulation（完整狀態寫法：每個狀態都有解的所有部分，只是還沒全放對）。
老師原話是什麼？ 「我允許你動一隻皇后，然後呢，這隻皇后只能夠在同一個column裡面移動」(2:26:43) 「做出最貪婪的決定，因為他永遠只取最強的那個鄰居來取代掉」(2:28:09) 「他絕對不保證永遠可以找到最佳解」(2:28:30)
## [2:29:33](https://www.youtube.com/watch?v=hNZQIO0q74o&t=8973s) 成功率與 sideways move 課本的八皇后實驗：從隨機盤面出發，steepest-ascent hill climbing 有 86% 會卡住，只有 14% 解得出來。但它很快：狀態空間有 8^8 ≈ 1,700 萬個盤面（每欄 8 種位置、8 欄相乘），它幾步就有結果。改良做法是允許 sideways move（橫著走：最好的鄰居跟自己一樣好也走過去），賭這片平地其實是 shoulder。成功率升到 94%，代價是步數變多（見下表），老師說這是一種妥協。 下面摺疊用 4 皇后示範 sideways move：卡在平地時先橫走一步，下一步就找到解；但橫走要限制次數，不然在平的山頂上會來回打轉、停不下來。
原版 steepest-ascent允許 sideways move
成功率14%94%
成功時平均步數421
失敗時平均步數364
sideways move 怎麼救回卡住的 4 皇后？ 沿用 4 皇后。狀態 A1、B4、C2、D3：只有 C-D 在同一斜線，h = 1。算完 12 個鄰居，最好的是 C 移到列 1，h 還是 1。原版在這裡停，宣告失敗。 允許 sideways move：走到 A1、B4、C1、D3（h = 1，一樣好）。再看鄰居，A 移到列 2 得到 A2、B4、C1、D3，h = 0，解出來了。原來這片平地是 shoulder。 為什麼要限制次數：上一段 11 格地形的 x=8、x=9 都是 4、兩側更低，是 flat local maximum，允許橫走會在兩格之間來回停不下來。課本的做法是限制連續 sideways move 的次數（八皇后例子最多連續 100 次）。
老師原話是什麼？ 「他也很快就卡住，他三步就卡住了」(2:30:43) 「至少讓你很快知道你失敗了」(2:31:09) 「這個就是一個妥協啦」(2:32:32)
## [2:32:35](https://www.youtube.com/watch?v=hNZQIO0q74o&t=9155s) 三種變形與收尾 原版每次都挑「最好的」鄰居，另外還有三種挑法，差別見下表。沒有哪一種保證成功，老師說會不會成功很看地形長怎樣。本週講到這裡，下週從 Ch4 p.10 simulated annealing（模擬退火）接續。
版本怎麼挑下一步好處代價
**Steepest-ascent**（原版）算完所有鄰居，挑最好的簡單、步數少容易卡住
**Stochastic**（隨機爬山）在比自己好的鄰居中隨機挑，越陡機率可以越高不會每次都走同一條路通常爬得比較慢（課本）
**First-choice**（先到先選）隨機產生鄰居，第一個比自己好的就走鄰居非常多時省時間不一定是最好的一步
**Random-restart**（隨機重新開始）換很多個隨機起點重爬跑得夠多次，終究會碰到解（課本）要跑很多次
**注意：「stochastic 的機率可隨上坡陡度不同」「first-choice 的鄰居是隨機產生的」這兩點只在投影片 p.9，老師口頭沒講，考試寫投影片的版本。** 最後一個「重來幾次」的摺疊是機率計算，在回答：單次只有 14% 成功，一直重來到成功，平均要走幾步？答案大約 22 步，所以「多試幾次」其實很划算。
用生活例子講，這幾種變形差在哪？ 老師用找工作比喻原版和 first-choice，另外兩種照同一個比喻延伸： - 原版：拿到所有 offer，挑薪水最高的。但第一份工作薪水最高，不保證整個職涯最好。 - Stochastic：在比現在好的 offer 裡抽一個（薪水越高越容易抽中）。 - First-choice：第一家說要錄取、又比現在好，就去了，不等其他家。 - Random-restart：人生重來好幾次，挑最好的那一次。
random-restart 平均要重來幾次、共走幾步？ 先懂一件事：每次成功機率是 p，平均要試 1/p 次才成功。像擲骰子等 6 點，p = 1/6，平均擲 6 次。 - 八皇后原版：p = 0.14，平均約 7 次（6 次失敗＋1 次成功）。總步數 ≈ 成功那次 4 步＋失敗次數 (1 − p)/p ≈ 6.14 × 每次 3 步 ≈ 4 + 18.4 ≈ 22 步。 - 加 sideways move：p = 0.94，平均約 1.06 次。總步數 ≈ 21 + (0.06/0.94) × 64 ≈ 21 + 4.1 ≈ 25 步。 所以單次只有 14% 也沒關係，重來幾次，平均 22 步左右就能解八皇后。 **注意：投影片寫的是重爬到找到 goal 為止（八皇后 h = 0 就是解）；老師講的是爬幾次、留最好的 local maximum，適合不知道最高分的問題。考試寫投影片的句子。**
老師原話是什麼？ 「我從這十個裡面，我隨機挑一個」(2:32:54) 「不見得一定是不好，也不見得一定好就是了啦」(2:33:57) 「那這些Local Maxima裡面，我就取相對最厲害的那一個」(2:34:34)
## Self-check
Q1. Why is local search suitable for the 8-queens problem? Give two advantages of local search.（中文：為什麼 local search 適合用在八皇后問題？舉出 local search 的兩個優點。） **Answer**: The path to the goal is irrelevant; what matters is the final configuration of queens. Local search keeps a single current node and moves only to its neighbors, so (1) it uses very little memory, usually a constant amount, and (2) it can often find reasonable solutions in large or infinite state spaces where systematic algorithms are unsuitable. 中文：八皇后只看最後擺法對不對，不管怎麼擺到那裡，所以路徑不重要，可以用 local search。優點一：只需要記住目前這一個狀態和分數，不用像前面的搜尋存整棵樹，省記憶體。優點二：就算狀態空間很大甚至無限大，也能找到還不錯的解，不需要能一格一格列舉的空間。
Q2. Describe steepest-ascent hill climbing and three reasons why it gets stuck.（中文：說明 steepest-ascent 爬山法怎麼運作，並說出讓它卡住的三種原因。） **Answer**: Repeatedly move to the highest-valued successor; stop and return the current state when no successor is better. It gets stuck at local maxima (higher than all neighbors but lower than the global maximum), ridges (a sequence of local maxima not directly connected), and plateaux (a flat local maximum or a shoulder). 中文：一直走到分數最高的鄰居，直到沒有鄰居比自己好就停下來，回傳目前狀態。它會卡在三種地形：local maximum（比周圍都高、但比全域最高點低的小山頂）、ridge（一串彼此不直接相連的小山頂組成的稜線，站在上面每個方向都是下坡）、plateau（一片平坦的高原，可能是平的山頂，也可能是還能往上走的 shoulder）。
Q3. For 8-queens, define the successors and h, and explain the effect of sideways moves.（中文：針對八皇后，定義鄰居和 h，並說明 sideways move 的效果。） **Answer**: A successor moves one queen to another square in the same column (8 × 7 = 56 successors); h is the number of attacking pairs. Steepest-ascent solves only 14% of instances. Allowing sideways moves raises this to 94%, at about 21 steps per success and 64 per failure; consecutive sideways moves must be limited to avoid looping on a flat local maximum. 中文：鄰居是把某一隻皇后移到同一欄的另一格，因為每欄有 8 個位置、8 隻皇后共 8×7=56 個鄰居；h 是互相攻擊的皇后對數，越小越好。原版 steepest-ascent 只解得出 14% 的題目。允許 sideways move（走到跟自己一樣好的鄰居）後成功率升到 94%，但代價是步數變多，成功平均要走 21 步、失敗平均要走 64 步；而且要限制連續橫走的次數，不然會在平的高原上來回走不出去。
Q4. Distinguish stochastic, first-choice, and random-restart hill climbing.（中文：區分 stochastic、first-choice、random-restart 三種爬山法。） **Answer**: Stochastic chooses at random among uphill moves, possibly weighted by steepness. First-choice generates successors randomly until one is better than the current state. Random-restart runs hill climbing repeatedly from random initial states until a goal is found. 中文：Stochastic 是在比現在好的鄰居裡隨機抽一個，坡度越陡的鄰居越容易被抽到；first-choice 是隨機生成鄰居，一找到比現在好的就直接走，不用比完全部鄰居；random-restart 是從很多個隨機起點各爬一次，重複做直到找到目標為止。
這週讀完了。下一週第一章：[01 下週預錄課與抽算力制度（0:09–0:23）](https://app.notion.com/p/3e6fc631b030813ebaaac6d55eece1b5)｜回到週頁：[W2（9/17）](https://app.notion.com/p/3e6fc631b0308175a433e5fa4bc500df)