思考(9)圖搜索演算法-BFS,DFS,Best First Search,A* and Dijkstras

思考(9)圖搜索演算法-BFS,DFS,Best First Search,A* and Dijkstras. 雪花台灣 2019-07-14 01:56. 本文參考了斯坦福大學兩位博士生Steve Mussmann和Abigail See寫 ... 思考(9)圖搜索演算法-BFS,DFS,BestFirstSearch,A*andDijkstras 雪花台灣 2019-07-1401:56 本文參考了斯坦福大學兩位博士生SteveMussmann和AbigailSee寫的tutorial。

如有錯誤疏漏，煩請指出。

如需轉載，請聯繫筆者，[email protected]。

Theshortestpathproblem 假設機器人的sourcenode在下圖中的五角星??處，targetnode在下圖中的畫叉?處，同時還有綠色的障礙物-牆。

那麼如何找到從起點到終點的最短路徑，同時避開障礙物？ 兩個問題要解決。

一是如何表達這個有障礙物的地圖？二是，如何找到最短路徑？首先我們把圖表達成graph，每個cell的中心就是graph中的一個node，如下圖所示 BreadthFirstandDepthFirst GraphSearchAlgorithms就是從sourcenode開始，keepsearching，直到到達targetnode為止。

Frontier是指那些已經看見但是還沒有訪問的nodes。

每個iteration，我們從frontier取一個新的node進行訪問，並且將該node的鄰居又加入到frontier。

BreadthFirstSearch(BFS)和DepthFirstSearch(DFS)最最基本的兩個GraphSearchAlgorithms。

他倆的不同就在於，從frontier的那些nodes中，按照什麼順序來visit，主要區別如下圖所示： 從上圖中可以看出，BFS是，在當前的frontier的所有node中，誰先進的frontier，就先訪問誰，即FirstInFirstOut(FIFO)。

具體可以看一下的動圖，1號cell最先進入frontier，最先訪問，然後依次2345678...... DFS是，在當前frontier的所有nodes中，誰最後進的frontier，就先訪問誰，即LastInFirstOut(LIFO)。

具體可以看一下的動圖。

最開始frontier有四個nodes，最先訪問4號cell(因為4號是1stiteration的frontier里最後加入的)，接著訪問7號(因為7號是2nditeration的frontier里最後加入的)，依次9、11、13...... 顯然我們可以利用BFS或者DFS，從起點出發，按照BFS或者DFS進行visit，直到到達終點後停止，然後把追溯到達終點的parentnode的鏈條弄好就可以。

BestFirstSearch 顯然BFS和DFS在搜索的時候，並沒有利用終點在哪裡這個信息而去選擇某些離終點近的node去優先visit。

BFS和DFS只按部就班，一個是FIFO，一個LIFO，所以導致到達終點的速度不是很快。

那麼於是就有了貪婪的BestFirstSearch(Itsagreedyalgorithm:agreedyalgorithmisonethatchoosesthebest-lookingoptionateachstep)。

BestFirstSearch在每一步，都在frontier中選擇那個離target最近的node去第一個visit。

我們把這種按照某種metric選擇bestnode去優先visit，叫做heuristic。

Aheuristicguidesyouintherightdirectionandisanapproximatemeasureofhowcloseyouaretothetarget。

總結一下，從計算機專業的數據結構的角度看: BreadthFirstSearchoperatelikeaQueue. DepthFirstSearchoperatelikeaStack. BestFirstSearchoperateslikeaPriorityQueue. HeuristicsforgreedyBestFirstSearch 顯然我們可以選擇不同heuristic，來估計到目標終點的距離。

Heuristic能滿足以下要求： aheuristicshouldbeaapproximatemeasureofhowclosewearetothetarget. Aheuristicshouldbeeasytocompute. 例如我們可以按照Euclideandistance或者Manhattandistance這兩種metrics的任意一個來作為我們的heuristic，但是我們要注意，這些metrics只是對trueshortestpath的近似，因為他們沒有考慮constraints，例如下圖中因為牆的存在，我們用Manhattandistance作為heuristic，那麼灰綠色的線的長度是heuristic，而trueshortestpath是紫色的線： 對比BreadthFirstSearch與BestFirstSearch 顯然BFS是最優路徑(最短)，但是因為BFS按部就班依照FIFO原則對frontier中的nodes進行訪問，所以到達目標終點的速度慢。

而貪婪的BestFirstSearch返回的通常不是最優的，但是到達目標終點的速度快。

如下所示的動圖，最後左圖和右圖中生成的紅紫色的線就是BFS和貪婪的BestFirstSearch分別返回的路徑： A*search BreadthFirstSearch和BestFirstSearch各有優點，那麼我們能否結合兩者的優點，設計一個新的演算法呢？答案就是著名的A*（Astar,1968年由斯坦福的三位學者發明，用來給robot在有障礙物的房間進行路徑規劃）。

A*的特點就是： LikeBreadthFirstSearch,A*findstheshortestpath(當theheuristicfunctionisbothadmissibleandmonotonic，具體請見wikipedia) LikeBestFirstSearch,A*isfast. LikeBestFirstSearch,A*operateslikeaPriorityQueue，butwithadifferentlydefinedpriority. A*search的做法，不同於BreadthFirstSearch優先從frontier中選擇對離sourcenode最近的所有node進行訪問，也不同於貪婪的BestFirstSearch，優先從frontier中選擇對離目標終點的heuristic最小的node進行訪問；而是每一步，優先從frontier中選擇對stepsfromsource+heuristic之和最小的node進行訪問，如下圖所示： 如下所示的動圖，最後左、中、右圖中生成的紅紫色的線就是BreadthFirstSearch、BestFirstSearch、A*分別返回的路徑。

AlgorithmsforWeightedGraphs前面動圖中介紹的例子，每一步的距離都是相同的。

那麼如果不同edge的cost不相等呢？於是就有了著名的DijkstrasAlgorithm。

BreadthFirstSearch與DijkstrasAlgorithm的聯繫如下： DijkstrasAlgorithmislikeBreadthFirstSearchwithweightedgraph.所以當eachedge的cost是一樣的，Dijkstra『s=BreadthFirstSearch! BreadthFirstSearch從frontier中按照FIFO規則來visit，DijkstrasAlgorithm按照依據離sourcenode的cost遞增的順序依次進行visit。

BestFirstSearch與DijkstrasAlgorithm的聯繫如下： Dijkstra』salgorithm跟BestFirstSearch一樣，也是按照priorityqueue來進行。

與BestFirstSearch不同的就是，BestFirstSearch是按照到達targetnode的cost，從小到大依次visit。

Dijkstra』salgorithm是按照距離sourcenode的cost，從小到大依次visit。

那麼WeightedGraph版的A*，把之前的steps換成cost，如下圖所示： 大總結：Searchalgorithmsforunweightedandweightedgraphs 推薦閱讀： 相关文章 {{article.title}} 为你推荐 無人車運動規劃的52篇文章 2年前 我自己寫了一個神經網路參數的搜索演算法，請問有發表價值嗎？ 1年前 二分查找中mid值的計算方法 2年前 怎麼用最短時間學習很多知識? 1年前 Johonson演算法 2年前 Floyd演算法 2年前 Bellman-ford演算法 2年前 dijkstra演算法 2年前 路徑規劃A*演算法 2年前 如何生成可行駛路徑 2年前 關於軌跡規劃框架開源 2年前 什麼是軌跡規劃 2年前 ortools系列：丟失部分節點的VRP問題 2年前 ortools系列：容量約束VRP問題 2年前 【交通+AI】結合路徑規劃和視覺控制的機器人導航 2年前 热门新闻 周热门 Copyright©2017雪花新闻Powered by  xuehua