A* Sökalgoritm

Från Wikipedia
Hoppa till navigering Hoppa till sök

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 effektivt 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 året 1968 av Peter Hart, Nils Nilsson och Bertram Raphael på SRI-International (f.d Stanford Research Institute) i Förenta Staterna.

Beskrivning[redigera | redigera wikitext]

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.

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

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

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

Processen[redigera | redigera wikitext]

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 bör besökas. Nodernas sortering är baserade på deras värden , där lägst placeras högst i kön. För varje steg i algoritmen vill nöden med lägst i listan (det vill säga först i kö) tas bort. Efter det beräknas och 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ö, det vill säga har lägst kostnad eller om kön blir tom (ingen lösning).

Exempel[redigera | redigera wikitext]

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

AstarExampleEn.gif

Egenskaper[redigera | redigera wikitext]

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

Om heuristik-funktionen är tillåtlig (att den inte överestimerar), är A* själv tillåtlig och optimal såvida att vi inte använder en sluten uppsättning.

A* är också optimalt för vilken heuristik som helst . Detta betyder att ingen annan algoritm som använder sig av samma heuristik kommer besöka färre noder än A*.

Komplexitet[redigera | redigera wikitext]

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

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

Applikationer[redigera | redigera wikitext]

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

Referenser[redigera | redigera wikitext]