Paprskové prohledávání

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Paprskové prohledávání (anglicky beam search) je jeden z algoritmů na prohledávání stavového prostoru. Jeho základem je myšlenka uspořádaného prohledávání pokračovat v prohledávání vždy z nejslibnějšího uzlu doplněná o „ořezávání“ nejméně slibných větví, což snižuje paměťové nároky. Pro každý prohledávaný uzel jsou všichni jeho následníci setříděni podle dané heuristiky a do prioritní fronty k dalšímu prohledávání je pak vložen jen určitý počet daný takzvanou „šířkou paprsku“, která je v základní verzi algoritmu pevně dána. Při nastavení šířky paprsku na nekonečno odpovídá algoritmus algoritmu uspořádaného vyhledávání.

Typické je užití paprskového prohledávání v systémech strojového překladu, které jsou založeny na statistice.