==Доказательство оптимальности и корректности==
Алгоритм A* и допустим, и обходит при этом минимальное количество вершин, благодаря тому, что он работает с «оптимистичной» оценкой пути через вершинуПолное доказательство расположено [http://www.cs.auckland.ac.nz/compsci709s2c/resources/Mike.d/astarNilsson. Оптимистичной в том смысле, что, если он пойдёт через эту вершину, у алгоритма «есть шанс», что реальная стоимость результата будет равна этой оценке, но никак не меньшеpdf здесь]. Но, поскольку A* является информированным алгоритмом, такое равенство может быть вполне возможнымЗдесь приведем основные факты. Когда A* завершает поиск, Алгоритм является допустимым(корректным) если он, согласно определению, нашёл гарантированно находит оптимальный путь, истинная стоимость которого меньше, чем оценка стоимости любого пути через любой открытый узелиз S до целевой вершины. Но поскольку эти оценки являются оптимистичными, соответствующие узлы можно без сомнений отбросить. Иначе говоря, A* никогда не упустит возможности минимизировать длину пути, Допустимые алгоритмы могут различаться числом рассмотренных вершин и потому является допустимымпорядком просмотра вершин.Допустимость А*Предположим теперь, что некий алгоритм B вернул Лемма 1. Для любой незакрытой вершины n и любого оптимального пути P из S в качестве результата путьn существует открытая вершина n', длина которого больше оценки стоимости лежащая на этом пути через некоторую вершину. На основании эвристической информации, для алгоритма B нельзя исключить возможность, что этот путь имел и меньшую реальную длину, чем результаткоторой найденная стоимость пути из S оптимальна.Теорема 1. Соответственно, пока алгоритм B просмотрел меньше вершин, чем A*, он Если для любой вершины эвристика не будет допустимым. Итакпереоценивает настоящую стоимость минимального пути до целевой вершины, Aто А* проходит наименьшее количество вершин графа среди допустимых алгоритмов, использующих такую же точную (или менее точную) эвристикудопустим.
==Ссылки==
