人工智慧/搜尋/啟發式搜尋/雙向搜尋
雙向搜尋是一種演算法，它使用兩個同時發生的搜尋來到達目標目標。雙向搜尋通常被認為是一種有效的圖搜尋，因為它不是在大型樹中搜索，而是從目標開始進行反向搜尋，從起點開始進行正向搜尋。這樣做的原因是樹木會隨著其深度的增加而呈指數增長，因此兩棵較小的樹的面積比一棵大的樹要小。一旦兩個搜尋都完成，它們將在中間交叉以完成路徑。搜尋相遇之前的部分稱為主階段，而交叉之後的部分稱為後處理階段。重要的是要注意，大多數雙向搜尋使用啟發式方法，這意味著無法確認找到的解決方案是否是最優解決方案。
圖搜尋演算法會系統地遍歷圖中的節點，直到找到最優解，而啟發式搜尋只會在短時間內確認某種解決方案。雙向搜尋的路徑通常基於幾種不同的其他搜尋型別，包括
- 廣度優先：每次使用樹結構檢查目標節點時，將節點新增到列表中，直到找到目標節點
- 最佳優先：將使用節點的評分（通常是 f 值）來選擇下一個節點，該評分會考慮其成本和長度
- A*：類似於最佳優先，但會考慮從起點到指定節點的路徑成本以及從該節點到目標的成本
路線圖
最有效的路線圖搜尋將是雙向搜尋與 A* 演算法的結合。
- posA(x, y, f) 和 posB (x, y, f)
- 建立一個位置來演示你在兩棵搜尋樹中的當前位置，它將具有一個 x 座標、一個 y 座標和一個 f 值來解釋路徑的成本。
- startPoint (coordX, coordY)
- 從起點節點開始，並帶有進一步行進的選項：還提供座標列表，其中節點演示了朝向目標交點的移動選項。
- endPoint (coordX, coordY)
- 從一個結束位置（節點）開始，它有幾個通往它的選項 -
還提供座標列表，其中節點演示了朝向起始交點的移動選項。
- if posA= posB(x, y)
- 這意味著交叉點，因此結束搜尋。
- else 從 startPoint 將 posA 移動到具有最小 f 值的下一個節點，並將 posB 從 endPoint 移動到具有最小 f 值的下一個節點，直到兩個點交叉。
註釋
- 綠色節點顯示應採取的路徑，紅色節點顯示希望的交叉點。
- 更粗的線顯示更高的成本，虛線顯示 posA 運動和 posB 運動之間的分隔線。
- f-valueA 將考慮從 startPoint 到 posA 的成本以及從 posA 到 posB 的成本。
- f-valueB 將考慮從 endPoint 到 posB 的成本以及從 posB 到 posA 的成本。
1- 需要有關目標狀態的具體資訊。
2- 當有多個選項時，很難保證交叉點。
3- 計算儲存。
雖然雙向搜尋似乎是最快的搜尋選項之一，但在很多情況下它並不實用。例如，如果你正在尋找一個丟失的物品，你無法從你的位置開始搜尋，也無法從物品所在的位置開始搜尋，因為你不知道它的位置。上面的示例中，如果要從一個地址到達另一個已知位置，則可以使用雙向搜尋設計。一個可以使用的場景如上面示例所示。
Des Champeaux (1983) 建立了一種演算法來克服交叉點問題。該解決方案基本上是進行兩次從前到前的搜尋，這兩個搜尋理想情況下會相互指向。然而，這種雙向啟發式從前到前演算法 (BHFFA) 最終被證明在計算上佔用太多空間。Politowisky 和 Pohl (1984) 設計了另一種模型來克服 Champeaux 提出的問題。這種稱為 d-Node 重新定位的演算法能夠使用更少的計算空間，並找到一種有效的在中間相遇的方法。Politowisky 和 Pohl 使用 Champeaux 模型提出的想法，使用了一種從前到前的設計，其中起點節點的路徑指向目標路徑中最有希望的節點，反之亦然。不幸的是，這種演算法出現了更多問題，因為它只能用於不可接受的啟發式方法，即使這樣，解決方案也不總是足夠明確。當搜尋演算法是可接受的時，這意味著搜尋將以最低成本的分支結束。
Ghosh 和 Mehanti (1991) 隨後嘗試解決這些問題，建議使用另一種用於雙向搜尋的從前到前的啟發式演算法。這種演算法使用預定義的引數來減少計算機儲存。他們的演算法結合了廣度優先搜尋和最佳優先搜尋。15-puzzle 被用來測試他們的演算法。15-puzzle 包含一個棋盤，棋盤上有隨機排列的數字的瓷磚，搜尋系統必須遍歷並按順序排列瓷磚。結果表明，在判斷解決方案質量時，他們的演算法比以前提到的演算法更成功。
Champeaux, D.D. (1983)。再次進行雙向啟發式搜尋。J. ACM 30, 22-32
Davis, H.W., Pollack, R.B., Sudkamp, T. (1984)。更好地理解雙向搜尋。AAAI-84 論文集
Ghosh, S., Mahanti, A. (1991)。資源有限的雙向啟發式搜尋。資訊處理快報 40, 335-340。
Pijils, W., Post, H. (2006)。一種具有縮短後處理的新型雙向搜尋演算法。歐洲運籌學雜誌。
Pohl, I., (1970)。啟發式搜尋被視為圖中的路徑查詢。人工智慧 1 193-204。
Pohl, I., Politowiski, G. (1984)。雙向啟發式搜尋中的 d-Node 重新定位。AAAI-84, 274-277