На этом шаге мы приведем функцию, рассчитывающую это расстояние.
Как известно из геометрии, кратчайшим путем между двумя точками является прямая. Следовательно, вполне оправданно, что для поиска пути по лабиринту прямолинейная эвристика всегда будет допустимой. Согласно теореме Пифагора евклидово расстояние составляет distance = √((difference in х)2 + (difference in у)2). Для наших лабиринтов разность по оси X эквивалентна разности в столбцах между двумя точками лабиринта, а разность по оси Y - разности в строках. Обратите внимание: мы снова реализуем этот код в исходном файле.
def euclidean_distance(goal: MazeLocation) -> Callable[[MazeLocation], float]: def distance(ml: MazeLocation) -> float: xdist: int = ml.column - goal.column ydist: int = ml.row - goal.row return sqrt((xdist * xdist) + (ydist * ydist)) return distance
Функция euclidean_distance() возвращает другую функцию. Такие языки, как Python, которые поддерживают функции первого класса, допускают применение этого интересного шаблона. Функция distance() фиксирует целевую точку MazeLocation goal, которую передает в euclidean_distance(). Фиксация целевой точки означает, что distance() может ссылаться на эту переменную при каждом вызове (постоянно). Функция, которую она возвращает, использует goal для выполнения своих вычислений. Этот шаблон позволяет создать функцию, требующую меньше параметров. Функция, возвращаемая distance(), принимает в качестве аргумента только начальную точку прохода по лабиринту и всегда знает конечную точку.
Применение евклидова расстояния для прохода по лабиринту - в данном случае по сетке улиц Манхэттена - показано на рисунке 1.
Рис.1. Евклидово расстояние - это длина прямой линии, соединяющей начальную и конечную точки
На следующем шаге мы рассмотрим Манхэттенское расстояние.
