EN*

Søg A * (udtales "A star" eller "A star", fra engelsk  A star ) - i datalogi og matematik , en søgealgoritme for det første bedste match på en graf , der finder ruten med den mindste pris fra et toppunkt ( initial) til en anden (mål, endelig).

Rækkefølgen, hvori toppunkterne krydses, bestemmes af afstanden + omkostninger heuristisk funktion (almindeligvis betegnet som f(x) ). Denne funktion er summen af ​​to andre: omkostningsfunktionen for at nå det betragtede toppunkt ( x ) fra den oprindelige (normalt betegnet som g(x) og kan enten være heuristisk eller ej), og funktionen af ​​heuristisk estimering af afstanden fra det betragtede toppunkt til det sidste (betegnet som h (x) ).

Funktionen h(x) skal være et gyldigt heuristisk estimat , dvs. den må ikke overvurdere afstandene til målet vertex. For et routingproblem kunne h(x) for eksempel være afstanden til målet i en lige linje, da det er den fysisk mindst mulige afstand mellem to punkter.

Denne algoritme blev først beskrevet i 1968 af Peter Hart , Nils Nilsson og Bertram Raphael . Det var i det væsentlige en udvidelse af Dijkstras algoritme , skabt i 1959. Den nye algoritme opnåede højere ydeevne (over tid) ved hjælp af heuristik. I deres arbejde omtales det som "Algorithm A". Men da den beregner den bedste rute for en given heuristik, har den fået navnet A*.

En generalisering for det er den tovejs heuristiske søgealgoritme .

Historie

I 1964 opfandt Nils Nilsson en heuristisk tilgang til at fremskynde Dijkstras algoritme . Denne algoritme blev kaldt A1 . I 1967 lavede Bertram Raphael væsentlige forbedringer af denne algoritme, men han formåede ikke at opnå optimalitet. Han navngav denne algoritme A2 . Så i 1968 fremlagde Peter E. Hart argumenter, der argumenterede for, at A2 var optimal, når man brugte den sekventielle heuristik med kun mindre modifikationer. Hans bevis for algoritmen inkluderede også et afsnit, der viste, at den nye algoritme A2 muligvis var den bedste algoritme givet betingelserne. Således markerede han den nye algoritme i syntaksen med en stjerne, den starter med A og inkluderede alle mulige versionsnumre.

Beskrivelse af algoritmen

A* itererer gennem alle stierne, der fører fra startspidsen til endespidsen, indtil den finder den mindste. Som alle informerede søgealgoritmer ser den først på de ruter, der "synes" at føre til målet. Den adskiller sig fra den grådige algoritme , som også er en søgealgoritme for det første bedste match, ved at den ved valg af toppunkt blandt andet tager højde for hele vejen dertil. Komponenten g(x)  er prisen på stien fra det oprindelige toppunkt, og ikke fra den foregående, som i den grådige algoritme.

I begyndelsen af ​​arbejdet ses knudepunkterne, der støder op til den oprindelige, igennem; den der har minimumsværdien f(x) vælges , hvorefter denne node udvides. På hvert trin opererer algoritmen på et sæt stier fra udgangspunktet til alle endnu uudforskede (blade) hjørner af grafen - et sæt af bestemte løsninger - som placeres i en prioriteret kø . Stiprioriteten bestemmes af værdien f(x) = g(x) + h(x) . Algoritmen fortsætter sit arbejde, indtil værdien f(x) for målet vertex er mindre end nogen værdi i køen, eller indtil hele træet er blevet scannet. Fra sæt af løsninger vælges løsningen med den laveste pris.

Jo mindre heuristisk h(x) , jo højere prioritet, så sorteringstræer kan bruges til at implementere køen .

Sættet af viste hjørner er gemt i closed, og de stier, der skal tages i betragtning, er i prioritetskøen open. Stiprioriteten beregnes ved hjælp af f(x) -funktionen inde i prioritetskøimplementeringen.

Pseudokode:

funktion A* ( start, mål, f ) % sæt hjørner allerede passeret var lukket := det tomme sæt % sæt af bestemte løsninger var åben := make_queue ( f ) kø ( åben , sti ( start )) mens åben er ikke tom var p := remove_first ( åben ) var x := den sidste knude på s hvis x lukket _ Blive ved hvis x = mål retur s tilføje ( lukket , x ) % tilføje tilstødende hjørner foreach y i efterfølgere ( x ) kø ( åben , tilføje_til_sti ( p , y )) returfejl _

Sættet af toppunkter, der allerede er passeret, kan udelades (i dette tilfælde vil algoritmen blive til en beslutningstræsøgning), hvis det vides, at løsningen eksisterer, eller hvis den successorskan afbryde cyklusser .

Eksempel

Et eksempel på A*-algoritmen i aktion, hvor noder er byer forbundet af veje, og H(x) er den korteste afstand til målpunktet:

Nøgle: grøn - start, blå - mål, orange - besøgte noder.

Egenskaber

Ligesom Breadth First Search er A* komplet i den forstand, at den altid finder en løsning, hvis der findes en.

Hvis den heuristiske funktion h er tilladelig, dvs. den overvurderer aldrig de faktiske minimumsomkostninger ved at nå målet, så er A* i sig selv tilladelig (eller optimal ), også forudsat at vi ikke afskærer de krydsede hjørner. Hvis vi gør dette, så kræves det for algoritmens optimalitet, at h(x) også er en monotonisk eller successiv heuristik. Monotonicitetsegenskaben betyder, at hvis der er stier A-B-C og A-C (ikke nødvendigvis gennem B ), så skal omkostningsestimatet for stien fra A til C være mindre end eller lig med summen af ​​estimaterne af stierne A-B og B-C . (Monotonicitet er også kendt som trekantens ulighed : den ene side af en trekant kan ikke være længere end summen af ​​de to andre sider.) Matematisk er x , y (hvor y  er et barn af x ) for alle stier:

A* er også optimalt effektiv for en given heuristisk h . Dette betyder, at enhver anden algoritme udforsker mindst lige så mange noder som A* (medmindre der er flere bestemte løsninger med samme heuristik, der nøjagtigt svarer til prisen på den optimale sti).

Mens A* er optimal til "tilfældigt" givne grafer, er der ingen garanti for, at den vil gøre et bedre stykke arbejde end simplere, men mere domænebevidste algoritmer. For eksempel, i en bestemt labyrint , skal du måske først gå i retningen fra udgangen og først derefter vende tilbage. I dette tilfælde vil undersøgelsen i begyndelsen af ​​de toppe, der er tættere på udgangen (i en lige linje), være spild af tid.

Særlige lejligheder

Generelt er dybde - første søgning og bredde - først søgning to specielle tilfælde af A*-algoritmen. For dybde - først søgning, lad os tage en global variabeltæller C , og initialisere den med en eller anden stor værdi. Hver gang vi udvider et toppunkt, vil vi tildele værdien af ​​tælleren til tilstødende hjørner og reducere den med én efter hver tildeling. Jo tidligere et toppunkt åbnes, jo større er værdien af ​​h(x) det vil modtage, hvilket betyder, at det vil blive set sidst. Hvis vi sætter h(x) = 0 for alle hjørner, får vi et andet specialtilfælde - Dijkstras algoritme .

Implementeringsdetaljer

Der er flere implementeringsfunktioner og -teknikker, der kan påvirke effektiviteten af ​​algoritmen markant. Det første, der ikke skader at være opmærksom på, er, hvordan prioritetskøen håndterer forbindelser mellem hjørner. Hvis der tilføjes toppunkter til den på en sådan måde, at køen fungerer efter LIFO- princippet , så vil A* i tilfælde af toppunkter med samme rating "gå" til dybden. Hvis FIFO -princippet implementeres , når der tilføjes knudepunkter, vil algoritmen tværtimod implementere en bredde-først søgning for knudepunkter med samme estimat. I nogle tilfælde kan denne omstændighed have en betydelig indvirkning på ydeevnen .

Hvis der i slutningen af ​​arbejdet kræves en rute fra algoritmen, gemmes normalt et link til den overordnede node sammen med hvert vertex. Disse links giver dig mulighed for at rekonstruere den optimale rute. Hvis det er tilfældet, så er det vigtigt, at det samme toppunkt ikke optræder to gange i køen (samtidig med sin egen rute og sit eget omkostningsoverslag). Normalt, for at løse dette problem, når de tilføjer et vertex, tjekker de, om der er en post om det i køen. Hvis det er det, så opdateres posten, så den svarer til minimumsomkostningerne for de to. For at finde et toppunkt i et sorteringstræ tager mange standardalgoritmer O(n) tid. Hvis du forbedrer træet med en hash-tabel , kan du reducere denne tid.

Hvorfor A* er gyldig og optimal

Algoritme A* er både tilladelig og krydser minimumsantallet af toppunkter, på grund af det faktum, at den arbejder med et "optimistisk" estimat af vejen gennem toppunktet. Optimistisk i den forstand, at hvis den går gennem dette toppunkt, "har algoritmen en chance" for, at de reelle omkostninger ved resultatet vil være lig med dette estimat, men ikke mindre. Men da A* er en informeret algoritme, kan en sådan ligestilling meget vel være mulig.

Når A* fuldfører søgningen, har den pr. definition fundet en sti, hvis sande pris er mindre end de estimerede omkostninger for enhver sti gennem enhver åben knude. Men da disse estimater er optimistiske, kan de tilsvarende noder kasseres uden tvivl. Med andre ord går A* aldrig glip af en mulighed for at minimere længden af ​​en sti og er derfor lovlig.

Lad os nu antage, at en eller anden algoritme B som et resultat returnerede en sti, hvis længde er større end estimatet af omkostningerne ved stien gennem et eller andet toppunkt. Baseret på heuristisk information kan det for Algoritme B ikke udelukkes, at denne vej havde en kortere reel længde end resultatet. Derfor, mens algoritme B har set på færre hjørner end A*, vil den ikke være gyldig. Så A* krydser det mindste antal grafhjørner blandt de gyldige algoritmer ved at bruge den samme nøjagtige (eller mindre nøjagtige) heuristik.

Sværhedsgrad

Tidskompleksiteten af ​​A*-algoritmen afhænger af heuristikken. I værste fald vokser antallet af knudepunkter, der udforskes af algoritmen, eksponentielt sammenlignet med længden af ​​den optimale vej, men kompleksiteten bliver polynomiel , når heuristikken opfylder følgende betingelse:

;

hvor h* er den optimale heuristik, dvs. et nøjagtigt estimat af afstanden fra x til målet. Med andre ord bør fejlen h(x) ikke vokse hurtigere end logaritmen af ​​den optimale heuristik.

Men et endnu større problem end tidskompleksitet er hukommelsesressourcerne , der forbruges af algoritmen . I værste fald skal den huske et eksponentielt antal noder. For at bekæmpe dette er flere variationer af algoritmen blevet foreslået, såsom A*-algoritmen med iterativ uddybning (iterativ uddybning A*, IDA*), A* med hukommelsesbegrænset A*, MA*, forenklet MA* (simplificeret MA ). *, SMA*) og rekursiv bedste-først-søgning (RBFS).

Litteratur

  • Laurier J.-L. Systemer for kunstig intelligens / Pr. fra fr. og udg. V. L. Stefanyuk. - M .: Mir, 1991. - S. 238-244. — 20.000 eksemplarer. kopi.  — ISBN 5-03-001408-X .
  • Russell S.J., Norvig, P. Artificial Intelligence: A Modern Approach = Artificial Intelligence: A Modern Approach / Pr. fra engelsk. og udg. K. A. Ptitsyna. - 2. udgave - M . : Williams, 2006. - S. 157-162. - 3000 eksemplarer. kopi.  — ISBN 5-8459-0887-6 .
  • Nilson N. Artificial Intelligence: Methods for Finding Solutions = Problem-solving Methods in Artificial Intelligence / Pr. fra engelsk. V. L. Stefanyuk; udg. S. V. Fomina. - M . : Mir, 1973. - S. 70 - 80.
  • Dechter, R., Pearl, J. Generaliserede bedste-først-søgestrategier og optimaliteten af ​​A*  // Journal of the ACM. - 1985. - T. 32 , nr. 3 . - S. 505 - 536 .
  • Hart PE, Nilsson, NJ, Raphael, B. Et formelt grundlag for den heuristiske bestemmelse af minimumsomkostningsstier // IEEE -transaktioner om systemvidenskab og kybernetik SSC4. - 1968. - Nr. 2 . - S. 100 - 107 .
  • Hart PE, Nilsson, NJ, Raphael, B. Rettelse til "Et formelt grundlag for den heuristiske bestemmelse af minimumsomkostningsstier" // SIGART Nyhedsbrev. - 1972. - T. 37 . - S. 28 - 29 .
  • Pearl J. Heuristics: Intelligente søgestrategier til computerproblemløsning. - Addison-Wesley, 1984. - ISBN 0-201-05594-5 .

Links

 Algoritmer til grafsøgning
Uoplyste metoder
Informerede metoder
Genveje
Minimumspændende træ
Andet