A* Algoritması Nedir ?
A*(star) search algoritması; ilk olarak 1968 yılında Peter Hart,Nils Nilsson ve Bertram Raphael tarafından teorik olarak geliştirilen A search algoritmasının daha sonra geliştirilmesiyle elde edilmiştir.
Bilgisayar ortamında, A* algoritması en iyi ilk sırada olan çözümü bulan,verilen noktalar arası en kısa maliyetli yolu üreten algoritma olarak bilinir.Bu algoritma ağaç yapısı üzerindeki noktaları tanımlarken her bir node için mesafe +herustic fonksiyon dan oluşan bir f(n) fonksiyonu oluşturur.Bu f(n) fonksiyonu belirttiğimiz üzere iki fonksiyonun toplamıdır:f(n)=g(n)+h(n).
g fonksiyonu noktalar arası gerçek mesafeyi (yol maliyetini),h fonksiyonu ise herustic tahmin fonksiyonunu belirtmektedir.h(n) fonksiyonu herustik tahmini fonksiyon olduğundan mutlaka başlangıçtan belirttiğimiz hedefe olan mesafeden küçük bir değer olmalıdır.Bu yüzden yol bulma veya yol planlaması problemlerinde h(n) değeri,noktalar arası fiziksel olarak mevcut olan yoldan daha kısa yol olan kuşbakışı mesafe değeri ölçümüyle elde edilir.
A* search algoritması rota üzerindeki bütün noktaları başlangıçtan hedef noktaya varıncaya kadar en kısa mesafeli çözümü elde edinceye kadar araştırır.Bu araştırmayı yaparken OPENLIST ve CLOSELIST yapılarını oluşturur ve hedef nokta oluşunca bu yapılar yardımıyla bir rota belirlenir.A* algoritmasının adım adım işleyişi aşağıdaki gibidir:
1-Başlangıç node unu OPENLIST e al ve maliyet f(n) fonksiyonunu hesapla.
2-En küçük f(n) maliyet fonksiyonlu node u seç ve OPENLIST ten kaldırıp CLOSELIST e ekle.
3-Hedef noktasına ulaşılıp ulaşımadığını kontrol et,eğer hedefe ulaşılmış ise algoritmayı sonlandır.Aksi halde algoritmaya devam et.
4-Hedef noktaya ulaşılıncaya kadar CLOSELIST e atılmamış bütün successor lar için maliyet fonksiyonlarını hesapla.
5-Bunları listelere alınmamış successor maliyetleri ile karşılaştır ve OPENLIST e al
6-OPENLIST e sonradan tekrar atılabilecek aynı eleman için f(n) değerlerini karşılaştır ve küçük f(n) değeri olanı seç
7- Adım-2 ye git
Problem Tanımı
a)Giriş:Yol planlaması ya da yol bulma problemleri günümüzde üzerinde çok yoğun bir şekilde çalışılmakta olan ağ optimizasyon uygulamalarından biridir.Bu konuyla bağlantılı günlük hayat problemlerini çözmeyi amaçlayan uygulamalarda geliştirilen türlü algoritmalar uygulamayı tasarlayan kişiler tarafından tercih edilebilir.Bizim uygulamamızda ise A* search algoritmasıyla elimizdeki yol haritasında istenen noktalar arası en kısa mesafeli yol harita üzerinden grafiksel olarak çizdirilip,kullanıcıya çözüm olarak sunulmaktadır.
b)PROBLEM: Belirli bir alanda bulunan noktalar arasında mesafe açısından en kısa maliyetli güzergahı tespit edip Matlab yardımıyla görselleştirmek
i ) Performance Measure : En kısa mesafeye göre istenen noktalarda ulaşımı sağlamak
Environment : Verilen yol haritası(yol ağı)
Actuator : Algoritma , veriler
Sensors : Klavye ,mouse
ii ) Bu problemdeki çevre ; duruma göre karar verme mekanizmasıyla işlediği için episodik ,aktarım noktalar arası geçişlerin gelişen koşullara göre değişmesi bakımından dinamiktir.
iii) A*(star) algoritmaları yardımıyla tüm seçenekler incelenerek en avantajlı güzergaha karar verilecektir.
Problemimize Matlab Üzerinde A* Algoritmasının Uygulanması
A* star search algoritmasını uygulamamıza ekleyip Matlab da programımızı bir M-file olarak çalıştırdık.Bu M-file içindeki kodu geliştirirken amacımız herhangi verilen bir ağ ya da harita üzerindeki noktalar arası en kısa yol problemini çözüm kısmında kullanıcıya grafiksel olarak çizdirip sunmaktı.
Ilk olarak oluşturduğumuz bir M-file içerisinde verilen yol haritası üzerindeki noktalar arası mesafeleri çift yönlü(geliş-gidiş,A->B ve B->A)olarak tanımladık.Bu adımdan sonra harita üzerindeki noktaları Matlab da grafik çizimi kullanacağımız için özel olarak ,Dreamweaver programı yardımıyla X ve Y boyutları için koordinatlarını elde ettik.Bunların devamında gerekli tanımlamalarımızı yaptıktan sonra başlangıç olarak seçtiğimiz noktadan hedef(goal state) e kadar algoritmamızın basamaklarını işletmeye başladık.Algoritmamızın her çalışma adımında OPENLIST ve CLOSELIST yapılarını A* search algoritmasının özelliklerine göre program içerisinde şekillendirdik.Daha sonra CLOSELIST e eklenen değerlerden birbiri ile bağlantılı olanları program içerisinde seçip kısayol haritamızı çıkardık.Çıkardığımız bu harita üzerindeki node değerlerinin X-Y koordinat değerlerini atayarak ,haritamız üzerinde Matlab programının grafik çizimi özelliklerini kullanarak ,ağ üzerinde yeni bir kısayol çizimi gerçekleştirdik.Bu görselliği yaparken node ların koordinat değerleriyle karışmayacak şekilde kısayol noktalarının bu değerlerden bir sabit kadar üst kısımda olup kullanıcıya değişik renkte bir görsellik sunmasını sağladık.
Aşağıdaki şekilde seçilen A-K noktaları arası en kısa yol kırmızı kesik çizgi işaretli güzergahla Matlab uygulamamız yardımıyla çizdirilmiştir.Bu örneği başlangıç ve hedef noktalarını değiştirmek şartıyla harita üzerindeki tüm noktalara uygulayabiliriz.
Sonuç: Ulaşım problemlerini çözmede, A* algoritması kullanılarak bir haritada bulunan noktalar arasında en kısa mesafeyi bulma uygulamaları geliştirilebilir. Örnek uygulamamızda da 10 farklı noktadan oluşan bir haritada bunu gözlemlemiş olduk.
Bu yazı yorumlara kapalı.