RRT 和 RRT 的时间和空间复杂度*

Question

RRT 和 RRT* 的时间和空间复杂度是多少？与基于图的增量启发式算法相比，基于增量采样的算法表现如何

Answer 1

RRT（快速探索随机树）和RRT*（快速探索随机树星）都是概率运动规划算法。这些算法的时间和空间复杂度如下：

RRT：

时间复杂度：O(K log K)，其中 K 是树中的节点数。

空间复杂度：O(K)

RRT*：

时间复杂度：O(K log K)

空间复杂度：O(K log K)

关于问题的第二部分，基于增量采样的算法（例如 RRT）和基于图的增量启发式算法（例如 PRM）具有不同的优点和缺点。基于增量采样的算法通常在高维空间中更有效，而基于图的增量启发式算法在低维空间中更有效。

此外，基于增量采样的算法可以以统一的方式有效地探索配置空间，而基于图的增量启发式算法则依赖于特定领域的启发式方法来指导搜索。

很难对这两类算法进行一般比较，因为它们的性能可能取决于当前的具体问题。通常最好选择一种非常适合要解决的特定问题的算法。

Answer 2

根据 Sertac Karaman 的论文，RRT 和 RRT* 的时间和空间复杂度为：

RRT

1. 空间复杂度：O(n)
2. 时间复杂度： 处理：O(n log n) 查询：O(n)

RRT*

1. 空间复杂度：O(n)

2. 时间复杂度： 处理：O(n log n) 查询：O(n)