Algoritem A*

Algoritem A*

Avtor: Sandi Hrvačanin

Motiv

Imamo podani dve točki oz. dve vozlišči na grafu. Med njima bi radi poiskali najcenejšo ali najkrajšo pot.

Premislek

  • Dijkstrov algoritem bi deloval
  • Iskali bi toliko časa dokler algoritem ne bi prišel iz začetne točke v našo končno točko
  • Pri tem bi iskali tudi v napačno smer, zato Dijkstrov algoritem malo popravimo
  • Ne nadaljujemo iz vozlišča, ki je najbližje izhodišču ampak iz vozlišča, ki je hkrati najbližje izhodišču in končni točki
(http://www2.nauk.si/files/665/dijkstra.png)
Dijkstrov algoritem - [1]

O algoritmu

Algoritem so izumili in izpopolnili Peter Hart, Nils Nilsson in Bertram Raphael s Stanford Reserch inštituta leta 1968. Želeli so razviti algoritem za navigacijo robota Shakey po sobi z ovirami.

Iskalni algoritem A* je eden najbolj znanih in najpopularnejših algoritmov umetne inteligence. Zasnovan je na podlagi hevristike - pristopa k reševanju problemov z izkušnjami ali predvidevanjem. V zameno za hitrejše delovanje izgubimo natančnost ali optimalnost.

(http://www2.nauk.si/files/665/a-star.png)
Iskalni algoritem A* - [2]

O algoritmu

Za razliko od Dijkstrovega algoritma, ki iz množice odprtih vozlišč vzame vozlišče, ki je najbližje začetnemu, pri algoritmu A* vzamemo vozlišče z minimalno vrednostjo funkcije .

  • , kjer sta:

    • je cena poti od začetnega vozlišča Z do vozlišča X in
    • je ocenjena cena najcenejše poti od vozlišča X do končnega vozlišča K.

Za izračun funkcije lahko uporabimo nekaj različnih načinov za merjenje razdalje (nekatere ocene razdalj lahko precenijo ceno povezav, zato niso vse ocene primerne):

  • Manhattanska razdalja:
  • Evklidska razdalja:
  • Chebysheva razdalja:

Psevdokoda

Vhod: graf G, začetno vozlišče, končno vozlišče

Izhod: najkrajša pot od začetnega do končnega vozlišča v grafu G (če obstaja pot med njima)

  1. Množica zaprtih vozlišč je prazna (množica že pregledanih).
  2. Množica odprtih vozlišč vsebuje začetno vozlišče (množica bo vsebovala vsa vozlišča, ki jih bo potrebno pregledati).
  3. Izvajamo naslednjo zanko dokler množica odprtih vozlišč ni prazna:

    1. Izberemo vozlišče n, ki ima najmanjšo vrednost f(n).
    2. Če je vozlišče n končno algoritem zaključimo in dobimo pot.
    3. Za vsako sosedno vozlišče m (ki ni zaprto) vozlišča n preverimo:

      • Če vozlišče m ni v množici odprtih, ga moramo še pregledati in ga dodamo med odprte. Zanj moramo izračunati vrednosti funkcij f(m), g(m) in h(m). Za njegovega očeta postavimo vozlišče n.
      • Če je vozlišče m že v množici odprtih preverimo ali cena povezav prek vozlišča n cenejša od trenutne poti do m. Ko je to res moramo posodobiti funkcije f(m) in g(m) ter oče postane vozlišče n.
    4. Vozlišče n odstranimo iz množice odprtih in ga dodamo med zaprte.
  4. Množico odprtih smo spraznili preden smo prišli do končnega vozlišča. Torej pot med začetnim in končnim vozliščem ne obstaja.

Primerjava

(http://www2.nauk.si/files/665/Astar_animation.gif)
Algoritem A* - [3]
(http://www2.nauk.si/files/665/Dijkstra_animation.gif)
Dijkstrov algoritem - [4]

Primer 1

Prikaz delovanja s komentarji na primeru

Zeleno polje je začetna točka, oranžno polje je končna točka, črna polja predstavljajo zid. Radi bi poiskali najkrajšo pot med zelenim in oranžnim poljem.

Primer 2

Prikaz delovanja s komentarji na primeru

Primer delovanja algoritma, kjer mora sesalec (zelen objekt) s prazno baterijo, kar se da hitro priti do polnilne postaje (rdeč objekt).

Kviz 1

Izberi pravilno trditev:


Preveri

Odgovor je pravilen.Dijkstrov algoritem je oblika algoritma A* pri katerem je .


Naprej

Odgovor je napačen. Dijkstrov algoritem je oblika algoritma A* pri katerem ne moremo oceniti razdalje do končnega vozlišča oz. .


Naprej

Kviz 2

Ob vsali ponovitvi koraka zanke med odprtimi vozlišči izberemo vozlišče, ki ima:


Preveri

Odgovor je pravilen.


Naprej

Odgovor je napačen.


Naprej

Kviz 3

Algoritem A* je algoritem umetne inteligence, ker:


Preveri

Odgovor je pravilen.


Naprej

Odgovor je napačen.


Naprej

Kviz 4

Katero polje (vozlišče) se bo pregledalo ob naslednjem koraku - glej sliko:

(http://www2.nauk.si/files/665/nasled_0.png)


Preveri

Odgovor je pravilen.


Naprej

Odgovor je napačen.


Naprej

Kviz 5

Kolikšna bo končna vrednost poti med začetnim in končnim vozliščem - glej sliko:

(http://www2.nauk.si/files/665/konec.png)


Preveri

Odgovor je pravilen.


Naprej

Odgovor je napačen.


Naprej

Viri

0%
0%