In informatica, la beam search è un algoritmo di ricerca basato su euristiche che esplora un grafo espandendo il nodo più promettente in un insieme limitato di nodi.
La beam search è un caso particolare di best-first search che mira a ridurre i requisiti di memoria. Best-first search è una ricerca su grafi che ordina tutte le soluzioni parziali (stati) in base ad una certa euristica. Nella beam search è tenuto in considerazione solo un numero predefinito di migliori soluzioni parziali.[1] Di conseguenza, è considerato un algoritmo greedy.
Il nome "beam search" venne introdotto da Raj Reddy dell'Università Carnegie Mellon, nel 1977.[2]
L'algoritmo beam search utilizza una ricerca in ampiezza per costruire il suo albero di ricerca. Ad ogni livello di profondità dell'albero, l'algoritmo genera tutti i successori dei nodi correnti, dispondendoli in modo che i valori della funzione euristica abbiano un ordine crescente.[3] Tuttavia, a differenza della best-first search, salva solo fino un numero predefinito, β {\displaystyle \beta } , di stati "migliori" per ogni livello. Questo numero β {\displaystyle \beta } è chiamato "beam width" (lett. "ampiezza del fascio"). Più grande è l'ampiezza predefinita, minore sarà il numero di stati esclusi dalla ricerca. Logicamente, per β = ∞ {\displaystyle \beta =\infty } non verrà escluso nessuno stato e il comportamento dell'algoritmo sarà identico ad una best-first search. L'ampiezza massima predefinita limita i requisiti di memoria per eseguire questa ricerca. L'algoritmo non fornisce garanzie sulla completezza, né sull'ottimalità della soluzione.
L'ampiezza β {\displaystyle \beta } può anche essere resa variabile. Un possibile approccio con ampiezza variabile prevede di eseguire inizialmente l'algoritmo con β {\displaystyle \beta } impostato al valore minimo e, se nessuna soluzione viene trovata, di aumentarne il valore ad ogni nuova esecuzione.[4]
La beam search viene usata in grandi sistemi aventi memoria insufficiente per memorizzare l'intero albero di ricerca.[5] Ad esempio, è usata in vari sistemi di traduzione automatica.[6] Per selezionare la traduzione migliore, di ogni parola vengono generate diverse possibili traduzioni, ciascuna delle quali dipende dalla parola e dal contesto sintattico-semantico in cui è inserita.[7] Per ogni parola viene dunque salvata una porzione limitata delle traduzioni disponibili, in modo da risparmiare spazio, e viene scartato il resto.
La beam search può essere resa completa combinandola con la ricerca in profondità. Fra le varianti di questo tipo, troviamo la beam stack search[8] e depth-first beam search[5].
Nel contesto di una ricerca locale, la local beam search è un particolare algoritmo che inizia selezionando β {\displaystyle \beta } stati generati casualmente e poi, per ogni livello dell'albero di ricerca, considera sempre β {\displaystyle \beta } nuovi stati fra i possibili successori di quelli correnti, fino a quando l'obiettivo non viene raggiunto.[9][10]
Dato che la local beam search è solita terminare su massimi locali (soluzioni sotto-ottimali), una soluzione adottata solitamente è quella di scegliere i nuovi β {\displaystyle \beta } stati in maniera casuale, con una probabilità dipendente dalla valutazione euristica di ciascuno stato. Questo tipo di ricerca è nota come stochastic beam search.[11]
Altre varianti sono flexible beam search e recovery beam search.[10]