A* Sökalgoritm
Den här artikeln behöver källhänvisningar för att kunna verifieras. (2018-03) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan. |
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
[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, .
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 , där lägst placeras först i kön. För varje steg i algoritmen tas noden med lägst i listan (det vill säga först i kön) 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ön, det vill säga har lägst kostnad eller om kön blir tom (ingen lösning).
Exempel
[redigera | redigera wikitext]![](http://upload.wikimedia.org/wikipedia/commons/5/5d/Astar_progress_animation.gif)
Ett exempel av 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 tills den når där har lägre kostnad än , detta visar att algoritmen kan arbeta på flera vägar samtidigt.
Egenskaper
[redigera | redigera wikitext]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 . 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]![](http://upload.wikimedia.org/wikipedia/commons/8/85/Weighted_A_star_with_eps_5.gif)
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 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 som en generell graf-navigerande algoritm.