Işın arama - Beam search

Gelen bilgisayar bilimleri , kiriş arama bir olan sezgisel arama algoritması sınırlı kümesinde en umut verici düğümü genişleterek grafiğini araştırır. Işın arama, bellek gereksinimlerini azaltan en iyi ilk aramanın bir optimizasyonudur . En iyi ilk arama, tüm kısmi çözümleri (durumları) bazı buluşsal yöntemlere göre sıralayan bir grafik aramadır. Ancak ışın aramada, aday olarak yalnızca önceden belirlenmiş sayıda en iyi kısmi çözüm tutulur. Bu nedenle açgözlü bir algoritmadır .

Dönem "ışın arama" tarafından icat edildi Raj Reddy ve Carnegie Mellon Üniversitesi'nde 1977 yılında.

Ayrıntılar

Işın arama , arama ağacını oluşturmak için genişlik öncelikli aramayı kullanır . Ağacın her seviyesinde, mevcut seviyedeki durumların tüm ardıllarını oluşturarak, artan buluşsal maliyet sırasına göre sıralar. Bununla birlikte, her seviyede (kiriş genişliği olarak adlandırılır) en iyi durumların yalnızca önceden belirlenmiş bir sayısını saklar . Daha sonra yalnızca bu eyaletler genişletilir. Kiriş genişliği ne kadar büyük olursa, o kadar az durum budanır. Sonsuz bir ışın genişliği ile, hiçbir durum budanmaz ve ışın araması, genişlik öncelikli arama ile aynıdır . Işın genişliği, aramayı gerçekleştirmek için gereken belleği sınırlar. Bir hedef durumu potansiyel olarak budanabileceğinden, ışın araması tamlığı (eğer varsa, bir algoritmanın bir çözümle sonlandırılacağı garantisi) feda eder. Işın araması optimal değildir (yani, en iyi çözümü bulacağına dair bir garanti yoktur). . ${\görüntüleme stili \beta }$

kullanır

Işın araması, çoğunlukla, tüm arama ağacını depolamak için yetersiz miktarda belleğe sahip büyük sistemlerde izlenebilirliği korumak için kullanılır. Örneğin, birçok makine çeviri sisteminde kullanılmıştır. (Tekniğin bilinen durumu, artık öncelikle sinirsel makine çevirisi tabanlı yöntemler kullanmaktadır.) En iyi çeviriyi seçmek için, her bölüm işlenir ve sözcükleri çevirmenin birçok farklı yolu görünür. Cümle yapılarına göre en iyi çeviriler tutulur ve geri kalanı atılır. Çevirmen daha sonra çevirileri belirli bir kritere göre değerlendirir ve amaçları en iyi şekilde tutan çeviriyi seçer. Bir ışın aramasının ilk kullanımı, Harpy Konuşma Tanıma Sistemi, CMU 1976'daydı.

Varyantlar

Kiriş araması, derinlik öncelikli arama ile birleştirilerek tamamlandı , bu da kiriş yığını araması ve derinlik öncelikli kiriş araması ile sonuçlandı ve sınırlı tutarsızlık araması ile sonuçlandı ve sınırlı tutarsızlık geri izleme (BULB) kullanılarak kiriş aramasıyla sonuçlandı . Ortaya çıkan arama algoritmaları, ışın araması gibi hızlı bir şekilde iyi ancak olası alt-optimal çözümleri bulan, daha sonra geriye doğru giden ve optimal bir çözüme yakınsayana kadar gelişmiş çözümler bulmaya devam eden herhangi bir zamanda algoritmalardır .

Yerel arama bağlamında, rastgele oluşturulmuş durumları seçmeye başlayan ve daha sonra, arama ağacının her bir seviyesi için, her zaman mevcut olanların tüm olası ardılları arasında yeni durumları dikkate alan belirli bir algoritmaya yerel ışın araması diyoruz . bir hedefe ulaşır. ${\görüntüleme stili \beta }$${\görüntüleme stili \beta }$

Yerel ışın araması genellikle yerel maksimumlarda sona erdiğinden, ortak bir çözüm, sonraki durumları, durumların buluşsal değerlendirmesine bağlı bir olasılıkla rastgele bir şekilde seçmektir . Bu tür aramaya stokastik ışın araması denir . ${\görüntüleme stili \beta }$

Diğer varyantlar, esnek ışın arama ve kurtarma ışın aramadır .

Referanslar