A star algoritması iki nokta arasındaki en kısa yolu bulmak için kullanılır. Basit olarak tanımlamak gerekirse üzerinde gidilebilen ve gidilemeyen alanların bulunduğu bir haritada belirtilen iki nokta arasındaki en kısa yolu oluşturan noktaları bulur. Bu noktalar birleştirildiğinde iki nokta arasındaki yol bulunmuş olur.
A Star Algoritması Nasıl Çalışır
Harita üzerinde başlangıç noktasından başlayarak her komşu noktaya başlangıç noktasına ve bitiş noktasına olan uzaklıkların toplamını gösteren bir sayı atanır ve diğer komşu noktaya geçilir aynı işlem bu nokta için de yapılır. Bu işlem bitiş noktasına ulaşılıncaya kadar devam eder. Bitiş noktasına ulaşılınca bitiş noktasından başlayarak en küçük değere sahip komşu nokta kaydedilir, bu komşu noktanın komşu noktaları içinde en küçük değere sahip noktaya gidilir bu işlem başlangıç noktasına ulaşana kadar devam eder. Başlangıç noktasına ulaşılınca yol bulunmuş olur kaydedilen noktaların tamamı yolu oluşturur.
A star algoritması 2 temel döngüden oluşur:
1.Noktaların başlangıç ve bitiş noktalarına olan uzaklıklarının hesaplanması
Bu döngü iki faklı değişken kullanılarak yapılabilir. Hesaplanacak komşu noktalar bir diziye kaydedilir ve ilk değişken her kayıtta dizinin sonunu göstermesi için her komşu noktada bir arttırılır. İkinci değişken ise hesaplanan noktayı gösterir ve her hesaplamadan sonra bir arttırılır. Döngü içinde hesaplanacak her nokta bitiş noktası ile karşılaştırılır karşılaştırma sonucu eşit ise bitiş noktasına ulaşılmış demektir ve daha fazla
karşılaştırmaya gerek olmadığı için döngüden çıkılır. Bu koşul sağlanmazsa döngü bütün komşu noktalar hesaplanana kadar devam eder ve bu tamamlandığında döngüden çıkılır. Bu durumda başlangıç ve bitiş noktaları arasında bir yol olmadığı anlaşılır.
hesaplanan=0
kalan=1
noktalar[hesaplanan]=başlangıç noktası harita[başlangıç noktası]=10 while(hesaplanan<kalan){ if(noktalar[hesaplanan]==bitiş noktası) //Bitiş noktasına ulaşıldı yol bulundu döngüden çıkılıyor break //Komşu noktaların uzaklığı hesaplanıyor for noktalar[hesaplanan] noktasının komşu noktaları{ if komşu nokta boş ise{ //Başlangıç noktasına olan uzaklığı haritaya kaydediliyor harita[komşu nokta]= noktalar[hesaplanan]+10 //Noktanın komşu noktalarının hesaplanabilmesi için //noktalar dizisine kaydediliyor noktalar[kalan]=komşu nokta kalan++ } } hesaplanan++ }
2.Başlangıç ve bitiş noktaları arasındaki yolun bulunması
Döngü bitiş noktasından başlayarak en küçük uzaklık değerine sahip komşu noktayı takip ederek başlangıç noktasına gelene kadar devam eder. Bu döngü içinde takip edilen her komşu nokta kaydedilir. Kaydedilen bu noktalar başlangıç ve bitiş noktası arasındaki yolu oluşturur.
Örnek uygulama: A star yol bulma algoritması
*Örnek uygulama standart C ile yazılmıştır ve Windows işletim sisteminde denenmiştir. ASCII karakterler nedeni ile farklı işletim sistemlerinde çıktı öngörüldüğü gibi olmayabilir düzeltme için main fonksiyonu içinde bulunan block değişkeninin değerini değiştirebilirsiniz.
Kaynaklar
https://en.wikipedia.org/wiki/A*_search_algorithm
https://www.youtube.com/watch?v=-L-WgKMFuhE
https://stackoverflow.com/questions/23705233/how-to-speed-up-a-algorithm-at-large-spatial-scales
