A* algoritm: heuristiline otsing ja kiire tee leidmine

A* algoritm selgitatuna: heuristiline otsing, kiire teeotsing ja praktilised näited — kuidas A* leiab efektiivselt marsruute võrreldes Dijkstra ja teistega.

A* on sammude kogum (algoritm), mida arvutid saavad kasutada, et leida, kuidas kahe koha vahel kiiresti kuhugi jõuda. Kui teil on nimekiri kohtadest ja sellest, kui raske on ühest kohast otse teise jõuda, saab A* abil kiiresti välja selgitada kiireima tee. See on seotud Dijkstra algoritmiga, kuid teeb arukaid oletusi, nii et see ei kuluta nii kaua aega aeglaste viiside proovimiseks. See on hea sammude rida, kui soovite ainult teed kahe koha vahel. Kui te tahate küsida palju teid samalt kaardilt, siis on olemas kiiremad viisid, mis leiavad kõik vastused korraga, näiteks Floyd-Warshalli algoritm. A* ei tööta, kui tahate ühe teekonnaga külastada mitut kohta (reisiv müügimehe probleem).

Kuidas A* töötab

A* otsib sammudeks jaotatud graafis parimat teed lähtepunktist sihtpunkti, kasutades kahte väärtust iga sõlme jaoks:

g(n) — teadaolev kulu lähtepunktist sõlmeni n;
h(n) — heuristiline hinnang (eniõige ehk ligikaudne) kulu sõlmest n sihtpunkti.

Neid kombineeritakse eesmärgiga hinnata, kui „paljulubav” mingi tee on:

f(n) = g(n) + h(n)

A* hoiab kahte hulka: open set (kandidaadid, mida veel uuritakse) ja closed set (sõlmed, mida on juba töödeldud). Iga sammu puhul võetakse open-ist välja sõlm, mille f-väärtus on väikseim, laiendatakse selle naabreid, värskendatakse nende g- ja f-väärtusi ning hoitakse parent/prev-viidad, et teekonda lõpuks rekonstrueerida. Kui sihtpunkt võetakse open-ist välja, on leitud optimaalse kulu tee (eeldusel, et heuristika on sobiv, vt allpool).

Heuristika — kui oluline see on

Heuristika h(n) on A* puhul määrava tähtsusega. Heuristika peab olema:

admissible (mitteliialt üleshinnatud) — ei tohi kunagi ülehinnata tegelikku minimaalkulu sihtpunkti; see tagab, et A* leiab optimaalse lahenduse;
consistent või monotone — iga kaare (n → m) korral peab h(n) ≤ cost(n,m) + h(m); see lihtsustab algoritmi ja tagab, et kord tasutud sõlmet ei pea uuesti töödelda.

Näited heuristikast kaartidel:

Manhattani kaugus (võrdne vertikaal+horizontaal sammudega) ruudustikul, kus liikumine on neljas suunas;
Euclidiline kaugus (otsejoone pikkus) kui saab liikuda vabalt suundades;
Chebyshevi kaugus 8-suunalistes liikumisskeemides.

Mida täpsem (aga siiski admissible) heuristika on, seda vähem sõlmi A* peab uurima ja seda kiirem on otsing.

Andmestruktuurid ja efektiivsus

Open-seti jaoks kasutatakse tavaliselt prioriteetjärjekorda (binary heap, fibonacci heap või muu), kuna tuleb kiiresti leida väikseima f-väärtusega sõlm.
Closed-set tavaliselt implementeeritakse hash-tabelina, et kontrollida kiirelt, kas sõlm on juba töödeldud.
A* aeg- ja mälukompleksus sõltub heuristikast: halval heuristikul võib käitumine olla sama nagu laiendaval otsingul (eksponentsiaalne), ning mäluvajadus võib olla väga suur, sest open-set võib kasvada suureks.

Võrdlus Dijkstra ja teiste meetoditega

Kui heuristika h(n) = 0 kõigi sõlmede puhul, siis A* muutub Dijkstra algoritmiks — otsing ei kasutagi sihtpunkti suunatud infot.
Dijkstra leiab lühima tee kõigile sõlmedele lähtepunktist (single-source), A* on suunatud ühe sihtpunkti leidmisele ja säästab tööd, kui heuristika juhib otsingut õigesti.
Kui eesmärk on leida kõigi paaride lühimad teed, sobib paremaks Floyd-Warshalli algoritm või korduv Dijkstra vastavalt vajadusele.

Kasutusalad

navigeerimine ja marsruutimine (GPS, reisimarsruudid);
mängutehisintellekt (tegelaste liikumine mängumaastikul);
robotite teekonna planeerimine;
graafipõhised optimeerimisülesanded, kus on olemas sobiv heuristika.

Piirangud ja variandid

A* võib vajada palju mälu suurte või keeruliste graafide korral.
Kui heuristika on ebatäpne (ülehinnatud), ei pruugi A* leida optimaalse teed.
Kui eesmärke on mitu või nõutakse järjekorras külastamist (nt reisiv müügimehe probleem), siis A* üksi ei sobi; vajalikud on teised algoritmid või optimeerimismeetodid.

Levinud variandid ja optimeeringud:

IDA* (iterative deepening A*) — vähendab mälu kasutust, kombineerides iteratiivset sügavuse-kasvu f-limiidiga;
Weighted A* — kasutab f(n)=g(n)+w·h(n) w>1, et leida kiiremini mitte-täiuslikke lahendusi;
Jump Point Search — optimeerib ruudustikuotsingut, vahele jättes mittevajalikke sõlmi;
Theta* — võimaldab joonelist (line-of-sight) liikumist ruudustikul, leidmaks lühemaid realistlikke teid.

Lühike toimimisjärjestus (pseudokäitumine)

Alguses asetatakse lähtepunkt open-seti, g(start)=0 ja f=start.h();
Kuni open-set ei ole tühi: võtke välja sõlm n, mille f on minimaalne;
Kui n on sihtpunkt, rekonstrueerige tee parent-viidete abil ja lõpetage;
Võïtke naabrid läbi: arvutage tentatiivne g (g(n)+cost(n,neighbor)). Kui see on parem kui eelnev g(neighbor), uuendage parentit, g ja f ning lisage neighbor open-seti;
Kui kõik naabrid töödelud ja sihtpunkti ei leitud, siis teed pole (või graaf ei ole ühendatud).

Näide

2D-ruudustikul, kus saab liikuda üles/alla/vasakule/paremale ja iga samm maksab 1:

Heuristika: Manhattani kaugus (|dx| + |dy|) on admissible;
A* avastab esmalt sõlmed, mis näivad lähenevat sihtpunktile madala f-väärtusega, seega ei laienda kogu kaarti nagu tavaline laiendav otsing;
Tulemuseks on lühim sammude arvuga tee, kui heuristika on admissible ja consistent.

Kokkuvõttes on A* väga paindlik ja võimas heuristiline otsingumeetod ühe sihtpunkti leidmiseks graafis. Selle edu sõltub suuresti sobiva heuristika valikust ning andmestruktuuridest, mis tagavad operatsioonide kiire teostamise.

Sammud

A* vajab kõigepealt nimekirja kõigist kohtadest, kuhu saab minna, ja seejärel nimekirja sellest, kui kaugel on tee iga koha vahel. Seejärel ütleb see teile, milline on kõige kiirem tee, et jõuda kohast A kohani Z.

Näitena ütleme, et A on ühendatud kohtadega B ja C ning B ja C on mõlemad ühendatud kohtadega D ja E. D ja E on mõlemad ühendatud kohtadega Z. A-st Z-sse saab minna 4 võimalust: A-B-D-Z, A-C-D-Z, A-B-E-Z või A-C-E-Z. Arvuti, mis kasutab A*, vaatab kõigepealt, kui raske on jõuda A-st B-sse ja A-st C-sse. See on nende kohtade "kulu". Koha maksumus tähendab seda, kui raske on jõuda kohast A sinna. Pärast mõlema kulu üleskirjutamist vaatab arvuti, kui raske on jõuda B-st D-sse, ja lisab selle B maksumusele. Ta kirjutab selle üles D maksumuseks. Seejärel vaatab arvuti, kui raske on jõuda C-st D-sse, ja lisab selle C maksumusele. See on teistsugune kulu D jaoks ja kui see on väiksem kui see, mis tal juba on, siis asendab ta vana. Arvuti tahab teada ainult parimat teed, seega ignoreerib ta suurema maksumusega teed. Ta jätab meelde ainult ühe A-B-D või A-C-D, olenevalt sellest, kumb neist on kiirem.

Arvuti läheb edasi ja leiab kõige kiirema tee, et jõuda E. Lõpuks läheb ta D-st Z-sse ja leiab maksumuse ning E-st Z-sse ja leiab maksumuse. Ta saab lõpliku maksumuse Z jaoks ja see on väikseim maksumus, mille ta saab. Nüüd teab arvuti, milline tee on kõige kiirem, ja tal on vastus. Arvuti võib teha samasuguse sammude seeria, kuid palju palju rohkemate kohtadega. Iga kord vaatab ta koha, mis on A-le kõige lähemal, ja liidab selle koha naabrite kulud kokku.

Inimesed nimetavad ülaltoodud sammude seeriat Dijkstra algoritmiks. Dijkstra algoritm võib olla aeglane, sest ta vaatab palju kohti, mis võivad minna Z-st valesse suunda. Kui te küsisite arvutilt, kuidas jõuda ühest linnast lähedasse linna, võib Dijkstra algoritm sattuda otsima teise riiki.

A* lahendab selle probleemi. A* laseb teil öelda arvutile, kui kaugele on igast kohast lõpuni. Arvuti saab arvamise põhjal öelda, kui kaugele on vaja minna teatud kohast Z. Selle asemel, et lihtsalt valida A-le lähim koht, vaatab ta seda, mille summa on tõenäoliselt kõige väiksem. Ta leiab selle kogusumma, lisades maksumuse eeldatavale järelejäänud vahemaale. Nii saab ta vaadata ainult selles suunas, kus asjad tõenäoliselt paremaks lähevad. See on okei, kui arvamine ei ole täiuslik, kuid isegi lihtne halb arvamine võib programmi palju kiiremini käima panna. Kui te püüate leida teed kahe koha vahel reaalses maailmas, on hea arvamine lihtsalt nende vaheline kaugus sirgjoonel. Tegelik tee üle teede on pikem, kuid see laseb programmil seda ära arvata ja ta ei lähe vales suunas.

Matemaatika- või arvutiteaduse kirjanduses on see arvamine sageli koha funktsioon ja seda nimetatakse heuristikaks. Iga koht on tipp ja iga tee kahe koha vahel on serv. Need on sõnad graafiteooriast.