A* søkealgoritme - A* search algorithm

Klasse	Søkealgoritme
Data struktur	Kurve
Ytelse i verste fall	${\ displaystyle O (| E |) = O (b^{d})}$
Kompleksitet i verste tilfelle	${\ displaystyle O (| V |) = O (b^{d})}$

A * (uttales "A-stjerne") er en graf traversering og bane søkealgoritme , som ofte brukes i mange områder av informatikk på grunn av sin fullstendighet, optimalitet, og optimal effektivitet. En stor praktisk ulempe er romkompleksiteten, da den lagrer alle genererte noder i minnet. I praktiske reiseruteringssystemer blir det derfor generelt bedre enn algoritmer som kan forhåndsbehandle grafen for å oppnå bedre ytelse, så vel som minnebegrensede tilnærminger; A* er imidlertid fortsatt den beste løsningen i mange tilfeller. ${\ displaystyle O (b^{d})}$

Peter Hart , Nils Nilsson og Bertram Raphael fra Stanford Research Institute (nå SRI International ) publiserte algoritmen første gang i 1968. Den kan ses som en forlengelse av Dijkstras algoritme . A* oppnår bedre ytelse ved å bruke heuristikk for å lede søket.

Historie

A* ble oppfunnet av forskere som jobbet med Shakey the Robots baneplanlegging.

En* ble opprettet som en del av Shakey -prosjektet , som hadde som mål å bygge en mobil robot som kunne planlegge sine egne handlinger. Nils Nilsson foreslo opprinnelig å bruke Graph Traverser -algoritmen for Shakeys baneplanlegging. Graph Traverser styres av en heuristisk funksjon h ( n ) , den estimerte avstanden fra node n til målnoden: den ignorerer helt g ( n ) , avstanden fra startnoden til n . Bertram Raphael foreslo å bruke summen, g ( n ) + h ( n ) . Peter Hart oppfant konseptene vi nå kaller tillatelse og konsistens for heuristiske funksjoner. A* ble opprinnelig designet for å finne rimeligste stier når kostnaden for en bane er summen av kostnadene, men det har blitt vist at A* kan brukes til å finne optimale stier for ethvert problem som tilfredsstiller betingelsene for en kostnadsalgebra.

Det originale A* -papiret fra 1968 inneholdt et teorem om at ingen A* -liknende algoritme kunne utvide færre noder enn A* hvis den heuristiske funksjonen er konsistent og A *s regel for likhetsbrudd er passende valgt. En ″ korreksjon ″ ble publisert noen år senere og hevdet at det ikke var nødvendig med konsistens, men dette ble vist å være feil i Dechter og Perles definitive studie av A*s optimalitet (nå kalt optimal effektivitet), som ga et eksempel på A* med en heuristikk som var tillatt, men ikke konsekvent, utvide vilkårlig flere noder enn en alternativ A*-lignende algoritme.

Beskrivelse

A* er en informert søkealgoritme , eller et best-first-søk , noe som betyr at den er formulert i form av vektede grafer : fra en bestemt startnode i en graf, tar den sikte på å finne en vei til den gitte målnoden som har den minste kostnad (minst tilbakelagt distanse, korteste tid osv.). Det gjør dette ved å opprettholde et tre av stier med opprinnelse i startnoden og forlenge disse banene en kant om gangen til avslutningskriteriet er oppfylt.

Ved hver iterasjon av hovedsløyfen må A* bestemme hvilken av banene de skal forlenge. Det gjør det basert på kostnaden for banen og et estimat av kostnaden som kreves for å forlenge banen helt til målet. Spesielt velger A* banen som minimeres

${\ displaystyle f (n) = g (n)+h (n)}$

hvor n er den neste noden på banen, er g ( n ) kostnaden for banen fra startnoden til n , og h ( n ) er en heuristisk funksjon som anslår kostnaden for den billigste banen fra n til målet. A* avsluttes når banen den velger å forlenge er en bane fra start til mål, eller hvis det ikke er noen stier som er kvalifisert til å bli forlenget. Den heuristiske funksjonen er problemspesifikk. Hvis den heuristiske funksjonen er tillatt , noe som betyr at den aldri overvurderer den faktiske kostnaden for å komme til målet, vil A* garantert returnere en minstebane fra start til mål.

Typiske implementeringer av A* bruker en prioritetskø for å utføre det gjentatte utvalget av minimum (estimerte) kostnadsnoder som skal utvides. Denne prioritetskøen er kjent som det åpne settet eller utkantene . Ved hvert trinn i algoritmen fjernes noden med den laveste f ( x ) -verdien fra køen, f- og g -verdiene til naboene oppdateres tilsvarende, og disse naboene legges til i køen. Algoritmen fortsetter til en fjernet node (dermed noden med den laveste f -verdien av alle utkantnoder) er en målnode. Den f verdien av dette målet er da også kostnadene for den korteste veien, siden h ved målet er null i en tillatelig heuristisk.

Algoritmen som er beskrevet så langt, gir oss bare lengden på den korteste banen. For å finne den faktiske trinnsekvensen, kan algoritmen enkelt revideres slik at hver node på banen holder orden på forgjengeren. Etter at denne algoritmen er kjørt, vil sluttnoden peke på forgjengeren, og så videre, til noen nodes forgjenger er startnoden.

Som et eksempel, når du søker etter den korteste ruten på et kart, kan h ( x ) representere den lineære avstanden til målet, siden det fysisk er den minste mulige avstanden mellom to punkter. For et rutenettkart fra et videospill blir bruk av Manhattan-avstanden eller den oktile avstanden bedre avhengig av settet med tilgjengelige bevegelser (4-veis eller 8-veis).

En* banefinneralgoritme som navigerer rundt en tilfeldig generert labyrint

Spill media

Illustrasjon av A* søk for å finne banen mellom to punkter på en graf.

Hvis heuristikken h oppfyller tilleggsbetingelsen h ( x ) ≤ d ( x , y ) + h ( y ) for hver kant ( x , y ) i grafen (hvor d angir lengden på den kanten), kalles h monoton eller konsistent . Med en konsekvent heuristikk vil A* garantert finne en optimal bane uten å behandle noen node mer enn én gang, og A* tilsvarer å kjøre Dijkstras algoritme med reduserte kostnader d ' ( x , y ) = d ( x , y ) + h ( y ) - h ( x ) .

Pseudokode

Følgende pseudokode beskriver algoritmen:

function reconstruct_path(cameFrom, current)
    total_path := {current}
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.prepend(current)
    return total_path

// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h)
    // The set of discovered nodes that may need to be (re-)expanded.
    // Initially, only the start node is known.
    // This is usually implemented as a min-heap or priority queue rather than a hash-set.
    openSet := {start}

    // For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start
    // to n currently known.
    cameFrom := an empty map

    // For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
    gScore := map with default value of Infinity
    gScore[start] := 0

    // For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to
    // how short a path from start to finish can be if it goes through n.
    fScore := map with default value of Infinity
    fScore[start] := h(start)

    while openSet is not empty
        // This operation can occur in O(1) time if openSet is a min-heap or a priority queue
        current := the node in openSet having the lowest fScore[] value
        if current = goal
            return reconstruct_path(cameFrom, current)

        openSet.Remove(current)
        for each neighbor of current
            // d(current,neighbor) is the weight of the edge from current to neighbor
            // tentative_gScore is the distance from start to the neighbor through current
            tentative_gScore := gScore[current] + d(current, neighbor)
            if tentative_gScore < gScore[neighbor]
                // This path to neighbor is better than any previous one. Record it!
                cameFrom[neighbor] := current
                gScore[neighbor] := tentative_gScore
                fScore[neighbor] := gScore[neighbor] + h(neighbor)
                if neighbor not in openSet
                    openSet.add(neighbor)

    // Open set is empty but goal was never reached
    return failure

Bemerkning: I denne pseudokoden, hvis en node nås med en bane, fjernet fra openSet, og deretter nås med en billigere bane, vil den bli lagt til openSet igjen. Dette er avgjørende for å garantere at veien som returneres er optimal hvis den heuristiske funksjonen er tillatt, men ikke konsekvent . Hvis heuristikken er konsistent, når en node fjernes fra openSet er banen garantert optimal, slik at testen 'tentative_gScore <gScore [neighbour]' alltid vil mislykkes hvis noden nås igjen.

Illustrasjon A * søke for å finne veien fra en start-node i et mål node i en robot bevegelse planlegging problem. De tomme sirklene representerer nodene i det åpne settet , dvs. de som gjenstår å utforske, og de fylte er i det lukkede settet. Farge på hver lukkede node indikerer avstanden fra målet: jo grønnere, jo nærmere. Man kan først se A* bevege seg i en rett linje i målretningen, så når den treffer hindringen, utforsker den alternative ruter gjennom nodene fra det åpne settet.

Se også: Dijkstras algoritme

Eksempel

Et eksempel på en A* -algoritme i aksjon der noder er byer forbundet med veier og h (x) er den rettlinjede avstanden til målpunktet:

Nøkkel: grønn: start; blå: mål; oransje: besøkt

A* -algoritmen har også virkelige applikasjoner. I dette eksemplet er kanter jernbaner og h (x) er avstanden med stor sirkel (kortest mulig avstand på en kule) til målet. Algoritmen søker etter en vei mellom Washington, DC og Los Angeles.

Gjennomføringsdetaljer

Det finnes en rekke enkle optimaliseringer eller implementeringsdetaljer som kan påvirke ytelsen til en A* implementering betydelig. Den første detaljen å merke seg er at måten prioritetskø håndterer bånd kan ha en betydelig effekt på ytelsen i noen situasjoner. Hvis bånd brytes slik at køen oppfører seg på en LIFO- måte, vil A* oppføre seg som et dybde-første søk blant likestillingsveier (unngå å utforske mer enn én like optimal løsning).

Når det er nødvendig med en bane på slutten av søket, er det vanlig å beholde en referanse til hver node for hver node. På slutten av søket kan disse referansene brukes til å gjenopprette den optimale banen. Hvis disse referansene beholdes, kan det være viktig at den samme noden ikke vises i prioritetskøen mer enn én gang (hver oppføring tilsvarer en annen bane til noden, og hver med en annen kostnad). En standard tilnærming her er å sjekke om en node som skal legges til allerede vises i prioritetskøen. Hvis det gjør det, endres prioritet og overordnet pekepinn for å tilsvare banen til lavere kostnader. En standard binærheapbasert prioritetskø støtter ikke direkte søket etter et av elementene, men den kan forsterkes med en hashtabell som kartlegger elementer til deres posisjon i haugen, slik at denne nedgangsprioriteringsoperasjonen kan utføres i logaritmisk tid. Alternativt kan en Fibonacci-haug utføre de samme operasjonene med redusert prioritet i konstant amortisert tid .

Spesielle tilfeller

Dijkstras algoritme , som et annet eksempel på en ensartet søkealgoritme, kan sees på som et spesialtilfelle av A* hvor for alle x . Generelt dybde-første søk kan implementeres ved hjelp av A* ved å vurdere at det er en global teller C initialisert med en veldig stor verdi. Hver gang vi behandler en node, tildeler vi C til alle de nylig oppdagede naboene. Etter hver enkelt oppgave reduserer vi telleren C med en. Jo tidligere en node blir oppdaget, jo høyere er verdien. Både Dijkstras algoritme og dybde-første søk kan implementeres mer effektivt uten å inkludere en verdi på hver node. ${\ displaystyle h (x) = 0}$${\ displaystyle h (x)}$${\ displaystyle h (x)}$

Egenskaper

Oppsigelse og fullstendighet

På endelige grafer med ikke-negative kantvekter vil A* garantert avsluttes og er komplett , dvs. den vil alltid finne en løsning (en vei fra start til mål) hvis en eksisterer. På uendelige grafer med en endelig forgreningsfaktor og kantkostnader som er avgrenset fra null ( for noen faste ), vil A* garantert bare avsluttes hvis det finnes en løsning. ${\ textstyle d (x, y)> \ varepsilon> 0}$${\ displaystyle \ varepsilon}$

Tillatelse

En søkealgoritme sies å være tillatt hvis den garantert gir en optimal løsning. Hvis den heuristiske funksjonen som brukes av A* er tillatt , er A* tillatt. Et intuitivt ″ bevis ″ på dette er som følger:

Når A* avslutter søket, har den funnet en bane fra start til mål hvis faktiske kostnad er lavere enn den estimerte kostnaden for en bane fra start til mål gjennom en hvilken som helst åpen node (nodens verdi). Når heuristikken er tillatt, er disse estimatene optimistiske (ikke helt - se neste avsnitt), så A* kan trygt ignorere disse nodene fordi de umulig kan føre til en billigere løsning enn den den allerede har. Med andre ord vil A* aldri overse muligheten for en billigere vei fra start til mål, og så vil den fortsette å søke til ingen slike muligheter eksisterer. ${\ displaystyle f}$

Selve beviset er litt mer involvert fordi verdiene til åpne noder ikke garanteres å være optimistiske selv om heuristikken er tillatt. Dette er fordi verdiene til åpne noder ikke er garantert å være optimale, så summen er ikke garantert å være optimistisk. ${\ displaystyle f}$${\ displaystyle g}$${\ displaystyle g+h}$

Optimal effektivitet

Algoritme A er optimalt effektiv med hensyn til et sett med alternative algoritmer Alts på et sett med problemer P hvis for hvert problem P i P og hver algoritme A ′ i Alts , settet med noder som er utvidet med A for å løse P er et delsett (ev. like) av settet med noder utvidet med A ′ for å løse P. Den definitive studien av den optimale effektiviteten til A* skyldes Rina Dechter og Judea Pearl. De vurderte en rekke definisjoner av Alts og P i kombinasjon med A*s heuristiske væring bare tillatt eller å være både konsekvent og tillatt. Det mest interessante positive resultatet de beviste er at A*, med en konsekvent heuristikk, er optimalt effektiv med hensyn til alle tillatte A*-lignende søkealgoritmer på alle ″ ikke-patologiske ″ søkeproblemer. Grovt sett er deres forestilling om ikke-patologisk problem det vi nå mener med "opp til slips". Dette resultatet holder ikke hvis A*s heuristikk er tillatt, men ikke konsekvent. I så fall viste Dechter og Pearl at det finnes tillatte A* -lignende algoritmer som kan utvide vilkårlig færre noder enn A* på noen ikke-patologiske problemer.

Optimal effektivitet handler om settet med noder som er utvidet, ikke antall nodeutvidelser (antall iterasjoner av A *s hovedsløyfe). Når heuristikken som brukes er tillatt, men ikke konsekvent, er det mulig for en node å bli utvidet med A* mange ganger, et eksponentielt antall ganger i verste fall. Under slike omstendigheter kan Dijkstras algoritme overgå A* med stor margin.

Avgrenset avslapning

Et* søk som bruker en heuristikk som er 5,0 (= ε) ganger en konsekvent heuristikk , og får en suboptimal bane.

Selv om akseptkriteriet garanterer en optimal løsningsbane, betyr det også at A* må undersøke alle like meritterte stier for å finne den optimale banen. For å beregne omtrentlige korteste stier, er det mulig å fremskynde søket på bekostning av optimalitet ved å slappe av godkjenningskriteriet. Ofte ønsker vi å binde denne avslapningen, slik at vi kan garantere at løsningsbanen ikke er verre enn (1 + ε ) ganger den optimale løsningsbanen. Denne nye garantien omtales som ε -tillatt.

Det er en rekke ε -tillatte algoritmer:

• Vektet A*/Statisk vekting. Hvis h _a ( n ) er en tillatt heuristisk funksjon, bruker man i den vektede versjonen av A* -søket h _w ( n ) = ε h _a ( n ) , ε > 1 som den heuristiske funksjonen, og utfører A* søket som vanlig (som til slutt skjer raskere enn å bruke h _a siden færre noder utvides). Stien derav funnet av søkealgoritmen kan ha en kostnad på maksimalt ε ganger kostnaden for banen med minst kostnad i grafen.
• Dynamisk vekting bruker kostnadsfunksjonen , hvor og hvor er dybden på søket, og N er den forventede lengden på løsningsbanen.${\ displaystyle f (n) = g (n)+(1+ \ varepsilon w (n)) h (n)}$${\ displaystyle w (n) = {\ begin {cases} 1-{\ frac {d (n)} {N}} & d (n) \ leq N \\ 0 & {\ text {ellers}} \ end {saker }}}$${\ displaystyle d (n)}$
• Samplet dynamisk vekting bruker prøvetaking av noder for bedre å estimere og debiasere den heuristiske feilen.
• ${\ displaystyle A _ {\ varepsilon}^{*}}$. bruker to heuristiske funksjoner. Den første er FOCAL -listen, som brukes til å velge kandidatnoder, og den andre h _F brukes til å velge den mest lovende noden fra FOCAL -listen.
• A _ε velger noder med funksjonen , der A og B er konstanter. Hvis ingen noder kan velges, vil algoritmen gå tilbake med funksjonen , der C og D er konstanter.${\ displaystyle Af (n)+Bh_ {F} (n)}$${\ displaystyle Cf (n)+Dh_ {F} (n)}$
• AlphA* prøver å fremme dybde-første utnyttelse ved å foretrekke nylig utvidede noder. ALPHA * benytter seg av kostfunksjonen , hvor der λ og Λ er konstanter med , π ( n ) er den overordnede av n , og ñ er den mest nylig utvidet node.${\ displaystyle f _ {\ alpha} (n) = (1+w _ {\ alpha} (n)) f (n)}$${\ displaystyle w _ {\ alpha} (n) = {\ begin {cases} \ lambda & g (\ pi (n)) \ leq g ({\ tilde {n}}) \\\ Lambda & {\ text {ellers }} \ end {cases}}}$${\ displaystyle \ lambda \ leq \ Lambda}$

Kompleksitet

Den tidskompleksitet av A * avhenger av heuristisk. I verste fall med et ubegrenset søkeområde, er antall utvidede noder eksponentielt i dybden av løsningen (den korteste banen) d : O ( b ^d ) , hvor b er forgreningsfaktoren (gjennomsnittlig antall etterfølgere per stat ). Dette forutsetter at en måltilstand eksisterer i det hele tatt, og er tilgjengelig fra starttilstanden; hvis det ikke er det, og tilstandsområdet er uendelig, vil ikke algoritmen avsluttes.

Den heuristiske funksjonen har stor effekt på den praktiske utførelsen av A* -søk, siden en god heuristikk gjør at A* kan beskjære bort mange av b ^d -nodene som et uinformert søk ville utvide. Kvaliteten kan uttrykkes i form av den effektive forgreningsfaktoren b * , som kan bestemmes empirisk for en problemforekomst ved å måle antall noder generert ved ekspansjon, N og dybden på løsningen, og deretter løse

${\ displaystyle N+1 = 1+b^{*}+(b^{*})^{2}+\ dots+(b^{*})^{d}.}$

Gode ​​heuristikker er de med lav effektiv forgreningsfaktor (det optimale er b * = 1 ).

Tidskompleksiteten er polynom når søkeområdet er et tre, det er en enkelt måltilstand, og den heuristiske funksjonen h oppfyller følgende betingelse:

${\ displaystyle | h (x) -h^{*} (x) | = O (\ log h^{*} (x))}$

hvor h ^* er den optimale heuristen, den eksakte kostnaden for å komme fra x til målet. Med andre ord vil feilen til h ikke vokse raskere enn logaritmen til den "perfekte heuristiske" h ^* som returnerer den sanne avstanden fra x til målet.

Den plass kompleksiteten av A * er omtrent den samme som for alle andre graf søkealgoritmer, som man vil holde alle genererte noder i minnet. I praksis viser dette seg å være den største ulempen ved A* -søk, noe som fører til utvikling av hukommelsesbegrensede heuristiske søk, for eksempel Iterativ utdypning A* , minnegrenset A* og SMA* .

applikasjoner

A* brukes ofte for det vanlige banen til å finne problemer i applikasjoner som videospill, men ble opprinnelig designet som en generell graftraversalgoritme. Den finner applikasjoner i forskjellige problemer, inkludert problemet med å analysere ved hjelp av stokastiske grammatikker i NLP . Andre tilfeller inkluderer et informasjonssøk med online læring.

Forhold til andre algoritmer

Det som skiller A* fra en grådig best-first-søkealgoritme, er at den tar kostnad/distanse som allerede er reist, g ( n ) , i betraktning.

Noen vanlige varianter av Dijkstras algoritme kan sees på som et spesialtilfelle av A* der heuristikken for alle noder; på sin side er både Dijkstra og A* spesielle tilfeller av dynamisk programmering . A* i seg selv er et spesielt tilfelle av en generalisering av gren og bundet . ${\ displaystyle h (n) = 0}$

Varianter

• Når som helst A*
• Blokk A*
• D*
• Felt D*
• Frynser
• Fringe Saving A* (FSA*)
• Generalisert adaptiv A* (GAA*)
• Inkrementell heuristisk søk
• Redusert A*
• Iterativ utdypning A* (IDA*)
• Søk med hoppepunkt
• Livslang planlegging A* (LPA*)
• Ny toveis A* (NBA*)
• Forenklet minne begrenset A* (SMA*)
• Theta*

A* kan også tilpasses en toveis søkealgoritme. Spesiell forsiktighet må utvises for stoppkriteriet.

Se også

• Bredde-første søk
• Dybde-første søk
• Planlegging av alle vinkler , søk etter stier som ikke er begrenset til å bevege seg langs grafkanter, men som kan ta hvilken som helst vinkel

Merknader

Referanser

Videre lesning

• Nilsson, NJ (1980). Prinsipper for kunstig intelligens . Palo Alto, California: Tioga Publishing Company. ISBN 978-0-935382-01-3.

Eksterne linker

• Klar visuell A* forklaring, med råd og tanker om stifinning
• Variasjon på A* kalt Hierarchical Path-Finding A* (HPA*)
• Brian Grinstead. "A* Søkealgoritme i JavaScript (oppdatert)" . Arkivert fra originalen 15. februar 2020 . Hentet 8. februar 2021 .