思考(9)圖搜索演算法-BFS,DFS,Best First Search,A* and Dijkstras
本文參考了斯坦福大學兩位博士生Steve Mussmann和Abigail See寫的tutorial。如有錯誤疏漏，煩請指出。如需轉載，請聯繫筆者，[email protected]。
The shortest path problem
假設機器人的source node在下圖中的五角星??處，target node在下圖中的畫叉?處，同時還有綠色的障礙物-牆。那麼如何找到從起點到終點的最短路徑，同時避開障礙物？
兩個問題要解決。一是如何表達這個有障礙物的地圖？二是，如何找到最短路徑？首先我們把圖表達成graph，每個cell的中心就是graph中的一個node，如下圖所示
Breadth First and Depth First
Graph Search Algorithms就是從source node開始，keep searching，直到到達target node為止。Frontier是指那些已經看見但是還沒有訪問的nodes。每個iteration，我們從frontier取一個新的node進行訪問，並且將該node的鄰居又加入到frontier。
Breadth First Search(BFS)和Depth First Search(DFS)最最基本的兩個Graph Search Algorithms。他倆的不同就在於，從frontier的那些nodes中，按照什麼順序來visit，主要區別如下圖所示：
從上圖中可以看出，BFS是，在當前的frontier的所有node中，誰先進的frontier，就先訪問誰，即First In First Out(FIFO)。具體可以看一下的動圖，1號cell最先進入frontier，最先訪問，然後依次2345678......
DFS是，在當前frontier的所有nodes中，誰最後進的frontier，就先訪問誰，即Last In First Out(LIFO)。具體可以看一下的動圖。最開始frontier有四個nodes，最先訪問4號cell(因為4號是1st iteration的frontier裏最後加入的)，接著訪問7號(因為7號是2nd iteration的frontier裏最後加入的)，依次9、11、13......
顯然我們可以利用BFS或者DFS，從起點出發，按照BFS或者DFS進行visit，直到到達終點後停止，然後把追溯到達終點的parent node的鏈條弄好就可以。
Best First Search
顯然BFS和DFS在搜索的時候，並沒有利用終點在哪裡這個信息而去選擇某些離終點近的node去優先visit。BFS和DFS只按部就班，一個是FIFO，一個LIFO，所以導致到達終點的速度不是很快。那麼於是就有了貪婪的Best First Search(Its a greedy algorithm: a greedy algorithm is one that chooses the best-looking option at each step)。Best First Search在每一步，都在frontier中選擇那個離target最近的node去第一個visit。我們把這種按照某種metric選擇best node去優先visit，叫做heuristic。A heuristic guides you in the right direction and is an approximate measure of how close you are to the target。
總結一下，從計算機專業的數據結構的角度看:
- Breadth First Search operate like a Queue.
- Depth First Search operate like a Stack.
- Best First Search operates like a Priority Queue.
Heuristics for greedy Best First Search
顯然我們可以選擇不同heuristic，來估計到目標終點的距離。Heuristic能滿足以下要求：
- a heuristic should be a approximate measure of how close we are to the target.
- A heuristic should be easy to compute.
例如我們可以按照Euclidean distance或者Manhattan distance這兩種metrics的任意一個來作為我們的heuristic，但是我們要注意，這些metrics只是對true shortest path的近似，因為他們沒有考慮constraints，例如下圖中因為牆的存在，我們用Manhattan distance作為heuristic，那麼灰綠色的線的長度是heuristic，而true shortest path是紫色的線：
對比Breadth First Search與Best First Search
顯然BFS是最優路徑(最短)，但是因為BFS按部就班依照FIFO原則對frontier中的nodes進行訪問，所以到達目標終點的速度慢。而貪婪的Best First Search返回的通常不是最優的，但是到達目標終點的速度快。如下所示的動圖，最後左圖和右圖中生成的紅紫色的線就是BFS和貪婪的Best First Search分別返回的路徑：
A* search
Breadth First Search和Best First Search各有優點，那麼我們能否結合兩者的優點，設計一個新的演算法呢？答案就是著名的A*（A star, 1968年由斯坦福的三位學者發明，用來給robot在有障礙物的房間進行路徑規劃）。A*的特點就是：
- Like Breadth First Search, A* finds the shortest path(當the heuristic function is both admissible and monotonic，具體請見wikipedia)
- Like Best First Search, A* is fast.
- Like Best First Search, A* operates like a Priority Queue，but with a differently defined priority.
A* search的做法，不同於Breadth First Search優先從frontier中選擇對離source node最近的所有node進行訪問，也不同於貪婪的Best First Search，優先從frontier中選擇對離目標終點的heuristic最小的node進行訪問；而是每一步，優先從frontier中選擇對steps from source+heuristic之和最小的node進行訪問，如下圖所示：
如下所示的動圖，最後左、中、右圖中生成的紅紫色的線就是Breadth First Search、Best First Search、A*分別返回的路徑。
Algorithms for Weighted Graphs
前面動圖中介紹的例子，每一步的距離都是相同的。那麼如果不同edge的cost不相等呢？於是就有了著名的Dijkstras Algorithm。Breadth First Search 與Dijkstras Algorithm的聯繫如下：
- Dijkstras Algorithm is like Breadth First Search with weighted graph. 所以當each edge的cost是一樣的，Dijkstra『s = Breadth First Search!
- Breadth First Search從frontier中按照FIFO規則來visit，Dijkstras Algorithm按照依據離source node的cost遞增的順序依次進行visit。
Best First Search 與Dijkstras Algorithm的聯繫如下：
- Dijkstra』s algorithm跟Best First Search一樣，也是按照priority queue來進行。與Best First Search不同的就是，Best First Search是按照到達target node的cost，從小到大依次visit。Dijkstra』s algorithm是按照距離source node的cost，從小到大依次visit。
那麼Weighted Graph版的A*，把之前的steps換成cost，如下圖所示：
大總結：Search algorithms for unweighted and weighted graphs
推薦閱讀：
