Introduzione
Il QAP consiste nell’allocazione di Attività in Stazioni di lavoro
(Locazioni) con lo scopo di minimizzare una specifica funzione obiettiva
che rappresenta il costo di trasporto totale che risulta dall’assegnamento.
L’inclusione di tale problema nella classe di problemi NP non dimostra
certamente la sua intrattabilità, però, permette di ipotizzare una possibile
intrattabilità.
Per giustificare una tale affermazione [5], si distingue tra due casi:
1. Una soluzione è cercata per mezzo di algoritmi che garantiscono
ottimalità;
2. Si è soddisfatti di ottenere una soluzione prossima all’ottima attraverso
degli approcci euristici, o delle riformulazioni del problema che
permettano l’impiego di algoritmi efficienti.
Nel primo capitolo sono illustrati in maniera non formale i problemi
appartenenti alle classi P, NP, e i problemi NP-hard.
Inoltre, sono formulate alcune definizioni essenziali che saranno utili per
una successiva formalizzazione, tra queste: istanza, algoritmo, lunghezza
d’ingresso, funzione della complessità del tempo, schema codificato,
modello di calcolo.
Gli algoritmi polinomiali ed esponenziali nel tempo sono introdotti,
poiché, la loro distinzione è rilevante per la nozione d’intrattabilità e per la
teoria della NP-completezza.
Un problema, infatti, risulta intrattabile se può risolversi con un algoritmo
polinomiale nel tempo, mentre intrattabile se tutti i suoi algoritmi risolutivi
hanno una complessità superiore a quella polinomiale.
Si vedrà inoltre, come la teoria della NP-completezza restringa la sua
attenzione unicamente a problemi, detti di decisione, in altre parole a
problemi caratterizzati da solo due possibili soluzioni, una risposta sì o una
no.
Nel secondo capitolo sono presentati i principali modelli di calcolo
necessari per formalizzare la nozione di algoritmo.
Introduzione
Tali modelli sono:
1. La macchina di Turing deterministica (DTM);
2. La macchina di Turing non deterministica (NDTM);
3. La macchina di Turing oracolo (OTM).
Tali macchine possono considerarsi come strumenti in grado di riconoscere
un determinato Linguaggio (Problema di Decisione) ed inoltre, per
classificare i problemi sulla base della loro complessità.
Si dirà, precisamente, che un problema appartiene alla Classe P o alla
Classe NP se esiste rispettivamente, una macchina DTM polinomiale nel
tempo o NDTM polinomiale nel tempo che riconosce il corrispondente
linguaggio.
Dalla relazione tra la Classe P e NP scaturisce che la prima Classe è
contenuta nella seconda; questo implica che un problema che può essere
risolto con un algoritmo polinomiale nel tempo deterministico può
risolversi anche con uno non deterministico.
Non è semplice determinare se un problema ΠΠ appartenente alla Classe NP
è NP-completo; tutto, però, si semplifica notevolmente nel caso in cui si
possiede un problema ΠΠ ′ ′′ che è noto essere NP-completo.
In questo caso, infatti, basta semplicemente mostrare che esiste una
trasformazione polinomiale da ΠΠ ′ ′′ a ΠΠ , in altre parole, che esiste una
funzione f che trasforma ogni istanza di ΠΠ ′ ′′ in una corrispondente istanza
di ΠΠ (f deve soddisfare, però, due proprietà: si veda par. 2.4).
La macchina di Turing Oracolo permette di introdurre la nozione di
riduzione di Turing polinomiale nel tempo la quale rappresenta una
generalizzazione di trasformazione polinomiale.
Infine, sono definiti i problemi NP-hard che sono problemi estranei alla
classe NP ma, che risultano comunque at least as hard quanto quelli NP-
completi.
La nozione di riduzione di Turing polinomiale nel tempo è essenziale per
dimostrare la NP-equivalenza del QAP.
Introduzione
Nel capitolo successivo è illustrato l’utilizzo della NP-completezza per
analizzare i problemi, concludendo la parte teorica relativa ai problemi
NP.
Il quarto capitolo espone il Problema dell’Assegnamento Quadratico
dandone anche una formulazione per mezzo di grafi.
Inoltre, si dimostra che il QAP è NP-hard, anzi NP-equivalente, in altre
parole, esiste una riduzione di Turing ad un problema che è noto essere
NP-completo (si veda par. 4.2).
Nel quinto capitolo sono descritte alcune applicazioni, in particolare:
1. Il QAP senza vincoli;
2. Il QAP con vincoli;
3. Un controesempio del QAP senza vincoli.
La prima esemplificazione considera il caso in cui tutte le Locazioni sono
collegate e, le Attività possono assegnarsi a qualsiasi Locazione; gli unici
vincoli impliciti al problema sono che ogni Locazione può ospitare una
sola Attività, e tutte le Attività devono essere allocate.
Date le difficoltà per ottenere una soluzione esatta in questo caso,
attraverso un algoritmo di tipo GREEDY è possibile trovarne una almeno
subottima.
La tecnica impiegata è la seguente:
le due Attività A
i
ed A
j
il cui c
ij
(quantità di risorse scambiata tra A
i
ed A
j
)
è più elevato sono assegnate alle due Locazioni S
h
e S
k
più vicine.
Si tratta, in altre parole, di ordinare i costi in senso decrescente e le
distanze in quello crescente e in seguito eseguire i vari assegnamenti.
Nel nostro esempio, la soluzione trovata è proprio quella ottima, e questo è
dimostrato applicando l’algoritmo a tutte le possibili permutazioni della
matrice dei costi.
Nel caso in cui le Locazioni non sono tutte collegate tra di loro, non è detto
che una soluzione sia possibile, poiché, può accadere che alcune Attività
non possano allocarsi oppure, che due Attività siano assegnate a due
Locazioni non raggiungibili.
Introduzione
Nella seconda applicazione sono imposti due vincoli, che sono:
1. Le Locazioni non sono tutte tra di loro collegate ed inoltre;
2. Le Attività possono assegnarsi solo a specifiche Locazioni.
In questo caso, ottenere una soluzione risulta piuttosto complicato poiché,
si deve tenere conto delle due restrizioni; per questo motivo, si applicherà
una procedura detta di scambio che permetterà di cercare, se esiste, una
possibile soluzione.
Inizialmente, sarà impiegato uno scambio singolo, in altre parole,
un’Attività sarà scambiata con un’altra applicando, successivamente,
l’algoritmo Greedy; se dopo aver eseguito tutti i possibili scambi non è
trovata nessuna soluzione, allora sarà applicato uno scambio doppio, in
pratica, due Attività alla volta.
Nel nostro esempio, a questo punto, si ottiene una soluzione; naturalmente,
questo non sempre accade.
Nell’ultima applicazione è mostrato come la soluzione trovata con
l’algoritmo Greedy non sempre sia quella ottima.
Tale soluzione è confrontata con quella cercata attraverso il calcolo di tutte
le permutazioni della matrice dei costi; in questo caso, si ottiene una
soluzione migliore di quella precedente.
In altri casi, le soluzioni subottime sono accettabili, specialmente quando è
praticamente impossibile trovarne una ottima.
Nell’Appendice sono raccolti i programmi relativi alla soluzione del QAP
senza vincoli (si veda Programma Principale1), del QAP nel caso in cui,
le Locazioni non sono tutte tra di loro collegate (si veda Programma
Principale2), del QAP che considera tutte le possibili permutazioni della
matrice dei costi (si veda variante del Programma Principale1 e del
Programma Principale2).
2
CAPITOLO 1
I Problemi NP
1.1 Alcune importanti definizioni
[1] In termini formali, un problema è una questione generale cui si deve
rispondere, normalmente avendo a disposizione diversi “parametri”, o
variabili libere, i cui valori non sono ben specificati.
Un problema può essere così definito:
1. Descrizione generale di tutti i suoi parametri;
2. Dichiarazione di quali sono le proprietà che la risposta, o la “soluzione”,
deve soddisfare.
Un’istanza
(1)
I di un problema Π è ottenuta specificando valori particolari
per tutti i suoi parametri.
Ad esempio, si consideri il classico problema del commesso viaggiatore
in cui i parametri sono:
l’insieme delle città C = { c
1
, c
2
, ... , c
m
} e, per ogni coppia di città c
i
, c
j
la
distanza d(c
i
,c
j
).
L’obiettivo è di riuscire ad ottenere un ordinamento delle città in modo da
conseguire il cammino minimo.
Un’istanza di tale problema potrebbe essere la seguente:
C = { c
1
, c
2
, c
3
, c
4
} , d(c
1
,c
2
) = 10, d(c
1
,c
3
) = 5, d(c
1
,c
4
) = 9, d(c
2
,c
3
) = 6, d(c
2
,c
4
)
= 9, d(c
3
,c
4
) = 3.
3
Il problema richiede che il commesso viaggiatore, partendo dalla città c
1
,
visiti ogni città in sequenza e infine, ritorni alla città di partenza.
La soluzione, in altre parole il cammino minimo, è dato in questo caso
dall’ordinamento < c
1
, c
2
, c
4
, c
3
> di lunghezza 27.
Un altro concetto essenziale è quello di algoritmo.
Gli algoritmi sono procedure generali passo a passo utilizzate per
risolvere problemi.
Un algoritmo risolve un problema Π, se può essere applicato ad ogni
istanza I di Π e inoltre produce sempre una soluzione per essa.
In generale, siamo interessati a trovare l’algoritmo più efficiente, in altre
parole, il più veloce.
I tempi necessari di un algoritmo sono, convenzionalmente, espressi in
termini di una singola variabile rappresentata dalla dimensione di
un’istanza, in pratica, dalla quantità di dati necessari a specificarla.
Un’istanza, fornita come ingresso al calcolo, è rappresentata con un'unica
stringa di simboli scelti da un alfabeto finito.
Per quanto le istanze di un problema possano descriversi in molti modi
diversi, in pratica ne viene scelto uno in particolare, e per ogni problema si
associa con esso uno schema codificato fisso o rappresentazione in
stringhe.
Un numero che viene utilizzato come misura formale della dimensione di
un’istanza è la lunghezza d’ingresso che rappresenta il numero di simboli
necessari per descrivere I, ottenuto dallo schema codificato di Π .
Per esempio, le istanze del problema del commesso viaggiatore potrebbero
descriversi utilizzando il seguente alfabeto:
{ c, [ , ] , /, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} .
Nel nostro esempio l’istanza del problema sarà codificata dalla seguente
stringa “c[1]c[2]c[3]c[4]//10/5/9//6/9//3”, mentre la lunghezza d’ingresso,
in pratica il numero di simboli che la rappresentano, sarà pari a 32.
(1)
Per istanza s’intende una realizzazione concreta di uno schema astratto.
4
La funzione della complessità del tempo esprime, invece, il tempo
necessario all’algoritmo per risolvere un'istanza di un problema di una
qualche dimensione.
Tale funzione, naturalmente, è ben definita nel momento in cui, è fissato lo
schema codificato impiegato per determinare la lunghezza d’ingresso e, il
modello di calcolo utilizzato per calcolare il tempo d'esecuzione.
Un particolare problema può descriversi utilizzando diversi schemi
codificati, ognuno dei quali presenta una differente lunghezza d’ingresso.
Ad esempio, si consideri un problema in cui ogni istanza è rappresentata
da un grafo G = (V,E), dove V indica l’insieme di tutti i vertici ed E di tutti
i lati. Tale istanza potrebbe essere descritta (si veda la tabella 1.2)
semplicemente elencando tutti i vertici e tutti i lati, oppure, elencando per
ogni vertice tutti gli altri vertici che presentano un lato in comune con esso
( si tratta di un elenco “neighbor”).
Schema codificato Stringhe Lunghezza
Elenco Vertici
Elenco Lati
V[1]V[2]V[3]V[4]
(V[1]V[2])(V[2]V[3)
36
Elenco Neighbor (V[2])(V[1]V[3])(V[2])( ) 24
Tabella 1.2
Nella tabella viene descritto, in base a due schemi codificati, un grafo G =
(V,E), dove V = {V
1
, V
2
, V
3
, V
4
} ed E = {(V
1
, V
2
), (V
2
, V
3
)},.
Ognuna di queste codifiche restituisce una diversa lunghezza d’ingresso
per lo stesso grafo.
In ogni caso, si può verificare facilmente che tali lunghezze differiscono al
più polinomialmente tra loro, in altre parole, a meno di una moltiplicazione
per un polinomio. Questo è mostrato nella tabella 1.3.
5
Schema codificato Limite inferiore Limite superiore
Elenco Vertici
Elenco Lati
4v + 10e
4v + 10e + (v + 2e) • log
10
v
Elenco neighbor 2v + 8e
2v + 8e + 2e • log
10
v
Tabella 1.3
In questa tabella sono indicati dei limiti generali sulla lunghezza
d’ingresso riferita ai due precedenti schemi codificati.
v rappresenta il numero dei vertici, e il numero dei lati mentre, il simbolo
x indica il più piccolo intero non meno di x (parte intera del numero
reale x).
Poiché, e < v
2
, questo significa che le lunghezze d’ingresso differiscono al
più polinomialmente da ogni altra.
Così che, qualsiasi algoritmo che ha una complessità del tempo
polinomiale sotto di uno di questi schemi, l'avrà sotto tutti gli altri.
Infatti, gli schemi standard, che s'utilizzano in pratica, differiscono al più
polinomialmente tra loro.
E' difficile immaginare, quindi, uno schema codificato ragionevole per un
problema che si discosta più che polinomialmente da quello standard.
Sebbene, il concetto di ragionevole non possa formalizzarsi, le seguenti
due condizioni cattureranno tale nozione:
1 La codifica di un’istanza I dovrebbe essere concisa e non riempita con
informazioni o simboli non necessari;
2 I numeri nell’istanza I dovrebbero avere una rappresentazione binaria (o
decimale, o comunque in un’altra base fissa di uno).
Lo stesso commento potrebbe farsi per quanto riguarda i modelli di
calcolo.
6
Tutti i modelli di calcolo realistici studiati, come la “macchina di Turing
ad un nastro”, la “macchina di Turing a nastri multipli”, la “macchina ad
accesso casuale”, sono equivalenti con rispetto alla complessità del tempo
polinomiale.
In questo caso, con il termine ragionevole s'intende il limite polinomiale
che si pone alla quantità di lavoro che può realizzarsi in una singola unità
di tempo.
Ad esempio, un modello che ha la capacità di realizzare molte operazioni
in parallelo, non dovrebbe considerarsi ragionevole.
Effettivamente, un modello di calcolo con queste capacità non esiste.
1.2 Algoritmi polinomiali ed esponenziali nel tempo
Facciamo, ora, una distinzione tra algoritmo polinomiale ed esponenziale
nel tempo.
Una funzione f(n) si dice O(g(n)), se esiste una costante c, tale che,
|f(n)|≤ c|g(n)| questo per tutti gli n≥ 0.
Un algoritmo polinomiale nel tempo è un algoritmo la cui funzione della
complessità del tempo è O(p(n)) per una qualche funzione polinomiale p,
dove n serve per indicare la lunghezza d’ingresso.
Mentre, un algoritmo esponenziale nel tempo è un algoritmo in cui tale
funzione non può essere così limitata.
La distinzione tra questi due tipi d'algoritmi è particolarmente significativa
nel caso di problemi di grandi dimensioni.
Infatti, al crescere di n, gli algoritmi polinomiali nel tempo sono, in
generale, più veloci di quelli esponenziali.
Questo è mostrato nella tabella 1.1, dove la funzione della complessità del
tempo esprime il tempo d'esecuzione in microsecondi.
7
La tabella mostra, quindi, alcune delle ragioni che rendono gli algoritmi
polinomiali nel tempo più desiderabili di quelli esponenziali.
Numerosità n
Funzione
della
complessità
del tempo
10
20
30
40
50
60
n
.00001
secondi
.00002
secondi
.00003
secondi
.00004
secondi
.00005
secondi
.00006
secondi
n
2
.0001
secondi
.0004
secondi
.0009
secondi
.0016
secondi
.0025
secondi
.0036
secondi
n
3
.001
secondi
.008
secondi
.027
secondi
.064
secondi
.125
secondi
.216
secondi
n
5
.1
secondi
3.2
secondi
24.3
secondi
1.7
minuti
5.2
minuti
13.0
minuti
2
n
.001
secondi
1.0
secondo
17.9
minuti
12.7
giorni
35.7
anni
366
secoli
3
n
.059
secondi
58
minuti
6.5
anni
3855
secoli
2*10
8
secoli
1.3*10
13
secoli
Tabella 1.1
La differenza tra i due tipi d'algoritmi, è centrale, anche, per la nozione
d'intrattabilità e per la teoria della NP-completezza.
La distinzione tra algoritmo polinomiale nel tempo efficiente ed
esponenziale nel tempo inefficiente, ammette delle eccezioni quando la
dimensione delle istanze del problema è limitata.
La tabella 1.1 mostra infatti, che l’algoritmo 2
n
è più veloce dell’algoritmo
n
5
per n≤ 20.
Si ricordi, comunque, che si sta parlando di funzionamenti “di caso
peggiore”, in altre parole, dati molti input, l’algoritmo potrebbe essere più
veloce su alcuni e più lento su altri.
8
Si valuterà la complessità dell’algoritmo rispetto al caso più sfavorevole,
in pratica, rispetto a quegli input che richiederanno massimo sforzo
computazionale.
Esistono, però, alcuni algoritmi esponenziali nel tempo che risultano
davvero vantaggiosi in pratica.
Ad esempio, l’algoritmo del simplesso per la programmazione lineare
mostra avere una complessità del tempo esponenziale, eppure presenta in
media un’elevata velocità d'esecuzione.
Sfortunatamente, esempi di questo tipo sono molto rari.
Addirittura, questo non ha fermato le ricerche sulla formulazione di
algoritmi polinomiali nel tempo.
Essi, infatti, sono dimostrabili efficienti e questa è una proprietà molto
desidera dal punto di vista teorico.
A titolo di curiosità, ricordiamo che nel caso della programmazione lineare
l’algoritmo di Karmakar (polinomiale) è in generale meno efficiente del
simplesso (come s’è visto, esponenziale nel caso peggiore).
1.3 Problemi intrattabili e NP-completezza
La definizione di problema intrattabile ci fornisce una struttura teorica
d'elevata generalità e potenza.
L’intrattabilità di un problema è essenzialmente indipendente dal
particolare schema codificato e dal modello di calcolo applicato per
determinare la complessità del tempo.
Esistono due differenti cause, ammesse dalla nostra definizione, che
determinano l’intrattabilità di un problema, che sono:
1. Il problema è così difficile che è necessario una quantità di tempo
esponenziale per trovare la soluzione;
9
2. La soluzione è richiesta così estesa, che non può descriversi con
un’espressione avente lunghezza limitata da una funzione della lunghezza
d’ingresso.
Il secondo tipo d'intrattabilità non è altro che un segnale che indica, che il
problema non è definito realisticamente, poiché richiede più informazioni
di quelle che s'utilizzeranno in realtà.
Quello che c'interessa è il primo tipo d'intrattabilità, quindi, s'assume che
la lunghezza della soluzione è limitata da una funzione polinomiale della
lunghezza d’ingresso considerata.
Un modo per risolvere problemi intrattabili è quello di riuscire a trovare
una relazione tra loro.
La principale tecnica impiegata per dimostrare che due problemi sono in
relazione, è quella della riduzione di uno all’altro, attraverso una
trasformazione costruttiva che rappresenta ogni istanza del primo problema
nell’equivalente istanza del secondo.
Una tale trasformazione stabilisce il modo di convertire un qualche
algoritmo che risolve il secondo problema, in uno corrispondente che
risolve il primo.
La teoria della NP-completezza ci fornisce un insieme di tecniche per
dimostrare che, un dato problema è just as hard come un ampio numero di
altri che sono diffusamente riconosciuti come difficili ( si tratta della classe
dei problemi NP Nondeterministic Polynomial).
Tale teoria fu presentata da Stephen Cook nel 1971 in uno testo intitolato
“The Complexity of Theorem Proving Procedures”.
Scoprire che un problema è NP-completo rappresenta già un buon inizio
del lavoro su tale problema.
I problemi NP-completi sono quelli hardest in NP.
La classe di tali problemi costituisce la frontiera fra trattabilità e
intrattabilità computazionale.
10
Un problema è considerato trattabile se esiste un algoritmo avente
complessità polinomiale che lo risolve, in altre parole, avente complessità
p(n), dove p è un qualsiasi polinomio e n è la dimensione dell’input.
Esso apparterrà, in questo caso, alla classe P (P = Polynomial).
Un problema è, invece, intrattabile se sarà così hard che tutti i suoi
algoritmi risolutivi avranno complessità maggiore di quella polinomiale.
I problemi NP-completi si trovano nelle seguenti condizioni:
1. Sono facilmente risolubili in tempo esponenziale;
2. Per essi non è stato trovato alcun algoritmo di complessità polinomiale, ma
non è stato dimostrato che non possa esistere;
3. Se si riesce a risolvere uno di essi in tempo polinomiale allora, ognuno può
essere risolto in tempo polinomiale.
Un esempio di problema NP-completo è il problema della soddisfacibilità
(SAT = Satisfiability):
dato un insieme di variabili X booleane e un insieme di clausole C su X,
esiste un’assegnazione di valori verità che soddisfa C ?
Tale problema ha la proprietà che ogni altro problema in NP può essere
ridotto polinomialmente ad esso, in altre parole, se può essere risolto da un
algoritmo polinomiale nel tempo così anche ogni altro in NP.
(Per la dimostrazione di questa proprietà, che si deve a COOK, si veda [1]
da pag. 38 a pag. 44).
Inoltre, se ogni problema in NP è intrattabile lo deve essere anche il
problema della soddisfacibilità.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
