Yazılım Mühendisliği ve Teknolojiler üzerine…

0%

A* Algoritması (A yıldız arama algoritması)

Yayın Kategori

Amacı : Bir düğümden, diğer düğüme en az maliyetli çözümü bulmak

Türü : Arama Algoritması, Sezgisel Algoritma (Yapay zeka)

Kâşifleri : Nils Nilsson,Bertram Raphael , Peter E. Hart

Kullanım yerleri :

  • Yol bulma
  • Oyunlarda aktörün hedefe doğru izleyeceği yolların tespiti
  • Gezgin satıcı probleminin çözümü
  • Labirentten en kısa çıkışı bulma
 

f(x) : durum fonksiyonu. Az olması, o durumun daha az maliyetli olduğunu belirtir.

f(x) = g(x) + h(x)

g(x) : Başlangıç durumuna göre maliyetimiz.

h(x) : Bitiş duruma olan sezgisel maliyet.

Algoritma

OPEN -> // fCost'a göre sıralı dizi


OPEN.ekle(başlangıç_düğümü)


DÖNGÜ - OPEN dizi boyutu 0 olmadığı müddetçe
    şuanki_düğüm <- OPEN.ilk elemanı
    OPEN.sil(şuanki düğüm)
    EĞER şuanki_düğüm, hedef düğüm ise
        DÖNGÜden çık // HEDEFE ULAŞTI
    şuanki_düğüm.closed=true
    şuanki_düğüm.gCostHesapla()
    komşular = şuanki_düğüm.komşular
    DÖNGÜ komşu <- komşular
        EĞER komşu.closed ise SONRAKİ_KOMŞUYA_GEÇ
        maliyet = şuanki_düğüm.gCost + komşuya_uzaklık
        komşu.gCostHesapla()
        EĞER komşu.OPENdaDeğilse veya maliyet<komşu.gCost ise
            komşu.gCost = maliyet
            komşu.hCostHesapla()
            komşu.ebeveyn = şuanki_düğüm
            EĞER komşu.OPENdaDeğilse
                OPEN.ekle(komşu)
OPEN dizi boyutu 0 olduğu için DÖNGÜden çıkıldıysa // HEDEFE ULAŞAMADI

Javascript Kodu

FIND (Yol bulmayı başlat)
RELOAD (Gridi yeniden yükle)
ilk tık -> başlangıç karesi
2. tık -> hedef kare
sonraki tıklar -> engel oluştur

See the Pen A* Algoritması by farukcan (@farukcan) on CodePen.

İlgili Gönderiler