İçeriğe geç
parazade
Yapay Zeka

A* Algoritması Nedir?

İngilizce: A* Search Algorithm

Yayın: · Son güncelleme:

A* Algoritması Nedir? Kısaca

A* algoritması, bir başlangıç noktasından hedefe giden en düşük maliyetli yolu bulmak için şimdiye kadarki gerçek maliyeti ve hedefe kalan mesafenin sezgisel tahminini birleştiren, yaygın kullanılan bir arama algoritmasıdır.

A* Algoritması nedir?
İçindekiler
  1. A algoritması nedir?
  2. Nasıl çalışır?
  3. Nelere dikkat etmeli?

A* algoritması (A-star), bir haritada ya da grafikte iki nokta arasındaki en kısa ya da en ucuz yolu bulmak için kullanılan bilgili bir arama algoritmasıdır. 1968'de Peter Hart, Nils Nilsson ve Bertram Raphael tarafından yayımlandı ve bugün oyunlardan robotik yol planlamaya kadar çok yaygın kullanılır.

A* algoritması nedir?

A*, aramayı rastgele genişletmek yerine hedefe en umut verici görünen noktalardan devam eder. Bunun için her nokta (düğüm) için bir puan hesaplar:

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

  • g(n): Başlangıçtan bu düğüme kadar gerçekten harcanan maliyet.
  • h(n): Bu düğümden hedefe kalan maliyetin sezgisel tahmini, örneğin kuş uçuşu mesafe.
  • f(n): Bu düğümden geçen bir yolun toplam tahmini maliyeti.

Nasıl çalışır?

  1. Başlangıç düğümü "açık listeye" eklenir.
  2. Açık listeden f değeri en düşük düğüm seçilir; hedefse arama biter.
  3. Seçilen düğümün komşuları için g, h ve f hesaplanır; daha iyi bir yol bulunduysa kayıt güncellenir.
  4. İncelenen düğüm "kapalı listeye" alınır ve döngü sürer.

Varsayımsal bir örnek: Bir oyunda karakterin duvarlarla dolu bir labirentte hedefe ulaşması gerekiyorsa A*, kuş uçuşu mesafeyi tahmin olarak kullanıp gereksiz yönleri büyük ölçüde atlayarak yolu bulur.

Nelere dikkat etmeli?

A*'ın en kısa yolu bulmayı garanti etmesi için sezgisel tahminin gerçek maliyeti asla abartmaması (kabul edilebilir olması) gerekir. Tahmin ne kadar isabetliyse arama o kadar hızlanır. Çok büyük haritalarda açık liste büyüyerek fazla bellek tüketebilir; bu yüzden pratikte bellek dostu türevleri de kullanılır.

Sıkça Sorulan Sorular

A* algoritması ile Dijkstra algoritması arasındaki fark nedir?

Dijkstra yalnızca gerçek maliyete (g) bakar ve her yöne eşit genişler. A* buna hedefe kalan mesafenin tahminini (h) ekleyerek aramayı hedefe yönlendirir ve genellikle daha az düğüm inceler.

A* her zaman en kısa yolu bulur mu?

Sezgisel tahmin gerçek kalan maliyeti hiçbir zaman abartmıyorsa evet. Tahmin abartılıysa daha hızlı çalışabilir ama en kısa yolu bulamayabilir.

İlgili terimler

Arama Algoritması(Search Algorithm)Arama algoritması, bir problemin olası durumları arasında sistematik biçimde gezinerek başlangıç durumundan hedef duruma ulaşan bir çözüm ya da yol bulan yöntemdir. Yapay zekâda planlama ve problem çözmenin temel araçlarındandır.Sezgisel Yöntem(Heuristic)Sezgisel yöntem (heuristic), bir problemi kesin ve en iyi çözümü garanti etmeden, deneyime dayalı kestirme kurallar ya da tahminler kullanarak makul sürede yeterince iyi bir sonuca ulaştıran problem çözme yaklaşımıdır.Yol Planlama(Path Planning)Yol planlama, bir robotun, otonom aracın ya da yazılım ajanının başlangıç noktasından hedefe engellere çarpmadan ve belirli ölçütlere (en kısa, en güvenli, en az enerji) göre en uygun rotayı bulmasını sağlayan algoritmik süreçtir.Algoritma(Algorithm)Algoritma, belirli bir problemi çözmek ya da bir görevi yerine getirmek için izlenen, sırası ve sonu belli, açık ve uygulanabilir adımlar dizisidir. Bilgisayar programları ve yapay zekâ sistemleri algoritmalar üzerine kuruludur.Robotik(Robotics)Robotik, çevresini algılayıp karar veren ve fiziksel dünyada hareket eden makineleri (robotları) tasarlayan, üreten ve programlayan disiplinlerarası mühendislik alanıdır; makine, elektronik ve yazılımı birleştirir.Harf Çevirisi(Transliteration)Harf çevirisi (transliterasyon), bir yazı sistemindeki metnin, anlamı çevrilmeden başka bir yazı sisteminin harfleriyle yazılmasıdır. Örneğin Kiril alfabesiyle yazılmış bir ismin Latin harflerine aktarılması harf çevirisidir.