演算法知識 - Two way search 雙向搜尋

2020-12-14

字數統計： 318 | 閱讀時間≈ 1分鐘

Two way search 介紹

雙向搜尋主要是透過起點與終點都進都進行搜尋來獲得答案，主要是為了加快搜尋效率而產生的一種新觀念

下面將介紹兩種雙向搜尋演算法

雙向同時搜尋

Meet in the middle

基本作法是先透過起點端或終點端進行一次搜尋(BFS or DFS)，其中當起點在進行的搜尋與終點在進行的搜尋遇到時則表示找到答案解，在其必要時透過兩次搜尋，將沒有連接終點與起點的節點進行刪除(枝剪)。

Meet in the middle 沒有正式的中文名稱，常見名稱中間相遇法，此觀念適用在於輸入數據較小，但並沒有小到能夠直接 brute force 的情況時就適合用 Meet in the middle。

基本作法為將一張圖切成兩部分，分別進行搜尋，最後再將兩邊的結果合併，brute force 的時間複雜度通常為 \(O(N_n)\)，但透過 Meet in the middle 可以將時間複雜度降為 \(O(N^{n/2})\)，方便我們去嘗試 brute force。