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