Изменения

Алгоритм является допустимым(корректным) если он гарантированно находит оптимальный путь из S до целевой вершины.

Допустимые алгоритмы могут различаться числом рассмотренных вершин и порядком просмотра вершин.

Допустимость А*

Лемма 1. Для любой незакрытой вершины n и любого оптимального пути P из S в n существует открытая вершина n', лежащая на этом пути, для которой найденная стоимость пути из S оптимальна.

Теорема 1. Если для любой вершины эвристика не переоценивает настоящую стоимость минимального пути до целевой вершины, то А* допустим.

Оптимальность А*

Лемма 2. Предположим, что в процессе работы А* вершина n была закрыта и эвристика монотонна. Тогда вычисленный до нее путь из стартовой вершины оптимален.