Алгоритм пошуку A*

Алгоритм А* спершу відвідує ті вершини, які ймовірно ведуть до найкоротшого шляху до мети. Аби розпізнати такі вершини, кожній відомій вершині ${\displaystyle x}$ співставляється значення ${\displaystyle f(x)}$, яке дорівнює довжині найкоротшого шляху від початкової вершини до кінцевої, який пролягає через обрану вершину. Вершини з найменшим значенням ${\displaystyle f}$ обираються в першу чергу.

Функція ${\displaystyle f(x)}$ для вершини ${\displaystyle x}$ визначається так:

${\displaystyle f(x)=g(x)+h(x)}$

де:

• ${\displaystyle g(x)}$ функція, значення якої дорівнюють вартості шляху від початкової вершини до ${\displaystyle x}$,
• ${\displaystyle h(x)}$ евристична функція, оцінює вартість шляху від вершини ${\displaystyle x}$ до кінцевої.

Використана евристика не повинна давати завищену оцінку вартості шляху. Прикладом оцінки може служити пряма лінія: загальний шлях не може бути коротшим за пряму лінію.

Ілюстрація пошуку A* на прикладі задачі планування шляху. Порожні сині кола — відомі вершини, зірочки — повністю досліджені вершини. Колір вершин означає відстань — червоні близько, зелені далеко. Алгоритм спочатку пробує дійти до цілі навпростець, а наткнувшись на перешкоду досліджує альтернативні шляхи використовуючи відомі вершини.

Алгоритм ділить вершини на три класи:

• невідомі вершини: ці вершини ще не були знайдені. Ще не відомий шлях до них. На початку роботи алгоритму всі вершини, окрім початкової, належать до класу невідомих.
• відомі вершини (OpenList): вже відомий (можливо не оптимальний) шлях до цих вершин. Всі відомі вершини разом зі значеннями ${\displaystyle f}$ зберігаються в списку. З цього списку вибираються, в першу чергу, найперспективніші вершини. Конкретна реалізація цього списку має суттєвий вплив на швидкодію алгоритму, і зазвичай має вигляд черги з пріоритетом (наприклад, бінарна купа). На початку роботи алгоритму до відомих вершин належить лише початкова вершина.
• повністю досліджені вершини (ClosedList): до цих вершин вже відомий найкоротший шлях. Повністю досліджені вершини додаються до так званого замкненого списку, аби запобігти багаторазовому дослідженню вже досліджених вершин. Список повністю досліджених вершин на початку роботи алгоритму порожній.

Кожна відома або повністю досліджена вершина має вказівник на попередні вершини. Завдяки цьому вказівникові, можна пройти шляхом від цієї до початкової вершини.

Коли вершину ${\displaystyle x}$ буде повністю досліджено (або розкрито, релаксовано), суміжні з нею вершини додаються до списку відомих вершин, а сама вершина додається в список повністю досліджених. Вказівники на попередню вершину встановлюються на ${\displaystyle x}$. Суміжні вершини, які вже є в списку повністю досліджених вершин, до списку відомих не додаються, а зворотні вказівники не змінюються. Суміжні вершини, які вже є в списку відомих, лише оновлюються (значення ${\displaystyle f}$ та вказівник на попередню вершину), якщо знайдений до них шлях коротший за вже відомий.

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

Відтворений за зворотніми вказівниками знайдений шлях починається з кінцевої вершини та прямує до початкової. Аби одразу отримати шлях в правильному напрямі, з початкової вершини до кінцевої, в умовах задачі треба переставити місцями початок та кінець. Якщо шукати шлях починаючи з кінцевої вершини, відтворений список починатиметься з початкової вершини й прямуватиме до кінцевої.

Алгоритм пошуку А* можна представити у вигляді псевдокоду:

program a-star
    // Ініціалізація списку відомих вершин, список досліджених порожній
    // (f-значення початкової вершини відсутнє)
    openlist.enqueue(startknote, 0)
    // цей шлях буде пройдений доки:
    // - буде знайдено оптимальний розв'язок або
    // - встановлено, що розв'язків не існує
    repeat
        // Вилучити вершину з найменшим f-значенням
        currentNode := openlist.removeMin()
        // Досягнута кінцева вершина?
        if currentNode == endknote then
            return PathFound
        // Якщо кінцева вершина не досягнута: додати суміжні
        // до поточної вершини в список відомих
        expandNode(currentNode)
        // поточна вершина вже повністю досліджена
        closedlist.add(currentNode)
    until openlist.isEmpty()
    // список відомих порожній, розв'язків не існує
    return NoPathFound
end

// перевіряє суміжні вершини та додає до списку відомих якщо:
// - суміжні вершини зустрічаються вперше або
// - знайдений кращий шлях до цієї вершини
function expandNode(currentNode)
    foreach successor of currentNode
        // пропустити, якщо вершина вже є списку досліджених
        if closedlist.contains(successor) then
            continue
        // обчислити значення g нового шляху: 
        // значення g попередньої вершини + вартість щойно пройденого ребра
        tentative_g = g(currentNode) + c(currentNode, successor)
        // якщо суміжна вершина вже в списку відомих,
        //  але знайдений шлях не кращий за вже відомий - пропустити
        if openlist.contains(successor) and tentative_g >= g[successor] then
            continue
        // встановити вказівник на попередню вершину та зберегти g
        successor.predecessor := currentNode
        g[successor] = tentative_g
        // оновити значення f вершини у списку відомих
        // або додати вершину до списку відомих
        f := tentative_g + h(successor)
        if openlist.contains(successor) then
            openlist.decreaseKey(successor, f)
        else
            openlist.enqueue(successor, f)
    end
end

Алгоритм пошуку А* знаходить оптимальний шлях між двома вершинами в графі. В залежності від функції вартості, яка задає кожному ребру його «вагу», оптимальність може означати найкоротший, найшвидший або навіть найпростіший шлях. Теоретично, алгоритм може розв'язувати всі задачі, які можна представити у вигляді задачі пошуку оптимального шляху на графі. Обмеження алгоритму А* описані в розділі Недоліки.

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

Існує два види евристичних функцій, які використовують в алгоритмі А*: припустимі та монотонні. Монотонні евристики також припустимі. Монотонність є сильнішою характеристикою припустимості. Зазвичай, використовують монотонні евристичні функції. Наприклад, пряма відстань між двома містами монотонна.

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

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

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

Деякі алгоритми намагаються уникнути потреби у великих обсягах пам'яті. Серед них:

• IDA* (A* з ітеративним заглибленям), варіант ітеративного пошуку в глибину;
• RBFS (рекурсивний пошук за найкращим збігом, англ. Recursive Best-First Search), вимагає лінійну кількість пам'яті в залежності від довжини розв'язку
• MA* (A* з обмеженням пам'яті), SMA* (Simplified MA*), використовують лише наперед виділений обсяг пам'яті.

Ці алгоритми обмежують потребу в пам'яті за рахунок швидкодії. За деяких обставин, не обов'язково зберігати всі вершини в пам'яті. Погані вершини можуть бути забуті і згодом можуть бути наново відтворені. При використанні монотонної евристики та за умови наявності достатньої кількості пам'яті, ці алгоритми оптимальні. При надто суворих обмеженнях пам'яті, оптимальний розв'язок може бути не знайдений.

Алгоритм пошуку D* (динамічний А*) є вдосконаленням алгоритму А*. Цей алгоритм враховує інформацію про структуру графа.

Серед інших алгоритмів можна назвати алгоритм Беллмана-Форда (дозволяє ребра з від'ємними вагами) або алгоритм Флойда-Воршала (знаходить найкоротший шлях між всіма парами вершин).

• Stuart Russell, Peter Norvig: Artificial Intelligence: A Modern Approach, 2004, Prentice Hall, ISBN 3-8273-7089-2
• P. E. Hart, N. J. Nilsson, B. Raphael: A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics SSC4 (2), pp. 100—107, 1968.
• P. E. Hart, N. J. Nilsson, B. Raphael: Correction to «A Formal Basis for the Heuristic Determination of Minimum Cost Paths», SIGART Newsletter, 37, pp. 28-29, 1972.
• Anthony Stentz: Optimal and Efficient Path Planning for Partially-Known Environments, Original D* paper, ICRA International Conference on Robotics and Automation, 1994.

• Задача комівояжера
• Алгоритм Дейкстри

• Пояслення алгоритму A* на каналі "Computerphile" на YouTube (англ.)
• Пошук маршрутів з поворотами (англ.)
• Опис алгоритму А* (англ.)