Algoritem A*

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Algoritem A* poišče najkrajšo pot med izbranima točkama v grafu.

Primer

Delovanje algoritma ponazorimo na nekoliko poenostavljenem področju iskanja. Izberimo pravokotno mrežo.

Na spodnji sliki je mesto A označeno z zelenim kvadratom, mesto B je označeno z rdečim kvadratom, moder pravokotnik pa je zid med njima.

Slika:Aslika1.jpg

Začnemo pri točki A. Dodamo jo na odprt seznam kvadratov, ki nam pridejo v poštev pri iskanju najkrajše poti. Odprt seznam je podoben nakupovalnemu listku. Trenutno je na njem samo en predmet (kvadrat), kasneje pa jih bomo dodali še več. Vsebuje kvadrate, ki bodo mogoče na naši poti - mogoče pa tudi ne bodo. Torej, to je seznam kvadratov, ki jih moramo preveriti.

Pogledamo vse sosednje kvadrate, spustimo "neprehodne" kvadrate (z zidovi, vodo...) in vse primerne kvadrate dodamo na odprt seznam. Za vsakega od teh kvadratov shranimo točko (kvadrat) A kot očeta.

Odstranimo kvadrat A s seznama in ga dodamo na zaprt seznam, na katerem so kvadrati, ki jih zaenkrat ni potrebno več preverjati.

V naslednjem koraku izberemo enega izmed sosednjih kvadratov in ponovimo postopek.


Pri odločanju, katerega izmed sosednjih kvadratov izberemo, nam pomaga naslednja enačba:

F = G + H

kjer je

G = cena premika od začetne točke A do izbranega kvadrata na mreži po poti.

H = cena premika od izbranega kvadrata do končne točke B. Pri iskanju H ugibamo, saj dejanske oddaljenosti do točke B ne vemo, dokler ne najdemo poti. Ena izmed metod, kako določiti H, je "Manhattan" metoda. Pri tej metodi pogledamo, koliko kvadratov je do naše končne točke. Premikamo se samo vodoravno ali navpično in ne upoševamo morebitnih ovir na poti.

F izračunamo tako, da seštejemo G in H.

Pot sestavimo tako, da znova in znova pregledujemo odprt seznam in izbiramo kvadrate z najmanjšim F rezultatom. Naše iskanje je končano, ko dodamo kvadrat B na zaprt seznam.

Povzamimo cel postopek na enem mestu:

  1. Dodajmo začetni kvadrat (ali node) na odprt seznam.
  2. Ponavljajmo naslednje:
    1. Poiščimo kvadrat z nanižjo F vrednostjo na odprtem seznamu. Ta kvadrat "poimenujemo" trenutni (oz. izbrani) kvadrat.
    2. Izbrani kvadrat prestavimo na zaprt seznam.
    3. Za vsakega od sosednjih kvadratov izbranega kvadrata:
      Če je neprehoden ali če je na zaprtem seznamu, ga ne upoštevamo. V nasprotnem primeru naredimo sledeče:
      Če ni na odprtem seznamu, ga nanj dodamo in naš izbrani kvadrat postane njegov oče.
      Če je že na odprtem seznamu, pogledamo če je pot čez izbrani kvadrat boljša. Pri tem si pomagamo z G vrednostjo. Nižja G vrednost pomeni, da je pot boljša. Če je, postane izbrani kvadrat njegov oče in na novo izračunamo G in F.
    4. Končamo ko:
      dodamo končni kvadrat na zaprt seznam. V tem primeru je bila pot najdena.
      Če ne najdemo končnega kvadrata in je odprt seznam prazen. V tem primeru ni poti.
  3. Shranimo pot. Začnemo pri končnem kvadratu in se pomikamo nazaj od kvadrata do njegovega očeta. To nas na koncu pripelje do začetne točke in že imamo najkrajšo pot.
Osebna orodja