Post on 01-May-2015
transcript
Master Bioinformatica 2002: Progetto di Algoritmi 1
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 2
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 3
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 4
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 5
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 6
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
Algoritmi Greedy - Schema generale 1
Se le appetibilita’ degli oggetti sono note fin dall’inizio e non vengono modificate
Master Bioinformatica 2002: Progetto di Algoritmi 7
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 8
Esempio: Problema della Selezione di attivita’
Input: S = {1, 2, …, n} insieme di attivita’che devono usare unarisorsa in modo esclusivo.Ogni attivita’ i e’ caratterizzata da un tempo di inizio e
daun tempo di fine: [si, fi) con (si < fi).
[si, fi) e [sj, fj) sono compatibili se si fj o sj fii j
si fisj fj
j ifj si fi
sj
sj
Master Bioinformatica 2002: Progetto di Algoritmi 9
Selezione di attvità
Output: insieme che contiene il massimo numero di attivita’mutuamente compatibili.
Master Bioinformatica 2002: Progetto di Algoritmi 10
Attitvità Inizio (s) fine (f)1 9 122 1 33 6 104 5 115 2 46 2 37 1 58 7 99 3 610 6 9
Master Bioinformatica 2002: Progetto di Algoritmi 11
1 2 3 4 5 6 7 8 9 10 11 12
1
2
3
4
56
789
10
Master Bioinformatica 2002: Progetto di Algoritmi 12
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 13
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 14
1 2 3 4 5 6 7 8 9 10 11 12
2
6
5
7
98
1034
1
Attività ordinate per fine visita
Master Bioinformatica 2002: Progetto di Algoritmi 15
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 16
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
si fj
Master Bioinformatica 2002: Progetto di Algoritmi 17
1 2 3 4 5 6 7 8 9 10 11 12
2
6
5
7
98
1034
1
Soluzione: {2,9,8,1}
Master Bioinformatica 2002: Progetto di Algoritmi 18
1 2 3 4 5 6 7 8 9 10 11 12
2
5
7
9
810
34
1
Altra soluzione: {6,9,10,1}
6
Master Bioinformatica 2002: Progetto di Algoritmi 19
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 20
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 21
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 22
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 23
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 24
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 25
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 26
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 27
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 28
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 29
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 30
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 31
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 32
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 33
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 34
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 35
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 36
Knapsack(W, w,v)Ordina {1,…,n} per vi/wi non crescente
C W
for i = 1 to n doLi 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 37
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 38
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 39
Esecuzione algoritmo
/ 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
Master Bioinformatica 2002: Progetto di Algoritmi 40
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 41
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 42
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 43
Esecuzione algoritmo
/ 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
Master Bioinformatica 2002: Progetto di Algoritmi 44
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 45
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