b'\n_START_ARTICLE_\nA*\n_START_PARAGRAPH_\nA* (uttales \xc2\xabA star\xc2\xbb eller \xc2\xabA stjerne\xc2\xbb) er en s\xc3\xb8kealgoritme for \xc3\xa5 effektivt kunne traversere noder i grafer. Den er kjent for \xc3\xa5 v\xc3\xa6re effektiv og presis og blir brukt mye innen kunstig intelligens. Den bruker en ekstensjon av Dijkstras algoritme. A* tar i bruk heuristikk som gj\xc3\xb8r den mer effektiv. Algoritmen ble f\xc3\xb8rst beskrevet av Peter Hart, Nils Nilsson og Bertram Raphael ved SRI International i 1968.\n_START_SECTION_\nProsess\n_START_PARAGRAPH_\nDet f\xc3\xb8rste algoritmen gj\xc3\xb8r er \xc3\xa5 s\xc3\xb8ke gjennom de stiene som mest sannsynlig leder til m\xc3\xa5let. Det som skiller A* fra beste-f\xc3\xb8rst-s\xc3\xb8k og andre gr\xc3\xa5dige algoritmer er at den tar hensyn til distansen den allerede har dekket (g(x))._NEWLINE_Den starter med den f\xc3\xb8rste noden, og opprettholder en k\xc3\xb8 av noder som skal bes\xc3\xb8kes. Nodene er sortert etter verdien av , den som har lavest  verdi er f\xc3\xb8rst i k\xc3\xb8en. I hvert steg av algoritmen vil noden med lavest  verdi fjernes fra k\xc3\xb8en og  og  verdiene til naboene til noden vil bli oppdatert og lagt til i k\xc3\xb8en. Dette fortsetter helt til en m\xc3\xa5l-node har lavest  verdi i k\xc3\xb8en, eller til k\xc3\xb8en er tom (ingen l\xc3\xb8sning finnes). M\xc3\xa5l-noder kan bli passerte flere ganger i algoritmen men siden det finnes andre stier med lavere  verdi stopper ikke algoritmen f\xc3\xb8r den finner den korteste veien.\n_START_SECTION_\nEksempel\n_START_PARAGRAPH_\nEtt eksempel der en A* algoritme s\xc3\xb8ker 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\xc3\xa5l-node som heuristikk.\n_START_SECTION_\nEgenskaper\n_START_PARAGRAPH_\nI likhet med bredde-f\xc3\xb8rst-s\xc3\xb8k er A* komplett og vil alltid finne en l\xc3\xb8sning om den finnes._NEWLINE_Om heuristikk funksjonen er tillatelig (at den aldri overestimerer), er A* selv tillatelig og optimal s\xc3\xa5vidt at vi ikke bruker et lukket sett. _NEWLINE_A* er ogs\xc3\xa5 optimalt effektiv for hvilken som helst heuristikk . Dette betyr at ingen annen algoritme som tar i bruk samme heuristikk vil bes\xc3\xb8ke f\xc3\xa6rre noder enn A*.\n_START_SECTION_\nKompleksitet\n_START_PARAGRAPH_\nTids-kompleksiteten til A* er avhengig av heuristikk funksjonen. I verste scenario er antallet noder  bes\xc3\xb8kt eksponentiell i vekst i forhold til lengden  av l\xc3\xb8sningen:  der  er forgreinings-faktoren (gjennomsnittet av ut-kanter per node). Dette forutsetter at det finnes en l\xc3\xb8sning.'