Căutare grindă
| Căutare grindă | |
|---|---|
| Clasă | Algoritm de căutare |
| Structură de date | Copac |
| Cel mai rău caz din punct de vedere temporal | |
| Cel mai rău caz spațial | |
| Optim | Nu |
| Costum de afaceri | Nu |
În informatică , căutarea prin fascicul este un algoritm de căutare bazat pe euristică care explorează un grafic prin extinderea celui mai promițător nod într-un set limitat de noduri.
Beam search este un caz special de cea mai bună căutare care are ca scop reducerea cerințelor de memorie. Cea mai bună prima căutare este o căutare grafică care sortează toate soluțiile parțiale (stările) pe baza unei anumite euristici. În căutarea prin fascicul, sunt luate în considerare doar un număr predefinit de cele mai bune soluții parțiale. [1] În consecință, este considerat un algoritm lacom .
Denumirea de „căutare cu fascicul” a fost introdusă de Raj Reddy de la Universitatea Carnegie Mellon în 1977. [2]
Detalii
Algoritmul de căutare cu fascicul folosește o căutare de lățime pentru a-și construi arborele de căutare. La fiecare nivel de adâncime al arborelui, algoritmul generează toți succesorii nodurilor curente, aranjându-i astfel încât valorile funcției euristice să aibă o ordine crescătoare. [3] Cu toate acestea, spre deosebire de cea mai bună primă căutare , salvează doar până la un număr predefinit, , cu „cele mai bune” stări pentru fiecare nivel. Acest număr se numește „lățimea fasciculului”. Cu cât este mai mare lățimea implicită, cu atât este mai mic numărul de stări excluse din căutare. În mod logic, pentru nicio stare nu va fi exclusă și comportamentul algoritmului va fi identic cu cea mai bună căutare. Lățimea maximă implicită limitează cerințele de memorie pentru efectuarea acestei căutări. Algoritmul nu oferă garanții asupra completitudinii și nici asupra optimității soluției.
Lățimea se poate face și variabil. O posibilă abordare cu amplitudine variabilă implică inițial rularea algoritmului cu setat la valoarea minimă și, dacă nu se găsește nicio soluție, să crească valoarea acesteia la fiecare nouă execuție. [4]
Utilizări
Căutarea cu fascicul este utilizată în sisteme mari cu memorie insuficientă pentru a stoca întregul arbore de căutare. [5] De exemplu, este utilizat în diverse sisteme de traducere automată . [6] Pentru a selecta cea mai bună traducere, sunt generate diferite traduceri posibile ale fiecărui cuvânt, fiecare dintre ele depinzând de cuvânt și de contextul sintactic-semantic în care este inserat. [7] Prin urmare, pentru fiecare cuvânt se salvează o porțiune limitată a traducerilor disponibile, pentru a economisi spațiu, iar restul este aruncat.
Variante
Căutarea cu fascicul poate fi completată combinând-o cu căutarea în adâncime . Variațiile de acest tip includ căutarea stivei de grinzi [8] și căutarea grinzii în prima adâncime [5] .
În contextul unei căutări locale , căutarea cu fascicul local este un anumit algoritm care începe prin selectare au fost generate aleatoriu și apoi, pentru fiecare nivel al arborelui de căutare, luați în considerare întotdeauna noi state printre posibilii succesori ai celor actuale, până la atingerea obiectivului. [9] [10]
Deoarece căutarea prin fascicul local se termină de obicei pe maxime locale (soluții sub-optime), o soluție adoptată de obicei este alegerea celor noi stări aleatorii, cu o probabilitate în funcție de evaluarea euristică a fiecărui stat. Acest tip de căutare este cunoscut sub numele de căutare cu fascicul stocastic . [11]
Alte variante sunt căutarea cu fascicul flexibil și căutarea cu fascicul de recuperare . [10]
Notă
- ^ (EN) FOLDOC - Dicționar de calcul , pe foldoc.org. Adus la 11 aprilie 2016 .
- ^ (EN) D. Raj. Reddy, Sisteme de înțelegere a vorbirii: un rezumat al rezultatelor efortului de cercetare de cinci ani , Universitatea Carnegie Mellon - Departamentul de Informatică, 1977.
- ^ (RO) CĂUTAREA MUZEULUI BRITANIC , pe bradley.bradley.edu. Adus la 11 aprilie 2016 ( arhivat la 6 mai 2018) .
- ^ (EN) Peter Norvig, Paradigme of Artificial Intelligence Programming: Case Studies in Common LISP , Morgan Kaufmann, 1 ianuarie 1992, ISBN 978-1-55860-191-8 .
- ^ A b (EN) David Furcy, Sven Koenig, Căutare limită de discrepanță limitată (PDF), 2005. Adus la 22 decembrie 2007 (depus de 'url original 16 mai 2008).
- ^ (EN) Christoph Tillmann, Hermann Ney, Word Reordering and Dynamic Programming Beam Search Algorithm for Statistical Machine Translation (PDF). Adus la 22 decembrie 2007 (arhivat din original la 18 iunie 2006) .
- ^ În cea mai simplă versiune, acest context constă din cuvinte deja traduse în aceeași propoziție în ramura curentă a arborelui de căutare.
- ^ (EN) Zhou, Rong. Hansen, Eric, Beam-Stack Search: Integrarea backtracking-ului cu Beam Search , 2005.
- ^ (EN) Svetlana Lazebnik, Algoritmi de căutare locală (PDF) pe cs.unc.edu, Universitatea din Carolina de Nord la Chapel Hill, Departamentul de Informatică, p. 15. Accesat la 21 noiembrie 2018 ( arhivat la 5 iulie 2011) .
- ^ a b ( EN ) Pushpak Bhattacharyya, Beam Search ( PPTX ), su cse.iitb.ac.in , Indian Institute of Technology Bombay, Department of Computer Science and Engineering (CSE), pp. 39-40. Adus la 21 noiembrie 2018 ( arhivat la 21 noiembrie 2018) .
- ^ (EN) James Parker, Căutare locală (PDF) pe www-users.cselabs.umn.edu, Universitatea din Minnesota, 28 septembrie 2017, p. 17. Accesat la 21 noiembrie 2018 ( arhivat la 13 octombrie 2017) .
