Почему имеет сложность* экспоненциал в памяти?
В Perl, если Вы хотите ограничить себя алфавитом нижнего регистра, можно сделать это:
my @result = ("a" .. "zzzz");
Это дает все возможные строки между 1 и 4 символами с помощью символов нижнего регистра. Для верхнего регистра, изменение "a" к "A" и "zzzz" к "ZZZZ".
Для смешанного случая это становится намного более твердым, и вероятно не выполнимое с одним из встроенных операторов Perl как этот.
3 ответа
A * - это просто управляемая версия поиска в ширину, которая имеет экспоненциальную сложность памяти по отношению к длине решения.
При использовании постоянной эвристики A * станет обычным поиском в ширину; если быть точным, поиск однородной стоимости.
При использовании оптимальной эвристики A * будет O (n) как по пространственной, так и по временной сложности, если не принимать во внимание сложность самого эвристического вычисления. Опять же n - длина пути решения.
Я думаю, что экспоненциальность вступает в игру, когда вы возвращаетесь к узлу 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 - число дочерних узлов. глубина поиска.
Я не эксперт, но я некоторое время изучал статью в Википедии, и мое объяснение будет таким (надеюсь, я хорошо его понял :)
Скажем, у нас есть 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