23/01/2014
Algoritmi e strutture di dati 2
Paola Vocca
Lezione 10: Algoritmi di approssimazione
Problemi di decisione
• un problema di decisione è un sottoinsieme
dell'insieme di tutte le possibili sequenze binarie, in
particolare tutte le sequenze che soddisfano una
determinata proprietà.
• un problema decisionale appartiene alla classese
esiste un algoritmo polinomiale A che, presa in ingresso
una sequenza binaria , determina se appartiene a o meno.
Lezione 10: Algoritmi di approssimazione
2
1
23/01/2014
La classe NP
•
•
Un problema in NP non ammette un algoritmo di risoluzione
polinomiale, e:
o se una sequenza appartiene a allora deve esistere una
dimostrazione breve (polinomiale) di questo fatto
o la dimostrazione può essere verificata in tempo polinomiale
Formalmente, NP include tutti i problemi di decisione per i
quali esiste un algoritmo polinomiale V e un polinomio tali
che, per ogni sequenza binaria :
o Completezza: se appartiene a , allora esiste un certificato
polinomiale (sequenza di lunghezza (||)) tale che V,
avendo in ingresso e , termina restituendo il valore TRUE;
o Consistenza: se non appartiene a , allora, per ogni
sequenza , V, avendo in ingresso e , termina restituendo il
valore FALSE.
Lezione 10: Algoritmi di approssimazione
3
P e NP
• La classe P è contenuta in NP.
• Dato un problema in P , con A un algoritmo di
risoluzione polinomiale per , possiamo definire V nel
modo seguente.
• Per ogni e , V con e in ingresso
o restituisce il valore TRUE se A con in ingresso risponde in
modo affermativo
o altrimenti restituisce il valore FALSE
• Chiaramente, V (per un qualunque polinomio e senza
usare ) soddisfa le condizioni di completezza e
consistenza sopra descritte: quindi, appartiene a NP.
Lezione 10: Algoritmi di approssimazione
4
2
23/01/2014
Riducibilità polinomiale
• Problemi , ′ ;
o polinomialmente riducibile a ′ se l'esistenza di un
algoritmo di risoluzione polinomiale per ′ implica
l'esistenza di un tale algoritmo anche per o polinomialmente trasformabile in ′ se esiste un
algoritmo polinomiale T tale che, per ogni sequenza
binaria , ∈ se e solo se T con in ingresso restituisce
una sequenza binaria in ′.
• polinomialmente trasformabile in ′ implica polinomialmente riducibile a ′.
• Se esiste un algoritmo polinomiale A di risoluzione per ′,
allora la composizione di T con A fornisce un algoritmo
polinomiale di risoluzione per .
Lezione 10: Algoritmi di approssimazione
5
Problemi NP-completi
Un problema di decisione è NP-completo se:
o appartiene a NP
o ogni problema in NP è polinomialmente trasformabile in e almeno tanto difficile quanto ogni altro problema in NP
Dimostrare che è in P, implica che l'intera classe NP è
contenuta in P (e quindi P=NP).
Lezione 10: Algoritmi di approssimazione
6
3
23/01/2014
Problemi NP-completi
Lezione 10: Algoritmi di approssimazione
7
Approssimazione
• Possibili approcci alla soluzione di problemi NP-completi
o Uso di tecniche non polinomiali (nel caso pessimo)
o Analisi nel caso medio
o Algoritmi di approssimazione
Lezione 10: Algoritmi di approssimazione
8
4
23/01/2014
Problemi di ottimizzazione
Problema di ottimizzazione
• =< , (), (), >:
o :istanze del problema
o :spazio di ricerca; data ∈ , ()indica le soluzioni
ammissibili di o : misura definita per coppie (, )tali che ∈ , ∈ ()
o : tipo di problema (max, min)
Lezione 10: Algoritmi di approssimazione
9
Tipi di problemi
• Tre problemi:
o Valore della soluzione ottima: data ∈ , il valore della
soluzione ottima è
∗ () = {(, )| ∈ ()}.
o Soluzione ottima: data ∈ una soluzione ottima è una
qualunque soluzione ∈ ∗ = ∈ , =
∗ ()}.
o Problema di decisione: data ∈ e ∈ ℕdecidere se
esiste tale che (, ) ≤ ( = min)o
o(, ) ≥
( = max).
Lezione 10: Algoritmi di approssimazione
10
5
23/01/2014
Esempio
Problema del commesso viaggiatore (Traveling Salesman
Problem: MIN-TSP).
o : grafi completi con pesi sugli archi
o : dato ( ∈ , (() = insieme dei possibili cicli Hamiltoniani su (
(permutazioni dei nodi di G che individuano un percorso che
visita esattamente una volta ogni vertice e torna al vertice di
partenza)
o :somma dei pesi degli archi appartenenti al ciclo
) , * , …, ,-* , )
o : min
• Tre problemi:
o dato (trovare il valore del ciclo di costo minimo
o dato (trovare un ciclo di costo minimo
o dato (e decidere se esiste un ciclo di costo ≤ .
Lezione 10: Algoritmi di approssimazione
11
Classe NPO
• Gli algoritmi di approssimazione sono interessanti
soprattutto per i problemi che hanno la versione di
decisione nella classe ..
• Classe Nondeterministic Polynomial Optimization
• Un problema di ottimizzazione =< , (), (), >
appartiene alla classe NPO se gode delle seguenti
proprietà:
o l’insieme è decidibile in tempo polinomiale;
o esiste un polinomio /tale che, data un’istanza ∈ , per
qualsiasi ∈ 01()vale che ∈ /(||);inoltre, per ogni
tale che || ≤ /(||),l’appartenenza a 01()è
decidibile in tempo polinomiale;
o la funzione misura ()è computabile in tempo
polinomiale.
Lezione 10: Algoritmi di approssimazione
12
6
23/01/2014
Classe PO
Lezione 10: Algoritmi di approssimazione
13
Algoritmi di approssimazione
• Dato un problema di ottimizzazione =< , (), (), >
un algoritmo di approssimazione è un algoritmo 3che
data un’istanza ∈ , fornisce una soluzione 3() = ∈
().
Valutazione dell’errore.
• Per determinare la qualità di un algoritmo di
approssimazione è necessario valutare l’entità
dell’errore delle soluzioni calcolate.
• Esistono due misure comuni per valutare la qualità di
una soluzione non esatta: l’errore relativo e il rapporto di
approssimazione.
Lezione 10: Algoritmi di approssimazione
14
7
23/01/2014
Errore relativo
Lezione 10: Algoritmi di approssimazione
15
Rapporto di approssimazione
In alternativa all’errore di approssimazione:
• Dato un problema di ottimizzazione ,
• per ogni istanza ∈ e per ogni soluzione ammissibile
∈ 01 (),
• Il rapporto di approssimazione di prestazione della
soluzione rispetto all’istanza è la quantità
, ∗ 45 , ≝ 7
,
∗ , • Nota: 45 , = * quando la soluzione è esatta, ≫ *
quando è di pessima qualità.
• Nota: Chiaramente i due indici sono collegati:
*
9::5 , = * − 4 ,
5
Lezione 10: Algoritmi di approssimazione
16
8
23/01/2014
Rapporto di approssimazione: Note
• Spesso può essere più intuitivo usare sempre il rapporto
,
che risulta ≤ *per problemi di massimizzazione e
∗
≥ *per problemi di minimizzazione.
• Chiaramente un algoritmo di approssimazione A per un
problema di ottimizzazione NP-hard è interessante se,
data un’istanza di , esso fornisce efficientemente,
cioè in tempo polinomiale in ||,una soluzione
approssimata A(x).
• In tal caso diciamo che A è un algoritmo di
approssimazione polinomiale e che è un problema
polinomialmente approssimabile.
Lezione 10: Algoritmi di approssimazione
17
Algoritmo di approssimazione:
Esempio
Esempio. Si consideri il seguente algoritmo per MAX-SAT:
• Maximum Satisfiability problem (MAX-SAT) è il problema di
determinare il massimo numero di clausole di una
determinata formula booleana, che possono essere
soddisfatte da un’assegnazione di verità.
ALGORITMO GREEDY SAT (Tecnica greedy)
Data una formula < = {=*, =>, … , =} ∈ ?.@:
ripeti
1. scegliere un letteraleAtra quelli che occorrono il massimo
numero di volte (affermato o negato);
2. seA = porre x=V
3. se A = ¬porre x=F
4. cancellare le clausole in cui occorre Ae cancellare ¬Adalle
altre finché <è vuota.
Lezione 10: Algoritmi di approssimazione
18
9
23/01/2014
Dimostrazione di approssimazione
Teorema L’algoritmo Greedy Sat è 2-approssimato.
Dimostrazione. Per induzione sul numero ,di variabili. Supponiamo di
avere clausole.
• Passo base: se , = * il risultato è vero.
• Ipotesi induttiva: supponiamo che l’enunciato del teorema sia
soddisfatto nel caso di , − * variabili ed ’clausole. L’algoritmo
garantisce dunque il soddisfacimento di almeno ’/>clausole.
• Supponiamo ora di avere ,variabili. Sia AG = G il letterale che
compare più.
• Supponiamo che Gcompaia =* volte e ¬Gcompaia => volte con
=* ≥ => .
• Assegnando a G valore H :soddisfiamo =* clausole. Ora
abbiamo una formula con , − *variabili ed ’ ≥ − =* − =>
clausole. Per ipotesi induttiva di queste ne possiamo soddisfare
almeno ’/>e quindi in tutto possiamo soddisfare =* + ’/> ≥
=* + ( − =* − => )/> ≥ />clausole. QED
Lezione 10: Algoritmi di approssimazione
19
Algoritmo di approssimazione
Lezione 10: Algoritmi di approssimazione
20
10
23/01/2014
Algoritmo di approssimazione
Lezione 10: Algoritmi di approssimazione
21
Algoritmo di approssimazione
Definizione con il rapporto di approssimazione
• Dato un algoritmo A per un problema di ottimizzazione • Data una costante: ≥ *,
o si dice che A è un algoritmo :-approssimante se e solo per
qualsiasi input , il rapporto di approssimazione della
soluzione determinata è inferiore alla costante ::
4(, 3 ) ≤ :
Nota!
• Un algoritmo esatto è 1-approssimante.
Lezione 10: Algoritmi di approssimazione
22
11
23/01/2014
Rapporto di approssimazione: Proprietà
Lezione 10: Algoritmi di approssimazione
23
Problema approssimabile
Lezione 10: Algoritmi di approssimazione
24
12
23/01/2014
Problema approssimabile
• Anche se alcuni problemi di ottimizzazione in NPO hanno
la versione di decisione NP-completa, risultano essere
sono molto diversi da un punto di vista
dell’approssimabilità.
• Accade infatti che:
o alcuni problemi sono approssimabili per valori di : ≥ ,
dove > *è una costante caratteristica del problema e
prende il nome di soglia di approssimazione;
o alcuni problemi sono approssimabili per valori di : >
*arbitrariamente vicini ad *.
o alcuni problemi non sono approssimabili per alcun
:costante;
Lezione 10: Algoritmi di approssimazione
25
Problema del commesso viaggiatore
Lezione 10: Algoritmi di approssimazione
26
13
23/01/2014
Problema del commesso viaggiatore:
NP-completezza
•
•
Teorema. Ciclo hamiltoniano è trasformabile in tempo
polinomiale nella versione decisionale del problema del
commesso viaggiatore.
Dimostrazione. Dato un grafo ( = (H, 9), definiamo un grafo
completo () = (H, 9) ) e una funzione tale che, per ogni
arco ∈ 9) , ( ) = * se ∈ 9, altrimenti ( ) = >. Scegliendo
= |H|, abbiamo che se esiste un ciclo hamiltoniano in (,
allora esiste un tour in () il cui costo è uguale a . Viceversa,
se non esiste un ciclo hamiltoniano in (, allora ogni tour in ()
deve includere almeno un arco il cui peso sia pari a 2, per cui
ogni tour ha un costo almeno pari a + *.
•
Iil problema del commesso viaggiatore (nella sua forma
decisionale) è NP-completo.
•
il problema di ottimizzazione non ammette neanche un
algoritmo efficiente di approssimazione.
Lezione 10: Algoritmi di approssimazione
27
Problema del commesso viaggiatore:
non approssimabilità
Teorema. Sia : > *una qualsiasi costante, non esiste alcun algoritmo di
: −approssimazione di complessità polinomiale per il problema del
commesso viaggiatore a meno che . = .
Dimostrazione. Per assurdo, sia : > *una costante e sia A un algoritmo
polinomiale di : −approssimazione per TSP.
Dato un grafo ( = (H, 9), definiamo un grafo completo () = (H, 9) ) e
una funzione tale che, per ogni arco ∈ 9), ( ) = * se ∈ 9,
altrimenti ( ) = 1+s|V|, dove > : − *.
• () ammette un tour di costo|V| sse (ha un circuito hamiltoniano
(un tale tour deve necessariamente usare archi di peso pari a *).
• Sia Jil tour di TSP che viene restituito da A con () in ingresso.
• Jpuò essere usato per decidere se (ammette un HC, se :
1.
2.
Il costo di J è uguale a|V|, per cui è tour ottimo. Allora (ammette
un ciclo hamiltoniano.
Il costo di J è maggiore di|V|, per cui il suo costo deve essere
almeno pari a |H| − * + * + |H| = (* + )|H| > :|H|. In questo caso, il
tour ottimo non può avere costo pari a |H|, in quanto altrimenti il costo
di J è maggiore di :volte il costo ottimo, allora A non è un algoritmo
di r-approssimazione:
quindi, non esiste un ciclo hamiltoniano in G. 28
Lezione 10: Algoritmi di approssimazione
14
23/01/2014
Tecnica del gap e risultati di non
approssimabilità
: problema di minimizzazione
1: un linguaggio NP-completo
Se esistono due funzioni K e =tali che
• Ktrasforma istanze del problema di decisione associato
ad 1in istanze di e, per un opportuno valore ‘gap’:
o se ∈ 1 allora ∗ K o se ∉ 1 allora
∗ (K())
≤= ≥ =()(* + M7).
• allora per non può esistere alcun algoritmo
: −approssimato con : < (* + M7)a meno che non sia
P=NP.
Lezione 10: Algoritmi di approssimazione
29
Tecnica del gap: Dimostrazione
• DIMOSTRAZIONE. Supponiamo per assurdo che 3sia un
algoritmo : −approssimato per e che : < * + M7. Per
decidere in tempo polinomiale se ∈ 1 o meno
possiamo procedere nel seguente modo. Calcoliamo
l’istanza K() del problema e poi applichiamo
l’algoritmo approssimato 3ad K() .
o Se abbiamo (K(), 3(K())) ≥ =()(* + M7)ciò implica
∗ (K()) > =()e quindi ∉ 1. Infatti abbiamo:
(* + M7)∗ (K()) > :∗ () ≥ (K(), 3(K()))
≥ =()(* + M7)
o Al contrario, se (K(), 3(K())) < =()(* + M7)a maggior
ragione∗ (K()) < =()(* + M7)e quindi ∈ 1.
o QED
Lezione 10: Algoritmi di approssimazione
30
15
23/01/2014
Minimum vertex cover
• Vertex Cover: Una copertura tramite vertici di un
( = (H, 9) non orientato è un sottoinsieme dei suoi
vertici tale che ogni arco ha almeno un'estremità in .
• Vertex Cover è NP-Completo
il problema di
ottimizzazione associato Minimo Ricoprimento di Vertici
è NPO.
Lezione 10: Algoritmi di approssimazione
31
Minimum vertex cover
Lezione 10: Algoritmi di approssimazione
32
16
23/01/2014
Minimum vertex cover
Lezione 10: Algoritmi di approssimazione
33
Minimum vertex cover
Lezione 10: Algoritmi di approssimazione
34
17
23/01/2014
Minimum vertex cover
Lezione 10: Algoritmi di approssimazione
35
Minimum vertex cover
Lezione 10: Algoritmi di approssimazione
36
18
23/01/2014
Vertex cover
• L’insieme trovato rappesenta un matching
Lezione 10: Algoritmi di approssimazione
37
Schemi di approssimazione
• Un algoritmo 3(, N)si chiama schema di
approssimazione polinomiale (PTAS) per un problema di
ottimizzazione se per ogni valore N esiste un polinomio
/tale che, per ogni istanza di l’algoritmo restituisce
una soluzione approssimata tale che l’errore relativo
9::(, ) ≤ N,in tempo limitato da /(||).
o Si noti che in questo caso il grado del polinomio può
dipendere da N .
• Un algoritmo 3(, N)si chiama schema di
approssimazione pienamente polinomiale (FPTAS) per
un problema di ottimizzazione se esiste un polinomio
/tale che, per ogni istanza di e per ogni valore N
l’algoritmo restituisce una soluzione approssimata tale
che 9::(, ) ≤ N,in tempo limitato da /( , */N)
Lezione 10: Algoritmi di approssimazione
38
19
23/01/2014
Min Parttion: PTAS
Lezione 10: Algoritmi di approssimazione
39
Algoritmo Min Partition
ALGORITMO MinPartition
{basato su sulla tecnica di completamento}
1. Data un’istanza del problema costituita da un insieme di
oggetti con pesi 7* , … , 7, , e un valore : > *:
2. ordinare gli oggetti in ordine di peso non crescente;
3. definire = (> − :)/(: − *) (ad esempio: se: = **/*),
= O);
4. individuare una partizione ottima dei primi elementi;
5. inserire i rimanenti elementi via via nell’insieme di peso
minore.
Lezione 10: Algoritmi di approssimazione
40
20
23/01/2014
Algoritmo Min Partition:
Dimostrazione
•
•
Th: L’algoritmo MinPartition è uno schema di approssimazione
:-approssimante che richiede tempo 0(,log, + > )
Dimostrazione. Assumiamo che:
o 7* , … , 7, siano i pesi degli oggetti ordinati in modo non
crescente,
o 3*ed 3>siano gli insiemi creati dall’algoritmo, <(3*)e <(3>)
siano i loro pesi e <(3*) > <(3>),
o ∗ () sia il valore della soluzione ottima,
o RST1 = (<(3*) + <(3>))/> ≤ ∗ () (la media dei pesi èun
lower bound per ogni soluzione)
o sia : < >,
o Sia 7A l’ultimo oggetto inserito in A1 con l > k (quindi solo parte
degli oggetti sono stati distribuiti in modo ottimo).
o Abbiamo dunque:
<(3*)– 7A ≤ <(3>) = >1– <(3*)
Lezione 10: Algoritmi di approssimazione
41
Algoritmo Min Partition:
Dimostrazione (2)
al
V
,
WXAY*
7W
Z(3*)
Z(3>)
Lezione 10: Algoritmi di approssimazione
42
21
23/01/2014
Algoritmo Min Partition:
Dimostrazione (3)
•
•
•
•
e quindi <(3*)– 1 ≤ 7A />.
Inoltre 7A ( + *) ≤ >1e quindi 7A />1 ≤ */( + *).
<(3*)/∗ () ≤ <(3*)/1 ≤ * + 7A />1 ≤ * + */( + *)
≤ * + */((> − :)/(: − *) + *) ≤ :
Per quanto riguarda il tempo di esecuzione abbiamo:
o 0(,log,)per ordinare gli oggetti,
o 0(> )per effettuare il partizionamento ottimo dei primi oggetti,
o 0(,)per inserire gli ultimi ,– oggetti.
o In totale 0(,log, + > )QED
Come si vede il costo è polinomiale se si assume fissato,
altrimenti sarebbe esponenziale in (sostanzialmente,
esponenziale in */:).
Lezione 10: Algoritmi di approssimazione
43
Knapsack: FPTAS
Esempio di schema di approssimazione pienamente polinomiale.
• Per fornire un esempio di problema che ammette uno
schema di approssimazione polinomiale pieno, dobbiamo
prima introdurre il problema dello knapsack (bisaccia) ed
illustrare l’algoritmo per la sua soluzione ottima.
• MAX KNAPSACK: dato un insieme di oggetti dotati di:
o pesi interi 7* , … , 7,
o profitti interi * , … , ,
o Un ntero Z(capacita),
• individuare un sottoinsieme di tale da massimizzare ∑,\X* \
con il vincolo ∑,\X* 7\ ≤ ].
Abbiamo già visto un algoritmo pseudopolinomiale
basata sulla tecnica di programmazione dinamica
Θ(,Z)
Lezione 10: Algoritmi di approssimazione
44
22
23/01/2014
Knapsack: FPTAS
Nota bene. Tempo di esecuzione pseudopolinomiale:
polinomiale non nella taglia dell’input ma nei valori che
compaiono nell’input!
• Il seguente algoritmo è uno schema di approssimazione
pienamente polinomiale.
ALGORITMO APPROX-BISACCIA
(Tecnica di scalatura, o partizionamento fisso)
Data un’istanza I del problema MAX KNAPSACK e dato un
valore ^ ≤ *:
1. sia = ^7 /,;
2. creare una nuova istanza ′ con pesi 7* , … , 7, , e profitti
′* , … , ′, con ′, = , /;
3. risolvere ′ in modo esatto con l’algoritmo di
programmazione dinamica;
4. determinare 3 () = (’).
•
Lezione 10: Algoritmi di approssimazione
45
FPTAS per Knapsack: Dimostrazione
Dimostrazione.
• Errore compiuto ad ogni passo ≤ .
• Errore totale ≤ ,.
• Errore relativo ≤ ,/∗ () ≤ ,/7 ≤ ^.
• Tempo di esecuzione 0(,> ′7 ) = 0((,> 7 /) =
0((,_ /^). QED
Lezione 10: Algoritmi di approssimazione
46
23
23/01/2014
Classi di approssimabilità
• APX: classe di problemi di ottimizzazione in .0che
ammettono un algoritmo polinomiale :-approssimato
per un opportuno :.
• PTAS: classe di problemi di ottimizzazione in .0che
ammettono uno schema di approssimazione
polinomiale.
• FPTAS: classe di problemi di ottimizzazione in .0che
ammettono uno schema di approssimazione
pienamente polinomiale.
• E’ possibile dimostrare che, se ≠ ., allora
.0 ⊃ 3b ⊃ J3 ⊃ @J3 ⊃ 0
Lezione 10: Algoritmi di approssimazione
47
Relazioni fra le classi di complessità
Lezione 10: Algoritmi di approssimazione
48
24
© Copyright 2024 ExpyDoc
