- То је хеуристичка метода претраживања која оптимизује путању између два чвора комбиновањем стварне цене и процене.
- Користи фундаменталну функцију процене засновану на збиру пређене удаљености и процењене удаљености до циља.
- Имплементира се коришћењем отворених и затворених листа за управљање чворовима на чекању и већ истраженим чворовима.
- То је технолошка основа навигације у видео играма, ГПС системима и напредној роботици.
Ако сте се икада запитали како лик из видео игре може да избегава препреке са запањујућом прецизношћу или како ваш ГПС проналази најбржи пут кући, одговор се често крије у А* (А-звезда) алгоритму . Овај систем је једноставно математички алат дизајниран да реши проблем проналажења пута , омогућавајући ентитету да се креће од тачке А до тачке Б на најефикаснији могући начин.
Иако у почетку може изгледати као лавиринт формула и чворова, то је заправо прилично интуитиван концепт који спаја најбоље из оба света: поузданост претраге са униформним трошковима и брзину похлепне претраге. У суштини, A* је хеуристички алгоритам , што значи да користи „паметну процену“ како би избегао губљење времена на истраживање путева који очигледно не воде никуда, увек се фокусирајући на најперспективнију опцију.
Од чега се тачно састоји А* алгоритам?
Овај алгоритам, који су 1968. године представили визионари Питер Е. Харт, Нилс Ј. Нилсон и Бертрам Рафаел, специјализован је за проналажење путање са најнижим могућим трошковима унутар графа. Да бисмо га разумели, прво морамо знати да граф може бити било шта: од сложене навигационе мреже до једноставне мреже ћелија, где је свака ћелија чвор , а везе између њих су ивице.
Магија алгоритма A* лежи у његовој способности да означи чворове према напору потребном за постизање циља. Да би се то постигло, ослања се на главну формулу: f(n) = g(n) + h(n) . Овде се доноси одлука алгоритма:
- г(н) представља стварни трошак путање од почетног чвора до тренутног чвора.
- h(n) ис тхе хеуристичка функцијашто је у основи процена колико смо удаљени од нашег одредишта.
- f(n) је процењени укупни трошковиАлгоритам ће увек дати приоритет чвору са најнижом f вредношћу.
Значај хеуристике
Хеуристика је, једноставно речено, „инстинкт“ алгоритма. У зависности од тога како дефинишемо h(n) , понашање A* ће се драстично променити. Да би алгоритам био прихватљив , хеуристика никада не сме преценити стварне трошкове достизања циља; то јест, увек мора бити или оптимистична или тачна.
Постоји неколико начина за израчунавање ове удаљености у зависности од окружења. На пример, Еуклидова удаљеност је права линија између две тачке, идеална за кретање под било којим углом. Ако можемо да се крећемо само дуж хоризонталних и вертикалних оса (као на шаховској табли без дијагонала), користимо Менхетн удаљеност . Постоји и Чебишовљева удаљеност за случајеве где дијагонални потези коштају исто као и ортогонални. На крају, програмер одлучује која функција најбоље одговара његовом специфичном случају употребе.
Корак-по-корак механика рада
Да би се спречило да се A* изгуби успут, користи две основне структуре података: отворену листу и затворену листу . Прва функционише као ред чекања где се чувају чворови који су откривени, али још нису у потпуности истражени. Друга је запис чворова који су већ потпуно анализирани , чиме се спречава да алгоритам уђе у бесконачне петље.
Процес прати веома јасну кружну логику. Прво, почетни чвор се додаје на отворену листу. Затим, све док постоје доступни чворови, алгоритам бира онај са најнижом вредношћу f . Ако је тај чвор циљ, бинго! Пронашли смо руту. Ако није, означен је као затворен, а његови суседи се анализирају . За сваког суседа се израчунавају његова цена g и његова процена h. Ако је сусед већ био на отвореној листи, али смо пронашли краћи пут до њега, ажурирамо његове податке и мењамо његов родитељски чвор.
Техничка имплементација и разматрања
Имплементација овога у коду, било у Јави, Пајтону или C++, захтева дефинисање ћелијске структуре која чува родитељски чвор , што нам омогућава да пратимо порекло када се циљ достигне и реконструишемо коначну руту. У програмским окружењима, веома је уобичајено користити PriorityQueue за управљање отвореном листом, осигуравајући да увек имамо тренутни приступ најјефтинијем чвору.
Међутим, нису све добре вести. Један од главних недостатака алгоритма A* је то што је велики потрошач меморије , јер мора да чува све генерисане чворове да би функционисао. Штавише, у динамичним световима где се препреке крећу у реалном времену, трошкови обраде могу нагло порасти, приморавајући програмере да оптимизују графикон или користе варијације алгоритма како би избегли преоптерећење процесора.
Апликације из стварног света
Овај алгоритам је златни стандард у индустрији видео игара . Од стратешких игара где премештате војске до RPG игара отвореног света, A* омогућава непријатељима да вас интелигентно прате. Такође је важан у роботици, омогућавајући дроновима и паметним усисивачима да избегну ударање у намештај, и наравно, у апликацијама за дигитално мапирање за оптимизацију градског саобраћаја.
Успех овог алата лежи у његовој свестраности. Можемо доделити „тежине“ чворовима како бисмо симулирали изазован терен; на пример, ходање по песку може имати већи g-трошак од ходања по асфалту, што приморава алгоритам да пронађе дужу, али бржу руту. Ова способност прилагођавања потребама пројекта чини га идеалном почетном тачком за свакога ко жели да учи о вештачкој интелигенцији и теорији графова.
А* алгоритам се истиче као бриљантно решење које балансира математичку прецизност са рачунарском ефикасношћу. Комбиновањем пређене удаљености са интелигентном проценом путање до циља, успева да испланира најкраћу руту, избегавајући препреке и оптимизујући ресурсе. Упркос захтевима за меморијом, његова флексибилност да се прилагоди различитим врстама хеуристика и окружења чини га преферираним алатом за навигацију у аутономним агентима и модерном софтверу за рутирање.