Ricerca locale CSP
La ricerca locale CSP è un algoritmo di ricerca locale applicato alla risoluzione dei problemi CSP. Un algoritmo di ricerca locale CSP analizza e modifica ogni singola variabile, in modo sequenziale, al fine di raggiungere l'obiettivo finale ( soluzione del problema ). L'algoritmo cambia il valore delle variabili, una alla volta, cercando di assegnare il valore migliore possibile dal punto di vista locale. Una volta trovato, l'algoritmo si sposta sulla variabile successiva e, via dicendo, fino al raggiungimento dell'obiettivo finale. Ad esempio, uno dei problemi giocattolo più utilizzato per verificare l'efficienza degli algoritmi è il problema delle 8 regine. Sulla scacchiera sono distribuite 8 regine in modo casuale. L'algoritmo deve spostare le regine fino a trovare una distribuzione tale che nessuna regine possa attaccare le altre. Per chi non conosce gli scacchi, la regina può muoversi in ogni direzione ( orizzontale, verticale, diagonale ) e senza alcun limite di caselle.
Tramite una semplice ricerca in profondità questo problema richiede migliaia di assegnazioni. Ogni regina ( variabile ) può essere collocata nelle 64 caselle della scacchiera. Essendo otto regine, le possibili combinazioni di valori tra le variabili sono pari a 178mila miliardi:
64x63x62x61x60x59x58x57= 178.462.987.637.760 combinazioni
Il problema delle otto regine può essere affrontato in ottica CSP. Invece di analizzare tutte le possibili assegnazioni delle variabili ( 178mila miliardi ), è possibile iniziare l'analisi a partire da una situazione iniziale in cui le regine sono distribuite in modo casuale sulla scacchiera ( distribuzione iniziale casuale ). Salvo improbabili colpi di fortuna, la distribuzione iniziale sarà caratterizzata da diverse situazioni conflittuali che l'algoritmo di ricerca locale CSP cercherà progressivamente di rimuovere. L'algoritmo analizza i miglioramenti di ogni singola regina ( variabile ), da sinistra verso destra, spostandola verso una posizione migliore rispetto a quella corrente. Ad esempio, la prima regina si trova nella posizione di origine A1 in una situazione di conflitto con altre regine ( 3 conflitti ). L'algoritmo di ricerca locale CSP analizza tutte le altre posizioni sulla scacchiera che la regina in questione può raggiungere, spostandola nella posizione A4 dove minimizza i conflitti a zero ( euristica del minimo conflitto ).
Nel nostro esempio l'algoritmo di ricerca locale CSP con euristica del minimo conflitto riesce a trovare la soluzione al problema soltanto dopo 10 assegnazioni di valori. In conclusione, in alcuni problemi l'algoritmo di ricerca locale CSP consente di ottenere elevati livelli di efficienza, trovando la soluzione al problema in pochi passi a partire da una distribuzione casuale di valori.
Efficienza. Considerando anche le 8 operazioni di assegnazione iniziale per generare la distribuzione casuale delle regine, il numero delle assegnazioni è 18 ( 8 scelte casuali iniziali + 10 variazioni successive ).
Spostamenti minimi. L'algoritmo di ricerca locale consente di migliorare la distribuzione degli elementi a partire da una determinata distribuzione iniziale, facendo evolvere la situazione iniziale verso quella finale-ottimale. Ciò consente di ridurre al minimo gli spostamenti degli elementi rispetto alla loro posizione di origine. Mentre un algoritmo di ricerca verticale individua un'allocazione finale degli elementi completamente diversa da quella di origine, in un algoritmo di ricerca CSP, invece, le differenze tra l'allocazione finale e quella iniziale sono inferiori. Questa caratteristica è particolarmente importante nei problemi di ottimizzazione online. Ad esempio, la ricerca locale CSP può essere utilizzata per migliorare la disposizione delle merci in un magazzino, le operazioni di logistica, il flusso dati, il traffico aereo, ecc. a partire da una determinata distribuzione corrente iniziale delle stesse. In questi casi, la distribuzione iniziale non è più casuale bensì reale. Per passare dalla distribuzione iniziale inefficiente a quella finale efficiente potrebbero essere necessarie soltanto poche variazioni.
Scelte alternative. Nella ricerca locale CSP può capitare di dover scegliere tra percorsi alternativi a parità di conflitto ( plateau ). Ad esempio, nel seguente caso l'algoritmo si trova a scegliere tra due caselle alternative da una situazione conflittuale ( A4 ). A partire dalla casella A4 ( blu ), sia la casella A6 ( verde ) che la casella A2 ( verde ) consentono di migliorare la posizione della regina e di ridurre il numero dei conflitti da due a zero. Quale casella scegliere?
In questi casi la decisione può essere inizialmente casuale. In un secondo ciclo, qualora la soluzione non sia stata trovata, l'algoritmo può scegliere la strada alternativa. Per gestire i plateau possono essere utilizzate le stesse tecniche utilizzate nella ricerca locale ( es. simulated annealing ). È opportuno mantenere in memoria le scelte già effettuate, al fine di evitare di incappare in un ciclo infinito ( loop ) della ricerca sulle stesse scelte.
