是A *最好的尋路算法嗎？

Question

一般認爲A *是解決尋路問題的最佳算法。

有沒有什麼情況當A *是不是找到解決方案的最佳算法？

A *與BFS，DFS，UCS等相比有多好？

Answer 1

A *是特殊的，因爲它可以演變爲其他路徑尋找算法，通過演示如何評估節點及其使用的啓發式。你可以這樣做來模擬Djikstra的，最先搜索，呼吸優先搜索和深度優先搜索。

此外，通常很容易加快速度。例如，如果將可容許的啓發式乘以常數c，則可以保證所得結果序列的成本不超過最優結果的c倍。

例如，以Ian Davis的awesome paper（爲Star Trek armada寫）。 A *與路標的分層集合一起使用，這會導致粗糙的路徑。然後，爲了平滑路徑，他們再次在包含路徑上的節點和附近的節點的新的生成的圖上運行A *以獲得更合理的路徑。最後，他們運行橡皮筋去除多餘的節點。所以，A *不是一切的解決方案，但它是一個非常多才多藝的工具。

Answer 2

簡短的回答是肯定的，有些情況下A *不是解決問題的最佳算法。然而，有多種方法可以評估什麼構成了尋找解決方案的最佳算法。

如果你正在考慮最好的單一來源的多次搜索性能方面到多個目的地，那麼你應該考慮使用一個更合適的方法（Dijkstra's algorithm）。

如果你正在考慮在性能方面最好，那麼在某些特殊情況下，DFS和BFS將顯著跑贏A *。從過去的經驗來看，這種情況發生在非常小的，幾乎微不足道的圖表上，但需要仔細測試和分析才能做出更強的說明。

如果你正在考慮在路徑長度方面最好，那是多麼長的加密算法生成最終路徑，則A *是等同於任何其他優化搜索算法。

如果你正在考慮在完整性方面最好，那就是，將算法如果這樣的路徑存在總是找不到球門的路徑。如果是這樣，那麼A *相當於任何其他完整的算法（例如，廣度優先搜索）。

如果你正在考慮在一些圖中的權重爲負箱子最好，那麼你就需要使用特殊的算法來解決這些問題（例如bellman-ford）

如果您正在考慮最好在沒有啓發式可用的情況下那麼你必須回落h(x,y)=0 forall states x and y。在這種情況下，A *相當於最佳首次搜索。

如果你正在考慮在連續配置空間有關運動規劃情況最好，那麼A *可以充分地在低維度的工作原理，但搜索圖的存儲開始於高尺寸變得不切實際，而需要使用概率完整的算法增加（例如RRT，碧RRT，RDT）

如果你正在考慮在該圖是部分可觀箱子最好，你只知道所有可能的頂點的一個子集以及a中圖形的邊緣您需要改變狀態以觀察更多的圖表，那麼您需要爲此設計一種替代算法（例如，Keonig的終身規劃A *，LPA *，完全是這樣）。

如果你正在考慮在圖隨時間的變化，頻繁當你整合移動障礙物發生在機器人技術，那麼你需要的是專爲這個（例如Stentz的D*或科尼格算法的情況下最好 & Likhachev的D * -Lite）。

Answer 3

一個非常簡單的選擇（沒有啓發式的爭論）是Collaborative Diffusion。它的工作原理寄望，當你需要的目標一個目標或一組的任何成員，胡亂，在這種情況下可以比A *更快。它模仿遊戲「你變暖/變冷」。

協作擴散會爲您希望定位的每個「羣組」創建一個熱圖...如果要跟蹤特定目標，請通過爲該目標創建一個熱圖來將其視爲自己的羣組; Collaborative Diffusion的領域是像足球一樣的遊戲（其中兩隊隊員專門跟蹤球和球門柱，導致只有3個影響圖）或Pacman（類似的，多個球員跟蹤Pac）或軍隊比賽，其中有一個代表身體的熱圖總計）由各軍隊人員確定，以便一個軍隊可以接近「另一支軍隊」，而不是「其他軍隊內的特定單位」。這種普遍性可能會提高性能。

步行包括爬山（從當前小區走向溫暖的鄰居小區），直到我們到達目的地（最熱點）。該方法隱含地處理移動的障礙物，即其他代理人。

這是最適合的地圖是相當密集的人口衆多，移動單位，因此證明必須發生在每個更新整個搜索空間的廣泛擴散。很明顯，在一張大而稀疏的地圖中，一個調整好的A *方法可以在一個數量級上便宜一個數量級，我們只有一個單位針對另一個單位，因爲在這種情況下，您只處理一個分數在探索者和目標之間的地圖瓦片;而使用Collaborative Diffusion，則只是爲了做同樣的事情，而不是在整個地圖上擴散，使其成本更高。