A*

Sök A * (uttalas "En stjärna" eller "En stjärna", från engelska  A star ) - i datavetenskap och matematik , en sökalgoritm för den första bästa matchningen på en graf som hittar rutten med lägst kostnad från en vertex ( initial) till en annan (mål, sista).

Ordningen i vilken hörnen korsas bestäms av den heuristiska funktionen avstånd + kostnad (vanligen betecknad som f(x) ). Denna funktion är summan av två andra: kostnadsfunktionen för att nå det betraktade hörnet ( x ) från det initiala (vanligtvis betecknat som g(x) och kan vara antingen heuristiskt eller inte), och funktionen för heuristisk uppskattning av avståndet från det betraktade hörnet till det sista (betecknat som h (x) ).

Funktionen h(x) måste vara en giltig heuristisk uppskattning , dvs den får inte överskatta avstånden till målpunkten. Till exempel, för ett routingproblem, kan h(x) vara avståndet till målet i en rät linje, eftersom det är det fysiskt minsta möjliga avståndet mellan två punkter.

Denna algoritm beskrevs första gången 1968 av Peter Hart , Nils Nilsson och Bertram Raphael . Det var i huvudsak en förlängning av Dijkstras algoritm , skapad 1959. Den nya algoritmen uppnådde högre prestanda (i tid) med hjälp av heuristik. I deras arbete kallas det "Algorithm A". Men eftersom den beräknar den bästa rutten för en given heuristik, har den fått namnet A*.

En generalisering för det är den dubbelriktade heuristiska sökalgoritmen .

Historik

1964 uppfann Nils Nilsson en heuristisk metod för att påskynda Dijkstras algoritm . Denna algoritm kallades A1 . 1967 gjorde Bertram Raphael betydande förbättringar av denna algoritm, men han lyckades inte uppnå optimalitet. Han döpte denna algoritm till A2 . Sedan 1968 presenterade Peter E. Hart argument som hävdade att A2 var optimal när man använder den sekventiella heuristiken med endast mindre modifieringar. Hans bevis på algoritmen innehöll också ett avsnitt som visade att den nya algoritmen A2 möjligen var den bästa algoritmen givet förutsättningarna. Således markerade han den nya algoritmen i syntaxen med en asterisk, den börjar med A och inkluderade alla möjliga versionsnummer.

Beskrivning av algoritmen

A* itererar genom alla banor som leder från startpunkten till slutpunkten tills den hittar den minsta. Som alla informerade sökalgoritmer tittar den först på de rutter som "tycks" leda till målet. Den skiljer sig från den giriga algoritmen , som också är en sökalgoritm för den första bästa matchningen, genom att den vid val av vertex tar hänsyn till bland annat hela vägen till den. Komponenten g(x)  är kostnaden för vägen från den initiala vertexen, och inte från den föregående, som i den giriga algoritmen.

I början av arbetet tittas noderna intill den initiala igenom; den som har minsta värdet f(x) väljs , varefter denna nod expanderas. I varje steg arbetar algoritmen på en uppsättning vägar från startpunkten till alla ännu outforskade (löv) hörn av grafen - en uppsättning specifika lösningar - som placeras i en prioritetskö . Sökvägsprioriteten bestäms av värdet f(x) = g(x) + h(x) . Algoritmen fortsätter sitt arbete tills värdet f(x) för målpunkten är mindre än något värde i kön, eller tills hela trädet har skannats. Från uppsättningen lösningar väljs lösningen med lägst kostnad.

Ju mindre heuristisk h(x) är, desto högre prioritet, så sorteringsträd kan användas för att implementera kön .

Uppsättningen av visade hörn lagras i closed, och sökvägarna som måste beaktas finns i prioritetskön open. Sökvägsprioriteten beräknas med hjälp av f(x) -funktionen inuti prioritetsköimplementeringen.

Pseudokod:

funktion A* ( start, mål, f ) % uppsättning hörn har redan passerats var stängd := den tomma uppsättningen % uppsättning särskilda lösningar var öppen := make_queue ( f ) enqueue ( öppen , sökväg ( start )) medan öppen är inte tom var p := remove_first ( öppen ) var x := den sista noden på sid om x stängt _ Fortsätta om x = mål tillbaka sid lägg till ( stängd , x ) % lägger till angränsande hörn för varje y i efterföljare ( x ) enqueue ( öppen , add_to_path ( p , y )) returfel _

Uppsättningen av hörn som redan passerats kan utelämnas (i det här fallet kommer algoritmen att förvandlas till en beslutsträdssökning), om det är känt att lösningen finns eller om den successorskan avbryta cykler .

Exempel

Ett exempel på A*-algoritmen i aktion, där noder är städer förbundna med vägar och H(x) är det kortaste avståndet till målpunkten:

Nyckel: grön - start, blå - mål, orange - besökta noder.

Egenskaper

Precis som Breadth First Search är A* komplett i den meningen att den alltid hittar en lösning om en sådan finns.

Om den heuristiska funktionen h är tillåten, det vill säga den överskattar aldrig den faktiska minimikostnaden för att nå målet, så är A* i sig tillåtet (eller optimal ), även förutsatt att vi inte skär av de korsade hörnen. Om vi ​​gör detta så krävs det för algoritmens optimalitet att h(x) också är en monoton eller successiv heuristik. Monotonicitetsegenskapen innebär att om det finns vägar A-B-C och A-C (inte nödvändigtvis genom B ), så måste kostnadsuppskattningen för vägen från A till C vara mindre än eller lika med summan av uppskattningarna av vägarna A-B och B-C . (Monotonicitet är också känd som triangelolikheten : en sida av en triangel kan inte vara längre än summan av de andra två sidorna.) Matematiskt är x , y (där y  är ett barn till x ) för alla banor :

A* är också optimalt effektiv för en given heuristisk h . Detta innebär att vilken annan algoritm som helst utforskar minst lika många noder som A* (såvida det inte finns flera specifika lösningar med samma heuristik exakt som motsvarar kostnaden för den optimala vägen).

Även om A* är optimal för "slumpmässigt" givna grafer, finns det ingen garanti för att den kommer att göra ett bättre jobb än enklare men mer domänmedvetna algoritmer. Till exempel, i en viss labyrint kan du först behöva gå i riktningen från utgången och först därefter vända tillbaka. I det här fallet kommer undersökningen i början av de toppar som är närmare utgången (i en rak linje) att vara ett slöseri med tid.

Särskilda tillfällen

Generellt sett är djup - första sökning och bredd först sökning två specialfall av A*-algoritmen. För djupsökning först, låt oss ta en global variabelräknare C och initialisera den med ett stort värde. Varje gång vi expanderar en vertex kommer vi att tilldela räknarens värde till intilliggande hörn, och minska det med en efter varje tilldelning. Alltså, ju tidigare en vertex öppnas, desto större värde på h(x) får den, vilket betyder att den kommer att ses sist. Om vi ​​sätter h(x) = 0 för alla hörn får vi ett annat specialfall - Dijkstras algoritm .

Implementeringsdetaljer

Det finns flera implementeringsfunktioner och tekniker som avsevärt kan påverka effektiviteten av algoritmen. Det första som inte skadar att uppmärksamma är hur prioritetskön hanterar kopplingar mellan hörn. Om hörn läggs till på ett sådant sätt att kön fungerar enligt LIFO- principen , så kommer A* i fallet med hörn med samma betyg att "gå" till djupet. Om emellertid FIFO- principen implementeras när hörn läggs till , då för hörn med samma uppskattning, kommer algoritmen tvärtom att implementera en bredd-först-sökning. I vissa fall kan denna omständighet ha en betydande inverkan på prestandan .

Om det i slutet av arbetet krävs en rutt från algoritmen, lagras vanligtvis en länk till föräldranoden tillsammans med varje vertex. Dessa länkar låter dig rekonstruera den optimala rutten. Om så är fallet är det viktigt att samma vertex inte dyker upp två gånger i kön (samtidigt som den har en egen rutt och en egen kostnadsberäkning). Vanligtvis, för att lösa detta problem, när de lägger till en vertex, kontrollerar de om det finns en post om det i kön. Om så är fallet uppdateras posten så att den motsvarar minimikostnaden för de två. För att hitta en vertex i ett sorteringsträd tar många standardalgoritmer O(n) tid. Om du förbättrar trädet med en hashtabell kan du minska denna tid.

Varför A* är giltigt och optimalt

Algoritm A* är både tillåten och korsar det minsta antalet hörn, på grund av att den fungerar med en "optimistisk" uppskattning av vägen genom vertexen. Optimistisk i den meningen att om den går igenom denna vertex så "har algoritmen en chans" att den verkliga kostnaden för resultatet blir lika med denna uppskattning, men inte mindre. Men eftersom A* är en informerad algoritm kan en sådan jämlikhet mycket väl vara möjlig.

När A* slutför sökningen har den per definition hittat en väg vars verkliga kostnad är mindre än den uppskattade kostnaden för en väg genom en öppen nod. Men eftersom dessa uppskattningar är optimistiska, kan motsvarande noder kasseras utan tvekan. Med andra ord, A* missar aldrig en möjlighet att minimera längden på en väg, och är därför laglig.

Låt oss nu anta att någon algoritm B som ett resultat returnerade en väg vars längd är större än uppskattningen av kostnaden för vägen genom någon vertex. Baserat på heuristisk information, för Algoritm B , kan möjligheten inte uteslutas att denna väg hade en kortare reell längd än resultatet. Följaktligen, även om algoritm B har tittat på färre hörn än A*, kommer den inte att vara giltig. Så, A* korsar det minsta antalet grafens hörn bland de giltiga algoritmerna med samma exakta (eller mindre exakta) heuristik.

Svårighetsgrad

Tidskomplexiteten för A*-algoritmen beror på heuristiken. I värsta fall växer antalet hörn som utforskas av algoritmen exponentiellt jämfört med längden på den optimala banan, men komplexiteten blir polynom när heuristiken uppfyller följande villkor:

;

där h* är den optimala heuristiken, dvs en exakt uppskattning av avståndet från x till målet. Med andra ord bör felet h(x) inte växa snabbare än logaritmen för den optimala heuristiken.

Men ett ännu större problem än tidskomplexitet är minnesresurserna som förbrukas av algoritmen . I värsta fall måste den komma ihåg ett exponentiellt antal noder. För att bekämpa detta har flera varianter av algoritmen föreslagits, såsom A*-algoritmen med iterativ fördjupning (iterativ fördjupning A*, IDA*), A* med minnesbunden A*, MA*, förenklad MA* (förenklad MA*). *, SMA*) och rekursiv bäst-först-sökning (RBFS).

Litteratur

  • Laurier J.-L. System för artificiell intelligens / Per. från fr. och ed. V. L. Stefanyuk. - M .: Mir, 1991. - S. 238-244. — 20 000 exemplar. kopiera.  — ISBN 5-03-001408-X .
  • Russell S.J., Norvig, P. Artificial Intelligence: A Modern Approach = Artificial Intelligence: A Modern Approach / Per. från engelska. och ed. K. A. Ptitsyna. - 2:a upplagan - M . : Williams, 2006. - S. 157-162. - 3000 exemplar. kopiera.  — ISBN 5-8459-0887-6 .
  • Nilson N. Artificiell intelligens: Metoder för att hitta lösningar = Problemlösningsmetoder inom artificiell intelligens / Per. från engelska. V. L. Stefanyuk; ed. S. V. Fomina. - M . : Mir, 1973. - S. 70 - 80.
  • Dechter, R., Pearl, J. Generaliserade bästa-först-sökningsstrategier och optimaliteten hos A*  // Journal of the ACM. - 1985. - T. 32 , nr 3 . - S. 505 - 536 .
  • Hart PE, Nilsson, NJ, Raphael, B. En formell grund för heuristisk bestämning av minimikostnadsvägar // IEEE Transactions on Systems Science and Cybernetics SSC4. - 1968. - Nr 2 . - S. 100 - 107 .
  • Hart PE, Nilsson, NJ, Raphael, B. Rättelse till "En formell grund för den heuristiska bestämning av minimikostnadsvägar" // SIGART Newsletter. - 1972. - T. 37 . - S. 28 - 29 .
  • Pearl J. Heuristics: Intelligenta sökstrategier för datorproblemlösning. - Addison-Wesley, 1984. - ISBN 0-201-05594-5 .

Länkar

 Algoritmer för grafsökning
Oinformerade metoder
Informerade metoder
Genvägar
Minsta spännträd
Övrig