Noto anche come Travelling Salesman Problem (TSP)
Il commesso viaggiatore deve visitare n città in automobile
Se viaggiasse per una distanza totale maggiore di k il viaggio non gli converrebbe più (per il costo della benzina)
Ogni città è collegata direttamente a tutte le altre
Esiste un percorso di lunghezza < k che visita una sola volta tutte le città ?
? Ancona Bari Como Domodossola
(Un) algoritmo
disponi le città in una permutazione qualunque…ABCD
somma le distanze tra A e B, tra B e C, tra C e D; se la somma è < k stampa il percorso e termina con successo
se non ci sono altre permutazioni termina con fallimento, altrimenti scegline un’altra e riparti dal passo 2
Complessità di TSP
Nel caso peggiore, dobbiamo esaminare tutte le permutazioni possibili
Date n città, le possibili permutazioni sono n!
TSP è O(n!)
Se n = 30, n! = 2,61032
Un computer capace di esaminare 1000 miliardi di percorsi al secondo, lanciato all’istante presunto del big bang, dovrebbe lavorare ancora per 8000 miliardi di anni
Problemi (in)trattabili
Si dicono intrattabili problemi i cui algoritmi richiedono una quantità irragionevolmente alta di risorse
Attualmente la distinzione tra problemi trattabili e non si basa sulla polinomialità
Problemi in O(nk) sono considerati trattabili
Problemi di complessità polinomiale
Sono considerati trattabili in base all’esperienza
O(n10300) non è affatto ragionevole
Fino ad oggi, però, per tutti i problemi con complessità polinomiale si è sempre trovato un algoritmo al più O(n4)
Se un giorno si dovesse scoprire un problema polinomiale il cui migliore algoritmo è O(n10300), allora l’equivalenza polinomiale ~ trattabile andrebbe rivista
La classe P
Contiene i problemi per i quali esiste un algortimo di complessità polinomiale
Il TSP ha un algoritmo O(n!)
Perché TSP sia dimostrabilmente in P, dobbiamo esibire un algoritmo O(nk) che lo risolva
Finora non è stato trovato niente del genere
Verifica di possibile soluzione TSP
< k? Dato un possibile percorso, verificare che soddisfa le condizioni del TSP
Verifica di possibile soluzione TSP
Avviene in tempo lineare rispetto al numero di città: O(n)
Se potessimo controllare tutti i percorsi possibili contemporaneamente, avremmo un algoritmo O(n) per TSP
È tale una MT la cui tavola può comprendere più di una quintupla in corrispondenza di una certa configurazione
Una MTN (MT non deterministica), in corrispondenza di certi input, riesce a produrre più di una singola sequenza di calcolo
TSP è O(n) per una MT non deterministica, perché viene effettuata contemporaneamente la verifica (di complessità lineare) per ogni possibile percorso
TSP è dunque nella classe NP dei problemi nondeterministico-polinomiali
P NP, perché ovviamente se una MT risolve un problema in tempo polinomiale, anche una MTN è in grado di farlo
P = NP ?
Clay Mathematics Institute One Bow Street Cambridge, Massachusetts 02138 USA
http://www.claymath.org/millennium/
Offerti $1000000 per chi lo dimostra o dimostra il contrario
Per dimostrare che P NP, ossia P NP, occorre dimostrare che esiste un problema in NP per il quale non esiste un algoritmo polinomiale
La collocazione di TSP
TSP è sicuramente in NP perché una MTN lo risolve in tempo polinomiale
Attualmente, il migliore algoritmo per TSP è O(n22n)
Non è stato dimostrato che non si possa migliorare
Né è stato dimostrato che sicuramente esiste un algoritmo polinomiale
Problemi di decisione
TSP è un problema di decisione
“Date queste città collegate in questo modo, esiste un percorso....?”
Sì / No
Riduzione polinomiale
Siano dati un problema di decisione p e un input d
Sia R un algoritmo che, dati p e d in input, restituisce un altro problema p’ e un altro input d’ tali che
p’(d’ ) = sì se e solo se p(d) = sì
Se R ha complessità polinomiale, si dice che p è polinomialmente riducibile a p’
Problemi NP-completi
Un problema NP si dice NP-completo quando tutti i problemi NP sono polinomialmente riducibili ad esso
È stato dimostrato che TSP lo è
I problemi NP-completi sono particolarmente interessanti perché se un giorno si trova un algoritmo polinomiale che ne risolve uno, allora avremo dimostrato che P = NP
Comments