Hledání paprskem

V informatice je Beam Search heuristický vyhledávací algoritmus , který zkoumá graf rozšiřováním slibných uzlů v omezené množině. Beam search je optimalizace vyhledávání první nejlepší shody , která snižuje požadavky na paměť. První vyhledávání s nejlepší shodou je vyhledávání v grafu, které seřadí všechna konkrétní řešení (stavy) podle nějaké heuristiky. Ale při vyhledávání paprsků je jako kandidáti uložen pouze předem určený počet nejlepších dílčích řešení [1] . Jedná se tedy o chamtivý algoritmus .

Termín hledání paprskem zavedl Raj Reddy z Carnegie Mellon University v roce 1977 [2] .

Podrobnosti

Beam search používá k vytvoření svého vyhledávacího stromu prohledávání šířky . Na každé úrovni stromu vygeneruje všechny následníky stavu na aktuální úrovni a seřadí je vzestupně podle heuristických nákladů [3] . Ukládá však pouze předem stanovený počet nejlepších stavů na každé úrovni (tzv. šířka paprsku). Dále jsou rozvinuty pouze tyto stavy. Čím větší je šířka paprsku, tím méně stavů je odstraněno. S nekonečnou šířkou paprsku se nezruší žádné stavy a prohledávání paprskem je totožné s prohledáváním do šířky. Šířka paprsku omezuje množství paměti potřebné k provedení vyhledávání. Protože cílový stav může být potenciálně redukován, ray search obětuje úplnost (záruku, že algoritmus skončí s řešením, pokud nějaké existuje). Hledání pomocí paprsku není optimální (to znamená, že neexistuje záruka, že bude nalezeno nejlepší řešení) [4] .

Aplikace

Beam search se nejčastěji používá k zajištění správy ve velkých systémech s nedostatečnou pamětí pro uložení celého vyhledávacího stromu [5] . Například byl použit v mnoha systémech strojového překladu [6] . (Za současného stavu techniky se nyní používají hlavně metody založené na neuronovém strojovém překladu .) Aby bylo možné vybrat nejlepší překlad, je každá část zpracována a objevuje se mnoho různých způsobů překladu slov. Nejlepší překlady podle jejich větné struktury jsou zachovány a ostatní jsou vyřazeny. Překladatel poté vyhodnotí překlady podle daného kritéria a vybere překlad, který nejlépe odpovídá cílům. První použití paprskového vyhledávání bylo v Harpy's Speech Recognition System, CMU 1976 [7] .

Možnosti

Prohledávání paprskem bylo provedeno výhradně jeho kombinací s vyhledáváním na hloubku , což vedlo k prohledávání zásobníku paprsků [8] , vyhledávání paprsku do hloubky [5] a s omezeným vyhledáváním rozdílů [9] , což vede k vyhledávání paprskem pomocí omezeného zpětného sledování . nekonzistence [5] (BULB [10] ). Výsledné vyhledávací algoritmy jsou algoritmy kdykoliv, které rychle najdou dobrá, ale pravděpodobně neoptimální řešení, jako je vyhledávání paprsků, pak se vrátí a pokračují v hledání lepších řešení, dokud nedosáhnou optimálního řešení.

V kontextu lokálního vyhledávání nazýváme paprskovým lokálním vyhledáváním konkrétní algoritmus, který začíná výběrem náhodně generovaných stavů a ​​poté pro každý vždy zvažuje na úrovni vyhledávacího stromu nové stavy mezi všemi možnými nástupci aktuálních stavů, dokud nedosáhne cíle [ 11] [12] .

Protože vyhledávání lokálního svazku často končí na lokálních maximech, obvyklým řešením je vybrat další stavy náhodně s pravděpodobností závisející na heuristickém odhadu stavů. Tento druh vyhledávání se nazývá stochastické vyhledávání paprskem [13] .

Dalšími možnostmi jsou flexibilní vyhledávání paprskem a rekonstrukční vyhledávání paprskem [12] .

Poznámky

1. ↑ FOLDOC - Počítačový slovník . Foldoc.org . Získáno 11. dubna 2016. Archivováno z originálu 25. ledna 2020. (neurčitý)
2. ↑ Reddy, Dabbala Raj . Systémy porozumění řeči: Shrnutí pěti let výzkumu. Katedra informatiky. , 1977
3. ↑ HLEDÁNÍ V BRITSKÉM MUZEU . bradley.bradley.edu _ Získáno 11. 4. 2016. Archivováno z originálu 6. 5. 2018. (neurčitý)
4. ↑ Peter Norvig . Paradigmata programování AI: Běžné příklady použití LISP  : [ eng. ] . — Morgan Kaufmann, 1992-01-01. — ISBN 9781558601918 . Archivováno 20. dubna 2021 na Wayback Machine
5. ↑ 1 2 3 David Fursey, Sven Koenig. Limited Beam Search Mismatch . 2005. Archivní kopie . Získáno 22. prosince 2007. Archivováno z originálu 16. května 2008. (neurčitý)
6. ↑ Christoph Tillmann, Hermann Ney. Změna pořadí slov a algoritmus dynamického programovacího paprsku pro statistický strojový překlad . Archivovaná kopie . Získáno 22. prosince 2007. Archivováno z originálu 18. června 2006. (neurčitý)
7. ↑ Bruce Lowerr. Harpy's Speech Recognition System , PhD práce, Carnegie Mellon University, 1976
8. ↑ Zhou Rong, Eric Hansen. Beam Stack Search: Integrace Backtracking s Beam Search . 2005. http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php Archivováno 20. dubna 2021 na Wayback Machine
9. ↑ CiteSeer x :  10.1.1.34.2426
10. ↑ BULB je zkratka anglického výrazu Beam search Using L imited discrepancy B acktracking _ _ _
11. ↑ Světlana Lazebnik. Algoritmy místního vyhledávání . Univerzita Severní Karolíny v Chapel Hill , Katedra informatiky. Archivováno z originálu 5. července 2011. (neurčitý)
12. ↑ 1 2 Pushpak Bhattacharya. Hledání pomocí paprsku 39-40. Indický technologický institut, Bombaj, Fakulta informatiky a inženýrství (CIS). Archivováno z originálu 21. listopadu 2018. (neurčitý)
13. ↑ James Parker. Místní vyhledávání . University of Minnesota (28. září 2017). Staženo 21. listopadu 2018. Archivováno z originálu 13. října 2017. (neurčitý)