Прогрессивная аппроксимация
Грубое решение может быть найдено, запустив обычный A* алгоритм на 'укрупненной модели' графа. Укрупненный граф создается из оригинала 'группируя вместе' квадратные области соседних вершин в одну вершину, для того чтобы получить уменьшенный граф, который все еще представляет оригинал. При коэффициенте укрупнения равном 4, имеем что 4x4 вершины собраны в одну новую, и мы имеем 16-кратное уменьшение и, числа граней и вершин как проиллюстрировано на рисунке 16. Количество использованной памяти A* алгоритмом, чтобы найти грубое решение на укрупненном графе соответственно уменьшается. Как мы должны определить функцию стоимости для укрупненного графа? Несколько подходов равнозначно. При первом подходе надо выбрать значения самого короткого пути между вершиной в первоначальном графе, которые совпадут с теми же в укрупненном графе (см. рисунок 16). При другом подходе, надо некоторым способом, 'вычислить среднее' всех возможных путей, которые могут быть созданы из граней, сгруппированых вместе. Оба этих подхода имеют ряд трудностей и требуют незначительного времени для вычислений. Вместо этого, был выбран подход с созданием нового набора атрибутов для укрупненного графа и 'многократного использования' 'первоначальной' функции стоимости. Если 'масштаб' уменьшен по всем пространственным координатам, зависящие от длины грани значения, которые использует функция стоимости не обязательно должны быть повторно вычислены; оптимальный путь будет тот же самый, хотя общая стоимость пути будет не такой же.
Как новые атрибуты должны быть выбраны? Атрибут высоты не представляет сложную философскую проблему, совершенно естественно выбрать среднее (интегрированное) значение из всех назначенных неукрупненных значений. Для атрибута дороги, взамен полезно выбрать значение наименьшей стоимости (то есть 'самый быстрый' атрибут дороги из тех, которые являются сгруппированными вместе) для того чтобы сохранить связность дорог. Если две дороги, оказались сгруппироваными вместе, надо естественно, выбрать самую быструю. Тип местности представляет более трудную проблему. Разные типы не могут просто быть 'усреднены', так как ячейки состоят из различных не-объединяемых категорий. Здесь мы производим выбор наиболее 'популярного' типа местности, и в случае возникновения неоднозначности выбираем 'наименее дорогостоящий' тип ( важно, что б была соблюдена проходимость ). Это ни в коем случае не очевидный выбор и может конечно быть обсужден и-или улучшен. Однако, для большинства приложений, дороги являются определяющими, и релевантная (уместная) информация относительно их протяженности сохраняется в представленной схеме. Однако надо подчеркнуть, что могут иметься приложения, где дело обстоит не так и где этот подход 'укрупнения' графа не является допустимым.
Рисунок 16 -Укрупненные грани, при факторе 4 Рисунок 17 - укрупненные сегмены пути
Затем, грубое решение (найденное на укрупненном графе) разделенно на 'сегменты', как несколько преувеличенно иллюстрировано на рисунке 17, где небольшой путь с девятью гранями был разделен на три сегмента по три грани каждый. Затем, оптимальный путь между конечными точками первого сегмента (отмеченными черными кругами на рисунке) найден, используя A* алгоритм на оригинальном 'точном' графе. Это повторяется для других сегментов, и все 'точные' решения сегментов в заключение вставляются вместе в полное решение.
Однако нельзя сказать, что точки конца сегмента должны лежать на оптимальном пути. Таким образом, эта схема улучшена, во-первых, при помощи использования фактической исходной вершины для первого точного сегмента путей и вершины адресата для последнего. Далее, для каждого нового сегмента (следующие после первого) предыдущий 'точный' путь находится по указателям возврата нескольких граней. Это положение затем принимается как исходная вершина для поиска A* в новом сегменте вместо 'грубой' отметки начала сегмента; см. рисунок 17. Хорошая идея добавить проверку, того что вершина, используемая как источник и адресат в каждом точном решении сегмента не попадает внутрь например воды или других недоступных областей. Так как любой сегмент может быть сделан намного короче чем общая длина пути, очередь поисков A* станет намного меньше. Имеются некоторые непроизводительные затраты, связанные с нахождением пути, используя эту процедуру, так что стандартный метод будет обычно быстрее. Однако, при намного меньшей очереди поиска можно найти путь только в оперативной памяти и не использовать жесткий диск для виртуальной памяти. Таким образом, на больших графах, мы можем фактически ожидать уменьшения времени поиска. Это было проверено на практических тестах, см. дальше раздел 5.5Этот процесс можно бы теоретически разбить на отдельные этапы, которые начинаются с очень грубого решения и продолжаются к более точным решениям на сетках/графах. Однако, при укрупнении может потеряться информация которая необходима для нахождения оптимальных путей, например узкие мосты , непроходимые реки и т.д.. Это означает это, если мы хотим найти 'возможное решение', грубый граф должен содержать все 'существенные' характеристики карты. Это можно обеспечить выбором наибольшего коэффициента укрупнения. Практические тесты показывают, что при коэффициенте 6 все еще можно избежать слишком очевидных побочных эффектов (особенно в городских регионах). Кроме того, не много можно использовать от графа, который является более точным чем первоначальные растровые данные, так что процесс с двумя шагами, кажется, единственный, который имеет смысл. Другая проблема - длина сегмента. Для максимальной скорости длина должна быть как можно большей до предельного значения, при которой A* алгоритм начинает использовать слишком много памяти. Фактическое значение предела зависит от очень многих вещей, и от фактической реализации также как и специфической среды, в которой поиск производится. Эмпирический анализ специфического приложения при хорошем 'запасе прочности' способен обеспечить подходящее значение длины сегмента ( это так же может зависить от времени рассуждения предоставляемого юниту для выбора пути ). 8