Припустима евристика

Евристика називається припустимою, якщо вона не переоцінює вартість маршруту. Тобто, оцінка шляху має знаходитись в проміжку , де дорівнює фактичній вартості. Якщо використана евристика припустима, але не монотонна, тоді для досліджених вершин може бути невідомий найкоротший шлях. Тому має зберігатись можливість повторно досліджувати таку вершину.

Монотонні евристики

Монотонна евристика має відповідати двом умовам:

•    не переоцінювати вартість (аби бути припустимою).
•    для кожної вершини та суміжної до неї вершини має виконуватись нерівність . Тут значить фактичну вартість шляху з до .

Другу умову також називають нерівністю трикутника.

Наприклад, евклідову відстань можна використовувати як монотонну евристику.

Властивості

Алгоритм А* має такі властивості:

•    припустимість: якщо розв'язок існує, він буде знайдений.
•    оптимальність: знайдений розв'язок завжди оптимальний. Якщо розв'язків декілька, буде знайдений один з них (в залежності від деталей реалізації алгоритму).
•    ефективність: не існує алгоритмів, які знаходять розв'язок швидше із застосуванням тієї ж евристичної функції (точніше: А* розкриває мінімальну кількість вершин.).

Часова складність

Зазвичай алгоритм А* переглядає лише частину вершин. Однак, в лабіринтах швидкодія наближається до найгіршого випадку. Швидкодія алгоритму істотно залежить від двох факторів: