Пространственно-временные сложности RRT и RRT*

Question

Каковы временные и пространственные сложности RRT и RRT*? Как работают алгоритмы, основанные на инкрементальной выборке, по сравнению с алгоритмами, основанными на инкрементных эвристических алгоритмах

Answer 1

RRT (Rapidly-exploring Random Tree) и RRT* (Rapidly-exploring Random Tree Star) являются алгоритмами вероятностного планирования движения. Временная и пространственная сложности этих алгоритмов следующие:

РРТ:

Временная сложность: O(K log K), где K — количество узлов в дереве.

Космическая сложность: O(K)

РРТ*:

Временная сложность: O (K log K)

Космическая сложность: O(K log K)

Что касается второй части вашего вопроса, алгоритмы на основе инкрементной выборки (например, RRT) и инкрементные эвристические алгоритмы на основе графа (например, PRM) имеют разные сильные и слабые стороны. Алгоритмы на основе инкрементной выборки обычно более эффективны в многомерных пространствах, в то время как инкрементальные эвристические алгоритмы на основе графов более эффективны в низкоразмерных пространствах.

Более того, алгоритмы, основанные на инкрементной выборке, могут эффективно исследовать конфигурационное пространство унифицированным образом, в то время как алгоритмы инкрементной эвристики, основанные на графе, полагаются на эвристику, специфичную для предметной области, для управления поиском.

Трудно провести общее сравнение между этими двумя типами алгоритмов, поскольку их производительность может зависеть от конкретной решаемой задачи. Часто лучше выбрать алгоритм, который хорошо подходит для конкретной решаемой задачи.