Beam search stocastico

L'algoritmo beam search stocastico è una versione dell'algoritmo di ricerca locale beam search. Nell'algoritmo beam search tradizionale sono selezionati come nodi successori le mosse migliori, mentre nell'algoritmo beam search stocastico la selezione dei nodi successori è determinata da una funzione stocastica. In altri termini, nell'algoritmo beam search stocastico possono essere analizzate anche le scelte second best. Pur essendo casuale la selezione dei nodi successori è comunque ponderata in base al loro grado di miglioramento. Alle scelte migliori viene associata una probabilità superiore rispetto a quelle peggiori, seguendo la stessa logica già vista nell'algoritmo hill climbing stocastico.

L'algoritmo beam search stocastico riduce il rischio di imbattersi in un punto di massimo locale e agevola l'esplorazione dei cammini secondari nello spazio di ricerca. Pur partendo dagli stessi nodi iniziali l'algoritmo si basa su una distribuzione probabilistica che delinea nello spazio di ricerca un cammino differente e conduce a un risultato diverso per ogni elaborazione, migliorando così la completezza della ricerca. Viceversa, in un algoritmo beam search tradizionale il cammino verso le soluzioni migliori è predeterminato. A partire dagli stessi nodi iniziali l'algoritmo segue il medesimo cammino verso la risposta finale.

BEAM SEARCH STOCASTICO

Completezza. Le caratteristiche dell'algoritmo beam search stocastico consentono di eseguire più volte l'algoritmo al fine di selezionare il risultato finale migliore. Questa logica di ricerca è utilizzata nell'algoritmo beam search stocastico iterativo. L'iterazione dell'algoritmo riduce fortemente l'efficienza dell'algoritmo di ricerca ma permette di migliorare ulteriormente la completezza della ricerca beam search stocastica. L'algoritmo beam search stocastico-iterativo è particolarmente utile quando i risultati devono essere registrati in un database di conoscenza e quando non esiste un limite massimo al tempo di risposta dell'algoritmo.

https://www.okpedia.it/beam_search_stocastico


Segnala un errore o invia un suggerimento per migliorare la pagina


Ricerca soluzioni

Problemi


FacebookTwitterLinkedinLinkedin