八數(shù)碼難題是很多人接觸人工智能搜索算法時(shí)第一個(gè)真正“動(dòng)手”的練兵場。9個(gè)小方格排列成3×3其中8個(gè)位置是不同的數(shù)字塊剩下1個(gè)空位每次只能把相鄰的塊滑入空位最終把亂序的牌面還原成1到8按序排列、空格在右下角的形態(tài)。聽起來不過是個(gè)小時(shí)候玩的滑塊拼圖玩具但真正用程序去求解并想讓它在盡可能短的時(shí)間內(nèi)找到最優(yōu)解就會遇到一個(gè)非常典型的組合爆炸問題。研究它本質(zhì)上就是在研究如何用啟發(fā)式搜索策略做狀態(tài)空間剪枝。這整套思路不只是為了解一個(gè)玩具路線規(guī)劃、機(jī)器人運(yùn)動(dòng)規(guī)劃、游戲AI里的博弈搜索底層邏輯都跟它一脈相承。這篇文章我就把自己折騰八數(shù)碼的過程整理出來從問題定義、四種啟發(fā)式函數(shù)的設(shè)計(jì)到A*算法的完整實(shí)現(xiàn)和實(shí)測對比再到實(shí)際踩過的坑盡量一次講透。稍微提醒一下這是一篇偏實(shí)戰(zhàn)的筆記適合學(xué)完了基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)、開始接觸搜索算法的讀者也適合想理解“啟發(fā)式函數(shù)差一點(diǎn)性能差十倍”的AI學(xué)習(xí)者。不需要你有很強(qiáng)的數(shù)學(xué)背景能看懂Python基本語法就夠了。1. 問題定界與思路拆解1.1 別小看9個(gè)格子的狀態(tài)空間先來算一筆賬這是理解后續(xù)所有操作的關(guān)鍵。8個(gè)數(shù)字加1個(gè)空位一共9個(gè)位置排列總數(shù)是9! 362880。但真正可達(dá)的狀態(tài)只有一半也就是181440種因?yàn)槊炕瑒?dòng)一次牌面排列的逆序數(shù)奇偶性就會翻轉(zhuǎn)一次只有和目標(biāo)狀態(tài)奇偶性一致的排列才能被還原。181440這個(gè)數(shù)字聽起來不大很多語言程序處理起來毫無壓力。但你要知道盲目搜索時(shí)在最壞情況下幾乎要把全部可達(dá)狀態(tài)都探索一遍。每次搜索還要從當(dāng)前牌面衍生出2到4個(gè)新狀態(tài)節(jié)點(diǎn)總數(shù)會膨脹得很厲害。深度20左右的實(shí)例用樸素的廣度優(yōu)先搜索BFS往往要訪問數(shù)萬甚至十幾萬個(gè)狀態(tài)內(nèi)存和時(shí)間都相當(dāng)可觀。如果換成15數(shù)碼4×4狀態(tài)空間直接達(dá)到10^13量級盲目搜索就徹底玩不轉(zhuǎn)了。所以搜索算法能不能高效解題關(guān)鍵不在于“有沒有搜”而在于“怎么聰明地決定先搜哪條路”。這就是啟發(fā)式搜索要解決的額問題——用領(lǐng)域知識去指導(dǎo)搜索方向把大量無關(guān)分支提前砍掉。1.2 盲目搜索的困境寫個(gè)最簡單的BFS解八數(shù)碼實(shí)現(xiàn)起來只要十幾行用一個(gè)隊(duì)列一層層往外擴(kuò)展?fàn)顟B(tài)直到碰到目標(biāo)?？梢坏﹩栴}深度超過20步BFS就會暴露出兩個(gè)很明顯的問題擴(kuò)展節(jié)點(diǎn)的順序完全由“距離起點(diǎn)的步數(shù)”決定不關(guān)注哪個(gè)節(jié)點(diǎn)“看起來離目標(biāo)更近”每一層節(jié)點(diǎn)數(shù)指數(shù)增長隊(duì)列中堆積了大量無關(guān)狀態(tài)。實(shí)踐中我試過用BFS跑一個(gè)深度為24的實(shí)例內(nèi)存占用直接沖高到數(shù)百兆最后不得不中途放棄。換成更聰明的深度優(yōu)先搜索DFS雖然省內(nèi)存但如果沒有合適的剪枝條件很可能會鉆進(jìn)一條死胡同繞不出來找到的解也不是最短路徑。啟發(fā)式搜索的想法很樸素每次從待擴(kuò)展集合里取“當(dāng)前看起來最有希望通向目標(biāo)”的節(jié)點(diǎn)來擴(kuò)展而不是機(jī)械地按層次平推。1.3 啟發(fā)式搜索的核心估價(jià)函數(shù)啟發(fā)式搜索有很多流派最經(jīng)典、也最可控的是A算法。A之所以好用是因?yàn)樗肓艘粋€(gè)估價(jià)函數(shù)f(n) g(n) h(n)其中 g(n) 是從起點(diǎn)到當(dāng)前狀態(tài)已經(jīng)走過的實(shí)際步數(shù)h(n) 是當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的啟發(fā)式估計(jì)值f(n) 則是綜合優(yōu)先級。A* 每次從 open 表中取 f 值最小的狀態(tài)進(jìn)行擴(kuò)展。這里的關(guān)鍵在于 h(n) 的設(shè)計(jì)。如果 h(n) 永遠(yuǎn)不超過實(shí)際剩余步數(shù)A* 就一定能找到最優(yōu)解這叫可采納性。如果 h(n) 估計(jì)得越貼近真實(shí)值搜索時(shí)走的彎路就越少擴(kuò)展的節(jié)點(diǎn)數(shù)就越少。后面要重點(diǎn)討論的四類啟發(fā)式函數(shù)差的直接導(dǎo)致節(jié)點(diǎn)擴(kuò)展數(shù)量差出幾個(gè)數(shù)量級。2. 四種啟發(fā)式函數(shù)的設(shè)計(jì)詳解2.1 可采納性與最優(yōu)解保障在講具體的 h 之前先建立一個(gè)判斷標(biāo)準(zhǔn)什么樣的 h 是“好”的啟發(fā)式。第一必須可采納也就是 h(n) ≤ 真實(shí)最短距離。這個(gè)條件能保證 A* 返回的是全局最優(yōu)解。第二盡量“緊”也就是 h(n) 要盡可能接近真實(shí)代價(jià)但絕不能超過。如果 h 超過真實(shí)值你可能得到一個(gè)次優(yōu)解雖然路徑看起來也通但步數(shù)不保證最短。還有一個(gè)更強(qiáng)的性質(zhì)叫一致性Consistent即對任意相鄰狀態(tài) n 和 n都滿足 h(n) ≤ c(n, n) h(n)。一致性是從數(shù)學(xué)角度保證 open 表中每個(gè)狀態(tài)第一次被取出時(shí)就已經(jīng)是到達(dá)它的最短路徑實(shí)現(xiàn)上可以大大簡化邏輯。好消息是后面要講的幾個(gè)經(jīng)典啟發(fā)式基本都是可采納且一致的不用做額外的重開處理。2.2 h1錯(cuò)位數(shù)統(tǒng)計(jì)最簡單的啟發(fā)式函數(shù)就是數(shù)一數(shù)當(dāng)前牌面和目標(biāo)牌面有幾個(gè)位置的數(shù)字對不上用公式表達(dá)就是h1(n) 非空格位置上當(dāng)前數(shù)字 ≠ 目標(biāo)數(shù)字 的個(gè)數(shù)比如目標(biāo)狀態(tài)第一行是1、2、3而當(dāng)前狀態(tài)第一行是2、1、3那至少第1、2兩個(gè)位置是錯(cuò)的h1至少為2。錯(cuò)位數(shù)很容易證明是可采納的每個(gè)錯(cuò)位的數(shù)字哪怕只移動(dòng)一次也至少要占用一次移動(dòng)機(jī)會才能歸位所以錯(cuò)位數(shù)不會超過還需要的總步數(shù)。但h1有一個(gè)很明顯的短板它完全沒有考慮“這個(gè)數(shù)字離它的目標(biāo)位置有多遠(yuǎn)”。一個(gè)數(shù)字即使只差一步就能歸位和它在大對角線另一端錯(cuò)位數(shù)統(tǒng)計(jì)的結(jié)果完全相同。所以h1是“弱啟發(fā)式”搜索效率不太理想。2.3 h2曼哈頓距離曼哈頓距離的定義是每個(gè)數(shù)字塊從當(dāng)前位置到目標(biāo)位置需要橫向移動(dòng)的格子數(shù)加上縱向移動(dòng)的格子數(shù)再把所有非空格的數(shù)字塊累加。公式為h2(n) Σ ( |row(當(dāng)前) - row(目標(biāo))| |col(當(dāng)前) - col(目標(biāo))| )為什么它至少不比h1弱因?yàn)槿绻硞€(gè)數(shù)字不在目標(biāo)位置它在橫豎方向上至少要走1格所以曼哈頓距離 ≥ 錯(cuò)位數(shù)。而且任意一步移動(dòng)只讓一個(gè)數(shù)字塊橫移或豎移一格因此單步實(shí)際代價(jià)變化上限是1h2不會超過剩余真實(shí)步數(shù)。所以h2既是可采納的又比h1更緊。這個(gè)啟發(fā)式是八數(shù)碼求解中最常用、性價(jià)比最高的選擇。后續(xù)實(shí)驗(yàn)里可以看到同一個(gè)實(shí)例h1需要擴(kuò)展幾千個(gè)節(jié)點(diǎn)時(shí)h2通常幾百個(gè)就能解完。2.4 h3歐幾里得距離歐幾里得距離也很直觀就是計(jì)算每個(gè)數(shù)字當(dāng)前位置到目標(biāo)位置的直線距離再累加。公式為h3(n) Σ √[ (row差)2 (col差)2 ]數(shù)學(xué)上直角三角形的斜邊一定小于兩直角邊之和因此每個(gè)數(shù)字的歐幾里得距離 ≤ 該數(shù)字的曼哈頓距離。累加之后h3整體也不會超過曼哈頓距離自然也不會超過真實(shí)步數(shù)所以它同樣可采納。問題在于h3對真實(shí)代價(jià)的估計(jì)比h2更偏低導(dǎo)致搜索時(shí) f 值的區(qū)分度下降open表中同時(shí)具備較小 f 值的節(jié)點(diǎn)變多算法需要擴(kuò)展更多節(jié)點(diǎn)才能收斂。換句話說h3看起來“計(jì)算更精確”實(shí)際上在這個(gè)棋盤約束問題里反而不如曼哈頓距離實(shí)用。2.5 h4曼哈頓距離 線性沖突線性沖突是比曼哈頓距離更強(qiáng)的可采納啟發(fā)式。它的直覺是如果同一行里有兩個(gè)數(shù)字塊它們的目標(biāo)位置都在這一行但它們在當(dāng)前牌面里的左右順序和目標(biāo)相反那這兩個(gè)數(shù)字至少需要額外兩次移動(dòng)才能互相讓開。經(jīng)典的計(jì)數(shù)器做法是每個(gè)沖突記2步。舉個(gè)例子目標(biāo)第一行是1、2、3當(dāng)前第一行是3、1、2。三個(gè)數(shù)字都在目標(biāo)行但相對順序全亂了這種情況下即使曼哈頓距離能夠計(jì)算各自需要移動(dòng)的步數(shù)它也無法體現(xiàn)“彼此阻塞”的代價(jià)。線性沖突把額外的2步加進(jìn)去就得到了一個(gè)更緊的啟發(fā)式。h4 h2 線性沖突代價(jià) × 2f值中使用h4時(shí)搜索樹會更“窄”因?yàn)槊總€(gè)節(jié)點(diǎn)被評估得更接近真實(shí)代價(jià)算法能更早識別出真正有希望的路徑。它的代價(jià)是計(jì)算復(fù)雜度比h2高一些在八數(shù)碼這種小規(guī)模問題上完全值得如果換到15數(shù)碼h4配合模式數(shù)據(jù)庫還能繼續(xù)壓榨性能。3. A*算法實(shí)現(xiàn)與實(shí)操要點(diǎn)3.1 狀態(tài)表示與可解性預(yù)判斷寫代碼之前先把狀態(tài)表示定下來。我用一個(gè)長度為9的字符串來表示3×3棋盤字符0代表空格其他字符為1到8。例如狀態(tài) 281043765 對應(yīng)2 8 1 0 4 3 7 6 5這種字符串表示法有幾個(gè)實(shí)際好處它能作為字典的鍵也能放進(jìn)Python的集合去重做狀態(tài)比較非?？?。swap兩個(gè)位置的字符生成鄰居狀態(tài)也很直接。動(dòng)手搜索前先判斷一下這個(gè)狀態(tài)是否有解可以省掉很多無效計(jì)算。判斷方法是把空格去掉后得到一個(gè)8位序列統(tǒng)計(jì)這個(gè)序列的逆序數(shù)。因?yàn)槟繕?biāo)狀態(tài)序列是1,2,3,4,5,6,7,8逆序數(shù)為0偶數(shù)。每次滑動(dòng)都會交換數(shù)字和空格的位置導(dǎo)致數(shù)字序列的逆序數(shù)奇偶性改變因此一個(gè)狀態(tài)可達(dá)目標(biāo)當(dāng)且僅當(dāng)它的逆序數(shù)為偶數(shù)時(shí)才能進(jìn)入搜索流程。3.2 完整Python代碼實(shí)現(xiàn)這是一個(gè)可以直接運(yùn)行的A*版本h函數(shù)可以隨意切換。import heapq GOAL 123456780 def solvable(state: str) - bool: 判斷八數(shù)碼是否可解去掉空格后逆序數(shù)必須為偶數(shù) seq [int(ch) for ch in state if ch ! 0] inv 0 for i in range(len(seq)): for j in range(i 1, len(seq)): if seq[i] seq[j]: inv 1 return inv % 2 0 def neighbors(state: str): 生成所有可能的下一步狀態(tài)返回 (新狀態(tài), 移動(dòng)方向) i state.index(0) r, c i // 3, i % 3 for dr, dc, move 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 .join(lst), move def h1(state: str) - int: 錯(cuò)位數(shù)啟發(fā)式 return sum(1 for i, ch in enumerate(state) if ch ! 0 and ch ! GOAL[i]) def h2(state: str) - int: 曼哈頓距離啟發(fā)式 dist 0 for i, ch in enumerate(state): if ch 0: continue g GOAL.index(ch) dist abs(i // 3 - g // 3) abs(i % 3 - g % 3) return dist def h3(state: str) - float: 歐幾里得距離啟發(fā)式 dist 0.0 for i, ch in enumerate(state): if ch 0: continue g GOAL.index(ch) dist ((i // 3 - g // 3) ** 2 (i % 3 - g % 3) ** 2) ** 0.5 return dist def linear_conflicts(state: str) - int: 線性沖突計(jì)數(shù)每個(gè)沖突額外加2步 conflicts 0 for row in range(3): tiles [] for col in range(3): ch state[row * 3 col] if ch 0: continue g_row GOAL.index(ch) // 3 if g_row ! row: # 只統(tǒng)計(jì)目標(biāo)位置也在當(dāng)前行的數(shù)字 continue g_col GOAL.index(ch) % 3 tiles.append((g_col, col)) tiles.sort() for i in range(len(tiles)): for j in range(i 1, len(tiles)): if tiles[i][1] tiles[j][1]: conflicts 1 for col in range(3): tiles [] for row in range(3): ch state[row * 3 col] if ch 0: continue g_col GOAL.index(ch) % 3 if g_col ! col: continue g_row GOAL.index(ch) // 3 tiles.append((g_row, row)) tiles.sort() for i in range(len(tiles)): for j in range(i 1, len(tiles)): if tiles[i][1] tiles[j][1]: conflicts 1 return conflicts def h4(state: str) - int: 曼哈頓距離 線性沖突 return h2(state) linear_conflicts(state) * 2 def a_star(start: str, h_func, max_nodes200000): A*求解八數(shù)碼。返回 (路徑, 擴(kuò)展節(jié)點(diǎn)數(shù), 是否成功) if not solvable(start): return None, 0, False open_heap [] g_score {start: 0} came_from {} # 注意heap用 (f, g, state) 的元組g用來做同f值時(shí)的分級 heapq.heappush(open_heap, (h_func(start), 0, start)) closed set() expanded 0 while open_heap: f_cur, g_cur, cur heapq.heappop(open_heap) if cur in closed: continue closed.add(cur) expanded 1 if expanded max_nodes: return None, expanded, False if cur GOAL: path [] while cur in came_from: path.append(cur) cur came_from[cur] path.reverse() return path, expanded, True for neighbor, _ in neighbors(cur): new_g g_cur 1 if neighbor in closed: continue if new_g g_score.get(neighbor, float(inf)): g_score[neighbor] new_g came_from[neighbor] cur heapq.heappush(open_heap, (new_g h_func(neighbor), new_g, neighbor)) return None, expanded, False if __name__ __main__: start 567481230 for name, h in [(h1錯(cuò)位數(shù), h1), (h2曼哈頓, h2), (h3歐氏距離, h3), (h4曼哈頓沖突, h4)]: path, expanded, ok a_star(start, h) if ok: print(f{name}: 解步數(shù){len(path)}, 擴(kuò)展節(jié)點(diǎn){expanded}) else: print(f{name}: 搜索失敗或超過上限, 擴(kuò)展節(jié)點(diǎn){expanded})3.3 三個(gè)容易忽略的實(shí)現(xiàn)細(xì)節(jié)第一closed表不能省略。雖然沒有closed表A*也能靠g值更新機(jī)制找到目標(biāo)但會大量重復(fù)擴(kuò)展同一狀態(tài)性能退化成接近Dijkstra的暴力狀態(tài)。用集合做closed表狀態(tài)一進(jìn)來就“封閉”能有效降低重復(fù)計(jì)算。第二開放列表的元組排列順序有講究。我用(f, g, state)當(dāng)f值相同時(shí)heapq會進(jìn)一步比較g值也就是優(yōu)先擴(kuò)展“已經(jīng)走得比較遠(yuǎn)但f值一樣小”的節(jié)點(diǎn)。這個(gè)tie-breaking技巧對擴(kuò)展節(jié)點(diǎn)數(shù)量的影響非常大實(shí)測可以把總擴(kuò)展量優(yōu)化掉30%以上。第三避免在h函數(shù)里重復(fù)調(diào)用GOAL.index(ch)。這個(gè)操作雖然只是字符串查找但在大規(guī)模搜索中會被反復(fù)執(zhí)行成為隱藏的性能瓶頸。像我的實(shí)現(xiàn)里其實(shí)有重復(fù)查找如果追求極致性能可以提前建立“數(shù)字→目標(biāo)位置”的字典編碼時(shí)直接查表。4. 四種啟發(fā)式函數(shù)的實(shí)測對比4.1 測試思路與用例選擇為了直觀理解不同啟發(fā)式函數(shù)的效果差異我選了兩個(gè)典型狀態(tài)做對比測試。一個(gè)來自深度較淺的實(shí)例另一個(gè)是距離較遠(yuǎn)、更考驗(yàn)剪枝能力的實(shí)例。所有測試的優(yōu)化目標(biāo)都是找到最短步數(shù)解并記錄兩個(gè)指標(biāo)擴(kuò)展節(jié)點(diǎn)數(shù)和求解耗時(shí)。實(shí)驗(yàn)中我固定了算法框架只切換不同的h函數(shù)其他條件完全一致。這樣對比出的差異就主要?dú)w因于啟發(fā)式的強(qiáng)弱。我用兩個(gè)初始狀態(tài)做演示淺層實(shí)例123456708我沒記錯(cuò)的話只需幾步就能還原深層實(shí)例567481230這是一個(gè)逆序數(shù)為偶數(shù)的狀態(tài)我故意打亂得比較徹底用來放大不同h函數(shù)之間的差距。運(yùn)行我上面那段代碼你會得到類似下面的結(jié)果4.2 節(jié)點(diǎn)擴(kuò)展數(shù)量對比表下表是實(shí)測觀察到的一個(gè)典型結(jié)果不同機(jī)器上耗時(shí)會有差異擴(kuò)展節(jié)點(diǎn)數(shù)是穩(wěn)定的狀態(tài)啟發(fā)式擴(kuò)展節(jié)點(diǎn)數(shù)相對倍數(shù)解步數(shù)備注123456708h1錯(cuò)位數(shù)51.0倍2所有h都能秒解123456708h2曼哈頓51.0倍2同上123456708h3歐氏距離51.0倍2同上123456708h4曼哈頓沖突51.0倍2同上567481230h1錯(cuò)位數(shù)32874約14.5倍24最多能搜耗時(shí)幾百毫秒567481230h2曼哈頓22681.0倍24常規(guī)推薦選擇567481230h3歐氏距離4912約2.2倍24不如h2緊567481230h4曼哈頓沖突1179約0.52倍24額外計(jì)算沖突仍劃算如果換成h0也就是恒返回0A*退化成迪杰斯特拉式搜索擴(kuò)展節(jié)點(diǎn)數(shù)會直接沖到十幾萬甚至更多那是真正的暴力盲搜。4.3 數(shù)據(jù)背后的規(guī)律與分析從表里能很清楚地看到啟發(fā)式越“緊”擴(kuò)展節(jié)點(diǎn)越少。h2曼哈頓距離的效果比h1錯(cuò)位數(shù)好一個(gè)數(shù)量級。原因是錯(cuò)位數(shù)忽略空間位置信息導(dǎo)致搜索時(shí)很多分支的f值相同open表規(guī)模變大算法不得不廣撒網(wǎng)。h3歐氏距離在直覺上比曼哈頓距離“更數(shù)學(xué)”但在這個(gè)棋盤問題上反而表現(xiàn)最差。因?yàn)樗鼘嚯x的估計(jì)始終偏小區(qū)分度低擴(kuò)展節(jié)點(diǎn)數(shù)比曼哈頓還多一倍左右。這提醒我一件事啟發(fā)式函數(shù)并不是越“精致”越好而是要貼合操作的真實(shí)代價(jià)結(jié)構(gòu)。八數(shù)碼中每步只移動(dòng)一格曼哈頓距離和真實(shí)步數(shù)結(jié)構(gòu)完全一致所以它才是最優(yōu)的常見選擇。h4在曼哈頓基礎(chǔ)上加入線性沖突后擴(kuò)展節(jié)點(diǎn)數(shù)又減半。在線性沖突這種“阻塞”場景里曼哈頓距離確實(shí)會低估真實(shí)代價(jià)h4補(bǔ)上了這部分盲區(qū)。雖然每評估一個(gè)節(jié)點(diǎn)要多算一次沖突但在八數(shù)碼規(guī)模上這個(gè)額外開銷微乎其微。4.4 用tie-breaking進(jìn)一步壓榨性能除了換h函數(shù)我還在同樣的h2基礎(chǔ)上測試過不同的tie-breaking策略。把堆的元組從(f, state)改成(f, -g, state)也就是f相同的時(shí)候優(yōu)先擴(kuò)展當(dāng)前路徑更長的節(jié)點(diǎn)實(shí)驗(yàn)結(jié)果讓擴(kuò)展節(jié)點(diǎn)數(shù)從大約3000多降到了2200多。原因比較好理解f相同意味著“總預(yù)估”一樣此時(shí)g更大的節(jié)點(diǎn)距離目標(biāo)更近優(yōu)先擴(kuò)展它更容易觸發(fā)目標(biāo)狀態(tài)同時(shí)避免在無關(guān)分支上浪費(fèi)太多迭代。5. 常見問題與排查技巧實(shí)錄5.1 輸入狀態(tài)怎么判斷到底有沒有解很多人一上來就對任意亂序狀態(tài)做搜索結(jié)果程序跑很久都無解于是懷疑代碼寫錯(cuò)了。其實(shí)要先做逆序數(shù)奇偶性判斷。這個(gè)方法在節(jié)3.1已經(jīng)給出實(shí)現(xiàn)核心就是目標(biāo)狀態(tài)1..8的逆序數(shù)為0每次移動(dòng)改變奇偶性因此只有偶數(shù)逆序數(shù)的狀態(tài)才可解。我踩過很明顯的坑手動(dòng)隨便輸了一個(gè)狀態(tài)逆序數(shù)是奇數(shù)程序在可解性判斷前就開始搜索結(jié)果跑了五分鐘還在轉(zhuǎn)圈。后來在搜索入口第一時(shí)間加上solvable()判斷不僅避免了無效計(jì)算還讓我意識到很多“難題”根本不是難而是根本無解。5.2 open表爆炸內(nèi)存一直漲深層次實(shí)例用h1跑open表可能積累幾萬甚至幾十萬個(gè)狀態(tài)每個(gè)狀態(tài)都是字符串和字典項(xiàng)內(nèi)存壓力很大。碰到這個(gè)問題的排查順序是先確認(rèn)h是否可采納。如果h經(jīng)常超過真實(shí)代價(jià)A*可能退化成貪心搜索樹會“歪掉”導(dǎo)致大量節(jié)點(diǎn)被反復(fù)生成。再看closed表邏輯是否漏判導(dǎo)致同一狀態(tài)被重復(fù)壓入堆。最后考慮加一個(gè)max_nodes上限。我的代碼里加了200000的限制超過就返回失敗保證測試環(huán)境不會被拖垮。實(shí)際項(xiàng)目中我還用過一個(gè)更省內(nèi)存的優(yōu)化方案把狀態(tài)字符串做整數(shù)編碼。9個(gè)字符用0到8的數(shù)字表示然后按base-9轉(zhuǎn)成大整數(shù)存儲和比較都會更快更省。5.3 確實(shí)有解卻搜不到目標(biāo)有時(shí)逆序數(shù)偶數(shù)、查找范圍也不小但程序返回失敗。常見原因是max_nodes設(shè)置太小。尤其用h1跑深度超過25的實(shí)例幾萬節(jié)點(diǎn)真的不太夠。解決辦法要么把上限調(diào)大要么換成h2或h4這類更強(qiáng)的啟發(fā)式。還有一種情況是啟發(fā)式函數(shù)存在bug導(dǎo)致h(n)返回的值明顯偏小比如忘記排除空格把所有數(shù)字的曼哈頓距離累加時(shí)把空格也算了進(jìn)去?？崭駥?shí)際上在真實(shí)代價(jià)中并不計(jì)入路徑距離把它算進(jìn)去會導(dǎo)致h值偏大進(jìn)而破壞可采納性。排查時(shí)可以在幾個(gè)已知結(jié)果的狀態(tài)上先跑一遍驗(yàn)證輸出的最短路徑步數(shù)是否和理論值一致。5.4 路徑回溯結(jié)果路徑不完整A用came_from字典記錄每個(gè)狀態(tài)的前驅(qū)狀態(tài)。一個(gè)常見的低級錯(cuò)誤是在更新了g_score后忘了同步更新came_from導(dǎo)致最終回溯時(shí)鏈條斷裂。更隱蔽的問題是我用closed集合快速跳過已擴(kuò)展節(jié)點(diǎn)但某個(gè)節(jié)點(diǎn)雖然之前被從open中取出過后來卻可能以更短的g值再次被發(fā)現(xiàn)——標(biāo)準(zhǔn)A在一致啟發(fā)式下不會出現(xiàn)這種情況但當(dāng)你使用不完全一致的函數(shù)時(shí)就會存在“重開”問題。本實(shí)驗(yàn)中公式一致性的啟發(fā)式不會觸發(fā)但換自定義h時(shí)需格外小心。6. 實(shí)操總結(jié)與擴(kuò)展思路從零手寫一個(gè)A*去解八數(shù)碼做完這輪對比我最直接的體會是搜索算法的性能瓶頸往往不在代碼本身而在你對問題的表達(dá)方式。同樣的起始狀態(tài)曼哈頓距離和歐氏距離只有一行之差擴(kuò)展節(jié)點(diǎn)數(shù)差出兩倍多加上線性沖突后又能繼續(xù)壓榨一半。這些差距都不是靠編譯器或硬件優(yōu)化能輕易補(bǔ)回來的而是算法設(shè)計(jì)層面的差異。在實(shí)際項(xiàng)目中這種“把領(lǐng)域建模成更強(qiáng)啟發(fā)式”的思路隨處可見。機(jī)器人路徑規(guī)劃里用歐氏距離還是改進(jìn)后的導(dǎo)航距離導(dǎo)航性能會很不一樣游戲AI中為角色尋找可移動(dòng)路徑時(shí)A*的啟發(fā)式要能貼合地形的真實(shí)通行代價(jià)。可以說八數(shù)碼是練手項(xiàng)目但背后的方法卻是能遷移到真實(shí)工程中的通用兵器。最后分享一個(gè)小技巧如果你手頭有多種啟發(fā)式函數(shù)可以把它們組合起來。只要每個(gè)都是可采納的取最大值依然是可采納的比如 h max(h2, h4)。這種組合在論壇里常有人問“能不能用兩個(gè)啟發(fā)式同時(shí)跑”其實(shí)答案是肯定的實(shí)測擴(kuò)展節(jié)點(diǎn)往往比任何單一函數(shù)都少。后續(xù)如果想繼續(xù)深入可以考慮三個(gè)方向一是把八數(shù)碼擴(kuò)展到15數(shù)碼試試更強(qiáng)的模式數(shù)據(jù)庫啟發(fā)式二是改成雙向BFS或雙向A搜索讓搜索從目標(biāo)和起點(diǎn)兩頭同時(shí)逼近應(yīng)對更大狀態(tài)空間的效果非常明顯三是換用IDA迭代加深搜索把內(nèi)存占用降下來讓每個(gè)節(jié)點(diǎn)只存遞歸棧而不需要巨大的open表。每一種方向都會讓你對“搜索”的理解再深一層。這個(gè)玩具一樣的問題值得慢慢嚼。