Căutare fascicul

În informatică , Beam Search este un algoritm de căutare euristică care explorează un grafic prin extinderea nodurilor promițătoare într-un set limitat. Căutarea fasciculului este o optimizare a căutării cu cea mai bună potrivire care reduce cerințele de memorie. Prima căutare a celei mai bune potriviri este o căutare grafică care ordonează toate soluțiile (stările) particulare în funcție de unele euristice. Dar în căutarea cu raze, doar un număr predeterminat de cele mai bune soluții parțiale sunt stocate ca candidați [1] . Astfel, este un algoritm lacom .

Termenul de căutare a fasciculului a fost introdus de Raj Reddy de la Universitatea Carnegie Mellon în 1977 [2] .

Detalii

Căutarea fasciculului folosește căutarea pe lățime pentru a-și construi arborele de căutare . La fiecare nivel al arborelui generează toți succesorii de stare la nivelul curent, sortându-i în ordine crescătoare a costului euristic [3] . Cu toate acestea, stochează doar un număr predeterminat de cele mai bune stări la fiecare nivel (numit lățimea fasciculului). Mai mult, doar aceste stări sunt desfășurate. Cu cât lățimea fasciculului este mai mare, cu atât sunt eliminate mai puține stări. Cu o lățime infinită a fasciculului, nicio stare nu este anulată, iar căutarea fasciculului este identică cu căutarea pe lățimea întâi. Lățimea fasciculului limitează cantitatea de memorie necesară pentru a efectua o căutare. Deoarece starea țintă poate fi redusă, căutarea razelor sacrifică completitatea (garanția că algoritmul se va termina cu o soluție dacă există una). Căutarea fasciculului nu este optimă (adică nu există nicio garanție că va fi găsită cea mai bună soluție) [4] .

Aplicație

Căutarea fasciculului este cel mai adesea folosită pentru a oferi manevrabilitate în sisteme mari cu memorie insuficientă pentru a stoca întregul arbore de căutare [5] . De exemplu, a fost folosit în multe sisteme de traducere automată [6] . (În stadiul tehnicii, metodele bazate pe traducerea automată neuronală sunt acum utilizate în principal .) Pentru a alege cea mai bună traducere, fiecare parte este procesată și apar multe moduri diferite de traducere a cuvintelor. Cele mai bune traduceri conform structurii propoziției sunt păstrate, iar restul sunt aruncate. Apoi, traducătorul evaluează traducerile în funcție de un criteriu dat, selectând traducerea care se potrivește cel mai bine obiectivelor. Prima utilizare a căutării fasciculului a fost în Harpy's Speech Recognition System, CMU 1976 [7] .

Opțiuni

Căutarea fasciculului a fost realizată în întregime prin combinarea acesteia cu căutarea depth-first , rezultând în căutarea în stiva de raze [8] , căutarea în adâncime a razei în primul rând [5] și cu căutarea cu disparitate limitată [9] , ceea ce duce la căutarea fasciculului folosind backtracking limitat inconsecvențe [5] (BULB [10] ). Algoritmii de căutare care rezultă sunt algoritmi de orice moment care găsesc rapid soluții bune, dar probabil suboptime, cum ar fi căutarea cu raze, apoi merg înapoi și continuă să caute soluții mai bune până când acestea converg către o soluție optimă.

În contextul căutării locale, numim căutare locală beam un anumit algoritm care începe prin selectarea stărilor generate aleatoriu și apoi, pentru fiecare, ia în considerare întotdeauna la nivelul arborelui de căutare stări noi dintre toți succesorii posibili ai stărilor curente până când atinge obiectivul . 11] [12] .

Deoarece căutarea fasciculului local se termină adesea la maxime locale, soluția obișnuită este de a selecta aleatoriu stările următoare cu o probabilitate în funcție de estimarea euristică a stărilor. Acest tip de căutare se numește căutare stocastică în fascicul [13] .

Alte opțiuni sunt căutarea fasciculului flexibil și căutarea fasciculului reconstructiv [12] .

Note

1. ↑ FOLDOC - Dicţionar de calculator . foldoc.org . Consultat la 11 aprilie 2016. Arhivat din original la 25 ianuarie 2020. (nedefinit)
2. ↑ Reddy, Dabbala Raj . Sisteme de înțelegere a vorbirii: un rezumat al cinci ani de cercetare. Departamentul de Informatică. , 1977
3. ↑ CĂUTARE ÎN MUZEUL BRITANIC . bradley.bradley.edu _ Preluat la 11 aprilie 2016. Arhivat din original la 6 mai 2018. (nedefinit)
4. ↑ Peter Norvig . Paradigme de programare AI: Exemple comune de utilizare LISP  : [ ing. ] . — Morgan Kaufmann, 1992-01-01. — ISBN 9781558601918 . Arhivat pe 20 aprilie 2021 la Wayback Machine
5. ↑ 1 2 3 David Fursey, Sven Koenig. Nepotrivire de căutare cu fascicul limitat . 2005. Copie de arhivă . Consultat la 22 decembrie 2007. Arhivat din original pe 16 mai 2008. (nedefinit)
6. ↑ Christoph Tillmann, Hermann Ney. Reordonarea cuvintelor și algoritmul de căutare a fasciculului de programare dinamică pentru traducerea automată statistică . Copie arhivată . Consultat la 22 decembrie 2007. Arhivat din original pe 18 iunie 2006. (nedefinit)
7. ↑ Bruce Lowerr. Harpy's Speech Recognition System , teză de doctorat, Universitatea Carnegie Mellon, 1976
8. ↑ Zhou Rong, Eric Hansen. Beam Stack Search: Integrarea Backtracking cu Beam Search . 2005. http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php Arhivat 20 aprilie 2021 la Wayback Machine
9. ↑ CiteSeer x :  10.1.1.34.2426
10. ↑ BULB este o abreviere a expresiei engleze Beam search Folosind discrepanța limitată B acktracking _ _
11. ↑ Svetlana Lazebnik. Algoritmi de căutare locale . Universitatea din Carolina de Nord la Chapel Hill , Departamentul de Informatică. Arhivat din original pe 5 iulie 2011. (nedefinit)
12. ↑ 1 2 Pushpak Bhattacharya. Căutare fascicul 39-40. Institutul Indian de Tehnologie, Bombay, Facultatea de Informatică și Inginerie (CIS). Arhivat din original pe 21 noiembrie 2018. (nedefinit)
13. ↑ James Parker. Căutare locală . Universitatea din Minnesota (28 septembrie 2017). Consultat la 21 noiembrie 2018. Arhivat din original la 13 octombrie 2017. (nedefinit)