• Ricerca in profondità (Depth-First search)
• Ricerca in ampiezza (Breadth-First search)
• Ricerca per allargamento iterativo (Iterative broadening)

L'idea di base dei tre algoritmi è la stessa, con sostanziali differenze nella modalità di conduzione della ricerca. La ricerca in profondità esamina percorsi via via sempre più profondi nello spazio problemico per poi far uso di backtracking e memorizzazione di path per risalire da un nodo ritenuto cieco. Ciò comporta una buona velocità di esecuzione nel caso di problemi piccoli o con molti casi da esaminare raggruppati però con pochi e sostanziali vincoli. Tra gli svantaggi la propensione al loop nel caso in cui il grafo dei problemi non sia aciclico, con conseguente inefficienza e temporale e funzionale. Di intenzioni opposte è la ricerca in ampiezza: come si evince dal nome, infatti, esamina i casi per livello, completando con successo e sempre l'analisi di tutto lo spazio delle soluzioni (se richiesto) per ritrovare il caso ottimo. Non necessita di backtracking e può più agevolmente essere codificata come procedura iterativa anzichè ricorsiva (sebbene in alcuni testi si faccia menzione di un aumento a volte inutile dell'occupazione in memoria dell'algoritmo dovuta alla metodologia di ricerca stessa). Per contro, la velocità soffre della caratteristica dell'algoritmo di esaminare casi tra loro "distanti" nel campo delle soluzioni e quindi non confrontabili per condizionare l'analisi dei casi successivi (questo ultimo dato sancisce una vocazione più spiccatamente brute-force della DFS rispetto alla BFS, che, a volte, viene usata come base anche per procedure di natura euristica). Infine, la ricerca per allargamento iterativo fonde alcuni dei principi ispiratori delle tecniche precedenti per garantire la sicurezza di esecuzione della BFS, usata per generare un sottospazio di casi da esaminare in ampiezza, con un aumento di velocità dovuto all'uso della DFS limitata come algoritmo usato nei passi intermedi.

Ricapitolando, per presentare la pseudocodifica dei suddetti algoritmi assumiamo che:

• La ricerca sia eseguita in un albero
• Tutti in nodi non foglia abbiano un fattore di ramificazione uniforme b
• La profondità dell'albero sia d
• Il singolo nodo obiettivo sia alla profondità d

Ricerca in profondità

• Usa la procedura generalizzata di ricerca su grafi
• Tratta l'insieme L dei nodi non espansi come una pila LIFO
• I nodi appena generati sono piazzati in testa alla pila
• I nodi sono estratti per espansione dalla testa
• Richieste di memoria
• Ad ogni punto di scelta i b-1 antenati devono essere già memorizzati
• Alla profondità d solo 1 nodo viene esaminato per passo
• Lo spazio totale è d(b-1) + 1
• Comportamento temporale
• Se il nodo obiettivo è in un ramo esterno sulla sinistra dell'albero (caso migliore) il tempo richiesto è d+1
• Se il nodo obiettivo è in un ramo esterno sulla destra dell'albero (caso peggiore) il tempo richiesto è (b^d+1-1) / (b-1)
• Caso medio per d grande: t b^d / 2

Ricerca in ampiezza

• Usa la procedura generalizzata di ricerca su grafi
• Tratta l'insieme L dei nodi non espansi come una coda FIFO
• I nodi appena generati sono posti in fondo alla coda
• I nodi sono ricavati per espansione dalla testa della FIFO
• Un nodo può essere estratti per espansione solo dopo che tutti i nodi di profondità inferiore sono stati estratti
• Richieste di memoria
• Il numero totale dei nodi alla profondità k è b^k
• Tutti i nodi di profondità k devono essere memorizzati prima che i nodi di profondità k+1 possano essere esaminati
• Un ammontare minimo di spazio peri a b^d-1 deve essere allocato prima che l'obiettivo possa essere riscontrato alla profondità d
• Se il nodo obiettivo non è il primo nodo della coda a profondità d, allora l'espansione dei nodi di pari profondità deve comunque essere memorizzata finché non venga ritrovato l'obiettivo
• Comportamento temporale
• Assumiamo tempo costante per l'analisi di ogni nodo
• Tempo impiegato = n.° di nodi esaminati prima di incontrare l'obiettivo * tempo di analisi unitario
• Tutti i nodi di profondità d-1 devono essere esaminati prima di scendere al livello soluzione d
• Nodi interni: 1 + b + b² + . + b^d-1 = (b^d-1) / (b-1)
• Minimo numero di foglie : 1
• Max numero di foglie : b^d
• Numero medio di foglie da esaminare: (b^d+1)/2
• Numero medio totale di nodi da esaminare: t = (b^d-1) / (b-1) + (b^d+1)/2
• Per d grande: t b^d / 2

Ricerca per allargamento iterativo

• Migliora le condizioni del caso medio della ricerca DFS, BFS e Iterative Deepening (approfondimento iterativo)
• Nei casi reali i nodi obiettivo non sono distribuiti in modo casuale nell'albero ma tendono a raggrupparsi in base a 515g68f lla semantica del problema che l'albero di ricerca stesso sta rappresentando
• Un errore iniziale nella scelta può portare in una porzione dell'albero che non contiene alcun nodo obiettivo
• L'allargamento iterativo esamina per errori successivi per trovare un obiettivo ad un livello di profondità sufficientemente alto come supposizione che, ispezionando nel sottoalbero radicato nel nodo in oggetto, si possano riscontrare altre soluzioni ottime al problema.
• Algoritmo
• Imposta il taglio in ampiezza a c=2
• L'insieme L è l'insieme dei nodi iniziali del problema
• Se L è vuoto allora incrementa il taglio in ampiezza c e ritorna al passo 2
• Rimuovi il primo nodo dal L e etichettalo come n
• Se n è un obiettivo, allora restituiscilo come risultato assieme al percorso per raggiungerlo
• Se n non è un obiettivo allora aggiungi in testa ad L i primi c figli di n con i path ad essi associati. Vai al passo 3
• Un taglio in ampiezza di valore c indica che ad ogni passo al più c figli di un nodo verranno esaminati prima che quel ramo venga abbandonato
• Comportamento temporale
• Al più vengono effettuate b ricerche
• Ogni ricerca con taglio c prende tempo o(c^d)
• Se c < b allora o(c^d) è minore di b^d
• Il tempo massimo è 1 + 2^d + .+ b^d (b^d+1) / d per valori di b sufficientemente grandi.
• Il fattore di speed up di DFS rispetto all'iterative broadening è di b/d, ma nel caso in cui gli obiettivi siano in numero > 3, questo algoritmo si rivela più efficiente.

Di seguito sono presentate due implementazioni in linguaggio C ed operanti su grafi dei due algoritmi DFS e BFS. Sia BFS che DFS e Iterative broadening sono facilmente scalabili su sistemi paralleli e multiprocessore. Nel caso di BFS,infatti la trasposizione su sistemi paralleli diviene immediata associando ad ogni processore un ramo partente dalla radice, eventualmente sfruttando le CPU a cui sono stati associati sottoalberi più piccoli rischedulando periodicamente le assegnazioni. Per la DFS e l'Iterative broadening il discorso è leggermente più complesso, vista l'impossibilità di assegnazione diretta di una fetta di problema ad ogni unità computazionale. Sfruttando, però, opportunamente le interconnessioni presenti nel network parallelo, è possibile associare al pool di processori interi livelli di profondità, eventualmente partizionati, incrementando se necessario il numero di nodi associati all'aumentare del livello di esame dell'albero.

Ricerca in profondità - Implementazione in C

(l'implementazione manca della funzione di test di ottimalità dei nodi in esame)

Ricerca in ampiezza - Implementazione in C

(l'implementazione manca della funzione di test di ottimalità dei nodi in esame)

Esempio - Il problema dei missionari e dei cannibali

Il problema dei tre missionari e dei tre cannibali consiste nel determinare come essi possano tutti e sei trasferirsi da un lato all'altro di un fiume utilizzando una barca che può portare al massimo due persone evitando che i cannibali mangino i missionari. I cannibali mangiano i missionari ogni volta che li superano in numero.

Si supponga, per semplicità, che non si possa riproporre durante la ricerca uno spazio già presente nell'albero ad un livello precedente (tali stati quindi non devono essere descritti nell'albero di ricerca).

SOLUZIONE

Nel risolvere questo problema come ricerca nello spazio degli stati, è necessario porre attenzione alla descrizione di stato che deve essere completa, ossia deve descrivere tutta l'informazione che caratterizza un nodo.

Descrizione stato:

Sx: Numero Missionari e Cannibali sulla riva Sx

Dx: Numero Missionari e Cannibali sulla riva Dx

Barca: Posizione barca.

Gli stati di fallimento (numero di cannibali maggiore a quello dei missionari su una sponda) non sono stati rappresentati. Potevamo rappresentarli ed etichettarli con fail. Nell'immagine seguente, l'albero di ricerca in profondità generato dall'algoritmo.

Esempio - Il problema dei mucchietti delle monete (fiammiferi)

Si supponga di avere 12 monete ripartite in tre distinte pile. La prima pila è formata da 4 monete, la seconda da 7 e la terza da 1. Lo spostamento delle monete deve avvenire secondo la seguente regola: ogni volta che si spostano delle monete da una pila A ad un'altra B, le monete in B devono raddoppiare di numero. Viene mostrato lo spazio di ricerca con stato iniziale rappresentato dalla tripla <4,7,1> e stato finale dalla tripla <4,4,4> generato in due spostamenti ed esplorato con strategia in ampiezza e profondità.

Il depth first (numeri in parentesi tonda) va in loop supponendo di avere un criterio preferenziale che seleziona le mosse come in figura <4,7,1>, <3,7,2>, <1,7,4>, <3,7,2>..... Se invece si suppone di fermarsi a due livelli di esplorazione (senza generare ed esplorare i livelli sottostanti), il depth first trova una soluzione in 9 passi. In breadth first (numeri in parentesi quadra) trova la soluzione in 10 passi.

Esempio - Capra e cavoli

Un contadino doveva trasportare al di là di un fiume il suo lupo, la sua capra e una cesta di cavoli, avendo a disposizione una barca poco capiente che avrebbe potuto trasportare solo lui in compagnia di una delle due bestie o lui insieme alla sola cesta di cavoli. Ma se avesse lasciato su una delle due rive del fiume il lupo insieme alla capra, questi l'avrebbe uccisa per mangiarsela; allo stesso modo non avrebbe potuto lasciare insieme capra e cavoli perché la bestia li avrebbe sicuramente mangiati. La sua presenza era importante perché il lupo non nuocesse alla capra e la capra non toccasse i cavoli.

Come fece ad attraversare il fiume con lupo, capra e cavoli?

% Source code for Farmer, Wolf, Goat and Cabbage

% Test this with: go(state(east,east,east,east),state(west,west,west,west)).

% Output with `writef', available in SWI-Prolog, possibly not in others

DOMAINS
LOC = east ; west
STATE = state(LOC farmer,LOC wolf,LOC goat,LOC cabbage)
PATH = STATE*

PREDICATES
go(STATE,STATE) % Start of the algorithm
path(STATE,STATE,PATH,PATH) % Finds a path from one state to another
nondeterm move(STATE,STATE) % Transfer a system from one side to another
opposite(LOC,LOC) % Gives a location on the opposite side
nondeterm unsafe(STATE) % Gives the unsafe states
nondeterm member(STATE,PATH) % Checks if the state is already visited
write_path PATH)
write_move STATE,STATE)

GOAL
go(state(east,east,east,east),state(west,west,west,west)),
write("solved").

CLAUSES

go(StartState,GoalState
path(StartState,GoalState,[StartState],Path),
write('A solution (backward) is:\n'),
write_path Path).

path(StartState,GoalState,VisitedPath,Path
move(StartState,NextState), % Find a move
not( unsafe(NextState) ), % Check that it is not unsage
not( member(NextState,VisitedPath) ), % Check that we have not had this
% situation before
path( NextState,GoalState,[NextState|VisitedPath],Path),!.
path(GoalState,GoalState,Path,Path % The final state is reached

move(state(X,X,G,C),state(Y,Y,G,C)):-opposite(X,Y). % Move FARMER + WOLF
move(state(X,W,X,C),state(Y,W,Y,C)):-opposite(X,Y). % Move FARMER + GOAT
move(state(X,W,G,X),state(Y,W,G,Y)):-opposite(X,Y). % Move FARMER + CABBAGE
move(state(X,W,G,C),state(Y,W,G,C)):-opposite(X,Y). % Move ONLY FARMER

opposite(east,west
opposite(west,east

unsafe( state(F,X,X,_) ):- opposite(F,X),!. % The wolf eats the goat
unsafe( state(F,_,X,X) ):- opposite(F,X),!. % The goat eats the cabbage

% member(X,[X|_]):-!. % already available
% member(X,[_|L]):-member(X,L). % in the interpreter

write_path [H1,H2|T] ) :-
write_move H1,H2),
write_path [H2|T]).
write_path

write_move( state(X,W,G,C), state(Y,W,G,C) ) :-!,
writef 'The farmer crosses the river from %w to %w',[X,Y]),nl.
write_move( state(X,X,G,C), state(Y,Y,G,C) ) :-!,
writef 'The farmer takes the Wolf from %w of the river to %w',[X,Y]),nl.
write_move( state(X,W,X,C), state(Y,W,Y,C) ) :-!,
writef 'The farmer takes the Goat from %w of the river to %w',[X,Y]),nl.
write_move( state(X,W,G,X), state(Y,W,G,Y) ) :-!,
writef 'The farmer takes the cabbage from %w of the river to %w',[X,Y]),nl.

RICERCA EURISTICA

Le procedure di ricerca Euristica sono delle tecniche di ricerca che, nella risoluzione di un problema non considerano tutti i possibili cammini dello spazio del problema, ma realizzano una selezione dei cammini, scegliendo di volta in volta quelli che risultano più promettenti.

Queste procedure si applicano dove il problema prevede uno spazio di stati molto ampio, tale da renderne impossibile la ricerca attraverso procedure esaustive.

Il criterio secondo il quale vengono selezionati i cammini è sempre basato su conoscenze di natura generale del problema, i vari criteri possibili prendono il nome di euristiche. E' necessario però specificare che le euristiche non sono né complete, né corrette, tuttavia ci danno risultati migliori rispetto ad operare con una ricerca cieca.

I principali vantaggi sono:

Riduzione drastica del numero di cammini considerati: ci sarà la possibilità di ignorare dei cammini, che secondo la nostra valutazione euristica, non portano alla soluzione;

miglioramento della qualità media di ogni cammino esplorato;

possibilità di ottenere una migliore comprensione del problema: il fallimento di una euristica ci fornisce indicazioni sulla natura del problema, studiando il motivo per cui l'euristica fallisce.

La mancanza di completezza e correttezza della ricerca euristica rappresentano le principali limitazioni di tale tecnica. Infatti rinunciando alla  completezza, rinunciamo alla possibilità di avere una soluzione "ottima" accontentandoci di una soluzione "buona". Per quanto riguarda la correttezza invece, ci sono problemi per cui è possibile stabilire un limite superiore sull'errore; in questo caso possiamo sapere quanto perdiamo in accuratezza in cambio di efficienza, tuttavia questo limite non è individuabile per tutte le euristiche in quanto per problemi reali è difficile misurare la bontà di una soluzione.

La conoscenza euristica può essere specificata nel problema in due modi

nelle regole Le regole non descriveranno solo le possibili mosse, ma anche le mosse "sensate".

con la funzione euristica La f.e. è una funzione che valuta gli stati del problema e determina quanto siano buoni per giungere alla soluzione.

Mentre non è sempre possibili inserire l'euristica nelle regole possiamo sempre trovare una funzione euristica, e di questo ci occuperemo nei prossimi paragrafi.

Le Funzioni Euristiche

Tali funzioni, assegneranno ad ogni stato del problema una misura di desiderabilità. Per tanto i programmi useranno metodi per massimizzare o minimizzare il valore di queste funzioni in modo da guidare la ricerca nella direzione più vantaggiosa diminuendo il numero di passi da effettuare, e nel caso limite trovando la soluzione senza effettuare ricerca. E' ovvio che più accurato sarà il calcolo della funzione tanto più sarà oneroso. E' necessario quindi trovare un compromesso per non far in modo che il costo del calcolo sia maggiore del risparmio nel processo di ricerca.

A questo punto è chiaro quanto sia cruciale la scelta dell'euristica. Tale scelta sarà realizzata attraverso uno studio accurato del problema, quindi è opportuna una classificazione. I problemi di solito vengono classificati secondo delle caratteristiche.

a) Annullamento dei passi distinguiamo tra problemi in cui si possono ignorare i passi già fatti in quanto non hanno portato a miglioramenti e problemi in cui ciò non è possibile.

b) Pianificazione: distinguiamo tra problemi in cui è possibile pianificare una sequenza di mosse e sapere dove si arriva, e problemi dove ciò non si può fare. Questo capita perché ad esempio non si ha conoscenza dell'ambiente;

c) Soluzione Assoluta o Relativa I problemi sono classificabili anche in base al tipo di soluzione; in problemi con un'unica soluzione non è importante come ci si arriva, mentre quando ci sono più soluzioni potremmo trovare una soluzione non ottimale.

d) Soluzione Stato o Cammino Abbiamo ancora una classificazione in base al tipo di soluzione, distinguiamo se la soluzione è uno stato (ad esempio in un problema di classificazione) oppure un cammino (ad esempio il gioco dell'8).

Nei prossimi paragrafi verranno presentati dei metodi di ricerca euristica.

Hill Climbing

L'algoritmo di Hill Climbing è una procedura euristica tra le più semplici e le più utilizzate per risolvere i problemi.

Il nome della procedura deriva dal fatto che essa opera come uno scalatore (e ne incontra gli stessi problemi), il quale per raggiungere la vetta, di fronte ad una scelta opta per quella che lo porta verso l'alto.

Così la procedura partendo dalla radice dell'albero fa espandere il figlio per cui il valore della funzione euristica si avvicina di più a quello finale.

Possiamo schematizzare l'algoritmo come segue

Considera la radice come nodo corrente.

SE il nodo corrente è un nodo finale allora hai RISOLTO il problema

Se il nodo corrente non ha figli allora la procedura ha FALLITO

Espandi il nodo corrente e calcola la funzione euristica per i figli

Scegli tra i figli quello che ha il miglior valore di funzione euristica

se tale nodo ha un valore euristico peggiore del corrente allora la procedura ha FALLITO

Considera nodo corrente il nuovo nodo. Ritorna al passo 2

In pratica lo HC risulta essere essenzialmente una ricerca in profondità nella quale non viene espanso il nodo più recente, ma il più promettente relativamente all'euristica adottata.

La procedura di HC tuttavia viene meno in presenza di situazioni denominate

a)   altipiani

b)   vette secondarie

c)   creste

In pratica, un'implementazione pura dell'HC determina una strategia di ricerca irrevocabile, senza la possibilità di back-tracking, quindi non mantiene tracce delle opzioni scartate. Quindi non si accorge quando entra il loop. I loop sono possibili nel caso in cui ci sia una serie di nodi con la stessa funzione euristica, questa situazione viene chiamata altipiano. Un altro problema insidioso è quello delle vette secondarie, che si presenta quando la funzione trova un massimo (ovvero minimo) relativo, quindi termina risolvendo il problema, ma non trovando una soluzione ottima. In fine abbiamo il problema delle creste, che si verifica quando in tutte le direzioni possibili troviamo nodi con funzione euristica peggiore del nodo corrente, facendo così fallire la ricerca.

Best First

Nella procedura di Hill Climbing, se ci sono vette secondarie, altipiani o creste la ricerca non può procedere. Per risolvere questi problemi è stata trovata un'altra euristica che ha un approccio globale al problema. La ricerca Best First prende in considerazione tutti i nodi che sono stati esaminati fino a quel momento ed espande il nodo che valutato con la funzione euristica migliore da risultati migliori.

L'algoritmo può essere schematizzato in 4 passi

Sia L la lista dei nodi iniziali del problema, ordinati secondo la distanza dal goal.

Sia n il primo nodo di L. Se L è vuota la procedura fallisce

Se n è il goal fermati e restituisci la strada percorsa per raggiungerlo.

Altrimenti rimuovi n da L e aggiungi a L tutti i nodi figli di n; riordina la lista L in base alla distanza relativa dal goal, e ritorna al passo 2.

La funzione euristica utilizzata è

f(n)=g(n)+h'(n)

dove g(n) è la profondità del nodo e h'(n) è la distanza dal goal.

Espandendo i nodi per cui f(n) è più piccola troviamo una via di mezzo tra i vantaggi dell'Hill Climbing cioè l'efficienza e quelli della ricerca a costo uniforme (ottimalità e completezza). Cioè consideriamo oltre la distanza dal goal anche il costo per raggiungerlo. In generale però questo tipo di ricerca non è ottimale.

Un problema della BF è la complessità spaziale, infatti in memoria deve essere conservata tutta la frontiera, problema che può essere risolto aggiungendo un'ulteriore fattore eurisitico e cioè mantenendo in memoria ad ogni passo solo i primi k nodi più promettenti

Applicazioni

La BF può risolvere problemi non banali del tipo "Missionari e Cannibali": 3 missionari e 3 cannibali devono attraversare un fiume. I missionari per non essere mangiati non devono essere mai meno dei cannibali che sono sulla tessa loro sponda , e c'è una sola barca che contiene al massimo due persone. In questo caso si considera come costo del cammino il numero di traversate, e come distanza dal goal il numero di persone rimaste sulla prima sponda.

Algoritmo A

Un Algoritmo A è un algoritmo Best First con una funzione di valutazione euristica del tipo

F(n)=g(n)+h(n)   con h(n) >=0 per ogni n e h(goal)=0

Dove g(n) è il costo del cammino per raggiungere il nodo n, e h(n) è una stima del costo per raggiungere un nodo goal.

Vediamo dei casi particolari di algoritmi di tipo A

h(n)=0 abbiamo una ricerca Uniforme

h(n)=0; g(n)=depth(n) abbiamo una ricerca in ampiezza.

g(n)=0; abbiamo una ricerca Greedy

In particolare è possibile dimostrare utilizzando funzioni euristiche con g(n) > depth(n) l'algoritmo A fornisce soluzione ottima.

Algoritmo A* ed euristiche Ammissibili  

Un algoritmo A* è un algoritmo A che una funzione euristica ammissibile monotona.

Una funzione Euristica ammissibile è una funzione del tipo

F(n) = g(n) + h (n)

Dove h(n) è una sottostima del cammino minimo tra n ed il goal e g(n) è il cammino percorso dalla radice al nodo n.

Un buona classe di funzioni ammissibili sono le funzioni che godono di monotonia su h

h(n) - h(n') <= g(n') - g(n) = costo_arco(n,n')

Le euristiche monotone garantiscono un'ottimalità locale e cioè che quando un nodo viene scelto

Conclusioni

Concludendo possiamo dire che le procedure euristiche non sono la panacea dei metodi di ricerca, ma possono velocizzare molto il lavoro, sono quindi utili in problemi in cui ci serve una soluzione velocemente ed in problemi in cui la complessità per avere la soluzione ottima è esponenziale (come ad esempio il problema del commesso viaggiatore).

3.3 CONSTRAINT SATISFACTION PROBLEMS

Per molti anni i Constraint Satisfaction Problems (CSP) sono stati un oggetto di studio nel campo dell'Intelligenza Artificiale, la cui ricerca era concentrata sui problemi combinatoriali. Il contributo dato da AI è stato considerevole, infatti, molti algoritmi sono diventati una base per risolvere i problemi CSP.

Un Constraint Satisfaction Problems (CSP) è così definito:

Un insieme di variabili X=.

Ogni variabile x_i, appartiene ad un finito insieme D_i (dominio).

Un insieme di vincoli (constraints) restringe i valori che le variabili possono assumere.

Una soluzione di un CSP è un assegnamento di valori alle variabili, in modo che ogni vincolo sia soddisfatto. Le soluzioni di un CSP si possono trovare, ricercando sistematicamente attraverso i possibili assegnamenti alle variabili. I metodi di ricerca si dividono in due ampie classi:

Quelle che attraversano lo spazio delle parziali soluzioni

Quelli che esplorano completamente lo spazio dei valori assegnati stocasticamente, a tutte le variabili.

Le ragioni, che spiegano perché un problema viene rappresentato come un CSP sono:

La vicinanza al problema originale, infatti, le variabili corrispondono direttamente agli input del problema, e i vincoli possono essere espressi senza traduzione in disuguaglianze lineari. Questo crea una formulazione più semplice.

Gli algoritmi per risolvere i CSP non sono complicati, e le soluzioni si possono trovare in tempi apprezzabili.

Vincoli Binari

Un vincolo può influenzare un certo numero di variabili. Bisogna distinguere, però, due casi: unario e binario. Per i vincoli unari si può eseguire un preprocessing del dominio, e possono essere ignorati. I vincoli binari possono essere rappresentati come un "grafo dei vincoli" (constraint network), in cui ogni nodo rappresenta una variabile, e ogni arco rappresenta un vincolo tra le due variabili (estremi dell'arco). Anche un vincolo unario, può essere rappresentato con un arco la cui origine e fine è nello stesso nodo.

Esempio: X # Y, Y # Z, X # Z

E' possibile convertire un CSP arbitrario, in un equivalente CSP binario mediante l'utilizzo di una nuova variabile che incapsula un insieme di variabili vincolate. Questa nuova variabile è chiamata incapsulata; ed il suo dominio è il prodotto cartesiano dei domini delle variabili individuali.

Esempio: Variabili individuali e i loro domini X::[1,2], Y::[3,4], Z::[5,6]

Variabile incapsulata e relativo dominio U::[(1,3,5), (1,3,6), (1,4,5), (1,4,6), (2,3,5), (2,3,6), (2,4,5), (2,4,6)]

Algoritmi di ricerca

Un CSP può essere risolto utilizzando le seguenti strategie:

Generate-and-test (GT)

Backtracking (BT)

Il metodo Generate-and-test ha origine dall'approccio matematico per la risoluzione di problemi combinatori. Il metodo GT genera ogni possibile valore da assegnare alle variabili, e poi verifica se la soluzione soddisfa i vincoli originari. La soluzione è data dalla prima combinazione di valori che soddisfa tutti i vincoli.

Algoritmo GT:

gt(Variables,Constraints,Solution):-
generate(Variables,Solution
test(Constraints,Solution).

generate([V::D|RemainingVariables],[V-X|PartialSolution]):-
select_value(X,D),
generate(RemainingVariables,PartialSolution).
generate(

test([C|RemainingConstraints],Solution):-
test_constraint(C,Solution),
test(RemainingConstraints,Solution).
test(

I difetti del metodo GT sono legati, alla generazione di molti valori, rifiutati poi dal test, da assegnare alle variabili. Per ovviare a tale inconveniente, l'algoritmo GT si utilizza con un approccio di backtracking.

Il backtracking è il più comune algoritmo per effettuare una ricerca sistematica. Esso cerca di estendere, una parziale soluzione che specifica dei valori coerenti per qualche variabile, verso una completa soluzione. Infatti sceglie ripetutamente dei valori da assegnare alle altre variabili, rispettando sempre la coerenza con i valori della soluzione corrente. Nel metodo BT le variabili sono stanziate in sequenza, rilevando man mano la validità dei vincoli; se una parziale soluzione viola un vincolo, si esegue il backtracking, che riporta le variabili al precedente assegnamento, per il quale ci sono ancora delle scelte. I principali svantaggi di tale metodo sono:

Thrashing, in pratica ripetuti fallimenti dovuti alle stesse ragioni. Questo è causato perché lo standard backtracking non identifica la reale ragione di un conflitto. Tale inconveniente può essere evitato, utilizzando intelligent backtracking, che memorizza le variabili che portano a fallimenti.

Redundant work, in pratica se i valori delle variabili che portano ad un conflitto sono identificati durante intelligent backtracking, essi non sono poi ricordati, per lo stesso conflitto, nel calcolo successivo. Per risolvere quest'inconveniente si utilizza dependency-directed backtracking, che aggiunge ulteriori algoritmi che causano un certo carico computazionale, bilanciato, però, dal vantaggio del loro utilizzo.

Detects the conflict too late, è dovuto alla non abilità nell'individuare i conflitti prima che essi accadano. Anche quest'inconveniente può essere evitato utilizzando delle tecniche consistenti (forward check).

Tecniche consistenti

Queste tecniche, sono state introdotte per migliorare l'efficienza dei programmi di riconoscimento d'immagine (picture recognition), dai ricercatori d'Intelligenza Artificiale. Il riconoscimento d'immagine, comporta un etichettamento di tutte le linee in un'immagine in modo consistente, ed il numero di possibili combinazioni può essere enorme, però sono poche quelle consistenti. Bisogna notare che tali tecniche sono deterministiche. Nei CSP binari, vengono utilizzate varie tecniche consistenti per i grafi dei vincoli, riducendo così la ricerca.

Nodo Consistente: è la più semplice tecnica consistente, ed è riferita ai nodi del grafo. Un nodo che rappresenta una variabile X, è un nodo consistente, se per ogni valore del dominio di X, il vincolo unario su X è soddisfatto. Per esempio, se il dominio D di X contiene un valore "a", che non soddisfa il vincolo unario di X, l'assegnazione di "a" a X sarà sempre inconsistente, e così il nodo inconsistente può essere eliminato rimovendo il valore di "a" dal dominio D. 

Arco Consistente: l'arco (X, Y) è un arco consistente, se per ogni valore x, del dominio di X, c'è un valore y, nel dominio di Y tale che X=x e Y=y è permesso dal vincolo binario tra X e Y. Bisogna notare che il concetto di arco consistente, è direzionale; cioè se (X, Y) è consistente, non significa che anche (Y, X) sia consistente. L'utilizzo di queste tecniche consistenti, permette di realizzare degli schemi per la risoluzione di problemi CSP, infatti, si possono creare delle strategie per prevenire i conflitti.

Strategie di anticipazione

Combinare metodologie come backtracking e tecniche consistenti, può essere d'aiuto, per rendere più efficienti gli algoritmi per la risoluzione dei CSP. Alcuni schemi che adottano tale soluzione sono: Forward Checking e Look Ahead.

Forward Checking

Tale metodo, esegue una "forma ristretta" di arco consistente per le variabili che ancora non sono state stanziate. Parliamo di forma ristretta di arco consistente, perché forward checking controlla solo i vincoli tra le variabili correnti, e quelle future. Quando un valore è assegnato ad una variabile corrente, ogni valore del dominio che sarà in conflitto (in futuro) con questa variabile, viene temporaneamente eliminato. Il vantaggio di questa tecnica, è che se il domino diventa vuoto, allora la soluzione parziale corrente è inconsistente. Questo permette di costruire un albero di ricerca, in cui i fallimenti sono eliminati prima.

Look Ahead

Questo metodo ha vantaggio, di riuscire a scovare i conflitti delle variabili future, permettendo così di eliminare dei rami nell'albero di ricerca, prima di un forward checking, però effettua più lavoro.

Ordine delle variabili e dei valori

Un algoritmo di ricerca per la risolvere i CSP, richiede un ordine nel considerare le variabili, non solo, ma anche un ordine dei valori a loro assegnati. Gli esperimenti eseguiti dai ricercatori, hanno mostrato che l'ordine delle variabili può avere un impatto sostanziale, per la ricerca della soluzione, infatti, un giusto ordine può migliorare l'efficienza dell'algoritmo. Le strategie impiegate sono:

Ordine statico, che è specificato prima che la ricerca inizi, e non viene cambiato.

Ordine dinamico, il quale dipende dallo stato corrente della ricerca.

Diverse euristiche, sono state sviluppate per selezionare l'ordine delle variabili. La più comune, è basata sul principio di "first-fail", in pratica, durante la ricerca è meglio fallire subito che sprecare risorse in una strada sbagliata. In questo metodo, la variabile con meno alternative successive viene stanziata, in questo modo l'ordine delle variabili stanziate, è in generale differente nei diversi rami dell'albero di ricerca. Un'altra euristica, applicata quando tutte le variabili hanno un uguale numero di valori, è di scegliere la variabile che partecipa in più vincoli.

Anche l'ordine dei valori, da assegnare alle variabili, ha una certa influenza sul tempo di calcolo della soluzione, infatti, l'euristica che può essere utilizzata, controlla che i valori assegnati, portano ad una più facile soluzione del CSP. Questo richiede, di stimare la difficoltà di risoluzione di un CSP.

Algoritmi stocastici ed euristici

Questi algoritmi, usano metafore tipo "rapair" o "hill-climbing", per muoversi verso soluzioni più complete. Per evitare di restare bloccati in minimi locali, si utilizzano varie euristiche, per randomizzare la ricerca.

Hill-Climbing

E' probabilmente l'algoritmo di ricerca locale più conosciuto. L'algoritmo è diviso in tre passi:

Assegnamento casuale a tutte le variabili (stato iniziale).

Dirigersi verso uno stato vicino, che ha numero di vincoli violati più piccolo.

Se un minimo locale è raggiunto, allora si ricomincia da un altro stato generato in modo casuale.

L'algoritmo, procede finché una soluzione del problema, non è trovata.

procedure hill-climbing(Max_Flips)
restart: s <- random valuation of variables;
for j:=1 to Max_Flips do
if eval(s)=0 then return s endif;
if s is a strict local minimum then
goto restart
else
s <- neighborhood with smallest evaluation value
endif
endfor
goto restart
end hill-climbing


Min-Conflicts

Per evitare di esplorare tutti gli stati vicini (allo stato corrente), sono utilizzate alcune euristiche per trovare le mosse successive. L'euristica Min-Conflicts, sceglie la variabile che è coinvolta in qualche vincolo non soddisfatto, e poi casualmente sceglie un valore che minimizzi il numero di vincoli violati. Se, tale valore non esiste, si sceglie casualmente un valore che non incrementa il numero di vincoli violati.

procedure MC(Max_Moves)
s <- random valuation of variables;
nb_moves <- 0;
while eval(s)>0 & nb_moves<Max_Moves do
choose randomly a variable V in conflict;
choose a value v' that minimizes the number of conflicts for V;
if v' # current value of V then
assign v' to V;
nb_moves <- nb_moves+1;
endif
endwhile
return s end MC

Min-Conflicts-Random-Walk

Dato che l'algoritmo min-conflicts non può sfuggire ai minimi locali, si utilizza una strategia random-walk, che per una data variabile si sceglie casualmente un valore con una probabilità p, e si applica l'algoritmo MC con probabilità 1-p.

procedure MCRW(Max_Moves,p)
s <- random valuation of variables;
nb_moves <- 0;
while eval(s)>0 & nb_moves<Max_Moves do
if probability p verified then
choose randomly a variable V in conflict;
choose randomly a value v' for V;
else
choose randomly a variable V in conflict;
choose a value v' that minimizes the number of conflicts for V;
endif
if v' # current value of V then
assign v' to V;
nb_moves <- nb_moves+1;
endif
endwhile
return s
end MCRW

Steepest-Descent-Random-Walk

L'algoritmo Steepest-Descent, è la versione Hill-Climbling dell'algoritmo Min-Conflicts. Invece di selezionare casualmente la variabile in conflitto, l'algoritmo esplora, gli stati vicini alla configurazione corrente, e seleziona il vicino migliore in base al numero di conflitti. Per evitare ottimi locali, si utilizza la strategia random-walk.

procedure SDRW(Max_Moves,p)
s <- random valuation of variables;
nb_moves <- 0;
while eval(s)>0 & nb_moves<Max_Moves do
if probability p verified then
choose randomly a variable V in conflict;
choose randomly a value v' for V;
else
choose a move <V,v'> with the best performance
endif
if v' # current value of V then
assign v' to V;
nb_moves <- nb_moves+1;
endif
endwhile
return s
end SDRW

Tabu-Search

Tabu search(TS) è un metodo, che permette di evitare i cicli e minimi locali. Esso si basa sull'utilizzo di una memoria flessibile, chiamata tabu list, capace di mantenere traccia delle precedenti configurazioni incontrate. Nella tabu list, vengono memorizzate gli attributi delle configurazioni. Sono definite delle regole, chiamate criteri di aspirazione, che permettono di sovrascrivere gli attributi di una configurazione presente nella memoria, nel caso in cui la nuova configurazione è migliore della precedente.

procedure tabu-search(Max_Iter)
s <- random valuation of variables;
nb_iter <- 0;
initialize randomly the tabu list;
while eval(s)>0 & nb_iter<Max_Iter do
choose a move <V,v'> with the best performance among the non-tabu moves and the moves satisfying the aspiration criteria;
introduce <V,v> in the tabu list, where v is the current values of V;
remove the oldest move from the tabu list;
assign v' to V;
nb_iter <- nb_iter+1;
endwhile
return s
end tabu-search

GSAT

Gsat è una procedura greedy di ricerca locale, utilizzata per soddisfacimento di formule logiche in forme normali congiuntive (CNF). Tali problemi sono chiamati SAT o k-SAT (k è il numero di letterali in ogni clausola), e sono NP-hard. La procedura inizia con un arbitrario assegnamento delle variabili, e permette di raggiungere, il più alto grado di soddisfacimento per piccole successioni di trasformazioni, chiamate rapairs o flips

procedure GSAT(A,Max_Tries,Max_Flips)
A: is a CNF formula
for i:=1 to Max_Tries do
S <- instantiation of variables
for j:=1 to Max_Iter do
if A satisfiable by S then
return S
endif
V <- the variable whose flip yield the most important raise in the number of satisfied clauses;
S <- S with V flipped;
endfor
endfor
return the best instantiation found
end GSAT

Local-Search

Tutti gli algoritmi visti precedentemente, sono basati su di un'idea comune, conosciuta come nozione di local search. Nella ricerca locale, una configurazione iniziale è generata, e l'algoritmo si muove da tale configurazione ad una vicina, finché una soluzione, o una buona soluzione non viene trovata.

procedure local-search(Max_Moves,Max_Iter)
s <- random valuation of variables;
for i:=1 to Max_Tries while Gcondition do
for j:=1 to Max_Iter while Lcondition do
if eval(s)=0 then
return s
endif;
select n in neighborhood(s);
if acceptable(n) then
s <- n
end if
endfor