Navigasyon sistemlerinde rotaları bulmak için kullanılan algoritmalar arasında A* algoritması oldukça önemli bir yere sahiptir. A* algoritması, en kısa yol bulma problemlerinde yaygın bir şekilde kullanılan bir yol bulma algoritmasıdır. Bu algoritma, sezgisel bir yaklaşım ile hedefe giden en kısa yolu bulmaya çalışırken diğer algoritmaların aksine tüm yolları denemek yerine daha verimli bir şekilde ilerler.
A* algoritmasının çalışma prensibi, her adımda mevcut durumdan hedefe en kısa yolun maliyetini ve sezgisel bir tahminle genel maliyetini hesaplayarak bir öncelik kuyruğu oluşturmaya dayanır. Bu kuyruk, her adımda en uygun olduğu düşünülen yolu seçerek ilerlemeyi sağlar. Bu sayede A* algoritması, hedefe doğru ilerlerken gereksiz yolları denemekten kaçınarak daha hızlı ve verimli bir şekilde en kısa yolu bulabilir.
A* algoritmasında 3 temel fonksiyon vardır:
h(n)=sezgisel (kuş uçuşu)
g(n)=gidilen (gerçek) mesafe
f(n)=g(n)+(n) toplam mesafe
Şekildeki örneği incelediğimizde A mesafesinden Z mesafesine gittiğimizi varsayalım ilk olarak A-E rotası ve A(B) rotasını hesaplayarak başlar F(E)=3+12 yani E noktasına gidilen gerçek mesafe + E noktasından Z noktasına gidilen kuş uçuşu mesafeyi toplar ve 15 bulur. F(B)=4+15 işlemini hesaplayarak 19 bulur ve E noktasına ilerler E noktasında iki tane alternatifi vardır bu noktadan sonra gidilen her mesafede gittiği noktanın kuş uçuşu mesafesini h(n)+ gidilen toplam mesafe g(n) olarak toplar bu noktada F(G)=10+7+3 olarak ve F(F)=8+3+9 olarak hesaplar işte tam burda a* algoritması F(B) mesafesini 19 olarak bildiğinden geri döner ve F(C)=4+4+6 ve F(D)=4+7+14 noktalarını hesaplar ve F(G),F(F),F(D) noktalarından küçük olduğundan F(C) den devam eder en son sezgisel bir değer kalmadığı için F(Z)=6+4+4 olarak hesaplayıp 14 mesafesini en küçük bulduğu için bu yolu rota olarak kullanıcıya sunar.
Yukarda gördüğünüz üzere A* algoritması tüm yolları teker teker hesaplamadan kullanıcıya en az maliyetle en kısa mesafeyi buldu bu algoritmanın daha kapsamlı ve daha entegre halleri navigasyonlarımızda mevcut ve çok kısa sürelerde çok uzun mesafeleri en kısa yoldan bulmaya yarıyor.
.
Diğer algoritmalardan farklı olarak A* algoritması, başlangıç noktasından hedefe ilerlerken tüm yolları değil, sadece en verimli olan yolları hesaplar. Bu da daha kısa sürede en kısa yolu bulmayı sağlar. Ayrıca bu algoritmada kullanılan öncelik kuyruğu sayesinde daha verimli bir yol seçilerek daha az adımda sonuca ulaşılabilir.
A* algoritması aynı zamanda her adımda bir önceki adımdan ilerlediği için daha az hesaplama gerektirir ve bu da daha hızlı sonuç alınmasını sağlar. Diğer algoritmalarda ise her adımda tüm yolların maliyetini hesaplamak gerektiği için daha fazla hesaplama ve daha uzun süre gerektirir.
A* algoritması ayrıca sezgisel bir yaklaşım kullanarak hedefe doğru ilerlediği için yanlış rotalara sapma ihtimali daha azdır.
Sonuç olarak, A* algoritması navigasyon sistemlerinde diğer algoritmalardan daha verimli bir şekilde kullanılır ve daha hızlı, doğru ve kısa rotaların bulunmasını sağlar. Bu nedenle günümüzde en yaygın kullanılan algoritmalardan biridir ve geliştirilmeye devam etmektedir.
Furkan Yılmaz
