Teoria della complessità

KNAPSACK

Nel problema (o problema dello zaino), dati n

KNAPSACK

oggetti aventi come pesi gli interi positivi e come

p , . . . , p

1 n

valori gli interi positivi e dato uno zaino con

n v , . . . , v

1 n

capacità pari a un intero positivo , vogliamo individuare un

b P

sottinsieme degli oggetti con peso complessivo p

K n i

i∈K

P massimo.

non superiore a e valore complessivo v

b i

i∈K – p. 9/65

Difficoltà problemi di ottimizzazione

Dato un problema di ottimizzazione il nostro scopo è

ovviamente risolverlo, restituendone una soluzione ottima e

il valore ottimo.

Per risolverlo abbiamo bisogno di un algoritmo di

A

risoluzione per il problema, ovvero una procedura che,

ricevuti in input i dati che definiscono un’istanza, restituisce

in output proprio una soluzione ottima e il valore ottimo di

quell’istanza. – p. 10/65

Esistenza algoritmo

Se ci limitiamo ai problemi di ottimizzazione combinatoria in

cui la regione ammissibile è costituita da un numero finito di

elementi (vale per i problemi , ,

MST SHORTEST PATH

, , ), è abbastanza semplice

CLIQUE TSP KNAPSACK

identificare un algoritmo di risoluzione.

Infatti se la regione ammissibile contiene un numero finito

S enumerazione

di elementi la seguente procedura, detta di

risolve il problema: valutare la funzione per

completa, f

ogni elemento in e restituire l’elemento con valore di

S f

minimo (o massimo se il problema è di massimo). – p. 11/65

Tuttavia ...

... una semplice osservazione metterà in luce i limiti di

questo approccio.

Consideriamo il problema su un grafo con numero di

TSP

= 22

nodi . Abbiamo osservato come in tale grafo il

n 19

−

(n 1)! = 21! 10

numero di circuiti hamiltoniani è pari a .

>

Supponiamo (ottimisticamente) che la valutazione della

funzione obiettivo per un singolo circuito hamiltoniano

−9

10

richieda un nanosecondo ( secondi).

Ne consegue che la valutazione di tutti i circuiti hamiltoniani

10

10

richiede più di secondi che corrispondono ad un tempo

superiore ai 200 anni. – p. 12/65

Continua

Ancora più impressionante è notare quello che succede se

si aumenta di uno il numero di nodi: il tempo richiesto

supera i 4000 anni!

Ciò dimostra che sebbene sia sempre possibile

teoricamente risolvere tali problemi, in pratica dobbiamo

fare i conti con dei limiti temporali e quindi, da un punto di

vista pratico, si parlerà di problema risolvibile con una data

procedura solo nel caso in cui la procedura restituisca una

soluzione in tempi ragionevoli.

Ciò rende la procedura di enumerazione completa

accettabile solo per istanze di problemi di dimensioni

limitate (quindi, ad esempio, per grafi con pochi nodi per i

problemi ).

TSP – p. 13/65

Domanda

Esistono altre procedure che consentono di risolvere in tempi ragionevoli istanze dei

problemi con dimensioni molto più elevate?

La risposta è: dipende dal problema.

È in generale vero che esistono procedure molto più efficienti dell’enumerazione completa

ma mentre per alcuni (come il problema ) si possono risolvere in tempi ragionevoli

MST

istanze di grandi dimensioni, per altri, come il problema e, ancor più, per il

KNAPSACK

problema può essere difficile risolvere anche istanze di dimensioni non troppo elevate

TSP

(si osservi il può: con algoritmi sofisticati si sono risolte anche istanze di con più di

TSP

15000 nodi, ma gli stessi algoritmi possono essere messi in crisi da istanze più piccole).

Tutto ciò ha una formulazione ben precisa nella teoria della complessità, alla quale

giungeremo dopo aver discusso di complessità degli algoritmi. – p. 14/65

Complessità

→

Dimensione istanza = quantità di memoria

I dim(I)

necessaria per memorizzare (in codifica binaria) l’istanza .

I

A

Procedura di risoluzione o algoritmo per il problema. A

(I) = numero di operazioni elementari eseguite da

numop A

per risolvere .

I – p. 15/65

Analisi worst case

(k)

L’analisi worst case definisce il tempo necessario

t A

A

all’algoritmo per risolvere istanze di dimensione come il

k

massimo tra tutti i tempi di esecuzione di istanze di

dimensione , cioè

k (k) = max (I).

t numop

A A

I: dim(I)=k – p. 16/65

Continua

Tipicamente non si conosce l’espressione analitica della

(k)

funzione ma se ne conosce l’ordine di grandezza. Si

t A (k) = (k)

dice che la funzione , ovvero che è

t O(g(k)) t

A A

dell’ordine di grandezza della funzione , se esiste una

g(k)

0

costante tale che

u > ≤

(k)

t ug(k).

A – p. 17/65

g

Diverse possibili funzioni

= 10 = 20 = 30 = 40 = 50

g(k) k k k k k

log (k) 3.32 4.32 4.90 5.32 5.64

2 10 20 30 40 50

k

2 100 400 900 1600 2500

k 3 1000 8000 27000 64000 125000

k 6 9 12 15

k

2 10 10 10 10

1024 > > > >

18 32 47 64

10 10 10 10

3628800

k! > > > > – p. 18/65

Complessità degli algoritmi

(k)

Un algoritmo per il quale fosse dell’ordine di

t A

k

2 complessità

grandezza di oppure si dice che ha

k!

esponenziale. È evidente che un tale algoritmo consente di

risolvere in tempi ragionevoli solo istanze di dimensioni

limitate.

Per questa ragione si cercano per i problemi algoritmi di

complessità polinomiale, in cui cioè la

risoluzione con p

funzione è dell’ordine di grandezza di un polinomio

t k

A

per un qualche esponente .

p – p. 19/65

Continua

Tanto maggiore è l’esponente del polinomio, quanto più

p

rapidamente cresce il numero di operazioni dell’algoritmo al

crescere di e quindi quanto più piccole sono le dimensioni

k

dei problemi che l’algoritmo è in grado di risolvere in tempi

= 4

ragionevoli (già per la crescita è piuttosto rapida).

p

Tuttavia la crescita polinomiale è sempre preferibile ad una

esponenziale. – p. 20/65

Domanda

Data una classe di problemi di ottimizzazione combinatoria,

possiamo sempre trovare un algoritmo con complessità

polinomiale che ne risolva le istanze?

Risposta: forse, ma è molto improbabile.

Vedremo di chiarire nel seguito il senso di questa risposta

introducendo qualche elemento di teoria della complessità.

Prima però prendiamo in esame algoritmi di risoluzione per

alcuni dei problemi di ottimizzazione precedentemente

discussi. – p. 21/65

Algoritmi per SHORTEST PATH

Per questo problema abbiamo presentato due algoritmi:

≥ ∀ ∈

0 (i,

Algoritmo di Dijkstra: valido solo se .

d j) A

ij ∈

Restituisce i cammini minimi tra un nodo fissato e

s V

tuuti gli altri nodi del grafo.

Algoritmo di Floyd-Warshall: valido anche per distanze

negative a patto che non ci siano cicli di lunghezza

negativa. Restituisce i cammini minimi tra tutte le

coppie di nodi del grafo se il grafo non contiene cicli a

costo negativo. In quest’ultimo caso restituisce un ciclo

a costo negativo. – p. 22/65

Complessità algoritmi

L’algoritmo di Dijkstra richiede un numero di operazioni

2 ) .

O(n

L’algoritmo di Floyd-Warshall richiede un numero di

3 )

operazioni .

O(n – p. 23/65

Algoritmi visti per MST

| |))

log(|

Algoritmo greedy (complessità );

O(| E E

2

| )

algoritmo MST-1 (complessità );

O(| V | |))

log(|

algoritmo MST-2 (complessità ).

O(| E V – p. 24/65

Problemi di riconoscimento

Se fino a ora abbiamo parlato di problemi di ottimizzazione,

nella teoria della complessità si parla generalmente di

problemi di riconoscimento.

problemi di ottimizzazione: vogliamo restituire soluzione

ottima e valore ottimo dell’istanza di un problema;

problemi di riconoscimento: l’output è semplicemente

un SI oppure un NO. – p. 25/65

Esempi

Date variabili booleane

n x , . . . , x

Satisfiability 1 n

e una formula booleana in forma normale disgiuntiva

(AND di un certo numero di clausole, dove ogni

m

clausola è un OR di variabili booleane eventualmente

negate), si vuole stabilire se esiste un assegnamento di

valori alle variabili booleane che rende vera la formula.

Come ma con

3-Satisfiability Satisfiability

non più di tre variabili booleane (eventualmente negate)

in ogni clausola. = (V,

Dato un grafo ,

G E)

Circuito hamiltoniano

stabilire se esiste un circuito hamiltoniano in tale grafo. – p. 26/65

Osservazione

Sotto ipotesi deboli, per ogni problema di ottimizzazione, ne

esiste uno corrispondente di riconoscimento di difficoltà

analoga:

problema di ottimizzazione di minimo (analogo per

(f,

massimo) con istanze tali che:

S)

esistano e (legate ai dati del problema attraverso

L U ≤ ≤

(x)

espressioni polinomiali) tali che per ogni

L f U

∈ ;

x S

la funzione obiettivo assume solamente valori interi su

.

S

Problema di riconoscimento corrispondente: ∈

(f,

dati e un valore intero , stabilire se esiste un

S) B x S

≤

(x)

tale che .

f B – p. 27/65

Esempi = (V,

ottimizzazione: dato un grafo ,

G E)

CLIQUE

individuare una clique (sottografo completo) di

riconoscimento: dato un intero

cardinalità massima;

≤| |

positivo , stabilire se nel grafo esiste una clique

k V

di cardinalità almeno pari a (in questo caso possiamo

k

|

= 1 =|

scegliere e ).

L U V = (V,

ottimizzazione: dato un grafo completo G E)

TSP

e le distanze con distanze interie non negative , per

d ij

∈

(i,

ogni , individuare nel grafo un circuito

j) E riconoscimento:

hamiltoniano di distanza totale minima;

dato un intero , individuare nel grafo un circuito

B

hamiltoniano di distanza totale non superiore a (in

B

|

=| min

questo caso possiamo scegliere e

L V d ij

(i,j)∈E

|

=| max ).

U V d ij

(i,j)∈E – p. 28/65

ottimizzazione: dati oggetti aventi come

n

KNAPSACK

pesi gli interi e come valori gli interi

p , . . . , p n

1 n

e dato uno zaino con capacità p