Beam search
# Beam search

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. Di conseguenza, è considerato un algoritmo greedy.

Il nome "beam search" venne introdotto da Raj Reddy dell'Università Carnegie Mellon, nel 1977.

## Dettagli

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. Tuttavia, a differenza della best-first search, salva solo fino un numero predefinito, $\beta$, di stati "migliori" per ogni livello. Questo numero $\beta$ è chiamato "beam width" (lett. "ampiezza del fascio"). Più grande è l'ampiezza predefinita, minore sarà il numero di stati esclusi dalla ricerca. Logicamente, per $\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 $\beta$ può anche essere resa variabile. Un possibile approccio con ampiezza variabile prevede di eseguire inizialmente l'algoritmo con $\beta$ impostato al valore minimo e, se nessuna soluzione viene trovata, di aumentarne il valore ad ogni nuova esecuzione.

## Utilizzi

La beam search viene usata in grandi sistemi aventi memoria insufficiente per memorizzare l'intero albero di ricerca. Ad esempio, è usata in vari sistemi di traduzione automatica. 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. Per ogni parola viene dunque salvata una porzione limitata delle traduzioni disponibili, in modo da risparmiare spazio, e viene scartato il resto.

## Varianti

La beam search può essere resa completa combinandola con la ricerca in profondità. Fra le varianti di questo tipo, troviamo la beam stack search e depth-first beam search.

Nel contesto di una ricerca locale, la local beam search è un particolare algoritmo che inizia selezionando $\beta$ stati generati casualmente e poi, per ogni livello dell'albero di ricerca, considera sempre $\beta$ nuovi stati fra i possibili successori di quelli correnti, fino a quando l'obiettivo non viene raggiunto.

Dato che la local beam search è solita terminare su massimi locali (soluzioni sotto-ottimali), una soluzione adottata solitamente è quella di scegliere i nuovi $\beta$ stati in maniera casuale, con una probabilità dipendente dalla valutazione euristica di ciascuno stato. Questo tipo di ricerca è nota come stochastic beam search.

Altre varianti sono flexible beam search e recovery beam search.

