API 2013/4Algoritmi di ricerca di una soluzione

Dipartimento di Elettronica Informazione e Biongegneria

@ G. Gini 2013

G. Gini 2013/42

Negli ultimi 20 anni…✦ Ragionamento simbolico (theorem prover, SAT, ontology reasoner)✦ CSP e nuovi linguaggi✦ Data mining e scoperta scientifica✦ Motori di ricerca (String matching, ranking)✦ e-services e autenticazione✦ simulazione di sistemi e processi✦ wireless networks e connettività✦…

✦Quali algoritmi negli ultimi anni?

G. Gini 2013/4

Altra vista sugli alberi

• L’albero non sempre è la struttura dati per memorizzare le informazioni

• Può essere la struttura dei processi generati dal codice

• Vediamo il caso di “spazio di ricerca” di una soluzione

Ruolo delle tecniche di baktracking e di scelta locale

G. Gini 2013/4

Problema di scelta: labirinto

• Dato un labirinto, andare da start a finish

• Ad ogni intersezione sceglierese andare:

AvantiDestraSinistra

• Non si ha informazione per scegliere sempre in modocorretto

• Se si arriva ad un punto morto, tornare indietro e provareun’altra scelta.

G. Gini 2013/4

Problema di scelta: colorare una mappa

• 4 coloriRosso, giallo, verde, blu

• Paesi adiacenti devono avereun colore diverso

• Si parte con una scelta, poi può essere necessariocambiarla

G. Gini 2013/4

Problema di scelta: puzzle

• All’inizio tutti i fori tranne unosono riempiti con pioli

• Un piolo può scavalcarne un altro

• Un piolo scavalcato varimosso

• Il gioco è lasciare solo un piolo

G. Gini 2013/4

Spazio di ricerca

• ESEMPIOtrovare tutti i numeri binari di 3 bit la cui somma di “1” èmaggiore o uguale a 2

Enumerare tutte le possibilità: (000, 001, 010, ....,111)

Le 8 possibilità sono lo SPAZIO DI RICERCA del problema.Possono essere rappresentare su un albero.

G. Gini 2013/4

Albero dello spazio di ricerca

0 0 _

0 0 0 0 0 1

0 1 _

0 1 0 0 1 1

1 _ _0 _ _

1 0 _

1 0 0 1 0 1

1 1 _

1 1 0 1 1 1

G. Gini 2013/4

backtracking• Non si hanno informazioni per fare sempre la scelta corretta• Si può modificare con backtracking sull’albero delle scelte

• Raggiunto il nodo N: 1. If N is a goal node, return “success” 2. If N is a leaf node, return “failure” 3. For each child C of N,

3.1. Explore C 3.1.1. If C was successful, return “success”

4. Return “failure”

StartSuccess!

Success!

G. Gini 2013/4

Backtracking

Backtracking è un modo sistematico per esaminarelo spazio di ricerca

Soluzione parziale: v = (a(1), a(2),..., a(k))poi la estendiamo e proviamo attraverso i passi:

• Se la soluzione parziale è ancora una soluzione candidataavanti

elsedelete a(k) e cerca un’altra scelta per a(k).

• Se nessuna altra scelta per a(k), backtrack e cerca un’altra scelta per a(k-1).

fail

G. Gini 2013/4

Backtracking e ricorsione

• Backtracking è implementato direttamente dalmeccanismo della ricorsione sul run-time stack

• In caso di fallimento si restituisce un codice di fallimento al chiamante

• Si possono aggiungere euristiche per ridurre lo spazio di ricerca

G. Gini 2013/4

Colorazione di grafo - 3 colori

C

A

FB

E

D

• esempioVertici in ordine A-FColori nell’ordine: R, G, B

G. Gini 2013/4

C

A

FB

E

D

C

A

FB

E

D

Primo nodo – primo coloreSecondo nodo – secondo colore

G. Gini 2013/4

C

A

FB

E

D

Terzo nodo – primo colore diverso dal nodo di provenienza

C

A

FB

E

D

Quarto nodo - primo colore diverso dal nodo di provenienza

G. Gini 2013/4

C

A

FB

E

D

Quinto nodo - Colore diverso da quelli cui è collegato

C

A

FB

E

D

Sesto nodo – nessun colore possibile

G. Gini 2013/4

C

A

FB

E

D

Backtrack e cambia colore di E?non ci sono altre scelte

Backtrack e cambia colore di D

C

A

FB

E

D

G. Gini 2013/4

C

A

FB

E

D

Continua su E

soluzione

C

A

FB

E

D

G. Gini 2013/4

C

A

FB

E

D

Partendo da primo nodo rosso, albero esplorato

G. Gini 2013/4

Problema delle 8 regine

• Mettere 8 regine sullascacchiera in modo che non si attacchino

• Una regina può attaccareuna regina se è sulla stessariga, colonna, diagonale,

• Si può risolvere il problemamettendo la prima regina, poi la seconda in modo chenon possa attaccare la prima, e così via

• Costruiamo una soluzioneparziale,

• backtrack la soluzione parziale di lunghezza k se non possiamoespanderla oltre

G. Gini 2013/4

implementazione

• Board, array 8 x 8 di 1 e 0 per la scacchiera• Inizializzata a 1; quando una regina è posizionata in la cella viene

messa a 0• Lo spazio di ricerca è 16,772, 216 possibilità.• Occorre ridurre lo spazio di ricerca• Sappiamo infatti che:

Ogni rigà avrà una reginaOgni colonna avrà una reginaOgni diagonale avrà una reginaAllora modelliamo la scacchiera non come array 2D ma come un insieme di righe, colonne, diagonali.

• Nel seguito usiamo 4 x 4 - questo problema ha 2 soluzioni

G. Gini 2013/4

scacchiera

• Array per le regine• (QUESTA è UNA

SOLUZIONE)

• Un altro array per lo stato delle colonne

PositionInRow

1

3

0

2

FTFT

Esempio:2 regine assegnate

G. Gini 2013/4

7 + 7 diagonali

T

T

F

T

F

T

T

T

F

T

T

F

T

T

Altri 2 array per lo stato delle diagonali

G. Gini 2013/4

putQueen

void putQueen(int row){for (int col=0;col<squares; col++)

if (column[col]==available && leftDiagonal[row+col]==available &&rightDiagonal[row-col+norm]== available) {

positionInRow[row]=col;column[col]=!available;leftDiagonal[row+col]=!available;rightDiagonal[row-col+norm]=!available;if (row<squares-1)

putQueen(row+1);else

println("solution found");column[col]=available;leftDiagonal[row+col]=available;rightDiagonal[row-col+norm]= available;

}}

G. Gini 2013/4

Solo definire i vincoli

Siccome sappiamo che possiamo avere solo una regina per riga, definiamo 4 variabili

Z = (riga1, riga2, riga3, riga4) con dominiiDzi = (1, 2, 3, 4) per 1 i 4vogliamo trovare per ogni riga la posizione (colonna) della

regina.Regine sulla stessa riga, colonna, o diagonale si attaccano.

Quindi abbiamo 3 vincoli :- Il primo è già soddisfatto dalla nostra rappresentazione- Il secondo ed il terzo sonoCij = (zi ≠zj) and |zi – zj| ≠ |i – j| per 1 i <j 4Il sistema risolve i vincoli (vedi CSP)

G. Gini 2013/4

Constraint Programming

• “... represents one of the closest approaches computer science has yet made to the Holy Gral of programming: the user states the problem, the computer solves it.”

– Eugene C. Freuder - 1999

G. Gini 2013/4

CSP (constraint satisfaction problem)

Un CSP è definito come:- un insieme di variabili

(X = {X1,..,Xn})• un dominio discreto per ogni variabile

(D={D1,..,Dn} ) • un insieme di vincoli fra queste variabili • (C={C1,..,Cm })

un vincolo c(Xi1, Xi2, …,Xik) tra k variabili è un sottoinsieme del prodotto cartesiano dei domini Di1 x Di2 x…x Dik e specifica quali valori delle variabili sono compatibili con le altre.

G. Gini 2013/4

esempio

• In una fattoria ci sono solo polli e conigli.• Sappiamo che ci sono 18 teste e 58 zampe.• Quanti conigli e polli ci sono?

• X numero di polli• Y numero di conigli• Dominii delle variabili: (X,Y) in 1-58)• Vincoli:• X+Y = 18• 2*X+4*Y = 58

G. Gini 2013/4

Esempio: Map-Coloring

• Variabili WA, NT, Q, NSW, V, SA, T• Dominii Di = {red,green,blue}• Constraints: regioni adiacenti devono avere colori diversi

e.g., WA ≠ NT, or (WA,NT) in {(red,green),(red,blue),(green,red), (green,blue),(blue,red),(blue,green)}�

• Soluzione: WA = red, NT = green, Q = red, NSW = green, V = red, SA = blue, T = green

G. Gini 2013/4

Rappresentazione a grafo

• Constraint graph: nodi sono le variabili, archi sono I vincoli (binari)

G. Gini 2013/4

Esempio: criptoaritmetica

• Variabili: F T U W R O X1 X2 X3• Domini: {0,1,2,3,4,5,6,7,8,9}• Constraints: Alldiff (F,T,U,W,R,O)

O + O = R + 10 · X1X1 + W + W = U + 10 · X2X2 + T + T = O + 10 · X3X3 = F, T ≠ 0, F ≠ 0

G. Gini 2013/4

Tecniche di risoluzione• Generate and Test

Vengono generati tutti i possibili assegnamenti fino a trovare unassegnamento che soddisfa i vincoli. Assegna le variabili e verifica la soddisfacibilità di tutti i vincoli con tale assegnamento

• BacktrackingAssegna le variabili in modo sequenziale e non appena le variabili relative ad un vincolo sono tutte istanziate verifica che tale vincolo sia soddisfatto. In caso positivo continua ad assegnare le altre variabili, in caso negativo backtracking sulla variabile istanziata più recentemente.

• Avanzate: sfruttano la consistenza locale

G. Gini 2013/4

Backtracking: è un metodo di visita Depth firstdell‘albero dello spazio del problema

Invece i metodi che generano una parte dellospazio del problema in cui i nodi attualmenteespansi non sono definitivamente assegnati finoalla fine sono i metodi Branch and Bound –metodi di visita breadth first limitata.

G. Gini 2013/4

SottoproblemiDivide-et-impera

✦Tecnica ricorsiva✦Approccio top-down (problemi divisi in sottoproblemi)✦Vantaggioso quando i sottoproblemi sono indipendenti

✦ Altrimenti, gli stessi sottoproblemi possono venire risolti più volte

Programmazione dinamica✦Tecnica iterativa✦Approccio bottom-up✦Vantaggiosa quando ci sono sottoproblemi in comune

✦Esempi: i numeri di Fibonacci, il triangolo di Tartaglia…

G. Gini 2013/4

Quando applicare la programmazione dinamica?Quando applicare la programmazione dinamica?

✦Sottostruttura ottima✦E' possibile combinare le soluzioni dei sottoproblemi per trovare la soluzione di un problema più grande in tempo polinomiale✦Le decisioni prese per risolvere un problema rimangono valide quando esso diviene un sottoproblema di un problema più grande

✦Sottoproblemi ripetuti✦Un sottoproblema può occorrere più volte

✦Spazio dei sottoproblemi✦Deve essere polinomiale

G. Gini 2013/4

Programmazione dinamica✦Caratterizzare la struttura di una soluzione ottima✦Definire ricorsivamente il valore di una soluzione ottima

✦La soluzione ottima ad un problema contiene le soluzioni ottime ai sottoproblemi

✦Calcolare il valore di una soluzione ottima “bottom-up” (cioè calcolando prima le soluzioni ai casi piùsemplici)

✦Si usa una tabella per memorizzare le soluzioni dei sottoproblemi✦Evitare di ripetere il lavoro più volte, utilizzando la tabella

✦Costruire la (una) soluzione ottima.

G. Gini 2013/4

– programmazione dinamica

G. Gini 2013/4

Triangolo di Tartagliadisposizione geometrica a forma di triangolo dei coefficienti dello sviluppo del binomio (a+b) elevato ad n ✦In ciascuna riga gli elementi si ottengono come somma di due elementi adiacenti della riga precedente

G. Gini 2013/4

Triangolo di Tartaglia✦Versione ricorsiva

✦Deriva direttamente dalla definizione✦C(n, k) = 1 se n=k o k=0, altrimenti✦= C(n-1,k-1) + C(n-1, k)

G. Gini 2013/4

Triangolo di Tartaglia✦Versione iterativa

✦programmazione dinamica

G. Gini 2013/4

Numeri di FibonacciNumeri di Fibonacci✦Definiti ricorsivamente

✦F(0) = F(1) = 1✦F(n) = F(n-2)+F(n-1)

G. Gini 2013/4

Implementazione ricorsivaImplementazione ricorsiva

✦Complessità computazionale

✦Soluzione✦T(n) = O(2n)

G. Gini 2013/442

Implementazione iterativaImplementazione iterativa

21

7

13

6

8

5

53211f [ ]

43210n

✦Complessità✦In tempo: O(n)✦In spazio: O(n)

✦Array di n elementi

G. Gini 2013/4

Riduzione di memoriaRiduzione di memoria

21

7

13

6

8

5

53211F2

43210n

F1

F0

138532111

853211--

✦Complessità✦In tempo: O(n)✦In spazio: O(1)

✦3 variabili

G. Gini 2013/4

Dalla programmazione dinamica

alla programmazione greedy

G. Gini 2013/4

problema di ottimizzazione

• Ad ogni problema è associato un costo/valore• Una soluzione e’ frutto di una sequenza di scelte,

ciascuna delle quali contribuisce a determinare ilcosto/valore finale

• Si è interessati a trovare una soluzione che abbia un costo/valore ottimo (minimo o massimo)

G. Gini 2013/4

Algoritmi greedy

Si applicano a problemi di ottimizzazione in cui dato un insieme di oggetti {a1,…,an} occorre selezionare un sottoinsieme “ottimo” S di oggetti che verificano unadeterminata proprietà

Idea: “per trovare un soluzione globalmente ottima, scegli ripetutamente soluzioni ottime localmente”

G. Gini 2013/4

Esempio: Cambio denaro

Cambio denaro somma usando n tagli (ordinati)= al numero di modi di cambiare somma usando tutti tranne

il primo+il numero di modi di cambiare somma-t1 dove t1 è il valore del primo taglio, usando tutti gli n tagli.

int cambiaMonete(float somma,float* tagli,int i,int n){if (somma < 0.0 || n == i) return 0;if (somma == 0.0) return 1;return cambiaMonete(somma,tagli,i+1, n) +

cambiaMonete(somma-tagli[i],tagli,i,n);}

G. Gini 2013/4

cambio di denaro iterativo• Input

Un numero intero positivo n• Output

Il più piccolo numero intero di banconote o monete per cambiare n euro usando pezzi da 20, 10, 5, e 1 euro.

• Esempin = 58, 7 pezzi: 20+20+10+5+1+1+1n = 18, 5 pezzi: 10+5+1+1+1

• AlgoritmoDispensa un pezzo alla voltaAd ogni passo, utilizza il pezzo più grande che non superi la cifra rimanente.

G. Gini 2013/4

Il criterio greedy non garantisce ottimalità

Ottimalità locale!

• InputUn intero positivo n

• OutputIl più piccolo numero di banconote per cambiare ndollari usando banconote da 12, 8, e 1 dollari.

• Esempion = 319 banconote: 12 + 12 + 1 + 1 + 1 + 1 + 1 + 1 + 16 banconote : 12 + 8 + 8 + 1 + 1 + 1

G. Gini 2013/4

Struttura degli algoritmi greedy

• Si assume che gli oggetti abbiano associato un valore di “appetibilità”.

• La soluzione viene costruita incrementalmentescegliendo ad ogni passo l’oggetto che ha appetibilita’ maggiore e puo’ essere aggiunto a quelli già selezionati.

• Si può permettere alla ottimalità di cambiaredurante l’esecuzione dell’algoritmo

La scelta greedy riduce un problema ad un problemapiù piccolo dello stesso tipo di quello di partenza. Una soluzione ottima è determinata dalla sequenzadi tali scelte che alla fine producono un problemavuoto.

G. Gini 2013/4© Alberto Montresor

quindi• algoritmi greedy

Semplici da programmareefficientiQuando è possibile dimostrare la proprietà di sceltaingorda,danno la soluzione ottimaLa soluzione sub-ottima può essere accettabile

• SvantaggiNon sempre danno la soluzione ottima

G. Gini 2013/4

Il problema dello zaino

Un ladro vuole rubare dei beni che trasporterà in uno zaino. Può prendere W chili di bottino (W èla capacità dello zaino). Deve scegliere tra n articoli, ognuno dei quali ha peso wi e valore vi. Può prendere qualsiasi articolo, purchè non ecceda la capacità W.

Quale è il massimo valore che può mettereinsieme e quali articoli deve prendere per massimizzare il valore complessivo del bottino?

G. Gini 2013/4

Due varianti del problema:

• Lo zaino frazionario (o continuo): si possono prenderefrazioni di ciascun articolo.

• Lo zaino discreto (0 -1): gli articoli sono indivisibili, quindi ciascun articolo o lo si prende oppure no (scelta0-1)

G. Gini 2013/4

Lo zaino frazionario - metodo greedy

Consideriamo come valore di appetibilità il valore di ciascun oggetto (vi) per unità di peso (wi):

vi/wi

G. Gini 2013/4

Idea dell’algoritmo greedy:

•Prendi il più possibile dell’oggetto con il più alto rapportovi/wi. •Se la dotazione dell’oggetto è esaurita e non hai ancorariempito lo zaino, considera il prossimo oggetto con il piùalto rapporto vi/wi. •Ripeti il procedimento finchè lo zaino è pieno.

G. Gini 2013/4

esempio

/ 50 0 0 0

1 40 10 0 0

2 20 10 20 0

3 0 10 20 20

Soluzione: V = 10*6 + 20*5 + 20*4 = 240

i C L1 L2 L3

C capacità residua, Li quantità di articolo i

peso w valore v v/w

articolo 1 10 60 6

articolo 2 20 100 5

articolo 3 30 120 4

G. Gini 2013/4

Zaino 0-1

Stesso problema, ma gli articoli vanno presiinteramente:Li = 1 se prendiamo l’articolo iLi = 0 se non prendiamo l’articolo i

Vale la proprietà della sottostruttura ottima anche per lo zaino 0-1: se ad un carico ottimo di peso W tolgo un oggetto j, ottengo un carico ottimo di peso W - wj

G. Gini 2013/4

Rivediamo l’esempio

/ 50 0 0 0

1 40 10 0 0

2 20 10 20 0

3 20 10 20 0 (w=30)

Soluzione: V = 10*6 + 20*5= 160

i C L1 L2 L3

peso w valore v v/w

articolo 1 10 60 6

articolo 2 20 100 5

articolo 3 30 120 4

G. Gini 2013/4

È ottima la soluzione?NO

Se prendo l’articolo 2 e l’articolo 3 ottengo:V = 100 + 120 = 220

La strategia greedy non trova una soluzione ottima per il problema dello zaino 0-1

Per trovare una soluzione ottima bisogna comparare la soluzione del sottoproblema in cui si è scelto di prendere un articolo con la soluzione in cui si è scelto di non prendere quell’articolo. Occorre la programmazione dinamica per risolverequesto problema

G. Gini 2013/4

Riassunto delle tecniche• Tecnica greedy

Approccio “ingordo”: si fa sempre la scelta localmente ottima

• BacktrackProcediamo per “tentativi”, tornando ogni tanto sui nostri passi

• Ricerca localeLa soluzione ottima viene trovata “migliorando” via via soluzioni esistenti

• Algoritmi probabilisticiMeglio scegliere con giudizio (ma in maniera costosa) o scegliere a caso (“gratuitamente”)

G. Gini 2013/4

Anytime Algorithms

• Se abbiamo un tempo definito per trovare la soluzione?

• TROVARE LA MIGLIOR SOLUZIONE POSSIBILE

Time

Qua

lity

of

Solu

tion Current Solution

Setup Time

STime

Qua

lity

of

Solu

tion Current Solution

Setup Time

S1. Suspend

3. ContinueIf you want2. Peek the results

G. Gini 2013/4

Anytime• Interruptability

After some small amount of setup time, the algorithm can be stopped at anytime and provide an answer

• MonotonicityThe quality of the result is a non-decreasing function of computation time

• Diminishing returnsThe improvement in solution quality is largest at the early stages of computation, and diminishes over time

• Measurable QualityThe quality of an approximate result can be determined

• PreemptabilityThe algorithm can be suspended and resumed with minimal overhead

[Zilberstein and Russell 95]

Time

Qua

lity

of

Solu

tion Current Solution

Setup Time

STime

Qua

lity

of

Solu

tion Current Solution

Setup Time

S

G. Gini 2013/4

Imparare dai dati

• Se non abbiamo idea di come costruire un algoritmo, lo facciamo “costruire” direttamente dai dati

• Il risultato è un “classificatore” che potrà essere usato in futuro per classificare simili istanze di dati

Il classificatore può avere diverse forme “simboliche” come insieme di regole, albero di decisione, etc e “non simboliche” come rete neurale addestrata, etc

• Strumenti: statistica e metodi di apprendimento

• Metodi supervisionati e non supervisionati

G. Gini 2013/4

EsEs: individuazione di facce: individuazione di facce

G. Gini 2013/4

Il metodoIl metodo• Sviluppato da Paul Viola e Michael Jones• accetta

Più oggetti per immagineRobusto a luminosità e scena

• Basato su:Immagine integraleCaratteristiche (features)Classificatori

G. Gini 2013/4

Caratteristiche e Immagine integraleCaratteristiche e Immagine integrale

Caratteristiche• I cambiamenti di luminosità non sono valutati

tra singoli pixel,ma tra regioni di pixel. Le regioni analizzate sono adiacenti, di forma rettangolare e di medesima dimensione. Una caratteristica è la differenza dei pixel contenuti in due rettangoli adiacenti.

Immagine integrale• non lavora direttamente sui pixel originali ma

su Immagine Integrale. L'immagine integrale in (x; y) contiene la somma dei pixel sopra e a sinistra del pixel in posizione (x; y), esso incluso.

• E' possibile calcolare l'immagine integrale leggendo una sola volta l'immagine originale.

G. Gini 2013/4

Cascata di classificatoriCascata di classificatori• Uso di un classificatore forte singolo

InefficienteAccuratezza limitata

• Cascata di classificatori forti (AdaBoost)Tasso di errore tende a zero

Sottofinestrescartate

Sottofinestrescartate

Sottofinestrescartate

Sottofinestrescartate

Sottofinestrescartate

G. Gini 2013/4

RilevatoreRilevatore

G. Gini 2013/4

Test Set MIT + CMU Test Set MIT + CMU • Test set A:

bassa qualitàDR: 56%FPR: 4,83 su un milione

• Test set B: media qualitàDR: 61%FPR: 6,35 su un milione

• Test set C: alta qualitàDR: 79%FPR: 5,8 su un milione

G. Gini 2013/4