Существует хорошо известный алгоритм...

Существует хорошо известный алгоритм поиска, который относится к группе первый лучший, получивший наименование А (произносится "А со звездочкой"). Основная идея алгоритма состоит в использовании для каждого узла п на графе пространства состояний оценочной функции вида

f(n) = g(п) + h(n).

Здесь g(п) соответствует расстоянию на графе от узла п до начального состояния, a h(n) —оценка расстояния от п до узла, представляющего конечное (целевое) состояние. Чем меньше значение оценочной функции f(n), тем "лучше", т.е. узел п лежит на более коротком пути от исходного состояния к целевому. Идея алгоритма состоит в том, чтобы с помощью f(n) отыскать кратчайший путь на графе от исходного состояния к целевому.

Отсюда следует, что если h(n) — нижняя оценка действительного расстояния до целевого состояния, т.е. если h(n) никогда не дает завышенной оценки расстояния, то алгоритм А всегда отыщет оптимальный путь до цели при помощи оценочной функции f(n). Алгоритм, обладающий таким свойством, называется разрешимым (более подробное обсуждение этого вопроса читатель найдет в специальной литературе, в частности в работах Нмпьсона [Nilsson, 1980, Chapter 2] и Перла [Pearl, 1984, Chapter 2]).

Обозначения: