Рассчитать эвристику для графа

Question

У меня есть эти данные для графа:

• количество вершин
• ребер с весом

и ничего более ,и я хочу рассчитать эвристику для каждой вершины, чтобы я мог использовать алгоритм поиска пути, как A Star.Что я могу сделать?Если вам известно более одного решения, укажите все из них.

Обратите внимание, что я не могу рассчитать расстояние до Манхэттена и использовать его как эвристику, поскольку у меня нет информации о местоположении.

Answer 1

Вы все еще можете использовать A *, но вам придется немного "обмануть". A * является расширением алгоритма кратчайшего пути Дейкстры. Расширение состоит в том, что A * использует эвристику расстояния, чтобы поиск продолжался в правильном направлении. Учитывая график только с весовыми ребрами, вы вычисляете кратчайшую сумму весов от узла n до узла цели и используете ее в качестве эвристического расстояния. Таким образом, расстояние от START до Target равно 8, расстояние от A до TARGET равно 7, расстояние (B, TARGET) = 2 и так далее. Поскольку это эвристика, вы также можете использовать другие измерения. Если вы установите расстояния на 0, то это станет алгоритмом Дейкстры. Если вы установите большие расстояния, то это превратится в алгоритм Greedy-Best-First.