Beam Search

L'algoritmo beam search è una tipologia di ricerca locale basata sull'esecuzione parallela e contemporanea della ricerca a partire da n nodi iniziali differenti. L'algoritmo seleziona i migliori successori degli n nodi e prosegue la ricerca locale seguendo il medesimo principio di funzionamento dell'algoritmo hill climbing. L'algoritmo beam Search consente di abbandonare progressivamente i nodi meno promettenti per concentrare gli sforzi nelle vicinanze dei nodi più promettenti.

La ricerca beam search non deve essere confusa con l'algoritmo di ricerca hill climbing iterativo. Nel caso dell'algoritmo hill climbing iterativo ogni ricerca locale viene eseguita in modo sequenziale e in modo indipendente dalle altre. I risultati parziali di una ricerca non influenzano il funzionamento delle altre ricerche. Viceversa, nell'algoritmo beam search i risultati parziali di ogni ricerca locale sono condivisi. In tal modo l'algoritmo può decidere di sospendere una ricerca locale per concentrare le risorse sui nodi successori migliori dei nodi restanti.

Massimi locali. L'algoritmo di ricerca locale beam search seleziona le mosse migliori. Se da un lato questo rende più efficiente la ricerca rispetto a un algoritmo hill climbing iterativo, dall'altro l'algoritmo beam search si espone maggiormente al rischio di imbattersi in un massimo locale e di concentrare l'esplorazione in un'unica area dello spazio di ricerca. Per ridurre questi problemi si ricorre all'algoritmo beam search stocastico, una versione dell'algoritmo beam search in cui la selezione dei nodi successori non è basata sul criterio delle mosse migliori ma è generata in modo casuale tramite una funzione stocastica.