Redigerer A* (avsnitt)

== 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).