A* эвристическое уточнение
Поскольку мы только заинтересованы в самом коротком пути между двумя вершинами, мы будем впустую тратить время, чтобы вычислять все пути от одной вершины до всех других вершин, как это делает алгоритм Дийкстры.
Наиболее очевидное уточнение состоит в том чтобы прекратить поиск тогда, когда вершина адресата t, удаляется. Знание о позиции адресата не используется вообще во время поиска, и 'глупо' его не использовать. A* алгоритм, представленный в [NILS82], учитывает это, добавляя эвристику, чтобы перенести направление поиска к адресату и таким образом возможно закончить поиск быстрее. Единственное различие между алгоритмами заключается в каком порядке вершины удаляются на каждом итерационном шаге, то есть каким образом они упорядочиваются в приоритетной очереди. Основная идея состоит в том, что вместо того, чтобы использовать g[v] (фактическая стоимость от источника до текущей вершины) чтобы упорядочить очередь как в алгоритме Дийкстры, новая стоимость, f[v] = g[v] + h[v] используется заместо старой, где h[v] - эвристика. Можно доказать, что, если h[v] является недооценкой (или в большинстве случаев равной) фактической наименьшей стоимости пути для перемещения от v до t, тогда A* производит оптимальное решение (точно так же как в случае Дийкстры). Строгое доказательство выходит за рамки данного документа; смотри в [NILS82]. Как только упорядочение приоритетной очереди изменено, характеристики с самого плохого случая такие же как для Дийкстры, но мы можем ожидать, что средняя эффективность будет намного лучше для графов 'реального мира', если мы сможем создать хорошую эвристику, h[v].Вообщем, время прохождения 'расстояния от u до v' является 'самой маленькой стоимостью' и будет самой лучшей оценкой, которую мы можем сделать для h[v], когда недооценку от действительной стоимости нужно учесть. Какова оптимальная оценка 'расстояния', зависит от структуры графа.
Истинное Евклидово расстояние можно использовать, но оно часто меньше, чем фактическая длина граней по самому короткому пути (см. рисунок 12). Вместо этого, так как структура графа однородна, мы можем фактически вычислить точное, 'оптимальное' расстояние. Если мы только имеем ортогональные грани, это будет так называемое расстояние 'Манхэттанна': |Dx| + |Dy|. В нашем случае, с диагональю грани также, это будет выглядеть таким образом : 'диагональная длина края'’ * min(|Dx|,|Dy|) + 'осевая длина края' * ||Dx|-|Dy||. Это очень хорошо посравнению с использованием Евклидова расстояния так как не требуется вычисление квадратного корня.Мы можем придержать вычисление h[v] для каждой вершины, до тех пор пока это не станет фактически необходимым, то есть когда она первый раз попадет в очередь поиска. Таким образом, тот же самый флаг какой используется для слежения за тем, если вершина находится в U (см. 4.2.1) также будет указывать на то, надо ли h[v] инициализировать. Поскольку большинство вершин никогда не будет посещено вообще, это поможет сохранить нам немного времени.
Обратите внимание, что, если стоимости граней местности без препятствий меняются в больших пределах (например, дороги очень мало стоят, в то же время как равниные типы местности дорого стоят), тогда добавляя эвристику, базирующуюся на 'самой маленькой стоимости местности' вообще-то обеспечивается наибольшая недооценка. В этих случаях A* - незначительной уточнение и будет вести себя подобно алгоритму Дийкстры. Альтернативой было бы использование 'типичной стоимости местности' вместо самой маленькой стоимости. Это нарушило бы утверждение что эвристика недооценивает реальную стоимость и таким образом ставит под угрозу гарантию оптимальности. В некоторых приложениях, такой способ может быть дать более быстрые решения. Фактически, мы могли бы использовать f[v] = g[v] + c*h[v], где c - 'управляющая' константа масштабирования. При c=0 мы имеем алгоритм Дийкстры, при c=1 мы имеем A*, при c>1, мы имеем модифицируемый 'приблизительный A*'. При больших значениях c решение находится быстрее (в среднем), но при этом оно более 'направлено на адресат'. Хорошую интерактивную обучающую программу на Java, которая иллюстрирует данное свойство, можно найти в [WAVE96]. При равной стоимости местности, эвристика h=0 дает для нашего специального графа фронт поиска, который расширяется в форме шестиугольника, в то время как A* с истинной Евклидовой эвристикой дает более груше-подобную форму.
Пример совершенно иного применения A* может быть найдено в [SONK93]. 7.2.3