A* Sökalgoritm

A* (uttalad "A star" eller "A-stjärna") är en sökalgoritm för att effektivt navigera genom knutpunkter i en graf. A* är känt för att vara effektiv och exakt och används ofta inom artificiell intelligens. A* använder en förlängning av Dijkstras algoritm. A* använder sig av heuristik för att effektivisera sökningen. Algoritmen beskrivs först år 1968 av Peter Hart, Nils Nilsson och Bertram Raphael på SRI-International (f.d Stanford Research Institute) i Förenta Staterna.

Beskrivning

A* använder sig av en bäst-först sökning för att generellt minska kostnaden (distansen till målet) genom att välja noder baserat på prioritet. Algoritmen baserar sin prioritet med hjälp av den minst förväntade totala kostnad med hjälp av en additiv funktion av två andra funktioner.

• $g(x)$ - Kostnaden ifrån start till nuvarande nod
• $h(x)$ - Estimerad kostnad (baserad på distans) från nuvarande nod till målet

Den totala estimerade kostnaden av en nod som genomsöks $f(x)$ beräknas och den minst kostsamma noden läggs till i sökvägen.

$f(x)=g(x) h(x)$

För att A* skall förbli optimal bör $h(x)$ aldrig överestimera kostnaden för att nå målet, det vill säga att den är tillåtlig. (engelska: admissible).

Processen

Det första algoritmen gör är att söka igenom den stigen som mest sannolikt leder till målet. Det som skiljer bäst-först-sökning och andra giriga algoritmer från A* är att tar hänsyn till kostnaden av den redan täckta vägen, $g(x)$.

Algoritmen börjar med den första noden, och sparar en kö av noder som ska besökas. Nodernas sortering är baserade på deras värden $f(x)$, där lägst $f$ placeras först i kön. För varje steg i algoritmen tas noden med lägst $f$ i listan (det vill säga först i kön) bort. Efter det beräknas $f$ och $g$ för alla dess grannar och de i sin tur läggs till i kön. Detta repeteras tills målet (noden) är först i kön, det vill säga har lägst kostnad eller om kön blir tom (ingen lösning).

Exempel

Illustration av A* för att finna en väg från start-noden till ett mål. Ifyllda cirklar representerar genomsökta noder och de tomma blå är potentiella noder (i listan). Den gröna cirkeln är målet.

Ett exempel av en A* algoritm söker igenom en graf av tunnelbanestationer (noder) sammankopplade av järnvägar (kanter). I detta exemplet baseras $h(x)$ på den raka distansen (tänk flyg) mellan nuvarande position till målet. Algoritmen följer vänstra vägen tills den når $c$ där $f(d)$ har lägre kostnad än $f(c)$, detta visar att algoritmen kan arbeta på flera vägar samtidigt.

Egenskaper

Precis som bredden-först-sökning är A* komplett och kommer alltid finna en lösning om sådan finns.

Om heuristik-funktionen är tillåtlig (ej överestimerarande), är A* själv tillåtlig och optimal såvida inte använder en sluten används.

A* är optimal för alla heuristiker $h(x)$. Detta betyder att ingen annan algoritm som använder sig av samma heuristik kommer besöka färre noder än A*.

Komplexitet

A* sökning som använder en heuristik som är 5.0(=ε) gånger en Konsekvent Heurestik, och erhåller ett sub-optimalt resultat.

Tidskomplexiteten av A* är beroende av den valda heuristik-funktionen. Det värsta fallet med ett obegränsat sökutrymme är antalet utökande noder $n$ exponentiellt i djupet $l$ (engelska: length) av lösningen (den kortaste vägen) $n(b^{d})$ där $b$ är divisionsfaktorn (medelvärdet av kanter per nod). Detta antar att det finns en lösning.

Applikationer

A* är vanligen använd för det allmänna vägsökningsproblemet i applikationer som spel, men var originellt designat som en generell graf-navigerande algoritm.