Terzo passo: lunghezza di una LCS LCS-Length(X, Y, m, n) for i = 0 to m c[i, 0] = 0 for j = 1 to n...

Terzo passo: lunghezza di una LCS

LCS-Length(X, Y, m, n) for i = 0 to m c[i, 0] = 0 for j = 1 to n c[0, j] = 0 for j = 1 to n for i = 1 to m if xi == yj

c[i, j] = c[i-1, j-1]+1, s[i, j] = “” elseif c[i-1, j] ≥ c[i, j-1] c[i, j] = c[i-1, j], s[i, j] = “” else c[i, j] = c[i, j-1], s[i, j] = “” return c,s

Quarto passoEsempio

X=ABCBDABY=BDCABA

i

0 65432

0

1

2

3

4

5

6

7

0

jCDB

cs

1BA A

0

0 0 0 0 0 0

0

0

0

0

0

0

A

B

C

B

D

A

B

cs

cs

cs

cs

cs

cs

cs

Y

X

0

1

1

1

1

1

1

0

1

1

1

2

2

2

0

1

2

2

2

2

2

1

1

2

2

2

3

3

1

2

2

3

3

3

4

1

2

2

3

3

4

4

4

4

LCS=....LCS=...A

3

3

LCS=..BA2

2

LCS=.CBA

1

1

LCS=BCBA

0cs

Quarto passo: Stampa della LCS

Print-LCS(X, s, i, j) if i > 0 and j > 0 if s[i, j] == “” Print-LCS(X, s, i-1, j-1) print X[i] elseif s[i, j] == “” Print-LCS(X, s, i-1, j) else Print-LCS(X, s, i, j-1)

0

1

00

0 0

0

0

1

1

1

1

2

2

3

0 1

1

1

1

2

2

2

2

2

3

4

3

4

4

Metodo top-downEsempio

X=ABCBDABY=BDCABA

i

0 65432

0

1

2

3

4

5

6

7

jCDB

1BA A

A

B

C

B

D

A

B

Y

Xcs

cs

cs

cs

cs

cs

cs

cs

Triangolazione ottima Una triangolazione di un poligono convesso è una suddivisione del poligono in triangoli ottenuta tracciando delle diagonali che non si intersecano .

Vi sono più triangolazioni possibili dello stesso poligono

In questo problema sono dati i vertici q1,q2,…,qn di un poligono convesso P presi in ordine antiorario.

Ad ogni triangolo T è attribuito un costo c(T).

Ad esempio c(T) potrebbe essere la lunghezza del perimetro, la somma delle altezze, il prodotto delle lunghezze dei lati, (l’area ?), ecc.

Si vuole trovare una triangolazione del poligono P tale che la somma dei costi dei triangoli sia minima.

In quanti modi possiamo suddividere in triangoli un poligono convesso di n vertici?

Ogni lato del poligono P appartiene ad un solo triangolo della triangolazione .

q1

qn

qk

T

Siano q1qkqn i vertici del triangolo T a cui appartiene il lato q1qn

Il vertice qk può essere scelto in n-2 modi diversi e i due poligoni hanno rispettivamente n1 = k ed n2 = n-k+1 vertici.

q1

qn

qk

P1

P2

T

Il triangolo T suddivide il poligono P nel triangolo T stesso e nei due poligoni P1 e P2 di vertici q1,…,qk e qk,…,qn

P1 quando k = 2 e P2 quando k = n-1 sono poligoni degeneri, ossia sono un segmento.

Il numero T(n) di triangolazioni possibili di un poligono di n vertici si esprime ricorsivamente come segue

2 se1

2 se11

2

nknTkT

nnT n

k

)()()(

E’ facile verificare che T(n) = P(n-1) dove P(n) sono le parentesizzazioni del prodotto di n matrici.

Quindi T(n) cresce esponenzialmente.

Primo passo: struttura di una triangolazione ottima.

Supponiamo che una triangolazione ottima suddivida il poligono convesso P di vertici q1q2...qn nel triangolo T di vertici q1qkqn e nei due poligoni P1 e P2 di vertici q1…qk e qk…qn rispettivamente.

Le triangolazioni subordinate di P1 e di P2 sono triangolazioni ottime. Perché?

Secondo passo: soluzione ricorsiva

Se j = i+1 allora Pi..j è degenere e ci,j = 0.

1 se

1 se0

ijqqqccc

ijc

jkijkkijki

ji )(min ,,,

I sottoproblemi sono le triangolazioni dei poligoni Pi..j di vertici qi …qj . Sia ci,j la somma dei costi dei triangoli di una triangolazione ottima di Pi..j .

Se j > i+1 allora Pi..j si può scomporre in un triangolo T di vertici qiqkqj e nei due poligoni P1 e P2 di vertici qi…qk e qk…qj con i < k < j

Triangulation-Cost(q, n) for i = 1 to n-1 c[i, i+1] = 0 for j = 3 to n for i = j-2 downto 1 c[i, j] = for k = i+1 to j-1 q = c[i, k]+c[k, j]+c(qiqkqj ) if q < c[i, j] c[i, j] = q s[i, j] = k return c,s

Terzo passo: calcolo costo minimo

Complessità: O(n3)

Print-Triangulation(s, i, j) if j > i+1 k = s[i, j] Print-Triangulation(s, i, k) print “triangolo:”, i, j, k Print-Triangulation(s, k, j)

Quarto passo: Stampa triangolazione

Complessità: O(n)

Algoritmi golosiTecniche di soluzione dei problemi viste finora:•Metodo iterativo•Divide et impera•Programmazione dinamica

Nuova tecnica:•Algoritmi golosi

Metodo iterativo

Soluzione del problema di dimensione n

Soluzione del problema di dimensione i

Soluzione del problema di dimensione i-1

Problema

Sottoproblemi

Sottosottoproblemi

Sottoproblemi semplici

Divide et impera

Soluzioni

Soluzioni

Soluzioni

Soluzioni Soluzioni Soluzioni

In un problema di ottimizzazione abbiamo un insieme generalmente molto grande di soluzioni e dobbiamo scegliere tra di esse una soluzione che sia ottima in qualche senso (costo minimo, valore massimo, lunghezza minima, ecc.)

Soluzioni possibili Ottime

Possiamo risolvere un problema di questo tipo con una enumerazione esaustiva

- si generano tutte le soluzioni possibili,

- si calcola il costo di ciascuna di esse

- e infine se ne seleziona una di ottima.

Purtroppo l’insieme di soluzioni è generalmente molto grande (spesso esponenziale nella dimensione dell’input) per cui una enumerazione esaustiva richiede tempo esponenziale.

Molto spesso le soluzioni di un problema di ottimizzazione si possono costruire estendendo o combinando tra loro soluzioni di sottoproblemi.

Problema

Sottoproblemi

Soluzioni


Esempio: Problema Torino-Trieste. Sottoproblemi: Torino-Asti, Asti-Trieste; Torino-Novara, Novara-Trieste, ecc.

Abbiamo visto che perché la programmazione dinamica sia vantaggiosa rispetto all’enumerazione esaustiva bisogna che siano soddisfatte due condizioni:

1. Esistenza di sottoproblemi ripetuti.

2. Sottostruttura ottima.

Problema

Sottoproblemi

Sottosottoproblemi


Sottoproblemi ripetuti

Soluzioni

Soluzioni

Soluzioni


Sottoproblemaripetuto

Problema OttSoluzioni

Sottoproblemi

Sottosottoproblemi


Sottostruttura ottima

Soluzioni ottime

Ott Ott Ott

OttOttOttOttOttOtt Ott

Soluzioni ottime

Soluzioni ottime

Soluzioni ottime

Combinazioni di soluzioni ottime dei sottoproblemi


Sottoproblemi

Ott Ott Ott

Ott

Sottosottoproblemi

OttOttOttOttOtt


Ott

Sottoproblemiripetuti

Programmazione dinamica


Sottoproblemi

Ott Ott Ott

Ott

Sottosottoproblemi

OttOttOttOttOtt


Ott

Algoritmi golosi Scelta golosa

1) ogni volta si fa la scelta che sembra migliore localmente.

2) in questo modo per alcuni problemi si ottiene una soluzione globalmente ottima.

Problema della scelta delle attività

Ogni attività ai ha un tempo di inizio si ed un tempo di fine fi con si < fi .

n attività a1,...,an usano la stessa risorsa (es: lezioni da tenere in una stessa aula).

ai occupa la risorsa nell’intervallo di tempo [si, fi).

ai ed aj sono compatibili se [si, fi) ed [sj, fj) sono disgiunti.Problema: scegliere il massimo numero di attività compatibili.

Storiella GolosaPersonaggi:

Pinocchio L’algoritmo goloso

Il grillo parlante

Controlla Pinocchio

Conosce il futuro

La fata turchina

Voglio scegliere il maggior numero possibile di

divertimenti.

Pinocchio arriva nella Città dei Balocchi e può scegliere i divertimenti che preferisce Ogni divertimento ha un’orario di inizio ed una durata

Perciò comincio scegliendo il divertimento che inizia per

primo!! Così non perdo tempo.

Attenzione Pinocchio!!! Se fai così non è detto che tu possa scegliere il maggior numero di divertimenti

Allora scelgo il divertimento che dura di meno!!

Così mi rimane più tempo per gli altri.

Attenzione Pinocchio!!! Anche così non è detto che tu possa scegliere il

maggior numero di divertimenti

Allora scelgo il divertimento che non si sovrappone a troppi altri!! Così me ne

rimangono di più tra cui scegliere.

Attenzione Pinocchio!!! Anche così non è detto che tu possa scegliere il maggior numero di divertimenti

Uffa!! Ma sei proprio un rompiscatole!!Ora riprovo e se non ti va ancora bene ti

schiaccio con il martello.

Scelgo il divertimento “D” che termina per primo!! Così quando ho finito mi

rimane più tempo per gli altri.

Bene Pinocchio!! In questo modo prendi sicuramente il massimo numero di

divertimenti ed io posso dimostrarlo.

Mumble…, per dimostrarlo debbo provare che la scelta di quel monello non lo conduce in un vicolo cieco.

Ossia deve esistere una soluzione ottima a cui Pinocchio può arrivare

dopo aver fatto la scelta (la proprietà della scelta golosa).

Ma per questo dovrei conoscere il futuro. Qui mi serve l’aiuto della fatina.

Io conosco una soluzione ottima ma non la mostro a nessuno.

So che la fatina conosce una soluzione ottima.

Insegnerò alla fatina come modificare la sua soluzione ottima in modo che

contenga il divertimento “D”.


Mumble… se la soluzione della fatina contiene già “D” non ci sono problemi.

Io conosco una soluzione ottima che contiene “D”.

Cara fatina, se la tua soluzione contiene il divertimento “D” lasciala invariata.

Ho scelto il divertimento “D” che termina per primo!! Così quando ho

finito mi rimane più tempo per gli altri.

Ora so che la fatina conosce una soluzione ottima che contiene il

divertimento “D”.

Primo caso:


Mumble…. se la soluzione della fatina non contiene “D” devo dirgli di mettere “D” al posto di un altro divertimento.



Mumble…. il primo divertimento nella soluzione della fatina termina dopo “D”

e quindi “D” è compatibile con i successivi

Cara fatina, se la tua soluzione non contiene il divertimento “D” metti “D” al

posto del primo divertimento.

Secondo caso:

D1 D2 Dm…………………..

D2 Dm…………………..D

Io conosco una nuova soluzione ottima che contiene “D”.



Ora so che la fatina conosce una soluzione ottima che contiene il

divertimento “D”.

Ho finito tutti i divertimenti scelti finora. Ora scelgo il divertimento “D” che termina per primo tra quelli non

ancora iniziati.

Mumble… devo mostrare che esiste una soluzione ottima che contiene sia

“D” che tutti i divertimenti scelti prima.

Io conosco una soluzione ottima che contiene tutti i divertimenti

scelti finora da Pinocchio.

Insegnerò alla fatina come modificare la sua soluzione ottima in modo che

contenga anche “D”.

Ho finito tutti i divertimenti scelti finora ed ora ho scelto quel divertimento “D” che terminerà per primo tra quelli non

ancora iniziati.

Io conosco una soluzione ottima che contiene tutti i divertimenti scelti finora

da Pinocchio.

Io conosco una soluzione ottima che contiene i divertimenti scelti finora

compreso il divertimento “D”.

Mumble… se la soluzione della fatina contiene il divertimento “D” non ci sono

problemi.

Cara fatina, se la tua soluzione contiene il divertimento “D” lasciala invariata.

Primo caso:

Mumble… se la soluzione della fatina non contiene “D” devo metterlo al

posto di un altro.


da Pinocchio.

Non posso certo metterlo al posto di uno di quelli scelti prima e che so

essere tutti contenuti nella soluzione della fatina.

Non posso neppure metterlo al posto di uno già iniziato perché questi sono

incompatibili con quelli scelti prima.

Mumble… Il primo che nella soluzione della fatina segue quelli già scelti deve terminare dopo “D”. Quindi tutti gli altri

sono compatibili con “D”.

Cara fatina, se la tua soluzione non contiene il divertimento “D” mettilo al posto del primo divertimento che nella tua soluzione segue quelli già scelti da

Pinocchio.

Secondo caso:


ancora iniziati.

DD1 Dk Dm….. …..Dk+2

D1 Dk Dm….. Dk+1 …..Dk+2

ora attuale

Io conosco una nuova soluzione ottima che contiene i divertimenti scelti finora

da Pinocchio compreso “D”.

So che la fatina conosce una soluzione ottima che contiene tutti i divertimenti

scelti finora da Pinocchio compreso “D”.


ancora iniziati.


da Pinocchio.

Ho finito tutti i divertimenti scelti finora ma tutti gli altri sono già iniziati.

Mumble… la soluzione ottima della fatina contiene tutti i divertimenti scelti

finora e non ci sono altri divertimenti compatibili.

Quindi la soluzione ottima della fatina non contiene altri divertimenti e quelli

scelti finora da Pinocchio sono una soluzione ottima.

Strategie golose:Scegliere l’attività che inizia per prima

Scegliere l’attività che dura meno tempo

Non funziona

Non funziona

Scegliere l’attività incompatibile con il minor numero di altre attività

Non funziona

Strategia che funziona: Scegliere l’attività che termina per prima.

ActivitySelector(Att) AttScelte = Ø, AttComp = Att while AttComp ≠ Ø “ in AttComp scegli l’attività ‘a’ che termina per prima, aggiungi ‘a’ a AttScelte e togli da AttComp tutte le attività incompatibili con ‘a’ ” return AttScelte

Per implementarla supponiamo le attività a1,...,an ordinate per tempo di fine non decrescente f1 ≤ ... ≤ fn

Altrimenti possiamo ordinarle in tempo O(n log n)ActivitySelector(a, s, f, n) // f1 ≤ ... ≤ fn

A = {a1}, k = 1 for m = 2 to n if s[m] ≥ f[k] A = A {⋃ am}, k = m return A

1 1 4

isi fi

0 1 2 3 4 5 6 7 8 91011121314

tempo

a1 a2

a3

a4

a5

a6

a7

a8 a9

a10

a11

a1 a2

a3

a4

a5

a6

a7

a8 a9

a10

a11

2 0 5

3 1 6

4 5 7

5 3 8

6 5 9

7 610

8 811

9 812

10 213

111214

f[k]

ActivitySelector(a, s, f, n) A = {a1}, k = 1 for m = 2 to n if s[m] ≥ f[k] A = A {⋃ am}, k = m return A

La soluzione trovata contiene quattro attivitàDue domande:

1) La soluzione trovata con l’algoritmo goloso è l’unica possibile che contiene quattro attività?

2) La soluzione trovata con l’algoritmo goloso è ottima o esistono anche soluzioni con più di quattro attività?

1 1 4

isi fi

0 1 2 3 4 5 6 7 8 91011121314

tempo

a1 a2

a3

a4

a5

a6

a7

a8 a9

a10

a11

2 0 5

3 1 6

4 5 7

5 3 8

6 5 9

7 610

8 811

9 812

10 213

111214

Terzo passo: lunghezza di una LCS LCS-Length(X, Y, m, n) for i = 0 to m c[i, 0] = 0 for j = 1 to n...

Documents

Transcript of Terzo passo: lunghezza di una LCS LCS-Length(X, Y, m, n) for i = 0 to m c[i, 0] = 0 for j = 1 to n...