Ricerca locale

La ricerca locale è un algoritmo di ricerca informata in grado di risolvere un problema elaborando soltanto in un sottoinsieme dello spazio di ricerca. A partire da un nodo corrente l'algoritmo di ricerca locale individua la soluzione al problema analizzando soltanto i nodi adiacenti a quello corrente. La ricerca locale appartiene alla categoria degli algoritmi metaeuristici. A differenza degli algoritmi di ricerca tradizionali, l'algoritmo di ricerca locale non analizza i cammini multipli nello spazio di ricerca ma soltanto quelli locali a partire da un determinato nodo ( nodo corrente ). Grazie a questa caratteristica gli algoritmi di ricerca locale utilizzano una quantità di memoria limitata ( bassa complessità spaziale ) e si prestano ad essere utilizzati, in particolar modo, negli spazi di ricerca molto vasti e in quelli a rete.

La ricerca locale si basa sul presupposto che il miglioramento di una soluzione si trovi nelle immediate vicinanze di quest'ultima ( vicinato ). Data una qualsiasi soluzione euristica ( nodo corrente ) la ricerca locale verifica l'esistenza di soluzioni migliori nell'insieme delle soluzioni più vicine ( nodi vicini ). Ad esempio, un algoritmo di ricerca locale può essere utilizzato per risolvere il problema del commesso viaggiatore. Le tecniche di ricerca locale consentono di raggiungere risultati sia nella ricerca delle soluzioni a un problema ( problem solving ) e sia nell'ottimizzazione Appartengono alla categoria degli algoritmi di ricerca locale i seguenti algoritmi.

• Ricerca hill climbing. L'algoritmo di ricerca hill climbing è una tecnica di ricerca locale in cui il nodo corrente è sostituito con il nodo migliore.
• Simulated annealing. L'algoritmo di Simulated annealing o Annealing simulato (SA) è un algoritmo probabilistico-metaeuristico di ottimizzazione della ricerca in uno spazio di ricerca di grandi dimensioni. Il suo nome prende spunto dal processo metallurgico che consente di riaggregare la materia fusa dei metalli in base a determinate caratteristiche comuni. Nell'algoritmo di simulated annealing un processo di selezione consente l'eventuale sostituzione della soluzione del nodo corrente con quella di un nodo selezionato casualmente da una lista di soluzioni candidate.
• Beam Search. La beam search è una ricerca locale basata su tecniche euristiche. La beam search ( ricerca di fascio ) esplora un fascio limitato di nodi promettenti ( soluzioni parziali ) dello spazio di ricerca e li analizza con una ricerca locale. Utilizzando le tecniche euristiche l'algoritmo beam search consente di riconoscere quando una soluzione parziale è anche una soluzione completa.

Le tecniche di ricerca locale possono incappare in situazioni di massimo o di minimo locale che impediscono l'individuazione delle soluzioni ottimali. Questo rischio può, in ogni caso, essere ridotto perfezionando le tecniche euristiche di ricerca e di localizzazione dei nodi da analizzare ( soluzioni candidate ) con la ricerca locale.

Ricerca negli spazi di ricerca infiniti. Gli algoritmi di ricerca locale sono particolarmente vantaggiosi quando lo spazio di ricerca è molto grande o è infinito. In tali casi un algoritmo di ricerca tradizionale avrebbe una complessità enorme e non potrebbe comunque soddisfare il requisito della completezza.

Spazio di memoria ridotto. Gli algoritmi di ricerca locale utilizzano una quantità di memoria limitata in quanto elaborano soltanto uno spazio di ricerca ridotto a partire da un nodo corrente.

Ricerca locale CSP. La ricerca locale è applicata con discreto successo nella risoluzione dei problemi CSP. Ad esempio, la ricerca locale CSP consente di risolvere il problema delle otto regine in pochi passi a partire da una distribuzione casuale iniziale dei valori alle variabili ( assegnazione casuale ).