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