Grafi e retiIl problema del commesso viaggiatore

Pensiamo ancora una volta a reti e mappe. Immagina che un servizio di consegna debba visitare ${tsn} città diverse per distribuire i pacchi. Possiamo pensare a queste città come ai vertici in un grafo. Se tutte le città sono collegate da strade, questo è un , quindi ci sono ${tsn} × (${tsn} - 1) 2 = ${tsn*(tsn-1)/2} spigoli in totale.

Il camion di consegna deve visitare tutte le città, in qualsiasi ordine. Nel problema dei ponti di Königsberg volevamo trovare percorsi che percorressero ogni spigolo esattamente una volta. Ora vogliamo trovare percorsi che visitino ogni vertice esattamente una volta. Questi percorsi sono chiamati cicli hamiltoniani.

Esistono innumerevoli possibilità diverse per i cicli hamiltoniani nei grafi completi. In effetti, possiamo selezionare qualsiasi vertice come vertice iniziale e poi scegliere le città rimanenti in qualsiasi ordine:

In costruzione…

In un grafo con ${tsn1} città, ogni ciclo hamiltoniano deve contenere anche ${tsn1} città. Adesso,

Ciò significa che, in totale, ci sono ${tsnPaths(tsn1)} possibili percorsi. Una scorciatoia per questo prodotto è ${tsn1}! o ${tsn1} Fattoriale.

Potrebbe non essere possibile viaggiare direttamente tra due città (senza passare per un'altra città). In quel caso non abbiamo più un grafo completo e trovare il numero di cicli hamiltoniani, se esistono, diventa molto più difficile.

Finora abbiamo ignorato la distanza fra le città. Nella vita reale, tuttavia, questa è una considerazione molto importante: non vogliamo trovare qualsiasi percorso, ma il percorso più breve. Questo è chiamato Problema del commesso viaggiatore. Non si applica solo nei trasporti e nella logistica, ma anche quando si posizionano i transistor sui microchip, per rendere i computer più veloci, o quando si analizza la struttura del DNA.

Un metodo semplice sarebbe quello di provare tutti i percorsi possibili, trovare la lunghezza di ciascuno e quindi scegliere quello più breve. Tuttavia abbiamo appena dimostrato che, anche con solo ${tsn2} città ci sono ${tsn2}! = ${factorial(tsn2)} possibili percorsi. Una volta che hai centinaia o migliaia di vertici, provare tutti i possibili percorsi diventa impossibile, anche usando computer potenti.

Purtroppo non esiste un algoritmo più efficiente per risolvere il problema del commesso viaggiatore. Invece, matematici e scienziati informatici hanno sviluppato vari algoritmi che trovano buone soluzioni, anche se potrebbero non essere le migliori. Questi algoritmi, che forniscono solo soluzioni approssimative, sono chiamati Euristici.

Prova a riorganizzare le città su questa mappa e osserva come cambia il percorso più breve tra di esse. Puoi rimuovere le città toccandole e puoi aggiungere città cliccando un punto qualsiasi della mappa (fino ad un massimo di 8):

L'Algoritmo Greedy (o Algoritmo del vicino più vicino) è molto semplice: inizi in una città a caso e ti sposti consecutivamente nella città più vicina che non hai mai visitato prima. Una volta che hai visitato tutte le città, ti fermi.

Animazione in arrivo ...

Puoi mostrare che, in media, i percorsi trovati usando l'algoritmo greedy sono più lunghi del 25% rispetto al percorso più breve possibile.

Con l'algoritmo 2-Opt si inizia con un percorso casuale possibile. Quindi si scegli ripetutamente due spigoli e si scambiano se ciò riduce la lunghezza del percorso. Ci si ferma quando non può ridurre ulteriormente la lunghezza scambiando qualsiasi coppia di spigoli.

Animazione in arrivo ...

Molto prima ancora che esistessero i computer, la Natura aveva trovato un modo intelligente per trovare percorsi ottimali tra diverse posizioni: nelle colonie di formiche.

Le formiche vogliono trovare i percorsi più brevi possibili tra il loro nido e le possibili fonti di cibo. Possono comunicare tra loro attraverso sostanze chimiche che lasciano lungo il loro cammino e che altre formiche possono seguire.

La colonia di formiche invia molti esploratori che inizialmente viaggiano in direzioni casuali. Una volta trovato il cibo, ritornano, lasciando dietro di sé una scia di feromoni.
Altre formiche tendono a seguire una scia che le conduce al cibo. Durante il viaggio di ritorno depositano più feromoni, rafforzando così quella pista.
Nel tempo, il feromone evapora. Più lungo è un percorso, maggiore è il tempo impiegato dalle formiche per percorrerlo, quindi il feromone ha più tempo per evaporare. I percorsi brevi, d'altra parte, possono essere rinforzati più rapidamente, quindi la loro forza aumenta più velocemente.

Diagramma in arrivo ...

Gli algoritmi delle colonie di formiche (Ant Colony System, ACS) provano a replicare questo comportamento con i computer. Usando molte formiche "virtuali", si possono trovare rapidamente ottime soluzioni per il problema del commesso viaggiatore.

Una proprietà particolarmente utile degli algoritmi ACS è che possono essere eseguiti continuamente e adattarsi in tempo reale alle modifiche dei grafi. Questi cambiamenti potrebbero essere causati da incidenti e chiusure sulle reti stradali o da picchi di traffico nei server Web delle reti di computer.

Il problema del commesso viaggiatore è NP-difficile, il che significa che è molto difficile risolverlo con i computer (almeno per un gran numero di città).

Trovare un algoritmo veloce ed esatto avrebbe serie implicazioni nel campo dell'informatica: significherebbe trovare algoritmi veloci per tutti i problemi NP-difficili. Inoltre renderebbe inutile la maggior parte della sicurezza di Internet, che si basa sul fatto che alcuni problemi sono ritenuti molto difficili per i computer.

Trovare un algoritmo veloce per risolvere il problema del commesso viaggiatore risolverebbe anche uno dei più noti problemi irrisolti in matematica e informatica, il problema P vs NP. È uno dei sette Problemi per il Millennio, la cui soluzione verrà ricompensato con un premio da 1 milione di dollari.

Cambia lingua

Accedi a Mathigon

Condividere

Ripristina avanzamento

Glossario

Grafi e retiIl problema del commesso viaggiatore