tag Arama Algoritması
A* Algoritması Nedir? Yapay Zekada Yol Bulma (A* Arama Algoritması)
Bu sayfada Arama Algoritması (A* Algoritması Nedir? Yapay Zekada Yol Bulma (A* Arama Algoritması)) etiketi ile işaretlenmiş 3 yapay zeka kavramını bulabilirsiniz.
A* (A-yıldız) algoritması, 1968 yılında Peter Hart, Nils Nilsson ve Bertram Raphael tarafından Stanford Araştırma Enstitüsü'nde geliştirilen, graflar ve ağlar üzerinde en kısa yolu bulan sezgisel bir arama algoritmasıdır. Yapay zeka, robotik, oyun geliştirme ve navigasyon sistemlerinde en yaygın kullanılan yol bulma (pathfinding) yöntemi olma özelliğini korumaktadır. A*, Dijkstra algoritmasının garantili optimalliği ile sezgisel arama yöntemlerinin verimliliğini bir araya getirir. Temel değerlendirme fonksiyonu f(n) = g(n) + h(n) formülüyle tanımlanır: g(n) başlangıç noktasından mevcut düğüme ulaşmanın gerçek maliyetini, h(n) ise mevcut düğümden hedef noktaya olan tahmini mesafeyi (sezgisel fonksiyon) ifade eder. Bu iki bileşeni birleştirerek algoritma, hem geçmiş maliyeti hem de gelecekteki tahmini maliyeti optimize eder. Algoritmanın doğruluk ve optimallik garantisi, kullanılan sezgisel fonksiyonun kabul edilebilir (admissible) olmasına bağlıdır. Kabul edilebilir sezgisel, gerçek maliyeti hiçbir zaman olduğundan fazla tahmin etmez. Düzlemsel koordinatlarda sıklıkla kullanılan Öklid ve Manhattan mesafe formülleri bu kriteri karşılar. Sezgisel aynı zamanda tutarlı (consistent/monotone) olduğunda A* keşfedilen düğümleri yeniden ziyaret etmez ve bellek kullanımı azalır. A*, açık liste (open list) ve kapalı liste (closed list) veri yapılarıyla çalışır. Önce başlangıç düğümünü açık listeye ekler; her adımda f değeri en düşük düğümü seçer, komşularını değerlendirir ve listeyi günceller. Bu süreç hedefe ulaşılana veya tüm olası yollar tükenene kadar devam eder. Öncelik kuyruğu (priority queue) ile uygulandığında zaman karmaşıklığı O(E log V) mertebesindedir. Yapay zeka araştırmalarında A*, pekiştirmeli öğrenmede planlama problemlerinin çözümünde, doğal dil işlemede sözdizimi ağaçlarının aranmasında ve konfigürasyon uzaylarında robot hareket planlamasında kullanılmaktadır. Oyun motorlarında ise NPC (Non-Player Character) yapay zekasının temel navigasyon bileşeni olarak yaygındır. Büyük ölçekli harita uygulamalarında A* varyantları (IDA*, D* Lite) bellek ve hız optimizasyonu için tercih edilmektedir.
A* Algoritması Nedir? Yapay Zekada Yol Bulma (A* Arama Algoritması)
A* (A-yıldız) algoritması, 1968 yılında Peter Hart, Nils Nilsson ve Bertram Raphael tarafından Stanford Araştırma Enstitüsü'nde geliştirilen, graflar ve ağlar üzerinde en kısa yolu bulan sezgisel bir arama algoritmasıdır. Yapay zeka, robotik, oyun geliştirme ve navigasyon sistemlerinde en yaygın kullanılan yol bulma (pathfinding) yöntemi olma özelliğini korumaktadır. A*, Dijkstra algoritmasının garantili optimalliği ile sezgisel arama yöntemlerinin verimliliğini bir araya getirir. Temel değerlendirme fonksiyonu f(n) = g(n) + h(n) formülüyle tanımlanır: g(n) başlangıç noktasından mevcut düğüme ulaşmanın gerçek maliyetini, h(n) ise mevcut düğümden hedef noktaya olan tahmini mesafeyi (sezgisel fonksiyon) ifade eder. Bu iki bileşeni birleştirerek algoritma, hem geçmiş maliyeti hem de gelecekteki tahmini maliyeti optimize eder. Algoritmanın doğruluk ve optimallik garantisi, kullanılan sezgisel fonksiyonun kabul edilebilir (admissible) olmasına bağlıdır. Kabul edilebilir sezgisel, gerçek maliyeti hiçbir zaman olduğundan fazla tahmin etmez. Düzlemsel koordinatlarda sıklıkla kullanılan Öklid ve Manhattan mesafe formülleri bu kriteri karşılar. Sezgisel aynı zamanda tutarlı (consistent/monotone) olduğunda A* keşfedilen düğümleri yeniden ziyaret etmez ve bellek kullanımı azalır. A*, açık liste (open list) ve kapalı liste (closed list) veri yapılarıyla çalışır. Önce başlangıç düğümünü açık listeye ekler; her adımda f değeri en düşük düğümü seçer, komşularını değerlendirir ve listeyi günceller. Bu süreç hedefe ulaşılana veya tüm olası yollar tükenene kadar devam eder. Öncelik kuyruğu (priority queue) ile uygulandığında zaman karmaşıklığı O(E log V) mertebesindedir. Yapay zeka araştırmalarında A*, pekiştirmeli öğrenmede planlama problemlerinin çözümünde, doğal dil işlemede sözdizimi ağaçlarının aranmasında ve konfigürasyon uzaylarında robot hareket planlamasında kullanılmaktadır. Oyun motorlarında ise NPC (Non-Player Character) yapay zekasının temel navigasyon bileşeni olarak yaygındır. Büyük ölçekli harita uygulamalarında A* varyantları (IDA*, D* Lite) bellek ve hız optimizasyonu için tercih edilmektedir.
Beam Search Decoding Nedir? Paralel Hipotez Arama (Işın Arama Kod Çözme)
Beam search decoding, otomatik çeviriden metin özetlemeye kadar geniş bir yelpazede kullanılan temel bir çıkarım algoritmasıdır. Greedy search her adımda yalnızca en yüksek olasılıklı tek tokeni seçerken; beam search 'ışın genişliği' (beam width, k) kadar hipotezi paralel biçimde takip eder. Her adımda mevcut k hipotezin her biri en olası devamlarıyla genişletilir, ortaya çıkan k×vocab_size aday arasından toplamda en yüksek log-olasılıklı k dizisi bir sonraki adım için korunur. Son token üretildiğinde (veya EOS tokeni görüldüğünde) en yüksek kümülatif olasılıklı dizi çıktı olarak döner. k=1 greedy search ile özdeştir; k arttıkça arama kalitesi artabilir ancak hesaplama ve bellek maliyeti de k katına çıkar.
Monte Carlo Tree Search (MCTS) Nedir? (Monte Carlo Ağaç Araması)
Monte Carlo Tree Search (MCTS), olasılıksal simülasyonlar kullanarak geniş karar ağaçlarında en iyi hamleyi bulan buluşsal bir arama algoritmasıdır. Klasik minimax aramasından farklı olarak tüm dalları değerlendirmek yerine yüzlerce rastgele simülasyon (rollout) çalıştırır ve kaynakları en umut verici bölgelere yoğunlaştırır. Dört aşamalı bir döngü üzerine kuruludur: Seçim aşamasında mevcut ağaçta UCT (Upper Confidence bounds applied to Trees) formülüyle en iyi düğüm seçilir; Genişleme aşamasında seçilen düğüme yeni çocuk düğümler eklenir; Simülasyon (Rollout) aşamasında rasgele ya da ağırlıklı politika oynamasıyla bir sonuca gidilir; Geri Yayılım aşamasında simülasyon sonucu ağaçtan köke kadar taşınarak istatistikler güncellenir. Verilen süre ya da iterasyon sayısı dolana dek bu döngü tekrar eder; en çok ziyaret edilen kök çocuğu nihai hamle olarak seçilir. Algoritma 2006 yılında Rémi Coulom tarafından bilgisayarlı Go için önerilmiş, Kocsis ve Szepesvári'nin UCT formülüyle güçlendirilmiştir. 2016'da DeepMind'ın AlphaGo programı MCTS'i derin sinir ağlarıyla birleştirerek dünya Go şampiyonu Lee Sedol'ü 4-1 yenerek tarihin en dikkat çekici yapay zeka başarılarından birini gerçekleştirmiştir. 2017'de AlphaZero, satranç, shogi ve Go'da yalnızca öz-oyun ve MCTS kullanarak insan yazılmış bilgiye ihtiyaç duymaksızın tablo kıran performanslar elde etmiştir. MCTS, değerlendirme fonksiyonu tasarlamak güç olmakla birlikte simülasyonların hızlı olduğu board oyunlarından robot planlamasına, ilaç keşfine ve operasyon araştırmasına kadar pek çok alanda tercih edilen güçlü bir karar verme aracıdır.