Master Bioinformatica 2002: Progetto di Algoritmi1 Problemi di ottimizzazione Allocazione di risorse...

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à


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)


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”


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


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.


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


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


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


Selezione di attvità

Output: insieme che contiene il massimo numero di attivita’mutuamente compatibili.


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


1 2 3 4 5 6 7 8 9 10 11 12

1

2

3

4

56

789

10


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


Applicando lo schema greedy:

• Oggetti: le attivita’• Appetibilita’: tempo di fine

Ordiniamo le attivita’ per tempo di fine visita non decrescente.


1 2 3 4 5 6 7 8 9 10 11 12

2

6

5

7

98

1034

1

Attività ordinate per fine visita


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


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


1 2 3 4 5 6 7 8 9 10 11 12

2

6

5

7

98

1034

1

Soluzione: {2,9,8,1}


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


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


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’.


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.


Proprietà2: scelta greedy

Sia 1 S, un’attività con tempo di fine f1 minimo.

Esiste una soluzione ottima A tale che 1 A


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’


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’


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.


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.


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


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.


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.


Problema:

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


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)


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


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.


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.


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.


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


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


if (wi > C)

then Li C (Li C/wi) C 0

else Li wi (Li 1)

C C - wi,

i i+1

return L


Esempio

peso w valore v v/w

articolo 1 10 60 6

articolo 2 20 100 5

articolo 3 30 120 4


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


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


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


if (wi > C)then Li 0

else Li 1

C C - wi,

i i+1

return L


Rivediamo l’esempio

peso w valore v v/w

articolo 1 10 60 6

articolo 2 20 100 5

articolo 3 30 120 4


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


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


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 Algoritmi1 Problemi di ottimizzazione Allocazione di risorse...

Documents

Transcript of Master Bioinformatica 2002: Progetto di Algoritmi1 Problemi di ottimizzazione Allocazione di risorse...