Università di Camerino

Dipartimento di Matematica e Informatica

TSP

Traveling Salesman’s Problem

Relatori

Massimo Sciarra, Romeo Pruno

http://members.xoom.it/romeopruno/ppt/presentazioneSeminario.ppt

Nel 1859 il famoso matematico irlandese Sir William Rowan Hamilton pose il seguente problema:

Egli prese un dodecaedro regolare di legno, ogni vertice del quale era contrassegnato con il nome di una città, e propose di trovare un itinerario lungo gli spigoli che, partendo da un punto A e passando per ciascuna città una ed una sola volta, permettesse poi di tornare al punto di partenza.

Input Output

Cammino hamiltoniano

Dato un grafo G = (V,A) con V insieme dei vertici ed A insieme degli archi, si definisce cammino hamiltoniano un cammino p = <v1, v2, …, vk> tale per cui:

* k è pari a |V| cardinalità di V

* vi ≠ vj i, j∀

…Più semplicemente un cammino hamiltoniano tocca tutti i vertici del grafo uno ed una sola volta!

Circuito hamiltonianoDato un grafo G = (V,A) e un insieme SA, S è l’insieme di archi di un ciclo hamiltoniano se e solo se:

- in ogni nodo di G incidono esattamente due archi di S - S non contiene cicli di cardinalità inferiore a |V|

…Un circuito hamiltoniano è semplicemente un cammino in cui l’ultimo vertice coincide con il primo!

Travelling Salesman’s ProblemIl problema del “Commesso Viaggiatore” non è altro che un’estensione del ciclo hamiltoniano e definito come segue:

Dato un grafo G = (V,A)V = (1,………,n) corrisponde ad un insieme di città.A = (i,j) corrisponde alle possibili strade che collegano coppie di città.Cij corrisponde al costo (distanza o tempo) ed è associato ad ogni elemento (i,j)A.

Determinare un percorso chiuso (ciclo hamiltoniano) che passi per tutte le città una sola volta, in modo che il suo costo sia minimo (min Cij).

Definizione del problema linguaggio naturale

TSP (Traveling Salesman’s Problem)

Un commesso viaggiatore deve visitare un certo numero di città; conosce la lunghezza ( o il tempo o il costo, a seconda dei casi) dello spostamento necessario per recarsi da una città all’altra: vuole determinare il percorso più breve ( o più veloce o più economico) che gli permetta di partire da casa sua e di farvi ritorno dopo aver visitato ogni città una sola volta. Come può fare?

Considerazioni generaliIl TSP è un problema che non ammette soluzione di complessità polinomiale

TSPNP-completo

NP è quella classe di linguaggi che possono essere verificati mediante un algoritmo di tempo non polinomiale

Cioè la complessità computazionale dell’algoritmo non è funzione polinomiale della dimensione del problema stesso!

TSP P

????

World-Record Traveling Salesman Problem for 3038 Cities Solved

Una potenza di calcolo di 50 WorkStation per trovare la soluzione ottima, un anno e mezzo per battere il vecchio record di 2392 “città visitate”

Branch & Boundhttp://nhse.cs.rice.edu/CRPC/newsletters/jan93/index.html

Algoritmo baseUn algoritmo che sicuramente trova la soluzione ottimale, consiste nell’effettuare una ricerca esaustiva di tutti i cicli hamiltoniani, attraverso una procedura ricorsiva e poi determinare quello con il peso minore.

Come detto in precedenza questo algoritmo troverà sicuramente la soluzione migliore ma impiegherà tantissimo tempo visto che la complessità è pari ad O((n-1)!), in quanto al primo passo ci sono n-1 scelte possibili, al secondo n-2... ed n-k al k-esimo.

(Il numero di cicli hamiltoniani in un grafo completo con n nodi è pari a (n-1)! da qui si ricava che il numero di cicli hamiltoniani cresce esponenzialmente col numero dei nodi n = 11 cicli hamiltoniani = 3.628.800)

Procedura principale Procedure Percorri(i,som:integer;cammino:vet);..cammino[i]:=x; (*inseriamo il nodo x nel cammino*) costo:=costi[cammino[i-1],cammino[i]]; (*assegna i costi degli archi*) (*presi in considerazione*) som:=som+costo; (*aggiunta del peso dell'arco alla somma finora calcolata*) i:=i+1; (*incrementiamo l'indice del vet cammino per inserire un nuovo nodo *) if i<=n then (*controlliamo se abbiamo raggiunto la fine del vettore*) begin percorri(i,som,cammino); (*chiamata ricorsiva della procedura percorri*) i:=i-1; (*torniamo indietro di un passo all'interno del vettore cammino*) (*per considerare nuovi cicli*) som:=som-costo; (*togliamo il peso dell'arco eliminato nel passo precedente*) end else begin som:=som+costi[cammino[n],cammino[1]]; if som<=min then (*confrontiamo se la soluzione è migliore di quelle già trovate*) begin min:=som; for j:=1 to n do write(cammino[j],' '); (*stampa tutto il contenuto del vettore cammino*)

Albero di ricerca

Soluzione 1 Soluzione 2

Come si può migliorare?Apportando alcune semplici modifiche è possibile evitare di esplorare alcune soluzioni

- Si inizia generando cammini completi, e si memorizza quello più corto generato fin ora

- Ogni altro cammino che si genera viene confrontato ad ogni passo con il più corto memorizzato

- Se il nuovo cammino è più lungo di quello memorizzato, la ricerca si ferma e si prende in considerazione un nuovo percorso

Albero di ricerca

Difetti Dà la sicurezza di trovare il cammino più corto (min Cij) ma nel caso peggiore impiega un tempo uguale all’algoritmo base

Soluzione inadeguata per problemi di grosse dimensioni (tempo elevatissimo)

Bisogna essere “fortunati” nel trovare subito un percorso minimo, cosi da avere meno confronti durante il cammino verso la soluzione **ottima

** Questo è un grande limite. In quanto l’”ottimizzazione del tempo” è vincolata dall’ordine con cui si esplorano le soluzioni: prima si trova il ciclo meno costoso e più si riduce il costo dell’elaborazione e quindi la complessità

Algoritmo Branch and Bound (dividi e limita)

L’algoritmo base può essere ulteriormente migliorato utilizzando la tecnica detta branch & bound

Anche qui si ricorre ad una ricerca esaustiva di tutti i cicli hamiltoniani, solo che tale ricerca è effettuta su delle partizioni del grafo

Branching = generazione di sottoinsiemi

Bounding = scelta e confronto del limite inferiore

Come funziona il B&B ?

Si divide il grafo iniziale in sottografiSi cercano, in modo esaustivo dei cammini minimi nei sottografi Si uniscono i percorsi trovati con eventuali modifiche

Soluzione ottima

Tecniche euristicheIl TSP è un problema cosi complesso che occorre costruire una tecnica che ci permetta di arrivare non alla soluzione ottima ma almeno ad una buona!

Sono delle tecniche efficienti in quanto portano ad una soluzione, non sono efficaci perché la soluzione trovata non sempre è ottima

Euristiche costruttive

Costruiscono un circuito hamiltoniano

Euristiche di miglioramento

Partono da un circuito esistente e lo migliorano

Quando le usiamo?- quando le dimensioni del problema sono eccessive

- quando i problemi devono essere risolti in tempi brevi

- quando i dati del problema sono approssimati

- quando si devono trattare problemi dinamici

Algoritmi euristici

ALGORITMO GREEDY (EURISTICA COSTRUTTIVA)

Prevede che ad ogni passo ci si sposti verso il vertice più vicino (utilizzando l’arco con il peso minore), tra quelli non ancora visitati, al vertice corrente

12

1

5

4

2

3

3

6

Soluzione trovata: 22

Soluzione ottima: 17

Complessità O(n2)

Algoritmi euristici

ALGORITMO K-OPT (EURISTICA DI MIGLIORAMENTO)

Tale algoritmo consiste nell’apportare alcune modifiche alla soluzione trovata con l’algoritmo precedente. Tali modifiche consistono nel sostituire alcuni archi del ciclo hamiltoniano trovato con altri archi per formarne uno nuovo di peso, ovviamente, minore. Si ripete l’operazione fino a trovare il ciclo hamiltoniano migliore.

Come funziona? (2-opt)Si parte da un ciclo hamiltoniano

5

2

3

1 15

Si sceglie una coppia di archi non adiacenti e la si rimuoveSi aggiungono due nuovi archi

Peso: 26

7

4

19

Pregi e difetti

- Più k è grande e più ci avviciniamo alla soluzione ottima

2-opt 8% peggiore dell’ottima

3-opt 4% peggiore dell’ottima

- Più k è grande e più aumenta la complessità

(O(nk))

ALGORITMO LIN – KERNIGHAN È difficile sapere quale k usare per realizzare il più buon compromesso tra complessità e qualità della soluzione

L'algoritmo cambia il valore di k durante la sua esecuzione, decidendo ad ogni iterazione quale dovrebbe essere il valore di k.

Ad ogni iterazione l'algoritmo esamina, per valori ascendenti di k, se un interscambio di collegamenti di k possono dare luogo ad un giro più corto.

Questo continua fino a che non si trovano più scambi che migliorano il percorso trovato in precedenza.

A cosa serve il TSP?Il problema del TSP è una questione aperta anche nella vita di tutti i giorni, molti modelli matematici sono stati sviluppati utilizzando i principi fondamentali del ciclo Hamiltoniano.

Di seguito poniamo alcuni dei possibili scenari applicativi del problema!

Ciclo di produzione delle schede elettroniche

Minimizzare il percorso della punta (riportandola alla posizione di riposo), corrisponde a risolvere il problema del TSP applicato alla struttura del grafo che rappresenta l’insieme dei fori, pesato con le distanze geometriche che li separano

Pianificazione delle consegne ai clienti

Questo è un problema fondamentalmente di logistica la quale porre come soluzione un modello vicinissimo a quello del TSP, infatti l’azienda fornitrice deve fare il più lungo tragitto spendendo il meno possibile per quanto riguardano le spese di spedizione!

Links utili per approfondireRiviste scientifichehttp://matematicamente.ithttp://computer.orghttp://acm.org

Siti specializzatihttp://polito.ithttp://www.diap.polimi.it/~grabino/metodiemodelli http://polimi.ithttp://cs.sunisb.eduhttp://www.is-frankfurt.de/cosa/tsp/tsp.html

Materiale genericohttp://nicoladimauro.ithttp://csep1.phy.ornl.gov/CSEP/MO/NODE28.htmlhttp://crmpa.it

BibliografiaGraphs and Hypergraphs C.Berge, Dunod Paris, 1970

Algoritmi Thomas H. Cormen, Charles E. Leisserson,

I Grafi e le loro applicazioni O.Ore, Zanichelli, MM2, 1963

"Extropy“Rivista, #9, vol.4, n.1, Summer 1992, Los Angeles

Un ringraziamento speciale al

University of AmsterdamInstitute of Actuarial Science & Econometrics