Vis kilden til A*

'''A*''' (uttales «A star» eller «A stjerne») er en [[algoritme|søkealgoritme]] for å effektivt kunne traversere [[node (grafteori)|noder]] i [[Grafteori|grafer]]. Den er kjent for å være effektiv og presis og blir brukt mye innen [[kunstig intelligens]]. Den bruker en ekstensjon av [[Dijkstras algoritme]]. A* tar i bruk [[heuristikk]] som gjør den mer effektiv. Algoritmen ble først beskrevet av Peter Hart, Nils Nilsson og Bertram Raphael ved [[SRI International]] i 1968.<ref>{{Kilde bok|tittel = A Formal Basis for the Heuristic Determination of Minimum Cost Paths|etternavn = Hart|fornavn = P. E.|utgiver = IEEE|år = 1968|sider = 100-107|issn = 0536-1567}}</ref>

== Beskrivelse ==
A* bruker beste-først søk og finner stien med minst kostnad gitt en initiell node til en mål-node. A* følger stien med minst forventet total kostnad. Den holder en prioritetsliste av alternative stier og om kostnaden på den nåværende stien overstiger den første i listen kan den skifte alternativ.

Det som gjør at A* er så effektiv er det at den tar i bruk heuristikk for å finne ut hvilke av nodene i treet den bør søke gjennom først. Dette blir representert som en funksjon <math>f(x)</math> som er en sum av to funksjoner:

* en funksjon som er distansen fra start-noden til den nåværende noden x (vanligvis <math>g(x)</math>)
* en heuristikk funksjon som er en estimering av distansen fra x til målet (vanligvis <math>h(x)</math>).
For at A* skal være optimal må <math>h(x)</math> aldri overestimere kostnaden for å nå målet. Det vil si at den er [[tillatelig]] (engelsk: admissible).

== Prosess ==
Det første algoritmen gjør er å søke gjennom de stiene som mest sannsynlig leder til målet. Det som skiller A* fra [[beste-først-søk]] og andre [[Grådig algoritme|grådige algoritmer]] er at den tar hensyn til distansen den allerede har dekket (g(x)).

Den starter med den første noden, og opprettholder en kø av noder som skal besøkes. Nodene er sortert etter verdien av <math>f(x)</math>, den som har lavest <math>f</math> verdi er først i køen. I hvert steg av algoritmen vil noden med lavest <math>f</math> verdi fjernes fra køen og <math>f</math> og <math>g</math> verdiene til naboene til noden vil bli oppdatert og lagt til i køen. Dette fortsetter helt til en mål-node har lavest <math>f</math> verdi i køen, eller til køen er tom (ingen løsning finnes). Mål-noder kan bli passerte flere ganger i algoritmen men siden det finnes andre stier med lavere <math>f</math> verdi stopper ikke algoritmen før den finner den korteste veien.

== Eksempel ==
[[Fil:Astar progress animation.gif|thumb|Illustrasjon av A* for å finne en sti fra start-node til en mål-node. De tomme sirklene representerer nodene som ikke er funnet enda. De fylte sirklene er de som er besøkt og de tomme blå sirklene er det som blir søkt igjennom. Den grønne sirkelen er mål-noden.]]
Ett eksempel der en A* algoritme søker gjennom en graf av byer(noder) koblet sammen av veier(kanter). Dette eksempelet bruker distansen i en rett linje(tenk fly) fra node til mål-node som heuristikk.

[[Fil:AstarExampleEn.gif|frameless|400x400px]]
== Egenskaper ==
I likhet med [[bredde-først-søk]] er A* komplett og vil alltid finne en løsning om den finnes.

Om heuristikk funksjonen er tillatelig (at den aldri overestimerer), er A* selv tillatelig og optimal såvidt at vi ikke bruker et lukket sett. 

A* er også optimalt effektiv for hvilken som helst heuristikk <math>h</math>. Dette betyr at ingen annen algoritme som tar i bruk samme heuristikk vil besøke færre noder enn A*.

== Kompleksitet ==
Tids-kompleksiteten til A* er avhengig av heuristikk funksjonen. I verste scenario er antallet noder <math>n</math> besøkt eksponentiell i vekst i forhold til lengden <math>l</math> av løsningen: <math>n(b^d)</math> der <math>b</math> er forgreinings-faktoren (gjennomsnittet av ut-kanter per node). Dette forutsetter at det finnes en løsning.

== Referanser ==
<references/>
{{Autoritetsdata}}

[[Kategori:Kunstig intelligens]]
[[Kategori:Algoritmer]]
[[Kategori:Søkealgoritmer]]