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