Как спроектировать функцию стоимости и функцию heuristi c, которая находит самый быстрый маршрут, используя алгоритм поиска пути A *?

Question

В настоящее время я создаю программу определения маршрута для дорожной сети, в которой я хочу найти кратчайший маршрут (по расстоянию), а также самый быстрый маршрут (время), используя поиск A *.

Для кратчайшего На маршруте я использую (длину дороги) в качестве стоимости, и я использую евклидово расстояние от соседнего узла до конечного узла как heuristi c. Это отлично работает.

Однако, пытаясь найти самый быстрый маршрут (по времени), я предполагаю, что автомобили будут двигаться с ограничением скорости постоянно, поэтому я использую (длина дороги / ограничение скорости дороги) в качестве цена. Для heuristi c я использую евклидово расстояние от соседнего узла до конечного узла, деленное на ограничение скорости дороги, используемой для достижения этого соседнего узла. Это, кажется, работает нормально, однако, когда я использую алгоритм кратчайшего пути между теми же начальными и конечными точками, я часто получаю более быстрое время в пути, а это не то, чего я хочу. c должен иметь ту же степень, и что функция heuristi c должна быть последовательной и допустимой. Я не уверен, планирую ли я стоимость и heuristi c для того, чтобы правильно найти самый быстрый маршрут. Если у меня уже нет правильной идеи, как бы я go нашел самый быстрый путь?

Редактировать: РЕШЕНО

Answer 1

Использование расстояния по прямой линии до узла цели / предела максимальной скорости любой дороги в сети в качестве значения heuristi c означает, что предполагаемая стоимость (время) никогда не будет завышать истинную стоимость пути. Проблема в моем коде состояла в том, что мой оригинальный heuristi c был завышен. Предложение @btilly устранило проблему, поскольку heuristi c допустимо и будет недооценивать стоимость.