Используя эти термины, давайте посмотрим, как они применяются в алгоритме и, более обобщенно, как работает алгоритм A*. Как вы теперь знаете, A* ищет кратчайший путь между двумя точками. Но какую систему измерения мы используем? Время? Расстояние? Число шагов? В то время как A* может быть использован для поиска в соответствии с наиболее подходящей системой измерения, мы выбираем расстояние. Другими системами измерения могут быть время (для поиска пути, занимающего кратчайшее время на прохождение) или количество канистр бензина (для поиска пути, на который требуется минимальное значение топлива для автомобиля). Стоимости перемещения между одной плиткой и ее вертикальным или горизонтальным соседом мы будем присваивать значение равное 1 (1 фут, 1 миля, 1 плитка – не имеет значения). Стоимость перемещения между одной плиткой и соседней по диагонали составляет 1.41. Число 1.41 представляет собой дистанцию между центрами двух соседних плиток по диагонали.
Эвристика представляет собой лучшее предположение, как далеко центр текущей плитки (которую вы проверяете при поиске) находится от плитки назначения. Вы можете сделать это предположение довольно просто, используя простую логику. После посещения каждому узлу назначается значение счета f:
f =g +h
Значение h представляет собой эвристику – лучшее предположение о расстоянии между этой плиткой и целью. Значение g представляет собой сумму счета каждого узла, посещенного вдоль пути к текущему узлу. Это может быть наилучшим образом понято по аналогии. Скажем, вы планируете поездку из Нью-Йорка в Париж. Вы ограничены в бюджете, поэтому вы хотите найти путь, который будет наименее дорогим. Вы можете представить Нью-Йорк, Лондон, Лиссабон, Брюссель, Мадрид и Париж в качестве узлов. В процессе вашего исследования вы вычисляете стоимость от Нью-Йорка до Лондона и сохраняете ее. Но вы также рассчитываете стоимость путешествия из Лиссабона до Нью-Йорка, из Лондона в Париж, и так далее. В конце, если вы применяете другие правила (еще не обсужденные) с алгоритмом A*, вы находите лучший путь (по стоимости)
Русская версия