<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # A Star Search - A\*搜索 -------- #### 問題 在$$ m \times n $$的二維方格圖$$ s $$中從$$ beg $$點移動到$$ end $$點。$$ s $$中存在一些黑色的方塊阻隔移動。 #### 解法 A\*算法是一種啟發式搜索（DFS和BFS屬于無差別搜索），通過函數$$ f(x) $$來評價節點$$ x $$的搜索代價（到目標的距離）。當存在多個待搜索節點時，總是優先搜索那些離目標更最近的點來提高搜索效率。  對于節點$$ x $$，函數$$ f(x) = g(x) + h(x) $$，其中$$ f(x) $$表示$$ x $$點到$$ end $$的估算/評價距離，$$ g(x) $$表示從$$ beg $$節點到$$ x $$節點需要移動的最短距離，$$ h(x) $$表示從$$ x $$點到$$ end $$節點的估算距離。 設置$$ open $$表和$$ close $$表，其中$$ open $$表類似BFS中的隊列，存放待搜索的節點$$ o $$；$$ close $$表存放所有已搜索過的節點$$ c $$，并存儲從$$ beg $$到達$$ c $$的最短距離$$ g(c) $$。 初始時將$$ beg $$推入$$ open $$和$$ close $$中，且$$ close[beg] = 0 $$，表示$$ beg $$到達自己的最短距離為$$ 1 $$。注意本算法中不會使用染色來標記某個節點是否已經被訪問，而是用$$ close $$表來記錄。 每次從$$ open $$取出節點$$ x $$，該節點滿足$$ f(x) $$在$$ open $$中是最小的（若存在多個相同的最小$$ f(x) $$則隨意選取其中一個即可），若$$ x = end $$則搜索結束；否則考慮將$$ x $$四周的節點$$ y $$加入$$ open $$表中，且顯然因為多走了一步有$$ g(y) = g(x) + 1 = close[x] + 1 $$。注意，若$$ close $$中已經存在$$ y $$節點，說明在此之前$$ y $$已經被搜索過，這時比較舊的$$ g(y)_{old} $$與當前新的$$ g(y)_{new} $$，顯然為了搜索最短路徑，若$$ g(y)_{old} > g(y)_{new} $$則用新路徑替換舊路徑，否則忽略節點$$ y $$不將其加入$$ open $$表。 當$$ open = \emptyset $$為空時，說明$$ beg $$永遠無法到達$$ end $$。 本問題中A\*搜索的時間復雜度為$$ O(n \times m) $$。 -------- #### 八數碼問題 * http://www.d.umn.edu/~jrichar4/8puz.html * https://www.cs.princeton.edu/courses/archive/fall12/cos226/assignments/8puzzle.html -------- #### 源碼 [AStarSearch.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/AStarSearch.h) [AStarSearch.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/AStarSearch.cpp) #### 測試 [AStarSearchTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/AStarSearchTest.cpp)