algoritmi
approssimati
1/15
Algoritmi approssimati
Per qualche problema NP-completo esistono algoritmi polinomiali che
ritornano soluzioni “quasi ottime”.
Un algoritmo approssimato A ha scostamento garantito r(n) se per ogni
input di dimensione n il costo C della soluzione prodotta da A si
discosta per un fattore r(n) dal costo C* di una soluzione ottima:
max(C/C*, C*/C)≤ r(n)
l’errore relativo  di un algoritmo approssimato A è dato da |C-C*|/C*.
L’algoritmo A ha un errore relativo limitato da (n) se
|C-C*|/C* ≤ (n)
2/15
Schemi di approssimazione
Uno schema di approssimazione (SdA) per un
problema di ottimizzazione è un algoritmo
approssimato A che prende in input un’istanza di un
problema e un qualsiasi valore >0 ed è in grado di
risovere l’istanza con errore relativo limitato da .
Uno schema di approssimazione polinomiale è uno
SdA che per qualsiasi >0 dato richiede un tempo
polinomiale rispetto a n per risolvere il problema.
Uno SdA pienamente polinomiale (fully polynomial
approximation scheme) è uno SdA polinomiale il cui
tempo di esecuzione è polinomiale sia per 1/ che per
la dimensione n dell’input dell’istanza.
3/15
Vertex cover
Vertex cover. Dato un grafo G trovare un sottinsieme S
di dimensione minima dei vertici di G, tale per cui ogni
arco abbia almeno un vertice in S.
Vertex cover è NP-completo (riduzione da sottografo
completo).
4/15
Vertex cover
Algoritmo approssimato per vertex cover:
S = 
E = E[G]
while E
sia (u,v) un arco arbitrario in E
S = S  {u,v}
togli da E ogni arco incidente in u o in v
return S
5/15
Vertex cover: esempio
b
c
d
a
e
f
g
6/15
Vertex cover: esempio
b
c
d
a
e
f
g
7/15
Vertex cover: esempio
b
c
d
a
e
f
g
8/15
Vertex cover: esempio
b
c
d
a
e
f
g
9/15
Vertex cover: esempio
cover ottima
b
c
d
a
e
f
g
10/15
Vertex cover: esempio
Teorema
L’algoritmo presentato trova un insieme S che è una
copertura dei vertici e che non contiene più del doppio del
numero dei vertici in una vertex cover minima.
Questo algoritmo approssimato ha rapporto limite pari a 2.
11/15
Il problema del commesso viaggiatore
Nel problema del commesso viaggiatore (TSP), dato
un grafo completo non orientato pesato G=(V,E,w),
con costi interi non negativi, si deve trovare un ciclo
hamiltoniano su G di costo minimo.
Ipotesi: è sempre più economico andare direttamente
da un posto u a un posto v direttamente piuttosto che
passando per stazioni intermedie w (disuguaglianza
triangolare).
12/15
Approx-TSP
Un algoritmo approssimato per TSP con
disuaglianza triangolare è:
Approx-TSP-Tour(G,w)
1 seleziona un vertice radice rV
2 costruisci un MST T per G dalla radice r
3 sia L la lista dei vertici visitati con la
visita in ordine anticipato di T
4 return il ciclo hamiltoniano H che visita i
vertici nell’ordine di L
13/15
Approx-TSP: esempio
a
d
e
b
f
g
c
h
14/15
Approx-TSP: esempio
a
d
e
b
f
g
c
h
15/15
Approx-TSP: esempio
a
d
e
b
f
g
c
h
16/15
Approx-TSP: esempio
a
d
e
b
f
g
c
h
17/15
Approx-TSP: grado
Teorema
Approx-TSP-Tour è un algoritmo
approssimato con grado limite pari a 2 per il
problema TSP che soddisfa la disuguaglianza
triangolare
18/15
Altri problemi
Esistono molti problemi per i quali sono stati
definiti algoritmi approssimati.
Ad esempio:
Set Covering
Subset Sum
...
19/15