雙向搜尋（Bidirectional Search）
先備知識
- 深度優先搜尋（DFS）
- A* 演算法 / 了解 heuristic 的意義
- 迭代加深（Iterative Deepening）的概念
雙向搜尋（Bidirectional Search）
不僅從起點往終點搜尋，也從終點往回起點搜尋。
# DFS(n1, n2, depth)：
# n1 為起點
# n2 為目標點之集合（目標是找到多個點其中之一）
# 從 n1 做 DFS，目標是找到 n2（n2可以是複數
# depth 為最大深度。
# 如果深度限制內找得到就回傳 True，否則回傳 False。
d = 1 # d 記錄當前 DFS 最大深度，為 iterative deepening 的概念
s = 起點
g = 終點
while True:
if DFS(n1=s, n2={g}, depth=d) is True:
return True # 找到
H = {儲存所有在深度為 d 的點}
if DFS(n1=g, n2=H, depth=d) is True:
return True # 倒著走的 DFS 找到路徑
if DFS(n1=g, n2=H, depth=d + 1) is True:
return True # 使用 d + 1 是要避免目深深度為奇偶數的問題
depth += 1
b = branching factor （每次分支展開的約略數量）
d = depth （深度）
使用 DFS 從上到下搜尋與從下到上搜尋的複雜度皆為 $O(b^{d/2})$。其實要用 BFS 也是可以的。
$O(b^{d/2}) + O(b^{d/2})=O(b^{d/2})$，整體的時間複雜度也是 $O(b^{d/2})$。
（g1, g2, g3 是要表現 goal state 不同的狀況下時間複雜度相同）
空間複雜度也是 $O(b^{d/2})$，因為要向下 DFS 要儲存節點讓向上 DFS 能檢查是否相交。
整理一下：
- 時間複雜度： $O(b^{d/2})$。
- 空間複雜度： $O(b^{d/2})$。
推廣至使用 Heuristic
上述是用每步代價相同的簡單搜尋來呈現雙向搜尋的效果，雙向搜尋當然也可以結合 heuristic，使用 IDA* 等方式。
指數空間複雜度如何解決？
由於記憶體空間有限，指數的空間複雜度是許多演算法的瓶頸。上述空間複雜度為 $O(b^{d/2})$ 是因為要記住向下 DFS 最大深度的節點們。如果改成不要存那些節點，在 DFS 遍歷時，當 DFS 到最大深度時就直接從做向上的 DFS。也就是說最大深度這層每個節點都會做一次向上 DFS，這樣就不用把這層的節點數量都存起來，空間複雜度變成 $O(bd)$，但時間複雜度會變大，整層 $O(b^{d/2})$ 個節點都做 $O(b^{d/2})$ 次的向上 DFS，時間複雜度變成 $O(b^{d})$。
用時間換取空間！
Reference
Wikipedia https://en.wikipedia.org/wiki/Bidirectional_search
Iterative Deepening Bidirectional Heuristic Search Algorithm: Shperberg, S. S., Danishevski, S., Felner, A., & Sturtevant, N. R. (2021). Iterative-deepening Bidirectional Heuristic Search with Restricted Memory. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 331-339. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/15978