проверить совместимость эвристики
я знаю, что совместимая эвристика — это та, которая при следующих условиях:
ч (п) <= c (n, a, n ‘) + h (n’).
И допустимая эвристика находится под условием: 0 <= ч (н) <= реальная стоимость. Однако я не знаю, как проверить, совместима ли эта эвристика:
Агент живет в мире сетки NxN. Текущая позиция агента задается кортежем (Xa; Ya), представляющим строку и
столбец, в котором он находится в данный момент. Местоположение цели, которого хочет достичь агент, представлено кортежем (Xg; Yg). Агент может только
двигаться вверх, вниз, влево или вправо на 1 квадрат за раз.
h (a) = (Xa — Xg) + (Ya — Yg)
Могу ли я иметь некоторые советы, чтобы сделать это? Спасибо огромное.
Решение
Насколько мне известно, для определения пути A * расстояние такси — это хорошая эвристика в вашем случае. Больше информации здесь: https://en.wikipedia.org/wiki/A*_search_algorithm.
Другие решения
Изменить: Как правильно указал @FeiXiang, вы должны идти с расстоянием такси, также известным как расстояние Манхэттен в вашем случае, где единственные допустимые движения — вверх, вниз, влево или вправо.
Если (Xa, Ya) ваша текущая позиция в сетке Point a а также (Xb, Yb) ваш пункт назначения Point b, тогда вы бы вычислили расстояние до Манхэттена следующим образом.
typedef std::pair<int, int> Point;
unsigned manhattanDistance(const Point &a, const Point &b)
{
return abs(a.first - b.first) + abs(a.second - b.second);
}
В Интернете есть много ресурсов для помощи с A * алгоритм поиска так что начинайте бить книги и удачи!