簡介人工智能搜索技術(shù)是AI問題求解過程的核心本PDF資源系統(tǒng)梳理了搜索技術(shù)的關(guān)鍵知識點(diǎn)適合正在學(xué)習(xí)人工智能算法、準(zhǔn)備考研復(fù)試或進(jìn)行項(xiàng)目開發(fā)的技術(shù)人員參考。內(nèi)容從搜索技術(shù)概述切入明確問題求解即狀態(tài)空間中的搜索過程隨后詳解狀態(tài)圖建模方法通過農(nóng)夫過河等經(jīng)典案例展示狀態(tài)向量與合法操作變換在盲目搜索部分對比了寬度優(yōu)先與深度優(yōu)先策略的適用場景啟發(fā)式搜索及A算法、A*算法則重點(diǎn)講解估價(jià)函數(shù)f(n)g(n)h(n)的設(shè)計(jì)思路最后深入博弈搜索中的極小極大法與α-β剪枝法展示如何通過閾值剪枝大幅降低搜索空間。資源共1個(gè)PDF文件大小6.54MB篇幅緊湊但結(jié)構(gòu)清晰圖文與狀態(tài)圖示例相結(jié)合便于按章節(jié)自學(xué)或作為課程講義補(bǔ)充。已有498人學(xué)習(xí)下載適合希望通過實(shí)例快速理解搜索策略、掌握狀態(tài)空間表示與剪枝優(yōu)化的讀者。1. 人工智能搜索技術(shù)先分清“搜索”和“查找”很多人第一次接觸人工智能搜索技術(shù)以為它是類似數(shù)據(jù)庫里那種“輸入關(guān)鍵字、返回結(jié)果”的查找。實(shí)際完全兩回事搜索技術(shù)解決的是在狀態(tài)空間里找到一條從初始狀態(tài)到目標(biāo)狀態(tài)的動(dòng)作序列核心不是“查”而是“試”和“比較”。學(xué)這塊內(nèi)容最快的路線是先會(huì)用狀態(tài)空間把問題描述清楚再依次掌握盲目搜索、啟發(fā)式搜索最后把 A* 算法作為主線跑通幾個(gè)典型場景。這篇筆記就按這個(gè)順序展開適合正在學(xué)人工智能導(dǎo)論課程、或者要做迷宮尋路類大作業(yè)的讀者看完能直接照著實(shí)現(xiàn)也能知道參數(shù)調(diào)歪了到底哪里出錯(cuò)。2. 狀態(tài)空間建模把問題變成一張“可搜索的圖”2.1 狀態(tài)、動(dòng)作、代價(jià)在寫任何搜索算法之前第一步不是打開編輯器寫代碼而是把問題抽象成三個(gè)要素狀態(tài)state問題世界中的一個(gè)完整描述。迷宮里的一個(gè)格子坐標(biāo)是狀態(tài)八數(shù)碼里的一個(gè)棋盤排列也是狀態(tài)。動(dòng)作action從一個(gè)狀態(tài)到另一個(gè)狀態(tài)的合法轉(zhuǎn)移。迷宮里通常是上下左右四個(gè)方向。代價(jià)cost執(zhí)行動(dòng)作付出的開銷。可以是步數(shù)、時(shí)間、油耗。這三個(gè)要素合起來就是狀態(tài)空間圖。搜索算法本質(zhì)上是在這張圖上游走盲目搜索完全不看方向啟發(fā)式搜索則借助估價(jià)函數(shù)猜哪個(gè)方向更接近目標(biāo)。我一般會(huì)先做一件看起來很笨的事把狀態(tài)、動(dòng)作、代價(jià)用結(jié)構(gòu)體或類寫出來即使用不上太多繼承關(guān)系也會(huì)把動(dòng)作函數(shù)抽象出來。原因很簡單——后面換算法時(shí)只有狀態(tài)轉(zhuǎn)移接口固定住了BFS、DFS、A* 才能共用同一套圖描述。2.2 以迷宮為例子四鄰域建模的代碼實(shí)現(xiàn)四鄰域迷宮是搜索入門最常見的載體。假設(shè)迷宮是一個(gè)二維字符數(shù)組0表示可以走1表示墻壁入口在左上角出口在右下角移動(dòng)代價(jià)固定為 1。from collections import deque class MazeState: def __init__(self, x, y): self.x x self.y y def __eq__(self, other): return self.x other.x and self.y other.y def __hash__(self): return hash((self.x, self.y)) def __repr__(self): return f({self.x}, {self.y}) def get_neighbors(state, maze): 返回當(dāng)前狀態(tài)的所有合法鄰居狀態(tài)按上下左右的順序 rows, cols len(maze), len(maze[0]) neighbors [] for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: nx, ny state.x dx, state.y dy if 0 nx rows and 0 ny cols and maze[nx][ny] 0: neighbors.append(MazeState(nx, ny)) return neighbors這段代碼里有兩個(gè)細(xì)節(jié)值得注意。__hash__必須和__eq__一起定義否則把狀態(tài)放進(jìn)集合或者作為字典鍵時(shí)會(huì)出現(xiàn)“明明內(nèi)容相同卻當(dāng)成兩個(gè)對象”的情況get_neighbors的邊界判斷先做坐標(biāo)越界檢查再做墻壁檢查順序不能反過來因?yàn)閙aze[nx][ny]在下標(biāo)越界時(shí)會(huì)直接拋異常。塊的邏輯就這么簡單。真正的坑在于后面的算法實(shí)現(xiàn)往往會(huì)改壞這個(gè)接口比如忘記把起點(diǎn)放在已訪問集合里或者生成鄰居時(shí)沒有過濾掉父狀態(tài)。接口保持穩(wěn)定后面換算法時(shí)才不會(huì)越換越亂。2.3 為什么要先建圖再談算法很多人在學(xué)搜索技術(shù)時(shí)習(xí)慣直接背 A* 的代碼最后寫出來的程序其實(shí)是按照“地圖上有一條直路”這個(gè)假設(shè)寫的換個(gè)地圖就翻車。先把狀態(tài)空間拆清楚本質(zhì)上就是逼自己想明白“搜索是在什么圖上進(jìn)行的”。狀態(tài)空間圖有幾個(gè)關(guān)鍵屬性直接決定算法選型有限還是無限。無限狀態(tài)空間必須用能保證終止的算法。有向還是無向。迷宮里的移動(dòng)無向拼圖類問題的箭頭可能不可逆。單步代價(jià)是否一致。全部為 1 時(shí) BFS 就有最優(yōu)性代價(jià)不同就該上 Dijkstra 或 A*。這些屬性在一張圖上同時(shí)存在比如尋路時(shí)單位步長一致但地形有沼澤時(shí)移動(dòng)代價(jià)不同。這些后續(xù)需要計(jì)算性能都會(huì)回到狀態(tài)空間的建模是否準(zhǔn)確。3. 盲目搜索先會(huì)用“蠻力”再談效率3.1 BFS 與 DFS 的代碼對照盲目搜索里最常用的是寬度優(yōu)先搜索BFS和深度優(yōu)先搜索DFS兩者只差一個(gè)“接下來先擴(kuò)展誰”的策略。BFS 用隊(duì)列先進(jìn)先出DFS 用棧后進(jìn)先出。對照代碼最能看清差別def bfs_search(start, goal, maze): BFS用隊(duì)列逐層擴(kuò)張找最短路徑 frontier deque([start]) came_from {start: None} while frontier: current frontier.popleft() if current goal: return reconstruct_path(came_from, start, goal) for next_state in get_neighbors(current, maze): if next_state not in came_from: frontier.append(next_state) came_from[next_state] current return None def dfs_search(start, goal, maze): DFS用棧一頭扎到底不保證最短 frontier [start] came_from {start: None} while frontier: current frontier.pop() if current goal: return reconstruct_path(came_from, start, goal) for next_state in get_neighbors(current, maze): if next_state not in came_from: frontier.append(next_state) came_from[next_state] current return None兩份代碼的結(jié)構(gòu)完全一樣唯一的區(qū)別是popleft()和pop()。前者從隊(duì)頭取保證先擴(kuò)展先入隊(duì)的層后者從棧頂取一路往深走。關(guān)鍵都在came_from字典它記錄了每個(gè)狀態(tài)“從哪來”最后從終點(diǎn)倒著逆向還原路徑。這里容易出現(xiàn)的認(rèn)知偏差是以為 DFS 代碼和 BFS 只是改一行跑起來沒區(qū)別。實(shí)際上 DFS 在深迷宮里有棧溢出的風(fēng)險(xiǎn)而且第一次到達(dá)終點(diǎn)時(shí)的路徑不保證最短。盲目搜索是這樣一種思想除了“不要走回頭路”之外不做任何方向判斷。3.2 迭代加深與代價(jià)一致搜索BFS 最優(yōu)但有空間問題DFS 省內(nèi)存但不保證最優(yōu)。兩者的折中是迭代加深深度優(yōu)先搜索限制搜索深度從 1 開始逐次增加每次都從頭跑 DFS。深度限制以內(nèi)的 DFS 會(huì)完整探索該深度層因此首次找到目標(biāo)時(shí)一定是最短步數(shù)。迭代加深的代碼并不復(fù)雜核心在循環(huán)里逐層增加深度上限。def id_dfs_search(start, goal, maze, max_depth100): for depth in range(max_depth): result dfs_with_limit(start, goal, maze, depth) if result is not None: return result return None def dfs_with_limit(state, goal, maze, limit, came_fromNone): if came_from is None: came_from {state: None} if state goal: return reconstruct_path(came_from, state) if limit 0: return None for next_state in get_neighbors(state, maze): if next_state not in came_from: came_from[next_state] state result dfs_with_limit(next_state, goal, maze, limit - 1, came_from) if result is not None: return result del came_from[next_state] # 關(guān)鍵回溯時(shí)刪除記錄防止污染其他分支 return Nonedel came_from[next_state]是這段代碼的靈魂。沒刪的話一條分支探索過的節(jié)點(diǎn)會(huì)阻塞另一條分支的訪問導(dǎo)致漏解。迭代加深看起來重復(fù)執(zhí)行了大量冗余擴(kuò)展但大多數(shù)地圖上時(shí)間開銷依然可以接受空間開銷只有 O(深度) 的遞歸棧實(shí)用性很強(qiáng)。如果每一步代價(jià)不相同BFS 的最優(yōu)性就失效了需要換成 Dijkstra 算法。Dijkstra 用優(yōu)先隊(duì)列按累計(jì)代價(jià)擴(kuò)展首次到達(dá)終點(diǎn)的路徑就是最小代價(jià)路徑。盲目搜索到這里已經(jīng)接近天花板剩下的事要靠啟發(fā)信息來加速。3.3 盲目搜索的適用邊界盲目搜索并不是一種“應(yīng)該被淘汰”的方法。地圖規(guī)模小、分支少、步數(shù)少時(shí)BFS 的實(shí)現(xiàn)簡單、行為可預(yù)期錯(cuò)誤率遠(yuǎn)低于啟發(fā)式搜索。很多大作業(yè)場景里地圖是固定的幾十乘幾十BFS 在幾十毫秒內(nèi)就能解決根本沒必要上 A*。但搜索空間一旦變大就完全不行。一個(gè) 20x20 的開放網(wǎng)格四鄰域狀態(tài)下狀態(tài)數(shù)是 400最長路徑可能上百步分支因子按 4 算盲目搜索在最壞情況下會(huì)擴(kuò)展接近全部狀態(tài)。而 15 數(shù)碼這類狀態(tài)空間有萬億級別的排列數(shù)盲目搜索直接不可用。算法數(shù)據(jù)結(jié)構(gòu)最優(yōu)性空間復(fù)雜度適用場景BFS隊(duì)列步數(shù)最短等代價(jià)圖O(b^d)小地圖、等代價(jià)DFS棧不保證O(d)大空間找任意解迭代加深遞歸棧步數(shù)最短等代價(jià)圖O(d)折中方案Dijkstra優(yōu)先隊(duì)列總代價(jià)最小O(b^d)不等代價(jià)圖盲目搜索的結(jié)論是不要指望一種搜索方法通吃所有場景。盲目搜索的價(jià)值是給啟發(fā)式搜索提供對比基線只有當(dāng)你能說出“BFS 在這里擴(kuò)展了多少節(jié)點(diǎn)、A* 在這里擴(kuò)展了多少節(jié)點(diǎn)”時(shí)才能真正體會(huì)啟發(fā)函數(shù)的意義。4. 啟發(fā)式搜索與 A* 算法從“會(huì)找到解”到“找到好解”4.1 啟發(fā)函數(shù)為什么有用盲目搜索不知道目標(biāo)在哪只能按固定順序擴(kuò)展。啟發(fā)式搜索的思路是給當(dāng)前節(jié)點(diǎn)打分優(yōu)先擴(kuò)展“看起來更接近目標(biāo)”的節(jié)點(diǎn)。這個(gè)“看起來”就是用啟發(fā)函數(shù)h(n)計(jì)算出來的估價(jià)值。迷宮里的曼哈頓距離是一個(gè)最直觀的啟發(fā)函數(shù)h(n) |x_n - x_goal| |y_n - y_goal|它計(jì)算當(dāng)前格子到終點(diǎn)在網(wǎng)格上橫向加縱向的格子數(shù)。注意曼哈頓距離不考慮墻壁阻擋因此它不會(huì)高估真實(shí)代價(jià)。啟發(fā)函數(shù)不高估真實(shí)代價(jià)稱為“可采納的”這是啟發(fā)式搜索保證最優(yōu)性的前提。4.2 A 算法與 A* 算法的區(qū)別很多教材把 A 算法和 A* 算法放在相鄰小節(jié)里講初學(xué)者容易混為一談。兩者的關(guān)系很簡單A 算法指“使用估價(jià)函數(shù) f(n) g(n) h(n) 的通用搜索框架”其中 g(n) 是從起點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)A* 算法是 A 算法在 h(n) 可采納且一致時(shí)的一個(gè)特例這時(shí)候能找到全局最優(yōu)解。換句話說只要用了 f g h 的搜索方式都可以叫 A 算法。但只有當(dāng)啟發(fā)函數(shù)滿足可采納性不會(huì)高估真實(shí)代價(jià)時(shí)才有資格叫 A*。這個(gè)區(qū)別直接對應(yīng)一個(gè)工程問題有人把啟發(fā)函數(shù)寫成了“非法高估”的形式比如迷宮里的歐氏距離乘以 1.2結(jié)果跑得很快但路徑明顯繞遠(yuǎn)。這時(shí)程序跑出來的東西嚴(yán)格說只是 A 算法的結(jié)果不是 A* 的。4.3 A* 算法的 Python 實(shí)現(xiàn)與參數(shù)說明給出一份可以抄作業(yè)的 A* 實(shí)現(xiàn)處理迷宮最短路徑。import heapq def a_star_search(start, goal, maze, heuristicNone): A* 搜索返回從 start 到 goal 的最短路徑狀態(tài)列表 if heuristic is None: # 默認(rèn)曼哈頓距離只適合四鄰域移動(dòng)代價(jià)為1的地圖 heuristic lambda a, b: abs(a.x - b.x) abs(a.y - b.y) open_heap [] # 堆里存 (f, g, counter, state)counter 避免 f 相同時(shí)比較狀態(tài)對象 counter 0 heapq.heappush(open_heap, (heuristic(start, goal), 0, counter, start)) came_from {start: None} g_score {start: 0} while open_heap: _, current_g, _, current heapq.heappop(open_heap) if current goal: return reconstruct_path(came_from, start, goal) for next_state in get_neighbors(current, maze): tentative_g current_g 1 # 迷宮單步代價(jià)固定為1 if tentative_g g_score.get(next_state, float(inf)): came_from[next_state] current g_score[next_state] tentative_g f tentative_g heuristic(next_state, goal) counter 1 heapq.heappush(open_heap, (f, tentative_g, counter, next_state)) return None代碼里三個(gè)參數(shù)最要命逐個(gè)展開說。open_heap里存的是四元組(f, g, counter, state)。只存(f, g, state)的話堆比較時(shí) f 相同比 gg 也相同就可能去比較 state 對象而MazeState沒有定義__lt__直接報(bào)TypeError。加一個(gè)遞增的counter就是為了打破平局保證比較永遠(yuǎn)能分出先后。第二個(gè)關(guān)鍵是tentative_g g_score.get(...)這個(gè)判斷。它并不檢查 next_state 是否已經(jīng)在閉集合或堆里而是看“這條路徑的 g 值是否比已知的更小”。更小就更新并重新入堆。這就是 A* 處理重復(fù)狀態(tài)的方式簡單且正確。第三個(gè)容易被忽略的點(diǎn)是堆里彈出的節(jié)點(diǎn)可能不是最新 g 值對應(yīng)的節(jié)點(diǎn)。代碼中彈出的current_g直接用于計(jì)算下一步的代價(jià)所以入堆時(shí)必須保證 g 值是當(dāng)時(shí)計(jì)算出的準(zhǔn)確值。上面代碼里采用了“每次更新都重新評估所有鄰居”的策略用current_g而不是g_score[current]正是為了處理這一情況。參數(shù)方面heuristic可以替換為任何滿足條件的函數(shù)。換成歐氏距離也能跑但最優(yōu)性要重新驗(yàn)證換成更大的值如h * 1.5跑得過快但路徑不是最優(yōu)。4.4 啟發(fā)函數(shù)選擇與一致性條件在工程里選啟發(fā)函數(shù)時(shí)有兩個(gè)層面的要求要區(qū)分開可采納性保證最優(yōu)但光可采納還不夠快一致性或稱單調(diào)性讓每個(gè)節(jié)點(diǎn)第一次被擴(kuò)展時(shí) g 值就已經(jīng)最優(yōu)避免不必要的重復(fù)擴(kuò)展。一致性的定義是對任意狀態(tài) n 及其后繼 n滿足h(n) cost(n, n) h(n)這有點(diǎn)像三角不等式。滿足一致性時(shí)A* 的行為更高效不需要維護(hù)復(fù)雜的重新打開邏輯。曼哈頓距離在四鄰域等代價(jià)圖上滿足一致性所以上面實(shí)現(xiàn)對每個(gè)狀態(tài)最多只會(huì)重新入堆有限次。如果地圖帶權(quán)重、對角線移動(dòng)成本不同曼哈頓距離的一致性會(huì)被打破。這時(shí)常見的做法是改用“對角線距離”或“八方向切比雪夫距離”同時(shí)把移動(dòng)代價(jià)設(shè)成對應(yīng)的代價(jià)函數(shù)。啟發(fā)函數(shù)必須和動(dòng)作代價(jià)配套否則一致性失效A* 的路徑可能悄悄變差。實(shí)戰(zhàn)建議先用一個(gè) 10x10 的無障礙地圖手動(dòng)算一遍 A* 的 f、g、h 值確認(rèn)代碼輸出的擴(kuò)展順序和自己的手算一致再換復(fù)雜地圖。5. 避坑A* 搜索的經(jīng)典常見問題與排查5.1 啟發(fā)函數(shù)高估導(dǎo)致結(jié)果不是最優(yōu)現(xiàn)象算法能很快跑完輸出路徑看起來也合理但手工數(shù)一下步數(shù)發(fā)現(xiàn)比實(shí)際最短路徑多出幾步。原因啟發(fā)函數(shù)出現(xiàn)了高估破壞了 A* 的可采納性。常見高估場景是用了歐氏距離卻讓移動(dòng)代價(jià)為 1、橫向縱向步進(jìn)歐氏距離在純網(wǎng)格里往往小于真實(shí)距離這不會(huì)高估但如果地圖有對角線移動(dòng)且對角線被簡化成“先橫再豎”的路徑啟發(fā)式估價(jià)就可能超過真實(shí)代價(jià)。解決逐條檢查啟發(fā)函數(shù)與代價(jià)函數(shù)是否匹配。最穩(wěn)妥的做法是單步代價(jià)為 1、四鄰域用曼哈頓距離允許斜走且斜走代價(jià)為 2、直走代價(jià)為 1可以用對角線距離公式。想快速驗(yàn)證寫一個(gè)小腳本隨機(jī)生成幾十張地圖把 A* 結(jié)果和 BFS 結(jié)果對比不一致就是啟發(fā)函數(shù)出問題。5.2 重復(fù)入堆、g 值更新錯(cuò)誤導(dǎo)致搜索“翻車”現(xiàn)象搜索明明已經(jīng)找到終點(diǎn)但路徑不是最短或者程序瘋狂占用內(nèi)存擴(kuò)展節(jié)點(diǎn)數(shù)量離譜。原因常見寫法是開一個(gè)closed_set把彈出的節(jié)點(diǎn)放進(jìn)去當(dāng)鄰居已經(jīng)在 closed_set 里就直接跳過。這種做法省內(nèi)存但如果第一次彈出的路徑不是最優(yōu)的后面發(fā)現(xiàn)了更短的 g 值卻因?yàn)椤耙殃P(guān)閉”而無法更新最優(yōu)性就丟了。解決不用 closed_set改用 g 值比較如上節(jié)代碼所示。核心邏輯只有一句“只有當(dāng)新路徑的 g 值更小時(shí)才更新?！边@個(gè)模式同時(shí)適用于 Dijkstra 和 A*。注意代碼里current_g的取值。如果從堆里彈出的 g 值已經(jīng)過時(shí)有更新的更小 g 值沒有被重新壓入堆用它去推算鄰居的 tentative_g 會(huì)出錯(cuò)。常見做法是彈出的current_g g_score[current]才繼續(xù)處理不滿足就跳過if current_g g_score.get(current, float(inf)): # 過期節(jié)點(diǎn)直接跳過 continue這行代碼能攔截大量重復(fù)處理建議加上。這是 A* 性能調(diào)優(yōu)中最立竿見影的幾行之一。5.3 鄰域與移動(dòng)代價(jià)不匹配導(dǎo)致路徑失真現(xiàn)象地圖允許斜走輸出路徑看起來“能通行”卻穿過了墻角或者明明斜走更短卻選擇了橫豎折線。原因斜向移動(dòng)時(shí)鄰域從 4 個(gè)變成了 8 個(gè)但代碼里get_neighbors更新了方向列表heuristic卻仍然用曼哈頓距離。由于斜走一步的直線距離比橫豎一步短但代價(jià)幾何沒配對啟發(fā)函數(shù)低估了代價(jià)破壞了搜索的優(yōu)先級判斷。解決把斜向移動(dòng)和代價(jià)綁定。常見做法是橫豎移動(dòng)代價(jià)為 1斜向移動(dòng)代價(jià)為約 1.414啟發(fā)函數(shù)用“切比雪夫距離或按八方向代價(jià)計(jì)算”也就是h(n) max(|dx|, |dy|) (sqrt(2) - 1) * min(|dx|, |dy|)用浮點(diǎn)代價(jià)時(shí)注意比較tentative_g 1.0不要直接做浮點(diǎn)相等比較用比較即可。更穩(wěn)妥的是所有代價(jià)用整數(shù)表示比如橫豎為 10、斜向?yàn)?14既能保持距離比例又避免浮點(diǎn)誤差。5.4 啟發(fā)函數(shù)設(shè)成 0A* 退化成 Dijkstra現(xiàn)象A* 代碼跑得奇慢無比擴(kuò)展節(jié)點(diǎn)數(shù)基本等于全圖節(jié)點(diǎn)數(shù)但路徑質(zhì)量完全正確。原因啟發(fā)函數(shù)直接return 0此時(shí) f gA* 的擴(kuò)展順序和 Dijkstra 一模一樣完全沒有利用目標(biāo)位置信息。很多人在調(diào)試時(shí)圖省事把 h 設(shè)成 0再也沒有改回來。解決在代碼入口處加一個(gè)斷言確保 h 不為全 0# 調(diào)試用如果 h 恒為 0立刻報(bào)警 assert any(heuristic(s, goal) 0 for s in [start]), 啟發(fā)函數(shù)疑似恒為0這種斷言平時(shí)不觸發(fā)但能攔住調(diào)試后的“忘記恢復(fù)”失誤。它也提醒一個(gè)道理A* 的性能完全系在啟發(fā)函數(shù)上h 越接近真實(shí)代價(jià)擴(kuò)展節(jié)點(diǎn)越少。5.5 堆里塞滿路徑導(dǎo)致內(nèi)存爆炸現(xiàn)象大迷宮跑 A*內(nèi)存占用飆升有時(shí)候是幾 GB程序直接被殺掉。原因最典型的寫法是把“完整路徑”直接存進(jìn)堆里的每個(gè)節(jié)點(diǎn)結(jié)果每個(gè)狀態(tài)攜帶一份長度可能幾百的列表內(nèi)存從 O(n) 膨脹成了 O(n*d)。這是新手常見的玄學(xué)翻車點(diǎn)。解決堆里只存狀態(tài)和代價(jià)值路徑統(tǒng)一通過came_from字典在終點(diǎn)處回溯。上面的核心實(shí)現(xiàn)已經(jīng)是這個(gè)模式。如果確實(shí)需要診斷路徑最多只在找到終點(diǎn)后調(diào)用reconstruct_path構(gòu)造一次。排查技巧在循環(huán)里每擴(kuò)展 10000 個(gè)節(jié)點(diǎn)打印一次堆大小和 g_score 字典長度觀察增長速度。正常情況下 g_score 增長接近線性如果堆大小持續(xù)數(shù)倍于狀態(tài)數(shù)且不下降很可能出現(xiàn)了重復(fù)入堆過多的狀況回到 5.2 的過期節(jié)點(diǎn)策略去排查。這些踩坑記錄里5.1 和 5.2 專門針對最優(yōu)性5.3 和 5.5 針對路徑質(zhì)量和資源開銷5.4 是性能問題。實(shí)際調(diào)代碼時(shí)按“先確認(rèn)路徑正確再確認(rèn)內(nèi)存合理最后確認(rèn)速度”的順序排查。6. 驗(yàn)證方法與進(jìn)階優(yōu)化把 A* 調(diào)到一個(gè)工程能用的狀態(tài)6.1 小圖手算驗(yàn)證的正確姿勢A* 實(shí)現(xiàn)完不驗(yàn)證就直接上大圖是自找苦吃。先拿一張 5x5 無障礙地圖起點(diǎn)在左下、終點(diǎn)在右上手工列出每次從堆里彈出的節(jié)點(diǎn)、對應(yīng)的 f/g/h 三個(gè)值再和代碼輸出逐行對比。如果第一行就不一致優(yōu)先檢查堆的排序規(guī)則和方向遍歷順序。如果彈出順序一致但路徑不一致檢查 g 值更新邏輯和came_from記錄的時(shí)間點(diǎn)。這類驗(yàn)證題在搜索引擎里搜“A* 算法原理圖”能找到大量手算例子挑一個(gè)節(jié)點(diǎn)數(shù)不超過 10 的圖按上面的方式走一遍10 分鐘內(nèi)能把 A* 的編碼錯(cuò)誤排掉大半。6.2 進(jìn)階權(quán)重 A* 與雙向搜索A* 跑通之后還有兩個(gè)簡單的工程級優(yōu)化值得嘗試。權(quán)重 A* 的核心是把估價(jià)函數(shù)改成 f g w * h其中 w 大于 1。它強(qiáng)烈偏向啟發(fā)方向擴(kuò)展搜索速度大幅提升代價(jià)是路徑不再是嚴(yán)格最優(yōu)但很多游戲?qū)ぢ穲鼍袄铩敖咏顑?yōu)且速度快”遠(yuǎn)比“絕對最優(yōu)但慢”更有價(jià)值。調(diào)整時(shí)觀察不同 w 值下的路徑長度與擴(kuò)展節(jié)點(diǎn)數(shù)的關(guān)系就能找到可以接受的折中。雙向搜索的思路是同時(shí)從起點(diǎn)和終點(diǎn)做 A*兩個(gè)方向交替擴(kuò)展相遇時(shí)拼接路徑。在起終點(diǎn)距離遠(yuǎn)的大地圖上雙向搜索通常比單向 A* 減少大量擴(kuò)展節(jié)點(diǎn)。要注意兩邊的啟發(fā)函數(shù)需要改成“到對方起點(diǎn)的距離”才能保持一致性。這些優(yōu)化都屬于“把 A* 調(diào)到一個(gè)工程能用的狀態(tài)”的具體手段每一類都值得單獨(dú)拿一張地圖做實(shí)驗(yàn)對比數(shù)據(jù)。說回到整體心得。搜索技術(shù)這條學(xué)習(xí)鏈上最容易辜負(fù)人的就是“以為自己懂 A* 了”會(huì)背公式容易能說清楚為什么h必須不高估、為什么closed_set不能單純關(guān)閉、為什么堆比較要加 counter 才算入門。我自己的習(xí)慣是每寫一個(gè)搜索算法都配一個(gè) 5x5 的手算測試和一張隨機(jī)地圖回歸測試前者保證邏輯對后者保證實(shí)現(xiàn)穩(wěn)。這套方法踩過無數(shù)坑之后依然可靠希望能幫到正卡在某一步的你。本文還有配套的精品資源點(diǎn)擊獲取