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. Ez tehát egy mohó algoritmus.
A „nyalábkeresés” kifejezést Raj Reddy alkotta meg a Carnegie Mellon Egyetemen 1977-ben.Reddy, D. Raj. "Speech Understanding Systems: A Summary of Results of the Five-Year Research Effort. Department of Computer Science.", 1977.
Részletek 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. 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.
Felhasználások 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.Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". 2005. 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).Tillmann, Christoph. Ney, Hermann. "Word Reordering and a Dynamic Programming Beam Search Algorithm for Statistical Machine Translation".
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.Lowerre, Bruce. "The Harpy Speech Recognition System", Ph.D. thesis, Carnegie Mellon University, 1976
Változatok 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ésselZhou, Rong. Hansen, Eric. "Beam-Stack Search: Integrating Backtracking with Beam Search". 2005. http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php és mélységi nyalábkereséssel, 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
Fordítás
Kategória:Keresőalgoritmusok