Какие есть хорошие методы для нахождения эвристики для алгоритма A *?

Question

У вас есть карта квадратных плиток, где вы можете двигаться в любом из 8 направлений. Учитывая, что у вас есть функция с именем cost(tile1, tile2), которая сообщает вам стоимость перехода от одной соседней плитки к другой, как найти эвристическую функцию h (y, цель), которая является допустимой и последовательной? Можно ли обобщить метод нахождения эвристики с учетом этого параметра или он будет отличаться по-разному в зависимости от функции cost?

Answer 1

Учебник Амит - один из лучших, которые я видел на A * (страница Амит) . На этой странице вы найдете несколько очень полезных советов по эвристике.

Вот цитата о вашей проблеме:

На квадратной сетке, которая допускает 8 направлений движения, используйте диагональное расстояние (L∞).

Answer 2

Это зависит от функции стоимости.

Существует несколько общих эвристик, таких как Евклидово расстояние (абсолютное расстояние между двумя плитками на плоскости 2d) и Манхэттенское расстояние (сумма абсолютных x и y дельт).Но они предполагают, что фактическая стоимость никогда не бывает меньше определенной суммы.Манхэттенское расстояние исключается, если ваш агент может эффективно перемещаться по диагонали (т. Е. Стоимость перехода по диагонали меньше 2).Евклидово расстояние исключается, если стоимость перемещения на соседний тайл меньше абсолютного расстояния этого хода (например, может быть, если соседний тайл был «вниз» от этого).

Редактировать

Независимо от вашей функции стоимости, у вас всегда есть допустимая и последовательная эвристика в h(t1, t2) = -∞.Это просто нехорошо.

Answer 3

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

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

Итак, какова ваша функция стоимости между плитками?Это основано на физических свойствах или определено за пределами вашего графика?