Pretraga bima
U informatici, pretraga bima je heurističan algoritam za pretragu koji istražuje grafikon šireći čvor, koji najviše obećava, u limitiran cet. Pretraga bima je optimizacija Pretrage prema najboljem koja smanjuje memorijsku zahtevnost. Pretraga „prvi najbolji“ je grafička pretraga koja sortira sva parcijalna rešenja u zavisnosti od neke heuristike koja pokušava da predvidi koliko blizz je parcijalno rešenje kompletnom rešenju (stanje pogotka). Ali u pretrazi bima, samo predodređeni broj najboljih parcijalnih rešenja se čuvaju kao kandidati.[1]
Pretraga bima koristi Pretragu po širini za kreiranje stabla pretrage. Na svakom nivou stabala, ona generiše sva uspešna stanja, sortirajući ih od najmanjeg ka najvećem po ceni heuristike.[2] Međutim, ona skladišti samo predodređen broj najboljih stanja na svakom nivou (nazvanom širina bima). Samo ta stanja se proširuju dalje. Što je veća širina bima, manje stanja je odbačeno. Sa beskonačnom širinom bima, nijedno stanje nije odbačeno i pretraga miba je identična pretrazi po širini. Širina bima veže memoriju potrebnu da izvede pretragu. Pošto stanje pogotka potencijalno može biti odbačeno, pretraga bima žrtvuje kompletnost (garanciju da će algoritam izbaciti rešenje, ako ono postoji) i optimalnost (garanciju da će biti pronađeno najbolje rešenje.
Širina bima može biti fiksna ili varijabilna. Pristup koji koristi varijabilnu širinu bima počinje sa širinom na minimumu. Ako rešenje nije pronađeno, bim se širi i proces se ponavlja.[3]
Ime
urediTermin „pretraga bima“ je osmislio Raž Redi(Raj Reddy), Univerzitet Karnegi Melon, 1976.
Upotreba
urediPretraga bima se najčešće koristi da održi obradivost u velikim sistemima sa nedovoljnom količinom memorije za sklaštenje celog stabla pretrage.[4] Npr. Koristi se u mnogim sistemima za „prevod“ mašina.[5] Da bi se pronašlo najbolje rešenje, svaki deo se procesuira, i mnogo različitih načina prevoda reči se pojavi. Nekoliko najboljih prevoda prema strukturama rečenice se čuvaju dok se ostali odbacuju. Prevodilac onda ocenjuje prevode prema datom kriterijumu, birajući prevod koji vajbolje čuva pogodak. Pretraga bima je prvi put upotrebljena 1976 u Harpy Speech Recognition System-u.[6]
Ekstenzije
urediPretraga bima je kompletirana kobinovanjem sa Pretragom u dubinu što je rezultovalo Bim-Stek Pretragom[7] i Pretragom bima u dubinu[4], kao i limitiranom pretragom protivrečnosti, što je rezultovalo Bektrekingom bim pretrage sa limitiranim raskorakom (engl. Beam Search Using Limited Discrepancy Backtracking).[4] Ovi algoritmi za pretragu su algoritmi u "svako doba" (engl. anytime algorithms) koji pronalaze dobra ali često polu-optimalna rešenja brzo, kao pretraga bima, a zatim se vraćaju i nastavljaju da traže poboljšanja rešenja dok ne pronađu optimalno.
Reference
uredi- ^ beam search from FOLDOC Архивирано на сајту Wayback Machine (25. јануар 2020)
- ^ British Museum Search
- ^ Norvig, Peter. Paradigms of Artificial Intelligence. http://books.google.com/books?id=X4mhySvjqUAC&pg=PA196&lpg=PA196&dq=beam+search+in+paradigms+of+artificial+intelligence+programming&source=web&ots=20BH2lB3sc&sig=udBIO2Qeg8awaySgwCu7gDEObY4&hl=en&sa=X&oi=book_result&resnum=1&ct=result#PPA196,M1 Programming
- ^ a b v Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". 2005. Архивирано на сајту Wayback Machine (16. мај 2008)
- ^ „Tillmann, Christoph. Ney, Hermann. "Word Reordering and a Dynamic Programming Beam Search Algorithm for Statistical Machine Translation".” (PDF). Arhivirano iz originala (PDF) 18. 06. 2006. g. Pristupljeno 31. 05. 2013.
- ^ Lowerre, Bruce. "The Harpy Speech Recognition System", Ph.D. thesis, Carnegie Mellon University, 1976
- ^ „Zhou, Rong. Hansen, Eric. "Beam-Stack Search: Integrating Backtracking with Beam Search". 2005.”. Arhivirano iz originala 20. 04. 2021. g. Pristupljeno 31. 05. 2013.