масштабный коэффициент для стоимости расстояния между узлами в алгоритме A *

Question

У меня есть набор данных, который представляет собой совокупность затрат, связанных с узлом. Эта стоимость представлена ​​как расстояние в футах.

У меня также есть x-y-координата для каждого узла. Теперь в алгоритме A * мне нужно будет добавить стоимость от узла к узлу + эвристическую стоимость от среднего узла до места назначения. Однако эти два значения должны иметь одинаковую метрику / единицу. У меня не может быть одного в футах, а другого на координатном расстоянии.

Я знаю, что для этого мне сначала нужно найти коэффициент масштабирования, чтобы масштабировать стоимость от фута до координаты x-y. Правильно? Все, что я могу сказать, это то, что все эти затраты являются масштабируемыми. Таким образом, это бета-значение будет одинаковым для всех пар узел-узел. Вопрос в том, как мне найти это значение?

То, что я сделал прямо сейчас, - это нахождение координатного расстояния между узлом и узлом, а затем сравнить его со стоимостью в футах. И поэтому я могу найти бета-версию, которая является константой и должна работать для каждой стоимости узла-узла (футы) ... Я не уверен, правда ли это. Я не ищу магический трюк здесь, просто простой способ / математика, чтобы решить это

Answer 1

Обычно мы знаем, что сетка моделирует физический мир с некоторым масштабным коэффициентом.Разве вы еще этого не знаете?

В любом случае, я думаю, что ваша интуиция верна.То есть вычислите координатное расстояние между двумя точками, где вы знаете фактическую стоимость в футах, разделите одну на другую, и это ваш масштабный коэффициент.Предполагая, конечно, что «стоимость» - это расстояние по прямой линии между двумя узлами.

То есть, если расстояние между узлом 1 и узлом 2 составляет, скажем, 3 фута, а координаты узлов равны [0,0] и [0,9] соответственно, тогда «коэффициент масштабирования» равен 3/9 ... или 9/3, в зависимости от того, каким образом вы хотите выполнить преобразование.

В этом случае одна единица вКоординатное расстояние составляет 1/3 фута.Или одна нога - 3 единицы в координатном расстоянии.Таким образом, чтобы перейти от координат к футам, вы делите на 3. Чтобы перейти от футов к координатам, вы умножаете на 3.