Изменения

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

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

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

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