Память и время
При выполнении A* алгоритма, наиболее важным фактором (с точки зрения и использования памяти и времени для вычисления) является то, как выполнена приоритетная очередь. Давайте обозначим число ячеек N.
В течение каждого прохода по основному циклу, PQ.ExtractMin вызывается только однажды. Когда узел был извлечен, он не будет пройден снова, так что цикл выполняет максимум N раз. Только операции, за исключением PQ.ExtractMin, внутри цикла, которые не выполняются за постоянное время, находятся внутри просмотра соседей. Цикл сканирования соседей непосредственно выполняется больше восьми раз, то есть он не увеличивает время больше чем на 'постоянное' количество операций внутри цикла. Из-за специального характера нашего представления графа, мы можем легко 'находить' соседей за постоянное время. Не-постоянные операции по времени возможны внутри цикла просмотра соседей - PQ:INSERT и PQ.DecreaseKey. Так что весь алгоритм отнимает O(N)*min{8*PQ.Insert, 8*PQ.DecreaseKey, PQ.ExtractMin времени.Самый простейший метод, который часто используется при небольших задачах, состоит в том, чтобы использовать сортированый связаный список для приоритетной очереди. Однако, в то время как операция PQ.ExtractMin для этого берет O(1) времени, операции PQ.Insert и PQ.DecreaseKey берут O(N) времени. Таким образом, целый алгоритм прошел бы за O(N2) времени. Для этой цели, лучше использовать хорошо - известную приоритетную очередь - так называемую кучу Фибоначчи. Поскольку теория и реализация этих куч несколько сложна, то их описание здесь опущено см. [CORM90] стр. 420 .. 439. Типовая реализация может быть найдена в [BOYE97]. Операции с кучей Фибоначчи выполняются за различное время в зависимости от внутреннего состояния переменных. Например, вставки могут вначале идти очень быстро, затем после нескольких вставок, приходит время делать некоторую 'очистку дома', которая может забрать значительно большее количество времени. Таким образом, 'амортизационные' издержки используются взамен, и время, требуемое, чтобы выполнить последовательность операций усредняется по всем операциями, выполняемыми в течение алгоритма; см.
[CORM90] глава 18 для дальнейшего рассмотрения. Удовлетворитесь здесь только замечанием, что издержки амортизации стоят для кучи Фибоначчи: O(1) для PQ.Insert, O(1) для PQ.DecreaseKey и O(log(N)) для PQ.ExtractMin. Таким образом самая лучшая известная реализация A* (также как алгоритм Дийкстры) выполняет за O(N?log(N)) времени. Константы, скрытые внутри нотации O совершенно большие для куч Фибоначчи, хотя, поэтому они не очень полезны для маленьких куч.А как насчет памяти? На старте, каждая вершина, v, нуждается в значении для g[v] и h[v], который таким образом требует O(N) памяти. Кроме того, каждый элемент в приоритетной очереди занимает некоторую память. Тривиальная верхняя граница максимального числа элементов в очереди - N, так что общая занимаемая память имеет верхнюю границу O(N). Практически, максимальный размер очереди имеет тенденцию, чтобы быть значительно меньше чем N, см. например рисунок 23 в разделе 5.4 (где вершина в очереди была отмечена белым). С другой стороны, при реализации кучи Фибонначи, каждый элемент, сохраненный в очереди забирает довольно большое (хотя линейное) количество памяти.
Для нашего приложения мы больше заинтересованы потреблением времени как функцией расстояния, d, между источником и адресатом. Некоторые модели для зависимости N от d были обсуждены в 3.1.1.1. В большинстве случаев N имеет квадратичную зависимость от d и при этом, что алгоритм выполяется за O(d2?log(d)) время. Таким образом на каждом 'реальном' компьютере когда верхняя граница расстояний, dmax, после, которой мы быстро исчерпаем память. В разделе 4.3 показан метод как увеличить dmax.
7.2.6