Алгоритм пошуку А* («А зірочка» або англ. «A star») — належить до евристичних алгоритмів пошуку. Використовується для пошуку найкоротшого шляху між двома вершинами графу з додатніми вагами ребер. Описаний 1968 р. , та .
Клас | Алгоритми пошуку, Алгоритми на графах |
---|---|
Структура даних | граф |
Найгірша швидкодія | |
Оптимальний | так |
Алгоритм використовує допоміжну функцію (евристику), аби скеровувати напрям пошуку та скорочувати його тривалість. Алгоритм повний в тому сенсі, що завжди знаходить оптимальний розв'язок, якщо він існує.
Ідея алгоритму
Алгоритм А* спершу відвідує ті вершини, які ймовірно ведуть до найкоротшого шляху до мети. Аби розпізнати такі вершини, кожній відомій вершині співставляється значення , яке дорівнює довжині найкоротшого шляху від початкової вершини до кінцевої, який пролягає через обрану вершину. Вершини з найменшим значенням обираються в першу чергу.
Функція для вершини визначається так:
де:
- функція, значення якої дорівнюють вартості шляху від початкової вершини до ,
- евристична функція, оцінює вартість шляху від вершини до кінцевої.
Використана евристика не повинна давати завищену оцінку вартості шляху. Прикладом оцінки може служити пряма лінія: загальний шлях не може бути коротшим за пряму лінію.
Принцип дії
Алгоритм ділить вершини на три класи:
- невідомі вершини: ці вершини ще не були знайдені. Ще не відомий шлях до них. На початку роботи алгоритму всі вершини, окрім початкової, належать до класу невідомих.
- відомі вершини (OpenList): вже відомий (можливо не оптимальний) шлях до цих вершин. Всі відомі вершини разом зі значеннями зберігаються в списку. З цього списку вибираються, в першу чергу, найперспективніші вершини. Конкретна реалізація цього списку має суттєвий вплив на швидкодію алгоритму, і зазвичай має вигляд черги з пріоритетом (наприклад, бінарна купа). На початку роботи алгоритму до відомих вершин належить лише початкова вершина.
- повністю досліджені вершини (ClosedList): до цих вершин вже відомий найкоротший шлях. Повністю досліджені вершини додаються до так званого замкненого списку, аби запобігти багаторазовому дослідженню вже досліджених вершин. Список повністю досліджених вершин на початку роботи алгоритму порожній.
Кожна відома або повністю досліджена вершина має вказівник на попередні вершини. Завдяки цьому вказівникові, можна пройти шляхом від цієї до початкової вершини.
Коли вершину буде повністю досліджено (або розкрито, релаксовано), суміжні з нею вершини додаються до списку відомих вершин, а сама вершина додається в список повністю досліджених. Вказівники на попередню вершину встановлюються на . Суміжні вершини, які вже є в списку повністю досліджених вершин, до списку відомих не додаються, а зворотні вказівники не змінюються. Суміжні вершини, які вже є в списку відомих, лише оновлюються (значення та вказівник на попередню вершину), якщо знайдений до них шлях коротший за вже відомий.
Алгоритм зупиняється, коли кінцева вершина потрапляє до списку повністю досліджених вершин. Знайдений шлях відтворюється за допомогою вказівників на попередню вершину. Якщо список відомих вершин порожніє, то розв'язку задачі не існує й алгоритм припиняє пошук.
Відтворений за зворотніми вказівниками знайдений шлях починається з кінцевої вершини та прямує до початкової. Аби одразу отримати шлях в правильному напрямі, з початкової вершини до кінцевої, в умовах задачі треба переставити місцями початок та кінець. Якщо шукати шлях починаючи з кінцевої вершини, відтворений список починатиметься з початкової вершини й прямуватиме до кінцевої.
Алгоритм пошуку А* можна представити у вигляді псевдокоду:
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* використовується як для планування шляхів, так і в комп'ютерних іграх. Для планування шляхів, як евристична функція використовується лінійна відстань до цілі, оскільки згідно з нерівністю трикутника вона дає оптимальні оцінки. Також алгоритм А* використовується в іграх, в яких необхідно досягти наперед заданий стан, наприклад, в задачі про вісім ферзів, або в п'ятнашках. Евристикою може слугувати, наприклад, кількість невірно пересунутих камінців.
Евристичні функції
Існує два види евристичних функцій, які використовують в алгоритмі А*: припустимі та монотонні. Монотонні евристики також припустимі. Монотонність є сильнішою характеристикою припустимості. Зазвичай, використовують монотонні евристичні функції. Наприклад, пряма відстань між двома містами монотонна.
Припустима евристика
Евристика називається припустимою, якщо вона не переоцінює вартість маршруту. Тобто, оцінка шляху має знаходитись в проміжку , де дорівнює фактичній вартості. Якщо використана евристика припустима, але не монотонна, тоді для досліджених вершин може бути невідомий найкоротший шлях. Тому має зберігатись можливість повторно досліджувати таку вершину.
Монотонні евристики
Монотонна евристика має відповідати двом умовам:
- не переоцінювати вартість (аби бути припустимою).
- для кожної вершини та суміжної до неї вершини має виконуватись нерівність . Тут значить фактичну вартість шляху з до .
Другу умову також називають нерівністю трикутника.
Наприклад, евклідову відстань можна використовувати як монотонну евристику.
Властивості
Алгоритм А* має такі властивості:
- припустимість: якщо розв'язок існує, він буде знайдений.
- оптимальність: знайдений розв'язок завжди оптимальний. Якщо розв'язків декілька, буде знайдений один з них (в залежності від деталей реалізації алгоритму).
- ефективність: не існує алгоритмів, які знаходять розв'язок швидше із застосуванням тієї ж евристичної функції (точніше: А* розкриває мінімальну кількість вершин.).
Часова складність
Зазвичай алгоритм А* переглядає лише частину вершин. Однак, в лабіринтах швидкодія наближається до найгіршого випадку. Швидкодія алгоритму суттєво залежить від двох факторів:
- Точність евристичної функції: Якщо евристика не монотонна, час роботи алгоритму буде експоненційним, оскільки вершини можуть переглядатись кількаразово Чим точніша оцінка вартості, тим менше вершин буде досліджено.
- Реалізація списків відомих та досліджених вершин: Найбільш витратними операціями в алгоритмі є операції додавання, вилучення та зміни елементів в списках відомих та досліджених вершин. На їхню швидкодію істотно впливають конкретні реалізації цих структур даних.
Нехай — множина вершин в графі, інформація про вершини та ребра доступна до початку роботи алгоритму; використана евристична функціїя — монотонна. Список відомих вершин реалізований як бінарна купа, список досліджених — як масив. Тоді алгоритм А* має квадратичний час роботи в найгіршому випадку:
Функція openlist.decreaseKey може бути оптимізована. Якщо кожна вершина зберігатиме вказівник на відповідний об'єкт в купі, то час роботи функції зменшиться з лінійного до логарифмічного, а загальний час роботи алгоритму — до лінійно-логарифмічного:
Недоліки
Основним недоліком алгоритму А* є потреба в пам'яті для збереження всіх відомих та досліджених вершин. Через це алгортим А* непридатний для багатьох задач. Наприклад, повний граф ходів для гри П'ятнашки має вершин.
Альтернативні алгоритми
Алгоритм пошуку А* може бути замінений алгоритмом Дейкстри або жадібним алгоритмом. Алгоритм Дейкстри не використовує евристичних функцій і обирає наступну вершину в залежності від поточної вартості шляху. Натомість, жадібний алгоритм обирає наступну вершину лише на основі оцінки можливого маршруту через неї. Тому алгоритм Дейкстри можна застосовувати для пошуку шляху коли кінцева вершина невідома (наприклад, пошук заправочної станції), і використання евристичної функції неможливе.
Деякі алгоритми намагаються уникнути потреби у великих обсягах пам'яті. Серед них:
- (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,
- 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: , Original D* paper, International Conference on Robotics and Automation, 1994.
Див. також
Посилання
- Пояслення алгоритму A* [ 30 листопада 2021 у Wayback Machine.] на каналі "Computerphile" на YouTube (англ.)
- Пошук маршрутів з поворотами [ 20 січня 2011 у Wayback Machine.] (англ.)
- Опис алгоритму А* [Архівовано 4 квітня 2012 у WebCite] (англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm poshuku A A zirochka abo angl A star nalezhit do evristichnih algoritmiv poshuku Vikoristovuyetsya dlya poshuku najkorotshogo shlyahu mizh dvoma vershinami grafu z dodatnimi vagami reber Opisanij 1968 r ta Algoritm poshuku A KlasAlgoritmi poshuku Algoritmi na grafahStruktura danihgrafNajgirsha shvidkodiyaO V log V displaystyle mathcal O V cdot log V Optimalnijtak Algoritm vikoristovuye dopomizhnu funkciyu evristiku abi skerovuvati napryam poshuku ta skorochuvati jogo trivalist Algoritm povnij v tomu sensi sho zavzhdi znahodit optimalnij rozv yazok yaksho vin isnuye Ideya algoritmuAlgoritm A spershu vidviduye ti vershini yaki jmovirno vedut do najkorotshogo shlyahu do meti Abi rozpiznati taki vershini kozhnij vidomij vershini x displaystyle x spivstavlyayetsya znachennya f x displaystyle f x yake dorivnyuye dovzhini najkorotshogo shlyahu vid pochatkovoyi vershini do kincevoyi yakij prolyagaye cherez obranu vershinu Vershini z najmenshim znachennyam f displaystyle f obirayutsya v pershu chergu Funkciya f x displaystyle f x dlya vershini x displaystyle x viznachayetsya tak f x g x h x displaystyle f x g x h x de g x displaystyle g x funkciya znachennya yakoyi dorivnyuyut vartosti shlyahu vid pochatkovoyi vershini do x displaystyle x h x displaystyle h x evristichna funkciya ocinyuye vartist shlyahu vid vershini x displaystyle x do kincevoyi Vikoristana evristika ne povinna davati zavishenu ocinku vartosti shlyahu Prikladom ocinki mozhe sluzhiti pryama liniya zagalnij shlyah ne mozhe buti korotshim za pryamu liniyu Princip diyiIlyustraciya poshuku A na prikladi zadachi Porozhni sini kola vidomi vershini zirochki povnistyu doslidzheni vershini Kolir vershin oznachaye vidstan chervoni blizko zeleni daleko Algoritm spochatku probuye dijti do cili navprostec a natknuvshis na pereshkodu doslidzhuye alternativni shlyahi vikoristovuyuchi vidomi vershini Algoritm dilit vershini na tri klasi nevidomi vershini ci vershini she ne buli znajdeni She ne vidomij shlyah do nih Na pochatku roboti algoritmu vsi vershini okrim pochatkovoyi nalezhat do klasu nevidomih vidomi vershini OpenList vzhe vidomij mozhlivo ne optimalnij shlyah do cih vershin Vsi vidomi vershini razom zi znachennyami f displaystyle f zberigayutsya v spisku Z cogo spisku vibirayutsya v pershu chergu najperspektivnishi vershini Konkretna realizaciya cogo spisku maye suttyevij vpliv na shvidkodiyu algoritmu i zazvichaj maye viglyad chergi z prioritetom napriklad binarna kupa Na pochatku roboti algoritmu do vidomih vershin nalezhit lishe pochatkova vershina povnistyu doslidzheni vershini ClosedList do cih vershin vzhe vidomij najkorotshij shlyah Povnistyu doslidzheni vershini dodayutsya do tak zvanogo zamknenogo spisku abi zapobigti bagatorazovomu doslidzhennyu vzhe doslidzhenih vershin Spisok povnistyu doslidzhenih vershin na pochatku roboti algoritmu porozhnij Kozhna vidoma abo povnistyu doslidzhena vershina maye vkazivnik na poperedni vershini Zavdyaki comu vkazivnikovi mozhna projti shlyahom vid ciyeyi do pochatkovoyi vershini Koli vershinu x displaystyle x bude povnistyu doslidzheno abo rozkrito relaksovano sumizhni z neyu vershini dodayutsya do spisku vidomih vershin a sama vershina dodayetsya v spisok povnistyu doslidzhenih Vkazivniki na poperednyu vershinu vstanovlyuyutsya na x displaystyle x Sumizhni vershini yaki vzhe ye v spisku povnistyu doslidzhenih vershin do spisku vidomih ne dodayutsya a zvorotni vkazivniki ne zminyuyutsya Sumizhni vershini yaki vzhe ye v spisku vidomih lishe onovlyuyutsya znachennya f displaystyle f ta vkazivnik na poperednyu vershinu yaksho znajdenij do nih shlyah korotshij za vzhe vidomij Algoritm zupinyayetsya koli kinceva vershina potraplyaye do spisku povnistyu doslidzhenih vershin Znajdenij shlyah vidtvoryuyetsya za dopomogoyu vkazivnikiv na poperednyu vershinu Yaksho spisok vidomih vershin porozhniye to rozv yazku zadachi ne isnuye j algoritm pripinyaye poshuk Vidtvorenij za zvorotnimi vkazivnikami znajdenij shlyah pochinayetsya z kincevoyi vershini ta pryamuye do pochatkovoyi Abi odrazu otrimati shlyah v pravilnomu napryami z pochatkovoyi vershini do kincevoyi v umovah zadachi treba perestaviti miscyami pochatok ta kinec Yaksho shukati shlyah pochinayuchi z kincevoyi vershini vidtvorenij spisok pochinatimetsya z pochatkovoyi vershini j pryamuvatime do kincevoyi Algoritm poshuku A mozhna predstaviti u viglyadi psevdokodu program a star Inicializaciya spisku vidomih vershin spisok doslidzhenih porozhnij f znachennya pochatkovoyi vershini vidsutnye openlist enqueue startknote 0 cej shlyah bude projdenij doki bude znajdeno optimalnij rozv yazok abo vstanovleno sho rozv yazkiv ne isnuye repeat Viluchiti vershinu z najmenshim f znachennyam currentNode openlist removeMin Dosyagnuta kinceva vershina if currentNode endknote then return PathFound Yaksho kinceva vershina ne dosyagnuta dodati sumizhni do potochnoyi vershini v spisok vidomih expandNode currentNode potochna vershina vzhe povnistyu doslidzhena closedlist add currentNode until openlist isEmpty spisok vidomih porozhnij rozv yazkiv ne isnuye return NoPathFound end pereviryaye sumizhni vershini ta dodaye do spisku vidomih yaksho sumizhni vershini zustrichayutsya vpershe abo znajdenij krashij shlyah do ciyeyi vershini function expandNode currentNode foreach successor of currentNode propustiti yaksho vershina vzhe ye spisku doslidzhenih if closedlist contains successor then continue obchisliti znachennya g novogo shlyahu znachennya g poperednoyi vershini vartist shojno projdenogo rebra tentative g g currentNode c currentNode successor yaksho sumizhna vershina vzhe v spisku vidomih ale znajdenij shlyah ne krashij za vzhe vidomij propustiti if openlist contains successor and tentative g gt g successor then continue vstanoviti vkazivnik na poperednyu vershinu ta zberegti g successor predecessor currentNode g successor tentative g onoviti znachennya f vershini u spisku vidomih abo dodati vershinu do spisku vidomih f tentative g h successor if openlist contains successor then openlist decreaseKey successor f else openlist enqueue successor f end endZastosuvannyaAlgoritm poshuku A znahodit optimalnij shlyah mizh dvoma vershinami v grafi V zalezhnosti vid funkciyi vartosti yaka zadaye kozhnomu rebru jogo vagu optimalnist mozhe oznachati najkorotshij najshvidshij abo navit najprostishij shlyah Teoretichno algoritm mozhe rozv yazuvati vsi zadachi yaki mozhna predstaviti u viglyadi zadachi poshuku optimalnogo shlyahu na grafi Obmezhennya algoritmu A opisani v rozdili Nedoliki Algoritm A vikoristovuyetsya yak dlya planuvannya shlyahiv tak i v komp yuternih igrah Dlya planuvannya shlyahiv yak evristichna funkciya vikoristovuyetsya linijna vidstan do cili oskilki zgidno z nerivnistyu trikutnika vona daye optimalni ocinki Takozh algoritm A vikoristovuyetsya v igrah v yakih neobhidno dosyagti napered zadanij stan napriklad v zadachi pro visim ferziv abo v p yatnashkah Evristikoyu mozhe sluguvati napriklad kilkist nevirno peresunutih kaminciv Evristichni funkciyiIsnuye dva vidi evristichnih funkcij yaki vikoristovuyut v algoritmi A pripustimi ta monotonni Monotonni evristiki takozh pripustimi Monotonnist ye silnishoyu harakteristikoyu pripustimosti Zazvichaj vikoristovuyut monotonni evristichni funkciyi Napriklad pryama vidstan mizh dvoma mistami monotonna Pripustima evristika Dokladnishe Prijnyatna evristika Evristika nazivayetsya pripustimoyu yaksho vona ne pereocinyuye vartist marshrutu Tobto ocinka shlyahu maye znahoditis v promizhku 0 k displaystyle 0 k de k displaystyle k dorivnyuye faktichnij vartosti Yaksho vikoristana evristika pripustima ale ne monotonna todi dlya doslidzhenih vershin mozhe buti nevidomij najkorotshij shlyah Tomu maye zberigatis mozhlivist povtorno doslidzhuvati taku vershinu Monotonni evristiki Monotonna evristika maye vidpovidati dvom umovam ne pereocinyuvati vartist abi buti pripustimoyu dlya kozhnoyi vershini k displaystyle k ta sumizhnoyi do neyi vershini k displaystyle k maye vikonuvatis nerivnist h k c k k h k displaystyle h k leq c k k h k Tut c k k displaystyle c k k znachit faktichnu vartist shlyahu z k displaystyle k do k displaystyle k Drugu umovu takozh nazivayut nerivnistyu trikutnika Napriklad evklidovu vidstan mozhna vikoristovuvati yak monotonnu evristiku VlastivostiAlgoritm A maye taki vlastivosti pripustimist yaksho rozv yazok isnuye vin bude znajdenij optimalnist znajdenij rozv yazok zavzhdi optimalnij Yaksho rozv yazkiv dekilka bude znajdenij odin z nih v zalezhnosti vid detalej realizaciyi algoritmu efektivnist ne isnuye algoritmiv yaki znahodyat rozv yazok shvidshe iz zastosuvannyam tiyeyi zh evristichnoyi funkciyi tochnishe A rozkrivaye minimalnu kilkist vershin Chasova skladnist Zazvichaj algoritm A pereglyadaye lishe chastinu vershin Odnak v labirintah shvidkodiya nablizhayetsya do najgirshogo vipadku Shvidkodiya algoritmu suttyevo zalezhit vid dvoh faktoriv Tochnist evristichnoyi funkciyi Yaksho evristika ne monotonna chas roboti algoritmu bude eksponencijnim oskilki vershini mozhut pereglyadatis kilkarazovo Chim tochnisha ocinka vartosti tim menshe vershin bude doslidzheno Realizaciya spiskiv vidomih ta doslidzhenih vershin Najbilsh vitratnimi operaciyami v algoritmi ye operaciyi dodavannya viluchennya ta zmini elementiv v spiskah vidomih ta doslidzhenih vershin Na yihnyu shvidkodiyu istotno vplivayut konkretni realizaciyi cih struktur danih Nehaj V displaystyle V mnozhina vershin v grafi informaciya pro vershini ta rebra dostupna do pochatku roboti algoritmu vikoristana evristichna funkciyiya monotonna Spisok vidomih vershin realizovanij yak binarna kupa spisok doslidzhenih yak masiv Todi algoritm A maye kvadratichnij chas roboti v najgirshomu vipadku O V 2 displaystyle mathcal O vert V vert 2 Funkciya openlist decreaseKey mozhe buti optimizovana Yaksho kozhna vershina zberigatime vkazivnik na vidpovidnij ob yekt v kupi to chas roboti funkciyi zmenshitsya z linijnogo do logarifmichnogo a zagalnij chas roboti algoritmu do linijno logarifmichnogo O V log V displaystyle mathcal O vert V vert cdot log vert V vert Nedoliki Osnovnim nedolikom algoritmu A ye potreba v pam yati dlya zberezhennya vsih vidomih ta doslidzhenih vershin Cherez ce algortim A nepridatnij dlya bagatoh zadach Napriklad povnij graf hodiv dlya gri P yatnashki maye 16 20 922 789 888 000 displaystyle 16 20 922 789 888 000 vershin Alternativni algoritmiAlgoritm poshuku A mozhe buti zaminenij algoritmom Dejkstri abo zhadibnim algoritmom Algoritm Dejkstri ne vikoristovuye evristichnih funkcij i obiraye nastupnu vershinu v zalezhnosti vid potochnoyi vartosti shlyahu Natomist zhadibnij algoritm obiraye nastupnu vershinu lishe na osnovi ocinki mozhlivogo marshrutu cherez neyi Tomu algoritm Dejkstri mozhna zastosovuvati dlya poshuku shlyahu koli kinceva vershina nevidoma napriklad poshuk zapravochnoyi stanciyi i vikoristannya evristichnoyi funkciyi nemozhlive Deyaki algoritmi namagayutsya uniknuti potrebi u velikih obsyagah pam yati Sered nih A z iterativnim zagliblenyam variant RBFS rekursivnij poshuk za najkrashim zbigom angl Recursive Best First Search vimagaye linijnu kilkist pam yati v zalezhnosti vid dovzhini rozv yazku MA A z obmezhennyam pam yati SMA Simplified MA vikoristovuyut lishe napered vidilenij obsyag pam yati Ci algoritmi obmezhuyut potrebu v pam yati za rahunok shvidkodiyi Za deyakih obstavin ne obov yazkovo zberigati vsi vershini v pam yati Pogani vershini mozhut buti zabuti i zgodom mozhut buti nanovo vidtvoreni Pri vikoristanni monotonnoyi evristiki ta za umovi nayavnosti dostatnoyi kilkosti pam yati ci algoritmi optimalni Pri nadto suvorih obmezhennyah pam yati optimalnij rozv yazok mozhe buti ne znajdenij Algoritm poshuku D dinamichnij A ye vdoskonalennyam algoritmu A Cej algoritm vrahovuye informaciyu pro strukturu grafa Sered inshih algoritmiv mozhna nazvati algoritm Bellmana Forda dozvolyaye rebra z vid yemnimi vagami abo algoritm Flojda Vorshala znahodit najkorotshij shlyah mizh vsima parami vershin LiteraturaStuart Russell Peter Norvig Artificial Intelligence A Modern Approach 28 lyutogo 2011 u 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 Original D paper International Conference on Robotics and Automation 1994 Div takozhZadacha komivoyazhera Algoritm DejkstriPosilannyaPoyaslennya algoritmu A 30 listopada 2021 u Wayback Machine na kanali Computerphile na YouTube angl Poshuk marshrutiv z povorotami 20 sichnya 2011 u Wayback Machine angl Opis algoritmu A Arhivovano 4 kvitnya 2012 u WebCite angl