Какие эвристические функции можно использовать для графического (несетевого) A *?

Question

Я изучаю алгоритм поиска пути A *, и все примеры, которые я нахожу, основаны на сетке. Из-за этого все их функции эвристики опираются на какое-то физическое расстояние (например, на основе Манхэттена, диагональ или евклид).

Но что, если вместо сетки мы имеем график свободной формы? Скажем, пример ниже, где S является началом и G цель:

S---A 
| 
| G 
| | 
B---C---D 

В этом случае «по прямому» приближению не будет иметь смысла, потому что этот граф является двусмысленным для

S---A 
| 
B---C---D 
    | 
    G 

Какую эвристическую функцию я мог бы использовать в этом случае?

Answer 1

Нет эвристики, которая улучшит время работы алгоритма Дейкстры в общем случае.

Эвристика полезна, когда конкретная проблема имеет дополнительную структуру . Графы, встроенные в плоскость, имеют именно это: понятие прямолинейного расстояния, которое может использоваться как эвристическое, как в вашем примере.

Рассмотрите аналогию сортировки. В общем случае мы знаем, что сортировка - это O (nlogn) для массива O (n). Однако если наши данные удовлетворяют условию, что числа в массиве находятся в диапазоне от 0 до k, где k < < n, то мы можем сортировать их в O (n) с помощью counting sort.

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