Определения и условия
- Эвристика адекватна (admissible): для любой вершины $n$ верно $h(n)\le h^{\ast }(n)$, где $h^{\ast }(n)$ — истинная стоимость кратчайшего пути от $n$ до цели.
- Эвристика монотонна (consistent): для любого ребра $(n,m)$ выполнено $h(n)\le c(n,m)+h(m)$. Монотонность влечёт адекватность.
Доказательство корректности (оптимальности) A* при адекватной эвристике
1. Обозначения. Пусть старт $s$, цель $G$. Пусть A* извлекла из OPEN цель $G$ с записанной стоимостью $g(G)=C$. Пусть истинная оптимальная стоимость пути до цели равна $C^{\ast }=g^{\ast }(G)$. Предположим противное: $C>C^{\ast }$.
2. Рассмотрим некоторый оптимальный путь $s=v_0,v_1,\dots ,v_k=G$. Пусть $i$ — наименьший индекс такой, что $v_i$ находится в OPEN в момент извлечения $G$ (все $v_j$ с $j<i$ уже были извлечены/рассмотрены). Тогда для этого $v_i$ после обработки предыдущих вершин A* имеет точное значение $g(v_i)=g^{\ast }(v_i)$ (путь до $v_i$ уже раскрыт).
3. Оценим $f(v_i)=g(v_i)+h(v_i)$. По адекватности $h(v_i)\le h^{\ast }(v_i)$, поэтому
$$f(v_i)=g^{\ast }(v_i)+h(v_i)\le g^{\ast }(v_i)+h^{\ast }(v_i)=g^{\ast }(G)=C^{\ast }.$$ 4. Для цели $h(G)=0$, значит в момент извлечения $G$ её приоритет $f(G)=g(G)=C$. По предположению $C^{\ast }<C$, следовательно $f(v_i)\le C^{\ast }<C=f(G)$.
5. Но A* всегда извлекает из OPEN вершину с минимальным $f$-значением, значит $G$ не мог быть извлечён раньше, чем $v_i$. Противоречие с шагом 1. Следовательно предположение неверно и $C=C^{\ast }$. A* возвращает оптимальный путь.
Замечания про монотонность: если эвристика монотонна, то $f$-значения невозрастают по извлекаемым вершинам и каждый узел извлекается не более одного раза (не требуется повторного открытия). Если эвристика адекватна, но не монотонна, корректность сохраняется, но алгоритм может повторно открывать вершины (нужно допускать обновление g-значений и повторную вставку в OPEN).
Влияние изменения эвристики на время и память
- Точность эвристики: чем ближе $h(n)$ к $h^{\ast }(n)$ (но не превышает его), тем меньше вершин A* расширит. Граничные случаи:
- $h(n)\equiv 0$ → A* совпадает с алгоритмом Дейкстры, возможны максимальные расширения (много времени и памяти).
- $h(n)=h^{\ast }(n)$ (идеальная эвристика) → A* расширяет только вершины на оптимальном пути (минимум расширений и хранения).
- Монотонность: монотонная эвристика уменьшает число повторных открытий и тем самым снижает время; также облегчает реализацию (не нужна обработка релаксаций закрытых узлов).
- Стоимость вычисления эвристики: более информативная эвристика часто дороже по вычислению. Итоговое время = (число расширений)×(стоимость обработки одной вершины+стоимость вычисления $h$). Иногда лучше простая и дешёвая эвристика, чем дорогая, хоть и более точная.
- Память: A* хранит OPEN и CLOSED; число хранимых вершин примерно равно числу сгенерированных/необработанных узлов. Более информативная $h$ уменьшает это число. Однако вычисление сложной эвристики может требовать дополнительной памяти (например, таблицы для паттерн-эвристик).
- Неправильная (overestimating) эвристика: может снизить число расширений и время, но теряется гарантия оптимальности. Управляемая компромиссная стратегия — взвешенный A*: $f=g+ϵh$ с $ϵ>1$ даёт приближённый ответ быстрее; при выбранном $ϵ$ можно получить предел на субоптимальность.
Коротко
- Адекватность $h(n)\le h^{\ast }(n)$ гарантирует оптимальность A* (доказано выше).
- Монотонность упрощает реализацию и уменьшает повторные открытия.
- Чем информативнее (ближе к $h^{\ast }$) эвристика, тем меньше расширений, следовательно меньше времени и памяти, но обычно выше стоимость вычисления эвристики; превышение $h^{\ast }$ даёт выигрыш в ресурсах ценой потери оптимальности.