Эвристическая функция для алгоритма A * Dijkstra с библиотекой графов наддува

Question

У меня нет подробных знаний об алгоритме A * Dijkstra.Я знаю, что это также алгоритм кратчайшего пути, который также рассматривает эвристику h (x) наряду с g (x).Я использую Boost Graph Library для своего проекта, и в библиотеке есть алгоритм A *.

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

Answer 1

Не имея реализованного примера, эвристика для A * выглядит примерно так: «Я знаю, что путь имеет по крайней мере эту длину (и не короче)».Примером может служить карта, на которой расстояние дороги между двумя узлами не может быть короче антенного расстояния (или евклидова расстояния или любой используемой вами системы координат).Поэтому примером эвристической функции может быть функция, возвращающая воздушное расстояние между двумя узлами.