Nyalábkeresés
A számítástechnikában a nyalábkeresés egy heurisztikus keresőalgoritmus, amely feltérképezi a gráfot egy korlátozott halmaz legígéretesebb csomópontjának kiterjesztésével. A nyalábkeresés a legjobbat először keresés optimalizálása, amely által csökken a memóriaigény. A legjobbat először keresés egy olyan gráfbejárás, amely az összes részmegoldást (állapotot) valamilyen heurisztika szerint rendezi. A nyalábkeresés során azonban csak előre meghatározott számú legjobb részmegoldást tartanak meg jelöltként.[1] Ez tehát egy mohó algoritmus.
A „nyalábkeresés” kifejezést Raj Reddy alkotta meg a Carnegie Mellon Egyetemen 1977-ben.[2]
Részletek szerkesztés
A nyalábkeresés a szélességi keresést használja a keresési fa felépítéséhez. A fa minden egyes szintjén legenerálja az állapotok rá következőit az aktuális szinten, növekvő sorrendbe rendezi a heurisztikus költségek alapján.[3] Azonban, ez csak szintenként a legjobb állapot egy előre meghatározott számát tárolja el, a -t (ezt hívjuk a nyaláb szélességének). Ezután csak ezeket az állapotokat fejti ki. Minél nagyobb a nyaláb szélessége, annál kevesebb terület lesz lenyesve. Végtelen nyalábszélesség esetén egyetlen terület sem lesz lenyesve, és a nyalábkeresés ekvivalens a szélességi kereséssel.
A nyaláb szélessége korlátozza a keresés végrehajtásához szükséges memóriát. Amíg egy célállapot nem kerülhet lenyesésre, a nyalábkeresés lemond a teljességről (a garanciáról, hogy egy algoritmus megoldással fejeződik be, amennyiben létezik). A nyalábkeresés nem optimális (vagyis nincs garancia arra, hogy megtalálja a legjobb megoldást).
Általánosságban véve a nyalábkeresés az első megoldással tér vissza. A gépi fordításhoz használt nyalábkeresés más eset: amint eléri a beállított maximum keresési mélységet (például a fordítási hosszt) az algoritmus kiértékeli a különböző mélységekben végzett keresés során megtalált megoldásokat, és visszatér a legjobbal (a legmagasabb valószínűségűvel).
A nyalábszélesség egyaránt lehet állandó vagy változó. Az egyik megközelítés, amely változó nyalábszélességet használ, minimum szélességgel kezdődik. Ha nem sikerül megoldást találni, akkor a nyalábot szélesítik és megismételik az eljárást.[4]
Felhasználások szerkesztés
A nyalábkeresést leggyakrabban arra használják, hogy fenntartsa a kezelhetőséget a nagy rendszerekben, nem elegendő mennyiségű memóriával, hogy a teljes keresési fa tárolásra kerüljön.[5] Például számos gépi fordítórendszerben használják (a technika jelenlegi állása szerint elsősorban neurális gépi fordításon alapuló módszereket használ).[6]
A legjobb fordítás kiválasztásához minden egyes rész feldolgozásra kerül, és a szavak fordításának számos különböző módja jelenik meg. A mondatszerkezetek szerint a legjobb fordítások megtartásra, a többi pedig elvetésre kerül. A fordító ezután kiértékeli a megadott kritériumnak megfelelő fordításokat és kiválasztja a célhoz legközelebb álló fordítást.
Nyalábkeresést először a Harpy Speech Recognition Systemben használtak 1976-ban.[7]
Változatok szerkesztés
A nyalábkeresés úgy vált teljessé, hogy kombinálták a mélységi kereséssel, az eredményként jelentkező nyaláb-verem kereséssel[8] és mélységi nyalábkereséssel,[5] valamint korlátozott eltérés kereséssel, illetve korlátozott eltérés-visszahúzódást (BULB) használó nyalábkereséssel. A kapott keresési algoritmusok „akármikor algoritmusok”, amelyek jó, de valószínűleg nem a legkedvezőbb megoldásokat találják meg gyorsan, mint a nyalábkeresés, ezután visszalépnek és folytatják a tovább fejlesztett megoldások keresését, amíg az nem konvergál az optimális megoldáshoz.
A helyi keresés kapcsán a helyi nyalábkeresést egy olyan speciális algoritmusnak nevezzük, amely a véletlenszerűen generált állapotok kiválasztásával kezdődik, majd a keresési fa minden szintjén mindig a új állapotait veszi figyelembe az összes aktuális, lehetséges utódja között, amíg el nem éri a célt.
Lévén a helyi nyalábkeresés gyakran végződik helyi maximumokon egy általános megoldás az, hogy a következő állapotokat véletlenszerűen választják ki, az állapotok heurisztikus kiértékelésének valószínűségétől függően. Az ilyen típusú keresést sztochasztikus nyalábkeresésnek nevezzük.
Egyéb változatok a rugalmas nyalábkeresés és a helyreállítási nyalábkeresés.
Jegyzetek szerkesztés
- ↑ FOLDOC - Computing Dictionary. foldoc.org. [2020. január 25-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. április 11.)
- ↑ Reddy, D. Raj. "Speech Understanding Systems: A Summary of Results of the Five-Year Research Effort. Department of Computer Science.", 1977.
- ↑ BRITISH MUSEUM SEARCH. bradley.bradley.edu . (Hozzáférés: 2016. április 11.)
- ↑ Norvig, Peter. Paradigms of Artificial Intelligence Programming: Case Studies in Common LISP (angol nyelven). Morgan Kaufmann (1992. január 1.). ISBN 9781558601918
- ↑ a b Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". 2005. Archived copy. [2008. május 16-i dátummal az eredetiből archiválva]. (Hozzáférés: 2007. december 22.)
- ↑ Tillmann, Christoph. Ney, Hermann. "Word Reordering and a Dynamic Programming Beam Search Algorithm for Statistical Machine Translation". Archived copy. [2006. június 18-i dátummal az eredetiből archiválva]. (Hozzáférés: 2007. december 22.)
- ↑ 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. http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php Archiválva 2021. április 20-i dátummal a Wayback Machine-ben
Fordítás szerkesztés
Ez a szócikk részben vagy egészben a Beam search című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.