Beam search stocastico iterativo
L'algoritmo beam search stocastico iterativo è una versione dell'algoritmo di ricerca locale beam search stocastico. La versione iterativa consiste nel riavviare più volte l'esecuzione dell'algoritmo beam search stocastico per analizzare cammini differenti a partire dagli stessi nodi iniziali o per analizzare nuovi cammini a partire da nodi differenti. In ogni iterazione l'algoritmo mantiene in memoria i risultati migliori in modo da restituirli in output al termine dell'ultima iterazione. Anche l'algoritmo beam search stocastico iterativo si basa su una funzione stocastica per determinare la selezione dei nodi successori tra quelli disponibili. A ogni iterazione avrà luogo, pertanto, una combinazione di cammini differenti che potrebbero portare a risultati migliori o, in ogni caso, differenti dalle precedenti iterazioni.
Completezza. L'iterazione consente di esplorare cammini secondari, diversi a ogni iterazione, e raggiungere un livello di completezza superiore. D'altra parte, l'iterazione riduce fortemente l'efficienza dell'algoritmo di ricerca beam search stocastico, allungandone i tempi di elaborazione e la complessità sia temporale che spaziale.
Complessità spaziale. L'algoritmo potrebbe ripercorrere le stesse scelte già analizzate in precedenti iterazioni. Per evitare di elaborare gli stessi cammini l'algoritmo dovrebbe mantenere in memoria i nodi e i percorsi già analizzati in precedenza. Tuttavia, ciò renderebbe proibitiva la complessità spaziale dell'algoritmo Potrebbe, infatti, richiedere una enorme capacità di memoria per registrare i dati.
Complessità temporale. La complessità temporale è ovvia. Ogni iterazione implica un incremento del tempo di elaborazione. Quanto maggiore è il numero delle iterazioni dell'algoritmo, tanto maggiore è il tempo necessario per giungere alla soluzione finale. Il numero delle iterazione è, comunque, impostabile in fase di progettazione a seconda delle esigenze. L'algoritmo beam search stocastico-iterativo non è efficace nei casi in cui sia necessario fornire una risposta in tempi rapidi.
