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

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

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

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

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

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

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

де:

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

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

інші мови
български: Алгоритъм А*
čeština: A*
français: Algorithme A*
Հայերեն: Ա*
Bahasa Indonesia: Algoritme a-star
italiano: Algoritmo A*
日本語: A*
한국어: A* 알고리즘
Nederlands: A*-algoritme
norsk: A*
polski: Algorytm A*
português: Algoritmo A*
русский: A*
Simple English: A* search algorithm
српски / srpski: A* algoritam