Почему сложность A * экспоненциальна в памяти? - PullRequest
Новая
       20

Почему сложность A * экспоненциальна в памяти?

17 голосов
/ 11 ноября 2009

Википедия говорит о сложности A * ( ссылка здесь ):

Более проблематично, чем его время Сложность - использование памяти A *. В наихудший случай, он также должен помнить экспоненциальное число узлов.

Я не вижу, что это правильно, потому что:

Скажем, мы исследуем узел A с преемниками B, C и D. Затем мы добавляем B, C и D в список открытых узлов, каждый из которых сопровождается ссылкой на A, и мы перемещаем A из открытых узлов к закрытым узлам.

Если в какой-то момент мы найдем другой путь к B (скажем, через Q), который лучше, чем путь через A, то все, что нужно, - это изменить ссылку B на A, чтобы указать на Q, и обновить ее фактическую стоимость. , г (и логически е).

Следовательно, если мы сохраним в узле его имя, имя ссылающегося узла и его оценки g, h и f, то максимальное количество сохраненных узлов - это фактическое количество узлов в графе, не так ли? ? Я действительно не могу понять, почему в любое время алгоритм должен хранить в памяти количество узлов, экспоненциальное по отношению к длине оптимального (кратчайшего) пути.

Может кто-нибудь объяснить, пожалуйста?

edit Как я понимаю, теперь, читая ваши ответы, я рассуждал с неверной точки зрения на проблему. Я считал само собой разумеющимся данный граф, тогда как экспоненциальная сложность относится к концептуальному графу, который определяется исключительно «фактором ветвления».

Ответы [ 3 ]

31 голосов
/ 11 ноября 2009

A * - это просто управляемый вариант поиска в ширину, который экспоненциально влияет на сложность памяти в зависимости от длины решения.

При использовании постоянной эвристики A * станет обычным поиском в ширину; точный поиск единой стоимости.

При использовании оптимальной эвристики A * будет иметь значение O(n) как в пространственной, так и во временной сложности, если мы игнорируем сложность самого эвристического вычисления. Снова n - длина пути решения.

7 голосов
/ 11 ноября 2009

Я думаю, что экспоненциальное значение вступает в игру, когда вы возвращаетесь к узлу B, чтобы развернуть его, но затем возвращаетесь к узлу C, чтобы развернуть его, а затем возвращаетесь к узлу D. Теперь мы должны отслеживать все дочерние элементы узлы A, B, C и D.

Возврат основан на стоимости ребер для перехода к следующему узлу, так что это реальная возможность, но в худшем случае.

Если у каждого узла есть ровно 2 дочерних элемента, и каждый узел имеет одинаковую стоимость, тогда уравнение равно 2 ^ n, где n - глубина поиска.

Например, вы начинаете с узла 0. 0 имеет 2 дочерних элементов 00, а 01. 00 имеет 2 дочерних элемента 000 и 001. В худшем случае с глубиной 4 уравнение равно 2 ^ 4, где 2 - это число детей имеет каждый узел, а 4 - глубина поиска.

2 голосов
/ 11 ноября 2009

Я не эксперт, но я некоторое время изучал статью в Википедии, и мое объяснение было бы именно этим (надеюсь, я хорошо понял:)

Скажем, у нас есть матрица 4x4 узлов.
A, B, C, D - направления, которые мы можем выбрать в данный момент времени (север, юг, восток, запад)
Алгоритм A * начинает поиск.

A
Очередь: B, C, D
AA
Очередь: B, C, D, AB, AC, AD
AAA -> Цель
Очередь: B, C, D, AB, AC, AD, AAB, AAC, AAD
Цель достигнута, но есть и другие возможности для рассмотрения.

D
Очередь: B, C, AB, AC, AD, AAB, AAC, AAD
DC
Очередь: B, C, AB, AC, AD, AAB, AAC, AAD, DA, DB, DD
DCA
Очередь: B, C, AB, AC, AD, AAB, AAC, AAD, DA, DB, DD, DCB, DCC, DCD
DCAB -> Цель
Очередь: B, C, AB, AC, AD, AAB, AAC, AAD, DA, DB, DD, DCB, DCC, DCD, DCAA, DCAC, DCAD
И т. Д.

Как видите, на каждый шаг в очередь добавляются еще три узла.
Поскольку A * следует только ациклическим путям [1], максимальное количество шагов на маршрут составляет 15.
Максимальное количество возможных маршрутов в этом случае составляет 3 ^ 15 или направления ^ узлов.
Поскольку на каждом маршруте 15 шагов, наихудшие шаги - 15 * 3 ^ 15.
В самом худшем случае каждый шаг, который когда-либо был сделан, «неправильный».
В этом случае 3 * 15 * 3 ^ 15 узлов находятся в очереди перед поиском ответа.
Таким образом, наихудшее количество узлов, которые должны храниться в памяти, является постоянным, в зависимости от количества доступных узлов. Другими словами, использование памяти экспоненциально количеству узлов.

[1] http://www.autonlab.org/tutorials/astar08.pdf, слайд 15

...