行人导航的路由算法比较

Question

我目前正在开发行人导航软件，对我来说很难的主题是找到最适合该任务的路由算法。我听说A*是这类软件中实际使用的算法之一。

您能建议解决这个问题的其他算法吗？他们的表现如何比较？它们需要多少内存和空间？

预先感谢您的答复。

Answer 1

好吧，你可以看看迭代深化搜索。在我看来，这是解决您的问题的一种非常聪明的方法，但是由于该算法旨在进行完整的探索，因此您可能会面临相对于 A* 而言具有良好启发式的相当糟糕的时间复杂度的风险。

来自维基百科：

IDDFS 结合了深度优先搜索的空间效率和广度优先搜索
搜索的完整性（当分支因子有限时）。这是
当路径成本是深度的非递减函数时是最优的
节点的。 IDDFS 的空间复杂度为 O(bd)，其中 b 是
分支因子，d 是最浅目标的深度。自从
迭代深化多次访问状态，看起来可能
浪费，但事实证明它并不那么昂贵，因为在树上最
的节点位于底层，因此如果
上层被多次访问。

再次，关于时间复杂度：

平衡良好的树中 IDDFS 的时间复杂度为
与深度优先搜索相同：O(bd)。