Problema del commesso viaggiatore

Da Nonciclopedia, l'enciclopedia libera...

La scuola uccide.jpg
NonIstruzione

Ambra guadagna un sacco di soldi:
perché io devo andare a squola e studiare?
Commesso viaggiatore nel deserto.jpg

TomTom di merda... ma che fine ha fatto Los Angeles?

Il problema del commesso viaggiatore, o TSP (dall'inglish Travelling Salesman Problem o, se preferite, dal romanesco Tanto S'è Perso) è un problema di teoria dei grafi, uno dei casi di studio tipici dell'informatica teorica, scienza che si occupa di concepire programmi che non servono a nulla, tipo quelli del governo. È oggetto di interesse anche per gli studiosi della teoria della complessità, che fanno sicuramente qualcosa di troppo complicato da capire e quindi ce ne freghiamo. Il nome nasce dalla sua più tipica enunciazione:

Quote rosso1.png Data una rete di città, connesse tramite delle strade, trovare il percorso ottimale che un commesso viaggiatore deve seguire per visitare tutte le città una e una sola volta, che la benzina costa uno sproposito per colpa delle accise e tende a finire. Quote rosso2.png

~ Brian Amedeo Kernighan, primo enunciatore, mentre va a piedi al distributore più vicino con un tanica in mano.

Espresso nei termini della teoria dei grafi è così formulato:

Quote rosso1.png Dato un grafo completo pesato, è sempre meglio ripesarlo (che il norcino è un gran paraculo). Quote rosso2.png

~ Tor Alsaker-Sbørre, Ti ingrifa il grafo?, collana Informatica ilare, Oslo 1964, Ed. Jackson.

La sostanziale differenza rispetto al ciclo hamiltoniano è che quest'ultimo viene formulato su di un grafo privo di pesi, detto grafo scansafatiche o anche grafo capetto. Il problema è di considerevole importanza pratica, al di là delle ovvie applicazioni nella logistica e nei trasporti: telefonare a Chi l'ha visto? tutte le settimane, per segnalare la scomparsa dell'ennesimo commesso viaggiatore[1], è seccante.

[modifica] Modello matematico

Problema del commesso viaggiatore.jpg

L'approssimazione di Sbutciafikis è al momento l'unica valida alternativa al suicidio.

Al problema del TSP è associabile un grafo, sempre che sia d'accordo e abbia la partita IVA aperta. La figura A ci mostra un chiaro esempio di ottimizzazione del percorso, ricavato dopo aver applicato il modello Limeccia (usato solo nell'Istituto tecnico agrario Pierfrancesco Topponi di Sambuca Pistoiese‎ (PT). Salta subito all'occhio che il tanto celebrato Prof. Ugo Limeccia Bombi, orgoglio della Valdinievole, in matematica era ignorante come un badile.

Wikiquote.png
«Il percorso migliore si ottiene applicando la formula di pag.8 della Settimana Enigmistica, ossia: unire i puntini da 1 a 6
(Lo studente di seconda elementare, nonché zingaro, Ciprian Rubolestu.)

Infatti, detto N l'insieme dei nodi (o città) e A l'insieme degli archi (o strade), finisce tutto a puttane perché A l'avevamo già usata per il nome della figura, e quindi è un casino. Allora facciamo finta che la figura si chiami Gennaro, quindi possiamo stabilire la relazione P = N-L², dove L rappresenta il tentativo estremo di mettere ordine, ma peggiora la situazione. Per tagliare la testa al toro siamo costretti (seppur controvoglia) a servirci della formula approssimata del guardacaccia greco Anastasios Sbutciafikis, massimo esperto mondiale di grafi e quaglie. La figura è eloquente: lim rappresenta la limousine, in cui vorresti trovare Ruby Rubacuori già con le mutande in mano, con la quale allontanarti repentinamente da questo genere di stronzate. Facciamo un esempio pratico: "Avete presente quando fate l'errore di non girare in tempo e il navigatore satellitare inizia a ricalcolare il percorso?"

Wikiquote.png
«Appena possibile eseguite una inversione a U
(Qualsiasi navigatore satellitare a seguito di una minchiata umana.)

Questa frase è frutto dell'approssimazione di Sbutciafikis, poi l'attrezzo inizia a lavorare sul serio.

[modifica] Algoritmi

Non esistono algoritmi efficienti per la risoluzione del TSP, l'unico metodo di risoluzione è rappresentato dall'enumerazione totale, ovvero nell'elaborazione di tutti i possibili cammini sul grafo per la successiva scelta di quello migliore. A volte questo non è possibile, sia per le ridotte capacità elaborative dei dispositivi in commercio, sia per le ridotte capacità mentali di chi ha scritto il programma. Si ricorre allora agli algoritmi euristici, cioè che producono soluzioni probabilmente buone, ma impossibili da provare essere ottimali (chiamati anche algoritmi "a fidasse"). L'uomo però è zuccone forte, s'incaponisce e vuole trovare soluzioni anche a cose di cui non frega un tubo a nessuno, sprecando tempo e soldi in imprese che non portano a niente.

Cartello stradale utilissimo.jpg

Come se non bastasse, i cartelli scemi aggravano il problema del commesso viaggiatore.

  • 1998, Francia. Una ditta di Marsiglia, al fine di ottimizzare il passaggio delle piste e delle saldature su una scheda elettronica di controllo del Concorde, utilizzò un comune computer. L'elaborazione richiese circa 15 mesi, durante i quali una società di Afragola (NA) gli soffiò l'appalto, facendo un disegno a mano su un foglio.
  • 2001, Texas-Italia. La Rice University di Houston e l'ITIS Ugo Ruzzolo di Cosenza, grazie ad una rete condivisa di processori (centosei XA9-Plus a 8500 MHz della Rice e un paio di Commodore VIC-20 della Ruzzolo), hanno trovato la soluzione esatta al TSP di tutti i comuni d'Italia. L'elaborazione si è fermata due sole volte: la prima quando è arrivata a Eboli (per ragioni non chiarite) e la seconda a Sala Consilina (SA), per una imprevista deviazione sulla Salerno-Reggio.
  • 2004, Svezia. Fu risolto il TSP per tutte le 24.978 città della Svezia e risultò un percorso ottimale di 72.492 chilometri. Il dato fu contestato da Sune Cronqvist (un trasportatore di renne da monta che fa il percorso abitualmente) il quale, in prossimità dello svincolo per Arvidsjaur, taglia sempre attraverso la tenuta di Pär-Gunnar Börjesson (un coltivatore di mele cotogne) risparmiando circa 37 chilometri, nonostante le fucilate del collerico contadino.
  • 2013, Andorra. Un ragazzino di 15 anni con un iPhone è riuscito a risolvere il problema del TSP calcolato su tutte le principali città della nazione.

[modifica] Note

Cioè, stai davvero leggendo le ♪♫note♫♪?! Pazzesco...
  1. ^ si è arrivati anche a pensare ad un serial killer

[modifica] Voci correlate

Strumenti personali
wikia