行人導航的路由算法比較

Question

我目前正在研究行人導航軟件，而對我來說很難的主題是找到最適合該任務的路由算法。我聽說A *是這種軟件實際使用的算法之一。

你能否提出解決這個問題的其他算法？他們如何比較表演？他們需要多少內存和空間？

在此先感謝您的答案。

Answer 1

那麼你可以看看iterative deepening search。在我看來，這是一個非常聰明的方法來解決你的問題，但是由於該算法是爲了進行全面的探索而設計的，所以你可能冒險在A *方面具有相當差的時間複雜度。

維基百科：

IDDFS結合深度優先搜索的空間效率和廣度優先搜索 的完整性（當分支因子是有限的）。當路徑成本是節點的深度 的非遞減函數時，最優是 。 IDDFS的空間複雜度爲O（bd），其中b是 分支因子，d是最淺目標的深度。由於 迭代深化訪問狀態多次，它可能看起來浪費，但事實證明並不那麼昂貴，因爲在一棵樹中，大多數節點的 處於底層，所以如果 上層級別訪問多次。

再次，對所關注的時間複雜度：

IDDFS的良好平衡樹的時間複雜度的作品出來是 一樣的深度優先搜索：O（BD）。