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

Алгоритм пошуку A*
Клас	Алгоритми пошуку, Алгоритми на графах
Структура даних	граф
Найгірша швидкодія
Оптимальний	так

Алгоритм пошуку А* («А зірочка» або англ. «A star») — належить до евристичних алгоритмів пошуку. Використовується для пошуку найкоротшого шляху між двома вершинами графу з додатніми вагами ребер. Описаний 1968 р. Пітером Хартом, Нільсом Нільсоном та Бертрамом Рафаелєм.

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

Ідея алгоритму

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

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

f(x)=g(x)+h(x)

де:

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

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

Принцип дії

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

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

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

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

Коли вершину $x$ буде повністю досліджено (або розкрито, релаксовано), суміжні з нею вершини додаються до списку відомих вершин, а сама вершина додається в список повністю досліджених. Вказівники на попередню вершину встановлюються на $x$ . Суміжні вершини, які вже є в списку повністю досліджених вершин, до списку відомих не додаються, а зворотні вказівники не змінюються. Суміжні вершини, які вже є в списку відомих, лише оновлюються (значення $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* використовується як для планування шляхів, так і в комп'ютерних іграх. Для планування шляхів, як евристична функція використовується лінійна відстань до цілі, оскільки згідно з нерівністю трикутника вона дає оптимальні оцінки. Також алгоритм А* використовується в іграх, в яких необхідно досягти наперед заданий стан, наприклад, в задачі про вісім ферзів, або в п'ятнашках. Евристикою може слугувати, наприклад, кількість невірно пересунутих камінців.

Евристичні функції

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

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

Докладніше: Прийнятна евристика

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

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

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

не переоцінювати вартість (аби бути припустимою).
для кожної вершини $k$ та суміжної до неї вершини $k'$ має виконуватись нерівність $h(k)\leq c(k,k')+h(k')$ . Тут $c(k,k')$ значить фактичну вартість шляху з $k$ до $k'$ .

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

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

Властивості

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

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

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

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

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

Нехай $V$ — множина вершин в графі, інформація про вершини та ребра доступна до початку роботи алгоритму; використана евристична функціїя — монотонна. Список відомих вершин реалізований як бінарна купа, список досліджених — як масив. Тоді алгоритм А* має квадратичний час роботи в найгіршому випадку:

{\mathcal {O}}(\vert V\vert ^{2}).

Функція openlist.decreaseKey може бути оптимізована. Якщо кожна вершина зберігатиме вказівник на відповідний об'єкт в купі, то час роботи функції зменшиться з лінійного до логарифмічного, а загальний час роботи алгоритму — до лінійно-логарифмічного:

{\mathcal {O}}(\vert V\vert \cdot \log \vert V\vert ).

Недоліки

Основним недоліком алгоритму А* є потреба в пам'яті для збереження всіх відомих та досліджених вершин. Через це алгортим А* непридатний для багатьох задач. Наприклад, повний граф ходів для гри П'ятнашки має $16!=20\ 922\ 789\ 888\ 000$ вершин.

Альтернативні алгоритми

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

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

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

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

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

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

Література

Stuart Russell, Peter Norvig: Artificial Intelligence: A Modern Approach [Архівовано 28 лютого 2011 у Wayback Machine.], 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* [Архівовано 30 листопада 2021 у Wayback Machine.] на каналі "Computerphile" на YouTube (англ.)
Пошук маршрутів з поворотами [Архівовано 20 січня 2011 у Wayback Machine.] (англ.)
Опис алгоритму А* [Архівовано 4 квітня 2012 у WebCite] (англ.)

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

Зміст

Ідея алгоритму

Принцип дії

Застосування