76
правок
Изменения
→Доказательство оптимальности и корректности
Лемма 1. Для любой незакрытой вершины n и любого оптимального пути P из S в n существует открытая вершина n', лежащая на этом пути, для которой найденная стоимость пути из S оптимальна.
Теорема 1. Если для любой вершины эвристика не переоценивает настоящую стоимость минимального пути до целевой вершины, то А* допустим.
Оптимальность А*
Лемма 2. Предположим, что в процессе работы А* вершина n была закрыта и эвристика монотонна. Тогда вычисленный до нее путь из стартовой вершины оптимален.
Теорема 2. Пусть А допустимый алгоритм информированный не больше чем А* и эвристика допустима и монотонна.Тогда если А* рассмотрела в процессе выполнения некоторую вершину n, то А тоже рассмотрит эту вершину.
==Ссылки==
