A Yıldız Arama Algoritması (A Star Search Algorithm, A*)

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde en kısa yol bulmak için kullanılan algoritmalardan birisidir. Örneğin seyyar tüccar problemi (travelling salesman problem, TSP) gibi bir problemin çözümünde kullanılabilir. Benzer şekilde oyun programlamada, oyunda bulunan oyuncuların en kısa yolu bularak hedefe gitmeleri için de sıklıkla kullanılan algoritmadır.

Kısaca bir düğümden (node) hedef bir düğüme (target node) en kısa hangi düğümler üzerinden gidileceğini bulmaya yarayan “en iyi yerleştirme (best fit)” algoritmasıdır.

A* algoritması yapı olarak muteber sezgisel (admissable heuristic) bir algoritma olarak sınıflandırılabilir. Bunun sebebi algoritmasının mesafe hesaplamada kullandığı fonksiyondur:

f(n) = g(n) + h(n)

denklemindeki

f(n) = hesaplama yapan sezgisel (heuristic) fonksiyon.
g(n) = Başlangıç düğümünden mevcut düğüme kadar gelmenin maliyeti
h(n) = Mevcut düğümden hedef düğüme varmak için tahmin edilen mesafe.

Dikkat edileceği üzere f(n) fonksiyonunun sezgisel olma sebebi, bu fonksiyon içerisinde bulunan ve tahmine dayalı olan h(n) sezgisel fonksiyonudur.

Algoritmanın çalışması:

Algoritma yukarıdaki toplama işlemini kullanan oldukça basit bir yapıya sahiptir. Veri yapısı olarak bir öncelik sırası (priority queue) kullanan algoritmada en öncelikli olan düğüm f(n) değeri en düşük olan düğümdür.

  1. Algoritma her adımda en düşük değeri (Ve dolayısıyla en önemli) düğümü alır (yani bu düğüme gider) ve düğümü sıradan (queue) çıkarır.
  2. Gidilen bu düğüme göre komşu olan bütün düğümlerin değerleri güncellenir (artık bu düğüme gelmenin bir maliyeti vardır ve dikkat edilirse f(n) fonksiyonu içerisinde bu değer yer almaktadır.)
  3. Algoritma yukarıdaki adımları hedefe varana kadar (yani hedef düğümü öncelik sırasında (priority queue) en öne gelene kadar) veya sırada (queue) düğüm kalmayana kadar tekrarlar.

Örnek Çalışma:

Algoritmanın çalışması için aşağıdaki örneği ele alalım:

Yukarıdaki grafikte sol üst köşedeki düğümden, sağ alt köşedeki düğüme gitmek isteyelim. Bu durumda f(n) fonksiyonunu oluşturan mesafe değeri, grafik üzerindeki yol maliyetleri olarak hesaplanbilir. Sezgisel fonksiyon olarak, bir düğümün hedefe olan kuş uçuşu mesafesini alalım. Yani iki düğüm arasındaki mesafeyi çizilen yoldan değil de iki düğüm arasındaki cetvel ile ölçülen değer olarak kabul edelim.

Bu durumda düğümlerin sezgisel mesafelerini (heuristic) gösteren graf aşağıdaki şekildedir:

Yukarıdaki bu grafikte kırmızı renkle gösterilen değerler, o düğümden hedef düğüm olan sağ alt köşedeki düğüme olan kuş uçuşu mesafeyi göstermektedir. Bu değerleri kısaca h(n) olarak kabul edebiliriz.

Başlangıç düğümümüz olan sol üst köşedeki düğümden başlayarak iki düğümün değerini hesaplayalım. Başlangıcın altında bulunan düğüm için h(n) = 9 ve g(n) = 4 olmaktadır.

Başlangıcın sağında bulunan düğüm için ise h(n) = 8 ve g(n) = 3 olmaktadır. Buna göre:

f(aşağı) = 9+4 = 13

f(sağa) = 8 +3 = 11

olarak bulunmaktadır. Algoritmamız bu seçimler arasından küçük olan (ve önceliği yüksek olan) sağa gitmeyi tercih eder.

Bu seçimi aşağıdaki şekilde gösterelim.

Yukarıdaki bu seçimden sonra değerler tekrar hesaplanır. Yukarıda yapılan seçime göre düğümlerin değerleri tekrar f(n) = g(n) + h(n) olarak hesaplanırsa:

Yukarıdaki bu grafikte görüldüğü üzere sıramızda (queue) iki düğüm bulunmakta ve iki düğümün değerleri sırasıyla 13 ve 11 olmaktadır.

Bu durumda 11 olan düğümü seçip aşağı doğru hareket ediyoruz.

Yukarıdaki son durumda 13 ve 21 değerleri olan iki düğüm arasında seçim yapıldığında, kısa değer olarak 13 bulunduğu için A* arama algoritmamız bu aşamada geldiği alternatif yoldan vaz geçerek en kısa yolun bu yeni düğüm olabileceğini düşünür ve bu yola gider.

Yukarıdaki şekilde bu yeni seçim yeşil renk ile gösteirlmiştir. Yeni seçim yapıldıktan sonra ulaşılan komşu düğümler 14 ve 21 değerlerine sahiptir. Bu durumda 14 değerine sahip olan daha öncelikli düğüme hareket edilecektir.

Yeni halinde değerler hesaplandığında sonuç düğümüne gidilmesi mümkündür ve ulaşım değeri yukarıdaki dolaşmaya göre daha düşüktür.

Yukarıdaki son durumda hedefe ulaşılmış ve aşağıdaki yol kullanılmıştır. Sonuçta ulaşım için harcanan mesafe toplandığında 4+6+4 =14 mesafesi diğer alternatif olan 3+4+6+8 =21 değerine göre daha kısadır.

Tabi A* algoritması sezgisel bir algoritma olduğu için bu durumu bilmemektedir.

Yorumlar

  1. Anonim

    Tesekkurler devamini bekliyoruz, ufak bi katki olarak, dugumlere isim verilirse daha da rahat okunabilir hale gelecektir. Cok tesekkurler

  2. Linker

    Teşekkürler faydalı bir çalışma fakat son cümleniz çelişiyor sanırım anlattıklarınızla

    açıklayabilir misiniz??

    sezgisel olduğu için anlamıyor mu ? yanlış sonucu mu buluyor ?

    şimdiden teşekkürler

  3. Şadi Evren ŞEKER Article Author

    Cümleyi farklı anlamış olmanızı anlıyorum. Anlatılmak istenen, 14 uzunluğundaki en kısa yolu, astar algoritmasının sezgisel olarak ararken ilk seferde bulamamasıdır. Algoritmamız, sonuç düğümüne giden yolu ilk bulduğunda, bu yol uzunluğu 21’dir. Dolayısıyla sezgisel arama sonucunda en kısa yolu her zaman bulamayabilir.

    başarılar

  4. kara

    Çok güzel anlatılmış gerçekten teşekkürler herşey çok temiz anlaşılıyor. bunu daha komplex bağlantılı yapılarda (Array üzerinde olabilir) uygulama olarak anlatılsa aslında çok daha faydalı hemde insanların programlarına başlamadan bakabileceği olayın array üzerinde uygulaması böyle oluyor anladım diyebileceği bir kaynak olabilir

  5. Şadi Evren ŞEKER Article Author

    bu değer sezgisel değerdir. Örneğin şehirleri (yukarıdaki haritayı) bir kağıda bastırın.

    Sonra şehirler arasındaki mesafeleri cetvel ile ölçün ve şehirlerin arasına yazın ( bu değerler yukarıdaki yazıda f(n) olarak ifade edilmiştir)

    Ardından her şehirden ayrı ayrı sonuç düğümüne olan mesafeyi cetvel ile ölçün (bu değer de h(n) olarak ifade edilmiştir) işte sezgisel mesafe bu doğrudan ölçülen değer olur.

    Şu şekilde bir örnekle anlatabilirsiz sanırım, siz karşınızdaki dağda bir köy gördüğünüzü düşünün. Bu köye giden labirent şeklinde de bir yol. Sizin köye yöneldiğinizde, sizi köye yaklaştıran yol aslında sizin sezgisel olarak köye gitmenize sebep olan yoldur. Ancak bu yol en kısa yol olmayabilir, labiretin sizi dolaştırmasına göre belki tam ters yöndeki bir yol daha kısa olabilir. İşte gerçekteki mesafeler (f(n)) ile sezgisel mesafeler (h(n)) bu farkı oluşturur.

    Yukarıdaki örnekte kırmızı sayılar sezgisel, siyah sayılar ise gerçek (gidilebilen) mesefalerdir.

    başarılar

  6. Hasan

    Merhabalar. Hocam öncelikle emeğinize sağlık, bu bilgileri bize sağladığınız için. Ben de bir problem üzerinde uğraşıyorum.

    gibi 3 boyutlu kutucuklardan oluşan bir küp düşünelim. Kutucuklar üzerlerindeki (siyah) numaralar gelmeleri gereken yerleri göstermektedirler. Kırmızı renkli numaralar doğru dizilimin sırasını vermektedir. Fotoğrafta da görüldüğü gibi ilk kutucuğun yeri boştur ve oraya üzerinde 1 yazan kutu gelmelidir. Bu şekilde dizildikleri zaman 27. kutucuğun yeri boş olacaktır. Hocam bu problem üzerinde A* algoritmasını nasıl uygulayabiliriz ve nasıl bir veri yapısı oluşturmalıyız sizce? Yardımcı olabilirseniz veya ipucu verebilirseniz çok sevinirim. Kolay gelsin.

  7. Şadi Evren ŞEKER Article Author

    probleminizi tam anlamamakla birlikte sanırım şekilde bulunan kareleri hareket ettirmekten bahsediyorsunuz (nasıl bir hareket olduğunu anlatmamışsınız) ama tek bir karenin boş kalmasından anladığım kadarıyla 8 puzzle benzeri bir şekilde oynanıyor. Şayet durum bu şekildeyse 8 puzzle üzerinde uygulanan a* algoritmasını burada uygulamanız ve sonuç almanız mümkün.

    başarılar

  8. Hasan

    Hocam cevabınız için teşekkür ederim. Yanlış fotoğrafı upload etmişim :

    Sizin de dediğiniz gibi bir boşluk var sistemde ve kutular o boşluktan yararlanılarak kaydırılacak, en son dizilim tamamlandığında sadece 27. yer boş kalacak, ancak 3 boyutlu olduğu için sıkıntı çekmekteyim. Biraz yardımcı olabilirseniz çok sevinirim. Hareketler sağa-sola, yukarı-aşağı olacak şekilde.

  9. Hasan

    Hocam en basitinden
    f(n) = hesaplama yapan sezgisel (heuristic) fonksiyon.
    g(n) = Başlangıç düğümünden mevcut düğüme kadar gelmenin maliyeti
    h(n) = Mevcut düğümden hedef düğüme varmak için tahmin edilen mesafe.

    fonksiyonlarını nasıl uygulayabiliriz bu problem üzerinde?

  10. Şadi Evren ŞEKER Article Author

    Daha önce de bahsettiğim üzere probleminiz 8 puzzle probleminin 3 boyutlusu. Olayı şu şekilde özetleyebiliriz.

    probleminiz bir arama algoritmasıdır. Şayet problemi bütün ihtimalleri arayacak şekilde modellerseniz o zaman bir arama algoritması ile bütün ihtimalleri dolaşıp sonuca varabilirsiniz.

    Yukarıdaki bu yaklaşım exhaustive search olup zaman ve hafıza olarak bütün ihtimalleri dolaştığından maliyetlidir. Sezgisel bir arama yapmak daha mantıklıdır. Bu durumda aşağıdaki yargıları çıkarmak mümkün:

    bir taşın, neticede olması gereken yere uzaklığı sezgisel olarak maliyetini verir. (örneğin 2 kare yanda olmasına göre 1 kare yanda olması daha iyi ama bu sonuca yakın olduğunu göstermez sadece sezgisel bir durumdur, bulmacanın öteki ucunu dolaşması da gerekiyor olabilir sadece sezgisel olarak yakındır) Buna göre her taşın hedefe uzaklığı sizin sezgisel maliyetiniz olabilir.

    Gerçek maliye ise, hedefe varmak için kaç taş oynamanız gerektiğidir. Örneğin aşağıdaki şekilde bulnan her değer, gerçek maliyeti verir ve bitiş durumuna varmak için kaç taş oynanacağını gösterir.

    yukarıdaki şekilde görüldüğü üzere (8puzzle çözümüdür) önce ihtimal ağacını oluşturur ve her hareketten sonra nasıl hareketler yapılacağına bakarsınız. Burada goal state en altta görüldüğü üzere bitiş durumudur ve maliyeti 0’dır.

    başarılar

  11. Hasan

    Hocam ilginiz için çok teşekkürler. Verdiğinize göre problem şu şekilde mi çözülecek? :
    “Gerçek maliyet ise, hedefe varmak için kaç taş oynamanız gerektiğidir” demişsiniz, diğer bir deyişle kaç taş yerinde olmadığını hesaplamak gerçek maliyeti veriyor anladığım kadarıyla.
    Yukarıdaki 8 puzzle ağaç gösterimini benim probleme uyarlarsak, initial durumda maliyet = yerinde olmayan taşların sayısı + bütün taşların doğru yere gitmesi için gerekli olan sezgisel uzaklıkları.
    Daha sonra boşluğun sağa,sola,yukarı,aşağı yönlerden hangisine gidebiliyorsa onları alt çocuk olarak ağaçta göstereceğiz ve o şekildeki durumların maliyetini tekrar hesaplayacağız ve maliyeti en az olanı seçerek aynı işlemleri onun üzerinde gerçekleştireceğiz. Böyle böyle maliyet sıfır olana kadar ilerleyeceğiz.
    Hocam doğru anlamış mıyım? Eğer yanıtlarsanız çok sevinirim. Kolay gelsin.

  12. Şadi Evren ŞEKER Article Author

    evet ayrıca sezgisel puan hesabınız da önemli. Yani sadece oynana taş değil sezgisel değere göre hesap yapacaksınız. A* algoritmasının amacı, bütün ihtimalleri deneMEmektir. Dolayısıyla sezgisel puanlar üzerinden yukarıdaki konuda anlattığım gibi arama yapmanız yeterlidir. Bu sırada sezgisel uzaklığınız ve o zamana kadar yaptığınız adım sayısını toplayıp bir maliyet çıkaracaksınız ve diğer alternatifler ile karşılaştıracaksınız. Şayet diğer alternatif (henüz oynamadığınız ama oynarsanız [sezgisel maliyet] + [oynamanın maliyeti] şeklinde hesapladığınız) değerler, o andaki oynadığınız maliyetten düşük olduğunda bunlardan birisine geri döneceksiniz.

    başarılar

  13. Zeynep

    Hocam merhaba. Konuyu okurken yorumlar dikkatimi çekti, Hasan Bey’in soruları özellikle. Siz son cevabınızda ” A* algoritmasının amacı, bütün ihtimalleri deneMEmektir. ” demişsiniz ancak bir nokta kafamı karıştırdı.

    Fotoğrafla biraz oynadım ve şöyle düşünürsek durumların üzerinde yazan rakamlar gerçek maliyeti değil de toplam maliyeti versin ([sezgisel maliyet] + [oynamanın maliyeti] ) kırmızıyla üzerini çizdiğim ve yazdığım rakamlar da o durumların maliyetleri olsun. Oklarla geldiğimiz son noktadaki durumda toplam maliyet 8 çıktı. Halbuki ağaçta üst düzeyde 6 ve 7 maliyetli durumlar ve onlarında üst düzeyinde 5 maliyetli durumlar yer almakta. Eğer biz bir üst düzeydeki en az maliyetli duruma değil de onun üstündeki 5 maliyetli duruma geri döneceksek (algoritma böyleyse anladığım kadarıyla) ve böyle bir durumunun derinliği çok olan bir ağaçta başımıza geldiğini düşünürsek(mesela biz 18. düzeydeyiz ve 3. düzeye geri dönmek zorunda kalıyoruz) biz bir nevi bütün durumları kontrol etmiş sayılmıyor muyuz hocam? Programın etkinliği açısından benim kafam karıştı bu noktada 😀 Umarım derdimi anlatabilmişimdir.

    Bir de hocam üstteki mesajda belirttiğiniz “o zamana kadar yaptığınız adım sayısı” olarak ağaçta bulunduğumuz düzeyi alabilir miyiz? Ayrıca “[sezgisel maliyet] + [oynamanın maliyeti]” deki “oynamanın maliyeti” tam olarak neye denk geliyor, yerinde olmayan taşların sayısına mı ?
    Yanıt verebilirseniz çok mutlu olurum. İyi günler.

  14. Şadi Evren ŞEKER Article Author

    Elbette yanıt veririz. Bakın, iki şeyi ayırmak gerekiyor. Maliyetin hesaplanması ile oynanması ayrı şeyler.

    Örneğin maliyetleri ezberlediğinizi düşünün ve pozisyona baktığınızda maliyeti bildiğinizi düşünün.

    Diğer bir deyişle her durumun maliyetini hesaplatıyorsunuz (1 kere) ve bunları bir yerde tutuyorsunuz. Bir pozisyonla karşılaştığınızda maliyeti biliyorsunuz ama hangi hamlelerle bu maliyette sonuca ulaşacağınızı bilmiyorsunuz. A* algoritması bütün hamlelere bakmadan size bu maliyeti bulmaya yardımcı oluyor. (istatistiksel olarak elbette, yani en kötü durumda her ihtimale bakar ama ortalama bir durumda bakmadığı hamleler vardır)

    Geri dönme işini ise bir veri yapısında tutmakta yarar var. Bahsettiğiniz üzer 18. adımdayken aslında yapınızdaki diğer ihtimallerin maliyet hesabı da duruyor. 18. adımdan vaz geçtiniz diyelim 3. adım ihtimali yapıdaki diğer ihtimaldir. Hatta mümkünse bu yapıyı, maliyetine göre sıralı tutup, sıradan almakta yarar var (örneğin priority queue (öncelik sırası) gibi).

    verdiğim formüldeki oynama maliyeti, kaç hamlede sonuca ulaştığınız. Yerinde olmayan taş sayısı ancak sezgisel maliyet olur. Yazıda bunu belirtmeye çalışmıştım. Örneğin olması gereken yerin bir yanındaki taş, sonuç durumuna ulaşmak için bütün tahtayı dolaşmak zorunda olabilir. Bu durumda maliyet 1 diyemeyiz. kaç hamle yaptıysak bu gerçek maliyettir. Bitiş durumuna uzaklığı, olsa olsa sezgisel maliyet olabilir.

    başarılar

  15. Hasan

    Hocam tekrar merhaba 🙂 Cevaplarınız için teşekkür ederim. Kafama takılan bir şey vardı. Üstte “Bu sırada sezgisel uzaklığınız ve o zamana kadar yaptığınız adım sayısını toplayıp bir maliyet çıkaracaksınız ve diğer alternatifler ile karşılaştıracaksınız. Şayet diğer alternatif (henüz oynamadığınız ama oynarsanız [sezgisel maliyet] + [oynamanın maliyeti] şeklinde hesapladığınız) değerler, o andaki oynadığınız maliyetten düşük olduğunda bunlardan birisine geri döneceksiniz. ” demişsiniz. Hocam burada kastettiğiniz diğer alternatifler o zamana kadar ki oynamadığımız bütün durumlar mı yok bir üst adımda oynamadığımız durumlar mı? Örneğin belli bir adımda bir node’un çocuklarını oluşturduk ve toplam maliyetlerini hesapladık. Bunlardan en küçüğünü seçtik ancak bunu listeye eklemeden önce, daha önceki oynanmamış bütün durumların maliyetleriyle karşılaştırmalı mıyız? Kolay gelsin, iyi günler.

  16. Şadi Evren ŞEKER Article Author

    A yıldız algoritmasında, o ana kadar açılan (kontrol edilen ,bakılan) değerlerin tamamını karşılaştırırsınız. Dolayısıyla o ana kadar baktıklarınızın en azı olan alternatifi seçersiniz. Bu alternatif daha önceki adımlardan herhangi birisi olabilir, hatta en başa bile dönmeniz gerekebilir.

    başarılar

  17. mustafa

    hocam allah razı olsun sizden sınavlara hazırlanırken yazılarınızın çok faydası oldu teşekkür ederim

  18. murat

    Hocam merhabalar. Bu A* algoritmasını bir navigasyonda en kısa yolu bulma işlemi için kullanmak sizce ne kadar mantıklı olur. Bunu yaparken yolun uzaklığını ve trafik durumunu hesapladığımızı düşüneceğiz. Yani maliyet analizi yapacağız. Eğer kullanışlı değilse sizce hangi algoritma çeşidi buna en uygundur. Teşekkürler.

Şadi Evren ŞEKER için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir