76
правок
Изменения
Нет описания правки
Алгоритм '''А*'''("A star", "А звёздочка") -- информированный алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
==Эвристика==
В процессе работы алгоритма для вершин используется функция <tex>f(v) = g(v) + h(v)</tex>, где <tex>g(v)</tex> - наименьшая стоимость пути в <tex>v </tex> из стартовой вершины, <tex>h(v)</tex> - эвристическое приближение стоимости пути от v до конечной цели. <tex>h(v)</tex> должна быть эвристически допустимой, то есть не должна переоценивать рассояние до цели. Например, если наш граф является некоторой картой, разбитой сеткой, то эвристику можно назначить минимальным числом перемещений из клетки в клетку.
К примеру, если <tex>(h(v) == 0)</tex>, то А* превращается в [http://chernykh.net/images/stories/Person/deiksteira.jpg Дейкстру ]. Если <tex>h(v)</tex> всегда меньше истинной стоимости пути до цели, то А* гарантированно найдет кратчайший путь, причем чем меньше разница между эвристикой и истинной стоимостью, тем меньше вершин рассмотрит алгоритм. Если выйдет так, что эвристика превысила истинную стоимость, то А* будет работать быстрее, но возможно найдет не лучший путь, хотя его можно считать "хорошим" и если производительность предпочтительнее точности можно использовать такую эвристику.
==Псевдокод==
==Доказательство оптимальности и корректности==
Полное доказательство расположено [http://www.cs.auckland.ac.nz/compsci709s2c/resources/Mike.d/astarNilsson.pdf здесь]. Здесь приведем основные факты.
Алгоритм является допустимым(корректным) если он гарантированно находит оптимальный путь из <tex>S </tex> до целевой вершины.
Допустимые алгоритмы могут различаться числом рассмотренных вершин и порядком просмотра вершин.
Допустимость А*
Лемма 1. Для любой незакрытой вершины <tex>n </tex> и любого оптимального пути <tex>P </tex> из <tex>S </tex> в <tex>n </tex> существует открытая вершина <tex>n'</tex>, лежащая на этом пути, для которой найденная стоимость пути из <tex>S </tex> оптимальна.
Теорема 1. Если для любой вершины эвристика не переоценивает настоящую стоимость минимального пути до целевой вершины, то А* допустим.
Оптимальность А*
Лемма 2. Предположим, что в процессе работы А* вершина <tex>n </tex> была закрыта и эвристика монотонна. Тогда вычисленный до нее путь из стартовой вершины оптимален.
Теорема 2. Пусть А допустимый алгоритм информированный не больше чем А* и эвристика допустима и монотонна.Тогда если А* рассмотрела в процессе выполнения некоторую вершину <tex>n</tex>, то А тоже рассмотрит эту вершину.
==Ссылки==
