Problemi di ottimizzazione
• Allocazione di risorse (merci in un magazzino)
• Scheduling (ordinamento temporale)
• Pianificazione di investimenti
• Pattern matching: date due sequenze di simboli:
AACCGATGTACCT
CGAACGATACGGTTAC
trovare la piu’ lunga sottosequenza comune
• Distanza minima in reti: dato un insieme di città collegate
da strade trovare il percorso minimo che collega ogni
coppia di città
Master Bioinformatica 2002: Progetto di Algoritmi
1
Soluzione di un 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 il
costo/valore finale
• si è interessati a trovare una soluzione che abbia
un costo/valore ottimo (minimo o massimo)
Master Bioinformatica 2002: Progetto di Algoritmi
2
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
una determinata proprietà
Idea: “per trovare un soluzione globalmente ottima,
scegli ripetutamente soluzioni ottime localmente”
Master Bioinformatica 2002: Progetto di Algoritmi
3
Esempio: Il problema del resto
Avendo a disposizione monete di vario tipo
determinare una collezione minima di monete la cui
somma sia uguale al resto.
Ad esempio: hai a disposzione monete da
50, 20,10, 2 e 1 cent.euro,
il resto “ottimo” di 87 è formato da:
50+20+10+5+1+1
Master Bioinformatica 2002: Progetto di Algoritmi
4
Struttura degli algoritmi greedy
• Si assume che gli oggetti abbiano associato un
valore di “appetibilità”.
• La soluzione viene costruita incrementalmente
scegliendo ad ogni passo l’oggetto che ha
appetibilita’ maggiore e puo’ essere aggiunto a
quelli già selezionati.
Master Bioinformatica 2002: Progetto di Algoritmi
5
Algoritmi Greedy - Schema generale 1
Se le appetibilita’ degli oggetti sono note fin dall’inizio e non
vengono modificate
Greedy1 ({a1, a2, …an})
S
“ ordina gli ai in ordine non crescente di appetibilita’ ”
for ogni ai nell’ordine do
if “ai puo’ essere aggiunto a S”
then S  S  {ai}
return S
Master Bioinformatica 2002: Progetto di Algoritmi
6
Algoritmi Greedy - Schema generale 2
Se le appetibilita’ degli oggetti possono essere modificate dalle
scelte gia’ fatte.
Greedy2 ({a1, a2, …an})
S
“valuta le appetibilita’ degli ai ”
while “ci sono elementi da scegliere” do
“scegli l’ai piu’ appetibile”
if “ai puo’ essere aggiunto a S”
then S  S  {ai}
“aggiorna le appetibilita’ degli ai ”
return S Master Bioinformatica 2002: Progetto di Algoritmi
7
Esempio: Problema della Selezione di attivita’
Input: S = {1, 2, …, n} insieme di attivita’che devono usare una
risorsa in modo esclusivo.
Ogni attivita’ i e’ caratterizzata da un tempo di inizio e da
un tempo di fine: [si, fi) con (si < fi).
sj
[si, fi) e [sj, fj) sono compatibili se si  fj o sj  fi
i
si
fi
j
sj
j
sj
fj
i
fj
si
Master Bioinformatica 2002: Progetto di Algoritmi
fi
8
Selezione di attvità
Output: insieme che contiene il massimo numero di
attivita’mutuamente compatibili.
Master Bioinformatica 2002: Progetto di Algoritmi
9
Attitvità
1
2
3
4
5
6
7
8
9
10
Inizio (s)
9
1
6
5
2
2
1
7
3
6
fine (f)
12
3
10
11
4
3
5
9
6
9
Master Bioinformatica 2002: Progetto di Algoritmi
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
Master Bioinformatica 2002: Progetto di Algoritmi
11
12
11
Idea dell’algoritmo
seleziona ad ogni passo un’attività che sia
compatibile con quelle già selezionate e lasci più
opportunità di selezione futura

seleziona ad ogni passo un’attività che sia compatibile
con quelle già selezionate e che abbia tempo di fine
minimo tra quelle che possono ancora essere selezionate
Master Bioinformatica 2002: Progetto di Algoritmi
12
Applicando lo schema greedy:
• Oggetti: le attivita’
• Appetibilita’: tempo di fine
Ordiniamo le attivita’ per tempo di fine visita non
decrescente.
Master Bioinformatica 2002: Progetto di Algoritmi
13
2
6
5
7
9
8
10
3
4
1
1
2
3
4
5
6
7
8
9
10
11
12
Attività ordinate per fine visita
Master Bioinformatica 2002: Progetto di Algoritmi
14
Activity_selector(s, f)
A
sia {a1, a2, …an} ordinata in modo che f1,  f2 ,…  fn
A = {1}
j1
for i = 2 to n do
if si  fj
then A  A  {i}
ji
return A
Master Bioinformatica 2002: Progetto di Algoritmi
15
Spiegazione dell’algoritmo
fj rappresenta il massimo tempo di fine visita delle
attivita’ gia’ selezionate (quelle in A)

per sapere se un’attivita’ i e’ compatibile con
quelle gia’ selezionate basta verificare che
s i  fj
Master Bioinformatica 2002: Progetto di Algoritmi
16
2
6
5
7
9
8
10
3
4
1
1
2
3
4
5
6
7
8
9
10
11
12
Soluzione: {2,9,8,1}
Master Bioinformatica 2002: Progetto di Algoritmi
17
6
2
5
7
9
10
8
3
4
1
1
2
3
4
5
6
7
8
9
10
11
12
Altra soluzione: {6,9,10,1}
Master Bioinformatica 2002: Progetto di Algoritmi
18
Tutte le soluzioni
•
•
•
•
{2, 9, 8, 1}
{6, 9, 10, 1}
{2, 9, 10, 1}
{6, 9, 8, 1}
Osserva che si ottiene una soluzione da un altra
sostituendo un’attività con un’altra con lo stesso
tempo di fine visita
Master Bioinformatica 2002: Progetto di Algoritmi
19
Proprietà1: sottostruttura ottima
Sia A una soluzione ottima per S, sia k  A.
Considera
Ak = {i A | fi  fk}
A’ = A - Ak
S’ = {i  S | si  fk}
A’ e’ una soluzione ottima per S’.
Master Bioinformatica 2002: Progetto di Algoritmi
20
Dimostrazione: supponi che A’ non sia ottima allora
esiste una soluzione B per S’con |B| > |A’|.
Poichè
B  Ak = 
e ogni attività in B è compatibile con quelle in Ak
ottengo che
Ak  B
è una soluzione per S e
|B  Ak| > |A’  Ak| = |A|
contro l’ipotesi che A sia ottima.
Master Bioinformatica 2002: Progetto di Algoritmi
21
Proprietà2: scelta greedy
Sia 1  S, un’attività con tempo di fine f1 minimo.
Esiste una soluzione ottima A tale che 1  A
Master Bioinformatica 2002: Progetto di Algoritmi
22
Dimostrazione: sia A una soluzione ottima per S e
sia j  A un’attività con tempo di fine minimo tra
quelle in A, vale
f1  fj
Considera l’insieme
A’ = (A -{j})  {1}
poichè vale
si  fj  f1 per ogni i in A -{j}
anche A’ e’una soluzione ed e’ottima essendo
|A’| = |A| e abiamo che 1  A’
Master Bioinformatica 2002: Progetto di Algoritmi
23
Correttezza dell’algoritmo
Segue dalle due proprietà dimostrate mediante un
ragionamento induttivo.
Considera un insieme di attività S = {1,…,n} ordinate in modo
che f1  f2  …  fn.
Per la Proprietà2 esiste una soluzione ottima che contiene la
prima scelta greedy 1. Sia A una tale soluzione. Per la
Proprietà1, A’ = A - {1} e’ una soluzione ottima per l’insieme
di attivita’ S’ = {i  S: si  f1}.
Riapplica lo stesso ragionamento ad S’
Master Bioinformatica 2002: Progetto di Algoritmi
24
Formalmente provo che: siano i1,…,ik le attività gia’ scelte
dall’algoritmo con k 0, supponi che esista una soluzione
ottima i cui primi k elementi (nell’ordine di f) sono i1,…,ik e
che l’algoritmo scelga al prossimo passo l’attività ik+1 allora
esiste una soluzione ottima i cui primi k+1 elementi i1,…ik, ik+1 .
Dimostrazione
• k = 0, allora ik+1 = 1, e’ la Proprietà2.
• k > 0, supponi che sia A soluzione ottima e che i1,…, ik siano i
primi k elementi di A,
caso i se ik+1  A non c’è niente da dimostrare.
Master Bioinformatica 2002: Progetto di Algoritmi
25
caso ii se ik+1  A considera A’= A - {i1,…, ik} e sia
S’= {i  S | si  f ik}. Per la proprietà 2 applicata a S’ esiste
una soluzione ottima B per S’che contiene ik+1 come elemento
piu’piccolo.
Per la Proprietà 1 A’ e’ottima per S’ quindi |B| =|A’|. Dato che
B  {i1,…, ik} =  e che ogni attivita in B è compatibile con
{i1,…, ik} ho che B  {i1,…, ik} è una soluzione ottima per S
e ha come primi k+1 elementi i1,… ik+1.
Master Bioinformatica 2002: Progetto di Algoritmi
26
Quando e’applicabile la metodologia
greedy?
• Sottostruttura ottima: una soluzione ottima del
problema contiene al suo interno una soluzione di
dei sottoproblemi
• Scelta greedy: la scelta dell’ottimo locale
garantisce una soluzione ottima globale
Master Bioinformatica 2002: Progetto di Algoritmi
27
La scelta greedy riduce un problema ad un
problema piu’piccolo dello stesso tipo di quello di
partenza. Una soluzione ottima e’ determinata
dalla sequenza di tali scelte che alla fine
producono un problema vuoto.
Master Bioinformatica 2002: Progetto di Algoritmi
28
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 dei quali ha peso wi e valore vi.
Può prendere qualsiasi articolo, purchè non ecceda la
capacità W.
Master Bioinformatica 2002: Progetto di Algoritmi
29
Problema:
Quale è il massimo valore che può mettere insieme e
quali articoli deve prendere per massimizzare il
valore complessivo del bottino?
Master Bioinformatica 2002: Progetto di Algoritmi
30
Due varianti del problema:
• Lo zaino frazionario (o continuo): si possono
prendere frazioni di ciascun articolo.
• Lo zaino discreto (o zaino 0-1): gli articoli sono
indivisibili, quindi ciascun articolo o lo si prende
oppure no (scelta 0-1)
Master Bioinformatica 2002: Progetto di Algoritmi
31
Lo zaino frazionario è risolvibile con un
metodo greedy
Consideriamo come valore di appetibilità il valore
di ciascun oggetto (vi) per unità di peso (wi):
vi/wi
Master Bioinformatica 2002: Progetto di Algoritmi
32
Idea dell’algoritmo greedy:
Prendi il piu’ possibile dell’oggetto con il piu’ alto
rapporto vi/wi.
Se la dotazione dell’oggetto e’ esaurita e non hai
ancora riempito lo zaino, considera il prossimo
oggetto con il piu’alto rapporto vi/wi. Ripeti il
procedimento finchè lo zaino è pieno.
Master Bioinformatica 2002: Progetto di Algoritmi
33
Proprietà della sottostruttura ottima
Se rimuovo una quantità w di un articolo j da un
carico ottimo ottengo un carico ottimo che pesa al
piu’ W-w e che posso mettere insieme avendo a
disposizione n-1 articoli con le quantità originarie e
wj -w chili dell’articolo j.
Altrimenti: se ci fosse un carico che vale di più,
potrei ottenere un carico migliore con la dotazione
originaria degli n articoli e peso W, aggiungendo w
chili di j a quel carico.
Master Bioinformatica 2002: Progetto di Algoritmi
34
Proprietà della scelta greedy
• Sia h un articolo con il più alto rapporto vh/wh.
• C’e’ una soluzione ottima L in cui prendo il
massimo di h, cioè
Lh= min(W,wh)
Dopo aver scelto Lh il problema si riduce a trovare
una soluzione ottima scegliendo tra n-1 oggetti (h
escluso) e potendo mettere insieme un peso non
superiore a W- Lh . Si ripete il ragionamento
considerando la prossima scelta greedy.
Master Bioinformatica 2002: Progetto di Algoritmi
35
Knapsack(W, w,v)
Ordina {1,…,n} per vi/wi non crescente
CW
for i = 1 to n do
Li  0
i1
while (i  n) and (C > 0) do
Li  min(C, wi)
C  C - Li
i  i+1
return L
Master Bioinformatica 2002: Progetto di Algoritmi
36
Knapsack(W, w,v)
(L valori frazionari)
Ordina {1,…,n} per vi/wi non crescente
CW
for i = 1 to n do
Li  0
i1
while (i  n) and (C > 0) do
if (wi > C)
then Li  C
(Li  C/wi)
C0
else Li  wi
(Li  1)
C  C - wi,
i  i+1
return L
Master Bioinformatica 2002: Progetto di Algoritmi
37
Esempio
peso w
valore v
v/w
articolo 1
10
60
6
articolo 2
20
100
5
articolo 3
30
120
4
Master Bioinformatica 2002: Progetto di Algoritmi
38
Esecuzione algoritmo
i
C
L1
L2
L3
/
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
Master Bioinformatica 2002: Progetto di Algoritmi
39
Zaino 0-1
Stesso problema, ma gli articoli vanno presi
interamente:
Li = 1
se prendiamo l’articolo i
Li = 0
se non prendiamo l’articolo i
Vale la proprietà della sottostruttura ottima anche per
lo zaino0-1: se ad un carico ottimo di peso W tolgo
un oggetto j, ottengo un carico ottimo di peso W - wj
Master Bioinformatica 2002: Progetto di Algoritmi
40
GreedyKnapsack0-1(W, w,v)
Ordina {1,…,n} per vi/wi non crescente
CW
for i = 1 to n do
Li  0
i1
while (i  n) and (C > 0) do
if (wi > C)
then Li  0
else Li  1
C  C - wi,
i  i+1
return L
Master Bioinformatica 2002: Progetto di Algoritmi
41
Rivediamo l’esempio
peso w
valore v
v/w
articolo 1
10
60
6
articolo 2
20
100
5
articolo 3
30
120
4
Master Bioinformatica 2002: Progetto di Algoritmi
42
Esecuzione algoritmo
i
C
L1
L2
L3
/
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
Master Bioinformatica 2002: Progetto di Algoritmi
43
E’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
Master Bioinformatica 2002: Progetto di Algoritmi
44
Non vale il principio della scelta greedy:
la scelta se prendere o no un oggetto non dipende
dalla sua appetibilità.
Per trovare una soluzione ottima bisogna comparare
la soluzione del sottoproblema in cui si e’ scelto di
prendere un articolo con la soluzione in cui si e’
scelto di non prendere quell’articolo.
Il problema è risolvibile con la Programazione
Dinamica
Master Bioinformatica 2002: Progetto di Algoritmi
45