這是我人工智能系列筆記里實操性最強的一章。第四章搜索策略與問題求解。不少初學者翻到教材這一章看著滿屏的樹、圖、隊列、優(yōu)先隊列會覺得這跟智能兩個字根本沒搭上邊但等你真正把八數(shù)碼、路徑規(guī)劃、迷宮尋路這類問題親手跑通再回頭看這一章會發(fā)現(xiàn)搜索其實是大量AI問題的底層共性——棋類游戲的決策樹、機器人的路徑規(guī)劃、知識圖譜里的關(guān)系查找本質(zhì)上都是在巨大的狀態(tài)空間里找一條路。這一章的核心任務(wù)就是把找路這件事從直覺變成可描述的數(shù)學形式再變成能運行的代碼。不同教材的章節(jié)順序略有差異但搜索這塊內(nèi)容基本都落在第四章附近各個版本都繞不開它。1. 第四章在AI知識體系中的位置與核心思路1.1 為什么搜索會被單獨拎出來講一章如果你把AI看成一門如何讓程序自己找到答案的學科搜索就是最樸素也最關(guān)鍵的一類方法。早期AI研究的相當一部分精力都花在如何高效地搜索上。后來深度學習火起來大家開口閉口是神經(jīng)網(wǎng)絡(luò)、梯度下降但仔細想一下模型訓練時的參數(shù)尋優(yōu)本質(zhì)上是在一個高維空間里搜索一組好參數(shù)自然語言生成時每個token的選擇也是在候選詞集合里搜索最合理的下一個詞。搜索并沒有過時它只是換了個名字藏在了各種現(xiàn)代算法的底層。教材里把它安排在第四章邏輯上也很順。前三章通常會講清楚什么是智能體、什么是理性決策、怎么把一個問題描述清楚第四章就要解決描述完之后怎么找到解的問題。搜索是連接問題定義和求解方法的橋梁。學完這一章你再看后面章節(jié)里的博弈樹、約束滿足、規(guī)劃問題會發(fā)現(xiàn)它們都共用同一套狀態(tài)空間思維只是換了不同的搜索策略而已。拿到這一章我心里給它的定位是不只學幾個算法而是建立一切問題都可以建模成狀態(tài)空間然后通過搜索求解的視角。帶著這個視角去讀后面的章節(jié)會比死記硬背算法好得多。1.2 問題形式化寫代碼前最容易被忽略的一步搜索的第一步不是寫算法而是把問題形式化。這一節(jié)經(jīng)常被初學者跳過去覺得能做題就行結(jié)果一寫代碼就翻車。這里以八數(shù)碼為例這是第四章的經(jīng)典問題一個3x3棋盤上放了1到8八個數(shù)字和空格每次只能把空格和相鄰數(shù)字交換目標是擺成目標排列。形式化需要定義五樣東西要素八數(shù)碼中的具體含義狀態(tài)一個3x3棋盤的全部排列情況初始狀態(tài)題目給定的亂序棋盤動作空格向上下左右移動轉(zhuǎn)移模型給定狀態(tài)和動作返回移動后的新狀態(tài)目標測試判斷當前狀態(tài)是否等于目標排列路徑代價每移動一步代價為1路徑總代價是步數(shù)很多同學卡住不是因為不懂BFS或A*而是狀態(tài)表示沒設(shè)計好。比如用二維列表表示棋盤每次移動要深拷貝又慢又容易錯用一維元組(tuple)表示九個位置空格下標直接算行列移動只需交換兩個元素又快又穩(wěn)。這個細節(jié)我放在后面實操部分展開但形式化階段就要想清楚。還有個容易被忽略的點目標測試不一定是狀態(tài)完全相等。有些問題只要達到某種條件就算成功比如八皇后問題要求任意兩個皇后不互相攻擊。這提醒我們形式化方案是為問題服務(wù)的不是為算法服務(wù)的。你把狀態(tài)定義清楚了后面寫轉(zhuǎn)移、寫判重、寫啟發(fā)函數(shù)都會順很多。1.3 搜索樹與可行解的本質(zhì)形式化做完問題就變成了狀態(tài)空間里的搜索問題。搜索過程會隱式地建一棵搜索樹根節(jié)點是初始狀態(tài)從某個節(jié)點展開動作得到子節(jié)點子節(jié)點繼續(xù)展開直到找到目標。這里有個關(guān)鍵區(qū)分節(jié)點和狀態(tài)不是一回事。節(jié)點記錄的是從起點到當前狀態(tài)的路徑信息狀態(tài)只描述當前局面。同一個狀態(tài)可能通過不同路徑到達對應(yīng)搜索樹里的不同節(jié)點但局面是一樣的。我一般用旅行規(guī)劃來類比。假設(shè)你要從A城市去D城市狀態(tài)就是當前在哪座城市節(jié)點則是完整的行程記錄比如A到B再到C。同樣的C城市可能是經(jīng)過B來的也可能是經(jīng)過E來的兩種方案的當前狀態(tài)相同但路徑不同代價也不同。搜索算法要處理的正是在這些路徑里選一條最劃算的。為了避免無限循環(huán)一般要維護一個已探索集合closed set。比如八數(shù)碼里空格先右移再左移狀態(tài)會回到原點如果不判重BFS和DFS都會陷入毫無意義的重復展開。閉環(huán)處理得不好再好的算法也是空談這一點到第6節(jié)我會專門說。2. 無信息搜索先把基礎(chǔ)打牢2.1 BFS和DFS兩種最極端的策略無信息搜索指的是搜索時除了問題本身沒有任何額外信息只能盲目地展開節(jié)點。最典型的兩個是廣度優(yōu)先搜索(BFS)和深度優(yōu)先搜索(DFS)。BFS用隊列實現(xiàn)。隊列的特點是先進先出就像銀行取號叫號先來先辦。每一層的節(jié)點全部展開完畢才會進入下一層。所以BFS從根節(jié)點出發(fā)一層一層往外探像水波擴散一樣。DFS用棧實現(xiàn)后進先出像摞盤子后放的先拿走。DFS會沿著一條路一路走到黑走不通了才回頭換另一條路。從結(jié)果看BFS的優(yōu)勢是完備且有最優(yōu)性的只要解存在BFS一定能找到而且如果每步代價相同它找到的第一個解就是步數(shù)最少的解。缺點是空間消耗大最后一層的節(jié)點都要存在內(nèi)存里深度一深就爆炸。DFS正好相反空間消耗小只需要保存一條路徑上的節(jié)點但可能一頭扎進死胡同出不來遇到無限分支還會找不完。我剛開始學的時候也納悶為什么教科書要講看起來這么笨的算法后來才明白它們是后面所有高級搜索的底座。BF S的逐層展開思想貫穿到一致代價搜索DFS的壓?；厮菟枷胴灤┑缴疃仁芟匏阉骱偷由?。不懂這兩個基礎(chǔ)后面的變體全都看不懂。2.2 一致代價搜索當每步代價不一樣時BFS有個隱含假設(shè)每走一步代價相同所以步數(shù)最少就是代價最小。但現(xiàn)實問題里不同動作的代價往往不同。比如地圖導航里走高速和走小路的時間不一樣不能光看經(jīng)過了多少個路口。這時候BFS就不頂用了得用一致代價搜索。一致代價搜索依然用優(yōu)先隊列但排序鍵是路徑代價g(n)每次從隊里取出代價最小的節(jié)點展開。這其實就是Dijkstra算法的思想不斷從已知代價最小的頂點出發(fā)松弛鄰居。如果所有邊權(quán)都是1一致代價搜索就退化成BFS如果邊權(quán)不同它依然能保證找到代價最小的路徑這一點比BFS更通用。不過一致代價搜索也有代價它會被代價小的路徑拖著走如果有一條代價很低但路很長的迂回路徑它可能把大量時間耗在探索這條路徑上導致效率下降。這也引出了下一節(jié)的核心問題能不能讓搜索有方向感而不是像無頭蒼蠅一樣亂轉(zhuǎn)。2.3 完備性、最優(yōu)性與復雜度對比這四個指標是面試和考試的高頻點完備性、最優(yōu)性、時間復雜度和空間復雜度。我整理了一張表學的時候直接對著記。算法完備性最優(yōu)性時間復雜度空間復雜度BFS完備僅每步代價相同時最優(yōu)O(b^d)O(b^d)DFS在有限狀態(tài)空間下完備否O(b^m)O(bm)一致代價搜索完備是O(b^(1?C*/ε?))同左這里b是分支因子d是最淺解的深度m是搜索樹最大深度C*是最優(yōu)解的代價ε是最小邊權(quán)?？催@張表的時候要抓住兩個核心矛盾一是時間和空間的矛盾二是完備最優(yōu)和效率的矛盾。BFS和DFS正好站在天平兩端一致代價站在BFS的肩膀上但更通用。深度優(yōu)先的改進版是迭代加深DFS做法是不斷加深深度限制一遍遍地跑深度受限D(zhuǎn)FS。它既保留了DFS的空間優(yōu)勢又獲得了BFS的完備性和最優(yōu)性只是會重復展開上層節(jié)點好在代價通?？梢越邮?。這是面試里經(jīng)常被追問的知識點建議自己寫一遍。3. 啟發(fā)式搜索讓程序?qū)W會挑路走3.1 啟發(fā)函數(shù)怎么選從曼哈頓距離說起無信息搜索最大的痛點是盲目。以八數(shù)碼為例明明目標排列就在某個方向上程序還是四平八穩(wěn)地一層層往外擴。啟發(fā)式搜索的思路是引入一個啟發(fā)函數(shù)h(n)用它對當前狀態(tài)到目標狀態(tài)還需要多少代價做估計讓搜索優(yōu)先展開有希望的方向。八數(shù)碼里最常用的啟發(fā)函數(shù)是曼哈頓距離計算每個數(shù)字當前位置與目標位置的行列差絕對值之和。為啥叫曼哈頓因為曼哈頓的街道是棋盤網(wǎng)格從一個街口到另一個街口只能橫著走豎著走走過的格子距離就是橫縱距離之和。用代碼寫就是遍歷九宮格對每個非空格數(shù)字計算兩次行差和列差。h(n)的大小直接決定搜索效率。h(n)越接近真實的剩余代價A*展開的節(jié)點就越少h(n)與實際值偏差太大搜索效率就會退化。八數(shù)碼里還有一個更弱的啟發(fā)函數(shù)是錯誤位置計數(shù)數(shù)一數(shù)有多少個數(shù)字不在目標位置。這個函數(shù)計算快但估計精度低展開的節(jié)點數(shù)會明顯多于曼哈頓距離。想驗證差異的同學可以把兩種啟發(fā)函數(shù)跑到同一個初始狀態(tài)對比展開節(jié)點數(shù)效果非常直觀。3.2 貪婪最佳優(yōu)先搜索的誘人與翻車有一種很自然的思路每次只選h(n)最小的節(jié)點展開完全不關(guān)心已經(jīng)走過的路。這就是貪婪最佳優(yōu)先搜索它極其激進一路朝著自認為離目標最近的方向沖跑得飛快。問題是它經(jīng)常翻車。h(n)只是估計不是真實距離。八數(shù)碼里某個狀態(tài)可能看起來離目標很近實際上那條路是死路走到一半才發(fā)現(xiàn)目標在另一個方向。貪婪最佳優(yōu)先可能先沖進一條死路才能退回來甚至因為貪心而找到一條繞遠路的解。它的本質(zhì)是只看眼前不看全局像開車時只盯著導航顯示的剩余距離卻忽視了已經(jīng)繞了多少冤枉路。我踩過這個坑用貪婪最佳優(yōu)先求解某個初始狀態(tài)展開節(jié)點數(shù)確實少但解出來的步數(shù)比最優(yōu)解多了好幾步。追求快的解和最優(yōu)解是完全不同的目標很多競賽題刁鉆的地方就在這里。所以它適合用來做快速近似不適合要求最優(yōu)解的場合。3.3 A*算法在已走的路和未走的路之間找平衡A*算法可以說是啟發(fā)式搜索里最經(jīng)典的存在。它定義評估函數(shù)f(n) g(n) h(n)其中g(shù)(n)是起點到當前節(jié)點的實際代價h(n)是對當前節(jié)點到目標的估計代價f(n)就是對從起點經(jīng)過當前節(jié)點再到目標的總代價估計。A的策略很樸素優(yōu)先展開f(n)最小的節(jié)點。它既不像一致代價搜索只認已走的路也不像貪婪最佳優(yōu)先只認沒走的路而是把兩者放在一起權(quán)衡。這個混合聽起來簡單實際效果卻非常好只要h(n)滿足一定條件A就能保證找到最優(yōu)路徑而且展開節(jié)點數(shù)在所有最優(yōu)搜索算法中最少。用生活類比就是你要去一個陌生城市既知道你已經(jīng)在路上花了多長時間也知道導航估算還要多久你自然傾向于走那種已經(jīng)花的時間加剩余估計時間最小的路線。A*里的g是真實開銷h是估算f就是你的決策依據(jù)。3.4 A*最優(yōu)性的條件可采納性與一致性A*不是隨便寫個h就能保證最優(yōu)的有兩個數(shù)學條件特別關(guān)鍵。第一個是可采納性要求h(n) h*(n)其中h*(n)是當前狀態(tài)到目標的真實最小代價。也就是說啟發(fā)函數(shù)永遠不能高估剩余代價。曼哈頓距離是八數(shù)碼的可采納啟發(fā)函數(shù)因為每個數(shù)字至少要走這么多步任何情況下都不會高估。反過來如果你自作聰明把h乘以2雖然搜索會快很多但找到的路徑不保證最優(yōu)。第二個是一致性也稱單調(diào)性要求對于任意狀態(tài)n及其后繼n滿足h(n) c(n, a, n) h(n)。這個條件比可采納性更強。滿足一致性時f值沿路徑單調(diào)不減A*首次展開某個節(jié)點時就已經(jīng)找到了它的最優(yōu)代價這樣圖搜索版本也能保證最優(yōu)。實際操作中曼哈頓距離滿足一致性所以可以放心用closed集合判重。這兩個條件看著數(shù)學味重但理解后對調(diào)試幫助極大。如果你的A*運行結(jié)果不是最優(yōu)第一反應(yīng)就應(yīng)該是檢查h是不是高估了而不是去改代碼邏輯。4. 局部搜索不關(guān)心路徑只關(guān)心終點4.1 為什么有些問題不需要全局搜索搜索章節(jié)后半部分會講一類完全不同的方法局部搜索。這類問題的特點是解是一個完整的配置而不是一條路徑。比如八皇后問題要找一個不沖突的擺放方案我們并不關(guān)心怎么一步步擺到那里只要最終方案正確即可。對這類問題樹搜索那套思路反而笨重。你可以想象一個地形圖橫軸縱軸是變量的取值高度是解的質(zhì)量。找最優(yōu)解就是在這樣的地形里找最高點。局部搜索的思路很簡單從一個候選解出發(fā)不斷向相鄰狀態(tài)移動直到到達一個不錯的位置為止。它不維護搜索樹不需要回溯只用少量內(nèi)存就能應(yīng)對超大規(guī)模問題。第一次接觸局部搜索時我最大的感觸是并不是所有AI問題都要從起點找到目標路徑很多實際問題只是要找到一個足夠好的答案。把問題分類成路徑問題和狀態(tài)問題是選擇算法前最重要的一步。4.2 爬山法快是快但容易困在半山腰爬山法是最簡單的局部搜索算法。它從當前狀態(tài)出發(fā)看所有鄰居狀態(tài)選擇其中質(zhì)量最好的那個移過去然后重復直到?jīng)]有鄰居比當前狀態(tài)更優(yōu)。就像一個近視的人蒙著眼在山里找頂每一步都往坡度最大的方向走。它的致命弱點是局部最優(yōu)。我舉個例子你走到一個山脊上發(fā)現(xiàn)周圍不論哪個方向都往下走于是認為自己到頂了但真正的山頂離你還有幾個山頭的距離。爬山法看不到全局一旦進入這種局部最優(yōu)陷阱就出不來了。還有一種更尷尬的情況是平頂或者山脊多個鄰居質(zhì)量一樣它會隨機挑一個可能原地打轉(zhuǎn)。教材里通常會有幾個改進方向隨機重啟爬山法多換幾個起點重新爬、模擬退火允許暫時往低處走、側(cè)移允許走到質(zhì)量相同的鄰居。這些改進并不能保證找到全局最優(yōu)但能大幅提高找到好解的概率。實操里我建議先用隨機重啟代碼簡單效果卻立竿見影。4.3 模擬退火與隨機重啟擺脫局部最優(yōu)的思路模擬退火從金屬冷卻工藝得到啟發(fā)先把金屬加熱到高溫再慢慢降溫讓分子有足夠時間排列成低能量結(jié)構(gòu)。對應(yīng)到算法里搜索過程中以一定概率接受比當前解更差的鄰居這個概率隨溫度降低而減小。溫度高的時候算法敢于亂跳跳出局部最優(yōu)溫度低的時候行為趨近于爬山法逐漸收斂。這里的核心心得是概率接受壞解的時機。我把初始溫度和降溫速率調(diào)整過很多次發(fā)現(xiàn)溫度降得太快算法還沒跳出局部最優(yōu)就固化了跟爬山法沒什么區(qū)別降得太慢算得慢且不穩(wěn)定。實際做的時候要針對問題規(guī)模調(diào)參數(shù)沒有放之四海而皆準的值。隨機重啟的思路更直白從多個隨機初始狀態(tài)出發(fā)各跑一遍爬山法最終取所有結(jié)果里最好的那個。它不保證找到全局最優(yōu)但能顯著降低一次運氣不好就全軍覆沒的風險。這類方法在資源調(diào)度、排課、布局優(yōu)化等場景里非常實用也是后面遺傳算法等進化類方法的雛形。5. 實操用Python從零實現(xiàn)A*解決八數(shù)碼5.1 狀態(tài)表示與相鄰狀態(tài)生成理論講再多不如跑一段代碼。下面是我建議的狀態(tài)設(shè)計方案用長度9的元組表示棋盤數(shù)字0代表空格位置下標從左到右、從上到下依次是0到8。比如(1,2,3,4,5,6,7,8,0)就是目標狀態(tài)?？崭裨谀膫€位置能往哪移動通過下標換算行列row index // 3col index % 3。上下左右四個方向就是對行列坐標做加減再判斷是否越界。生成鄰居時先轉(zhuǎn)成列表交換空格和目標位置的下標再轉(zhuǎn)回元組。用元組的好處是它可哈希能直接放進set判重也能作為字典的鍵。GOAL (1, 2, 3, 4, 5, 6, 7, 8, 0) def get_neighbors(state): i state.index(0) r, c i // 3, i % 3 for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)): nr, nc r dr, c dc if 0 nr 3 and 0 nc 3: j nr * 3 nc lst list(state) lst[i], lst[j] lst[j], lst[i] yield tuple(lst)這段代碼量不大但把狀態(tài)轉(zhuǎn)移寫得很干凈。設(shè)計時我特意避開二維數(shù)組因為一維元組在判重和比較時更省事。寫到這里也想提醒一句狀態(tài)表示方式?jīng)Q定了后續(xù)所有代碼的復雜度這里多花十分鐘思考后面能省一個小時。5.2 啟發(fā)函數(shù)與優(yōu)先隊列實現(xiàn)啟發(fā)函數(shù)用曼哈頓距離。對每個非空格數(shù)字計算它在當前棋盤的行列和目標棋盤的行列累加絕對值差。代碼里的目標行列直接用數(shù)字倒推數(shù)字k的目標位置是(k-1)//3和(k-1)%3因為目標排列是1到8按順序排0在末尾。def manhattan(state): dist 0 for idx, val in enumerate(state): if val 0: continue r, c idx // 3, idx % 3 tr, tc (val - 1) // 3, (val - 1) % 3 dist abs(r - tr) abs(c - tc) return distA*主循環(huán)用Python的heapq實現(xiàn)優(yōu)先隊列。堆里的每個元素是(f, g, state)按f值從小到大排序f相同就比g再相同就比state本身。為了記錄路徑我用了兩個字典came_from記錄每個狀態(tài)從哪個狀態(tài)轉(zhuǎn)移而來cost_so_far記錄到達該狀態(tài)的最短代價。當目標狀態(tài)第一次出隊時沿came_from回溯就能拼出完整路徑。細節(jié)上要注意入隊前檢查新代價是否優(yōu)于歷史記錄只有更優(yōu)時才更新并入隊。這樣既避免無意義的重復入隊也保證A*的正確性。5.3 完整代碼與運行分析下面是完整實現(xiàn)把之前的內(nèi)容串起來。import heapq def a_star(start): if start GOAL: return [start], 0, 0 frontier [] heapq.heappush(frontier, (manhattan(start), 0, start)) came_from {start: None} cost_so_far {start: 0} explored set() expanded 0 while frontier: f, g, state heapq.heappop(frontier) if state in explored: continue explored.add(state) expanded 1 if state GOAL: path [] cur state while cur is not None: path.append(cur) cur came_from[cur] return path[::-1], cost_so_far[state], expanded for nxt in get_neighbors(state): new_g g 1 if nxt not in cost_so_far or new_g cost_so_far[nxt]: cost_so_far[nxt] new_g priority new_g manhattan(nxt) heapq.heappush(frontier, (priority, new_g, nxt)) came_from[nxt] state return None, 0, expanded用幾個初始狀態(tài)跑一下比如start (1,2,3,4,0,5,6,7,8)輸出目標步數(shù)和展開節(jié)點數(shù)。你會看到曼哈頓距離驅(qū)動的A*展開節(jié)點數(shù)遠少于BFS而且解出來的路徑是最優(yōu)的。想加深理解的話把manhattan換成錯誤位置計數(shù)對比同樣輸入下的展開節(jié)點數(shù)差距會是數(shù)量級的。運行時的觀察點我列兩個一是展開節(jié)點數(shù)這個數(shù)字直接反映算法效率二是搜索樹深度對應(yīng)著解的步數(shù)。把這兩個數(shù)字和BFS對比你才能真正感受到啟發(fā)函數(shù)的價值。6. 常見問題與避坑指南6.1 狀態(tài)爆炸為什么你的搜索跑不動八數(shù)碼的狀態(tài)空間總共是9!個排列約36萬種BFS在多數(shù)初始狀態(tài)下還行但換成15數(shù)碼狀態(tài)空間變成16!直接量級爆炸。無信息搜索在這種規(guī)模下完全跑不動網(wǎng)絡(luò)上有不少求解器能處理幾十步的八數(shù)碼核心原因就是用了A*加曼哈頓距離這類強啟發(fā)。遇到搜索跑不動第一件事不是優(yōu)化代碼而是檢查搜索空間和啟發(fā)函數(shù)。我見過有人用BFS跑15數(shù)碼跑了十分鐘沒出結(jié)果換成A加曼哈頓距離后秒出答案。搜索算法領(lǐng)域有個經(jīng)驗法則如果能設(shè)計出一個好的啟發(fā)函數(shù)效果比任何代碼層面的微優(yōu)化都顯著。這也是為什么第四章花了大量篇幅講貪心和A而不是教你怎么把BFS寫得更快。6.2 啟發(fā)函數(shù)高估的隱患A代碼看起來對了但跑出來的路徑不是最優(yōu)這是很隱蔽的坑。問題幾乎都出在啟發(fā)函數(shù)上。只要h(n)曾經(jīng)高估過真實代價A就可能提前放棄一條實際最優(yōu)的路徑因為它的f值被算大了。我調(diào)試過一個問題用了一個看似合理的啟發(fā)函數(shù)結(jié)果解的步數(shù)比最優(yōu)解多兩步。排查了很久才發(fā)現(xiàn)是這個函數(shù)在某些狀態(tài)下高估了。修好之后步數(shù)立刻回到最優(yōu)。建議所有人在動手寫A前先寫一個暴力BFS做基準用小規(guī)模問題對比A的步數(shù)和展開節(jié)點數(shù)。如果A*的路徑不是最優(yōu)第一嫌疑就是啟發(fā)函數(shù)不滿足可采納性。6.3 判重與優(yōu)先級隊列的細節(jié)坑代碼里有個常見問題用list做判重。八數(shù)碼狀態(tài)一共才36萬種list的in檢查是O(n)雖然小規(guī)模能跑但15數(shù)碼一上來就卡死。正確做法是用set存元組狀態(tài)查找是O(1)。另外如果你在heapq里直接存(f, state)Python會在f相同時去比較state元組本身這個沒問題但如果你在元組里混入了list類型的路徑字段就會引發(fā)嚴重的性能問題因為list比較是逐元素遞歸的。我的建議是路徑不要塞進優(yōu)先隊列用came_from字典回溯優(yōu)先隊列元素限定為可比較的、定長的數(shù)據(jù)。這樣既快又不容易踩坑。另一個容易被忽略的問題是closed集合的更新時機A*主循環(huán)里要在出隊時判重而不是入隊時判重否則可能錯過更優(yōu)的到達路徑。這一點我在代碼里特意用了出隊判重的寫法。6.4 學習地圖與后續(xù)章節(jié)銜接搜索這一章是整個AI基礎(chǔ)的地基學完它應(yīng)該能在腦子里畫出地圖無信息搜索解決我不會失敗但要慢慢找的問題啟發(fā)式搜索解決我知道目標在哪所以找得快的問題局部搜索解決我不關(guān)心路徑只要好答案的問題。后面學博弈搜索時Minimax和Alpha-Beta剪枝就是在搜索樹基礎(chǔ)上加了對局雙方的博弈視角學約束滿足問題時回溯搜索和推理是處理離散組合的利器。建議學完這一章做三件事鞏固第一把八數(shù)碼的BFS、一致代價、貪婪最佳優(yōu)先、A各寫一遍對比展開節(jié)點數(shù)第二把A的啟發(fā)函數(shù)換掉觀察最優(yōu)性和效率變化第三找一個地圖最短路徑問題把八數(shù)碼代碼改成通用狀態(tài)空間搜索框架。做完這三件事這一章你就真正吃透了。我個人在實際操作中最深的體會是別急著把代碼寫漂亮先把狀態(tài)定義和啟發(fā)函數(shù)想清楚。狀態(tài)定義錯了后面所有代碼都是白寫啟發(fā)函數(shù)選對了整個算法的性能天差地別。還有一個屢試不爽的小技巧調(diào)試A*的時候先跑一個最簡單的初始狀態(tài)比如只差一步的目標確認基礎(chǔ)邏輯沒問題再上復雜狀態(tài)。這樣一旦出錯你能立刻縮小排查范圍。搜索這一章最迷人的地方在于你能親眼看到同一個問題不同策略的效率差距可以大到幾百倍這種直觀感受比任何理論描述都更有說服力。