Sezgisel Arama ve A*
Sezgisel arama, bir hedefe ulaşmak için kalan maliyetin probleme özgü bir tahminini, hangi durumların önce keşfedileceğine rehberlik etmek amacıyla kullanmaktadır; A*, bu yaklaşımın kanonik algoritması olup, şu ana kadarki maliyet ile tahmini kalan maliyetin toplamına göre durumları genişletmektedir.
Tanım
Sezgisel arama, başlangıçtan bilinen maliyeti kalan maliyetin sezgisel tahminiyle birleştiren bir değerlendirme fonksiyonu kullanarak sınırları sıralayan bilgilendirilmiş bir arama yöntemidir; A*, f(n) = g(n) + h(n) formülünü kullanır ve h kabul edilebilir (admissible) olduğunda optimaldir.
Kapsam
Bu konu, en iyi-önce arama ve A* algoritması üzerine odaklanarak, bilgilendirilmiş (sezgisel) arama stratejilerini kapsamaktadır. Sezgisel fonksiyonların tasarımı ve özellikleri (kabul edilebilirlik (admissibility), tutarlılık/monotonluk), bu özelliklerin sağladığı optimallik ve verimlilik garantileri ile yinelemeli derinleşen A* (IDA*) gibi bellek sınırlı varyantlar incelenmektedir. Sezgisel fonksiyonların nasıl oluşturulduğu (gevşetilmiş problemler, örüntü veritabanları) ve doğruluk ile hesaplama arasında nasıl bir denge kurulduğu ele alınmaktadır. Verilerden sezgisel fonksiyon öğrenimi, makine öğrenimi alt alanına girmektedir.
Temel sorular
- Bir sezgisel fonksiyonu kabul edilebilir (admissible) kılan nedir ve kabul edilebilirlik (admissibility) neden A* optimalliğini garanti eder?
- Tutarlılık (monotonluk), garantileri nasıl güçlendirir ve düğümün yeniden genişletilmesini nasıl önler?
- İyi sezgisel fonksiyonlar, örneğin problemin gevşetilmiş versiyonlarından yola çıkarak nasıl tasarlanır?
- IDA* gibi bellek sınırlı varyantlar, sınırlı alanla optimalliği nasıl korur?
Anahtar kavramlar
- değerlendirme fonksiyonu f = g + h
- kabul edilebilir (admissible) sezgisel fonksiyon
- tutarlı (monoton) sezgisel fonksiyon
- açgözlü en iyi-önce arama
- A* arama
- yinelemeli derinleşen A* (IDA*)
- sezgisel baskınlık
- gevşetilmiş problem ve örüntü veritabanları
Temel kuramlar
- Kabul edilebilir (admissible) sezgisel fonksiyonlar altında A* optimalliği
- Sezgisel fonksiyon h, gerçek kalan maliyeti asla fazla tahmin etmediğinde, A* düğümleri artan f = g + h değerine göre genişletir ve en düşük maliyetli bir yol döndürmeyi garanti eder; aynı sezgisel bilgiyi kullanan algoritmalar arasında A*, optimal derecede verimlidir.
- Gevşetme yoluyla sezgisel tasarım
- Kabul edilebilir (admissible) sezgisel fonksiyonlar, problemin gevşetilmiş bir versiyonunu (eylemler üzerinde daha az kısıtlaması olan bir versiyon) çözerek sistematik olarak türetilebilir, çünkü daha kolay bir problemin kesin maliyeti orijinal problemin bir alt sınırıdır; baskın (daha bilgilendirilmiş) sezgisel fonksiyonlar daha az düğüm genişletir.
- Bellek sınırlı sezgisel arama
- Yinelemeli derinleşen A*, artan bir f-maliyet eşiği ile sınırlanmış ardışık derinlik-önce aramalar gerçekleştirerek, çözüm derinliğine göre doğrusal bellekle A*-benzeri optimallik elde etmektedir.
Klinik önem
Sezgisel arama, haritalarda ve oyunlarda yol bulma, robotikte hareket planlama ile otomatik planlayıcılar ve bulmaca çözücüler içindeki arama motorlarının temelini oluşturmaktadır; sezgisel tasarımın pratik sanatı, büyük problemlerin kabul edilebilir bir sürede çözülüp çözülemeyeceğini doğrudan belirlemektedir.
Tarihçe
A* algoritması, Hart, Nilsson ve Raphael (1968) tarafından tanıtılmış, sezgisel aramaya resmi bir optimallik temeli sağlamıştır. Pearl'ün 1984 tarihli Heuristics monografisi, kesin teorik yaklaşımı sunmuş ve Korf'un 1985 tarihli IDA* çalışması A*'ın bellek maliyetini ele almıştır. Bu sonuçlar, yapay zeka eğitiminde temel materyal olmaya devam etmektedir.
Öne çıkan isimler
- Peter E. Hart
- Nils J. Nilsson
- Bertram Raphael
- Judea Pearl
- Richard E. Korf
İlgili konular
Temel eserler
- hart1968
- pearl1984
- korf1985
Sıkça sorulan sorular
- Kabul edilebilir (admissible) bir sezgisel fonksiyon nedir?
- Bir sezgisel fonksiyon, herhangi bir durumdan hedefe ulaşmanın gerçek maliyetini asla fazla tahmin etmiyorsa kabul edilebilir (admissible) olarak tanımlanır. Kabul edilebilirlik (admissibility), A*'ın optimal (en düşük maliyetli) bir çözüm bulmayı garanti ettiği koşuldur.
- Açgözlü en iyi-önce arama ile A* arasındaki fark nedir?
- Açgözlü en iyi-önce arama, yalnızca sezgisel fonksiyona (h) göre hedefe en yakın görünen durumu genişletir; bu hızlıdır ancak optimalden uzak olabilir. A*, şu ana kadar katlanılan gerçek maliyeti (g) ekleyerek f = g + h ile genişletme yapar, bu da sezgisel fonksiyon kabul edilebilir (admissible) olduğunda optimalliği korur.