A* Arama Algoritması
A* Search
Tanım
Başlangıç durumundan hedefe giden en kısa ve en az maliyetli yolu bulmak için maliyet fonksiyonu ile sezgisel tahmini birleştiren en iyi-ilk arama algoritmasıdır.
Örnek Vaka / Uygulama
Bir robotun laboratuvar ortamında engellerle dolu bir odada en kısa sürede masaya ulaşması gerektiği senaryoda, robot her adımda kat ettiği mesafeyi ve hedefe olan kuşbakışı tahmini uzaklığını toplar. En düşük toplam değere sahip rotayı seçerek engellerin etrafından dolaşır ve hedefe varır.
Derin Analiz
Bilişsel bilimler, yapay zeka ve karar verme süreçlerinde sıklıkla kullanılan A* algoritması, grafik geçişi ve rota bulma problemlerini çözmek için tasarlanmıştır. Algoritmanın temel çalışma prensibi, her düğüm için toplam tahmini maliyeti ($f(n) = g(n) + h(n)$) hesaplamasına dayanır. Burada $g(n)$, başlangıç düğümünden mevcut düğüme kadar geçen gerçek maliyeti; $h(n)$ ise mevcut düğümden hedef düğüme olan tahmini sezgisel maliyeti temsil eder. Sezgisel fonksiyonun kabul edilebilir (admissible) olması, yani hiçbir zaman gerçek maliyeti aşmaması, algoritmanın her zaman en optimal çözümü bulmasını garanti eder. Bilişsel modellemede insan problem çözme stratejilerinin ve mekânsal navigasyonun simülasyonunda matematiksel bir temel oluşturur.
Etimoloji
İngilizce 'A' harfi (algoritmanın orijinal adındaki ilk harf) ve 'star' (yıldız, * karakterinin matematiksel gösterimi) kelimelerinin birleşiminden türetilmiştir; bilgisayar bilimlerinde optimal yol bulma simgesi olarak seçilmiştir.
Karıştırmayın
Dijkstra Algoritması ile karıştırılır; ancak Dijkstra sadece kat edilen gerçek maliyeti ($g(n)$) hesaba katarken, A* algoritması hedefe olan tahmini uzaklığı da ($h(n)$) hesaba katarak çok daha az düğüm ziyaret eder ve daha hızlı sonuç verir.