A* Arama Algoritması (A* Search)

a* arama algoritması nedir?

A* (a-yıldız diye okunur), bir başlangıç noktasından hedefe giden en kısa yolu bulan bir arama algoritmasıdır. 1968'de Peter Hart, Nils Nilsson ve Bertram Raphael tarafından, Shakey adlı robotun odalar arasında yol bulması için geliştirildi. Bugün oyunlardan harita navigasyonuna kadar yol bulmanın (pathfinding) temel taşıdır.

nasıl çalışır?

A*, her adayı iki maliyetin toplamıyla değerlendirir: g(n), başlangıçtan o düğüme kadar gelmenin gerçek maliyeti; h(n) ise o düğümden hedefe kalan maliyetin tahmini (heuristic). Bu ikisinin toplamı f(n) = g(n) + h(n), "bu düğümden geçen yol ne kadar umut verici?" sorusunun cevabıdır.

Algoritma her turda f değeri en düşük düğümü seçip genişletir, komşularını sıraya ekler. Böylece hem şimdiye kadar katedilen yolu hem de hedefe olan tahmini mesafeyi birlikte dikkate alır; bu, onu kör aramadan çok daha verimli yapar.

Kritik koşul, kullanılan heuristic'in kabul edilebilir (admissible) olmasıdır: hedefe kalan maliyeti asla olduğundan fazla tahmin etmemelidir. Bu koşul sağlandığında A*, bulduğu yolun kesinlikle en kısa yol olduğunu garanti eder. Yol bulmada sık kullanılan bir heuristic, iki nokta arasındaki kuş uçuşu (düz çizgi) mesafedir.

neden önemli?

A*, hem en kısa yolu garanti etmesi (doğruluk) hem de gereksiz düğümleri elemesi (verimlilik) sayesinde arama algoritmaları arasında bir denge noktasıdır. Heuristic'i sıfır alırsanız algoritma Dijkstra'ya dönüşür; iyi bir heuristic ise aramayı doğrudan hedefe yönlendirir.

kullanım alanları

Video oyunlarında karakter ve düşman yol bulması, GPS ve harita uygulamalarında rota hesaplama, robot navigasyonu, bulmaca çözme (örneğin 15-puzzle) ve ağ yönlendirme A*'ın yaygın uygulama alanlarıdır. "Bir noktadan diğerine en verimli nasıl giderim?" sorusunun olduğu her yerde karşımıza çıkar.