<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Bidirectional Breadth Search - 雙向廣度搜索 -------- #### 問題 在二維方格圖$$ s = n \times m $$中用雙向廣度搜索從$$ beg $$點移動到$$ end $$點。 #### 解法 雙向廣度優先搜索是在廣度優先搜索基礎上的一個變種，搜索速度更快。該算法從$$ beg $$和$$ end $$兩個點開始，同時進行廣度優先搜索，兩邊的點在某一處相遇，即可得到一條從$$ beg $$到$$ end $$的路徑。 初始時將$$ beg $$和$$ end $$分別加入兩個隊列$$ bq $$和$$ eq $$中。每次分別從$$ bq $$和$$ eq $$隊列中取出節點$$ x $$和$$ y $$進行訪問，在節點加入$$ bq $$之前將其染成紅色，加入$$ eq $$之前其染成藍色。若$$ x $$取出后發現已被染成藍色，說明$$ x $$被$$ eq $$訪問過，或$$ y $$取出后發現其已被染成紅色，說明$$ y $$被$$ bq $$訪問過。說明兩個隊列在此處相遇，算法結束。 在二維方格$$ s = 5 \times 4 $$中，從$$ beg = [1,0] $$移動到$$ end = [4,3] $$的過程如下：  $$ (1) $$初始時，將$$ beg = [1,0] $$染紅并加入$$ bq $$中，將$$ end = [4,3] $$染藍并加入$$ eq $$；  $$ (2) $$從$$ bq $$中取出頭節點$$ [1,0] $$，將其四周未被染色的鄰節點$$ [0,0], [1,1], [2,0] $$染紅并加入$$ bq $$中。從$$ eq $$中取出頭節點$$ [4,3] $$，將其四周未被染色的鄰節點$$ [4,2], [3,3] $$染藍并加入$$ eq $$中；  $$ (3) $$從$$ bq $$中取出頭節點$$ [0,0] $$，將其四周未被染色的鄰節點$$ [0,1] $$染紅并加入$$ bq $$中。從$$ eq $$中取出頭節點$$ [4,2] $$，將其四周未被染色的鄰節點$$ [4,1], [3,2] $$染藍并加入$$ eq $$中； $$ \cdots $$  $$ (7) $$從$$ bq $$中取出頭節點$$ [2,1] $$，其鄰節點$$ [2,2], [1,3] $$已經被染藍（已經被$$ eq $$訪問過）。因此$$ [2,2], [1,3] $$為$$ bq $$和$$ eq $$相遇的位置，算法結束； 對于二維方格$$ s $$，廣度優先搜索從$$ beg $$點遍歷到$$ end $$點的過程一般是從$$ beg $$向四周發散開，一直到達$$ end $$點。而雙向廣度優先搜索則是從$$ beg $$和$$ end $$兩個點分別發散開，在中間相遇。  雙向廣度搜索的時間復雜度與廣度優先搜索一樣，也是$$ O(n \times m) $$。 -------- #### 源碼 [BidirectionalBreadthSearch.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/BidirectionalBreadthSearch.h) [BidirectionalBreadthSearch.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/BidirectionalBreadthSearch.cpp) #### 測試 [BidirectionalBreadthSearchTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/BidirectionalBreadthSearchTest.cpp)