На этом шаге мы рассмотрим общие принципы организации такого поиска.
Очистка луковицы слой за слоем, как при поиске в ширину, может занять очень много времени. Поиск по алгоритму А*, подобно BFS, стремится найти кратчайший путь от начального к конечному состоянию. В отличие от предыдущей реализации BFS при поиске А* используется объединение функции затрат и эвристической функции, что позволяет сосредоточить поиск на путях, которые, скорее всего, быстро приведут к цели.
Функция затрат g(n) проверяет затраты, необходимые для того, чтобы добраться до определенного состояния. В случае с нашим лабиринтом это было бы количество шагов, которые пришлось бы пройти, чтобы добраться до нужного состояния.
Эвристическая функция h(n) позволяет оценить затраты, необходимые для того, чтобы из заданного состояния достичь целевого состояния. Можно доказать, что если h(n) - допустимая эвристическая функция, то найденный конечный путь будет оптимальным. Допустимая эвристическая функция - это функция, которая никогда не переоценивает затраты на достижение цели. На двумерной плоскости примером такой эвристической функции является расстояние по прямой линии, поскольку прямая линия - всегда кратчайший путь.
Для получения дополнительной информации об эвристике см. книгу: Рассел С., Норвиг Я. Искусственный интеллект: современный подход. 3-е изд. - М.: Вильямс, 2019
(Russell S., NonigP. Artificial Intelligence: A Modern Approach, 3rd ed. - Pearson, 2010).
Общие затраты для любого рассматриваемого состояния определяются функцией f(n), которая является простым объединением g(n) и h(n). В сущности, f(n) = g(n) + h(n). При выборе следующего рассматриваемого состояния из области поиска алгоритм А* выбирает состояние с наименьшим f(n). Именно этим он отличается от алгоритмов BFS и DFS.
На следующем шаге мы рассмотрим очереди с приоритетом.
