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.[1] Di conseguenza, è considerato un algoritmo greedy.
Il nome "beam search" venne introdotto da Raj Reddy dell'Università Carnegie Mellon, nel 1977.[2]
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.[3] Tuttavia, a differenza della best-first search, salva solo fino un numero predefinito, , di stati "migliori" per ogni livello. Questo numero è chiamato "beam width" (lett. "ampiezza del fascio"). Più grande è l'ampiezza predefinita, minore sarà il numero di stati esclusi dalla ricerca. Logicamente, per 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 può anche essere resa variabile. Un possibile approccio con ampiezza variabile prevede di eseguire inizialmente l'algoritmo con impostato al valore minimo e, se nessuna soluzione viene trovata, di aumentarne il valore ad ogni nuova esecuzione.[4]
Utilizzi
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.
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[8] e depth-first beam search[5].
Nel contesto di una ricerca locale, la local beam search è un particolare algoritmo che inizia selezionando stati generati casualmente e poi, per ogni livello dell'albero di ricerca, considera sempre 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 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]
Note
- ↑ Template:Cita web
- ↑ Template:Cita pubblicazione
- ↑ Template:Cita web
- ↑ Template:Cita libro
- ↑ 5,0 5,1 Template:Cita pubblicazione
- ↑ Template:Cita pubblicazione
- ↑ Nella versione più semplice, tale contesto è costituito dalle parole già tradotte all'interno della stessa frase all'interno del ramo corrente dell'albero di ricerca.
- ↑ Template:Cita pubblicazione
- ↑ Template:Cita web
- ↑ 10,0 10,1 Template:Cita web
- ↑ Template:Cita web