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. Ez tehát egy mohó algoritmus.

A „nyalábkeresés” kifejezést Raj Reddy alkotta meg a Carnegie Mellon Egyetemen 1977-ben.

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 $\beta$ -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. 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).

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.

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éssel é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 $\beta$ véletlenszerűen generált állapotok kiválasztásával kezdődik, majd a keresési fa minden szintjén mindig a $\beta$ ú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ő $\beta$ á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.