На этом шаге мы рассмотрим, что это такое, и как она используется в алгоритме A*.

Эвристика - это интуитивное представление о том, как решить задачу. В случае прохода по лабиринту эвристика стремится выбрать в нем лучшую точку для поиска следующей точки в желании добраться до цели. Другими словами, это обоснованное предположение о том, какие узлы из области поиска находятся ближе всего к цели. Как уже упоминалось, если эвристика, используемая при поиске по алгоритму А*, дает точный относительный результат и является допустимой (никогда не переоценивает расстояние), то А* составит кратчайший путь. Эвристика, которая вычисляет меньшие значения, в итоге дает поиск по большему количеству состояний, тогда как эвристика, значение которой ближе к точному реальному расстоянию (но не больше его, иначе эвристика будет недопустимой), выполняет поиск по меньшему количеству состояний. Следовательно, идеальная эвристика максимально приближается к реальному расстоянию, но не превышает его.

На следующем шаге мы рассмотрим евклидово расстояние.