Problema del commesso viaggiatore: differenze tra le versioni

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 [[Programma Di Governo|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:

La sostanziale differenza rispetto al [[Ciclociclo Hamiltonianohamiltoniano]] è che quest'ultimo viene formulato su di un grafo privo di pesi, detto ''grafo [[Fancazzismo|scansafatiche]]'' o anche ''grafo [[Capo|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<ref>si è arrivati anche a pensare ad un [[serial killer]]</ref>, è seccante.

Al problema del TSP è associabile un [[grafo]], sempre che sia d'accordo e abbia la [[partita IVA]] aperta. La figura {{Dimensione|130%|'''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‎ ([[Pistoia|PT]]). Salta subito all'[[occhio]] che il tanto celebrato Prof. Ugo Limeccia Bombi, orgoglio della Valdinievole, in [[matematica]] era [[ignorante]] come un [[badile]].

Infatti, detto '''N''' l'insieme dei nodi (o città) e '''A''' l'insieme degli archi (o strade), finisce tutto a [[Puttana|puttane]] perché '''A''' l'avevamo già usatousata 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 [[ManualiNonbooks:Tagliare la testa al toro|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 [[Quaglia|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 [[Problema|stronzate]].<br /> Facciamo un esempio pratico: ''"Avete presente quando fate l'errore di non girare in tempo e il navigatore satellitare inizia a ricalcolare il percorso?"''

{{Quote|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.

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 [[Idiota|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]].

* [[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 ([[Napoli|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 ([[Salerno|SA]]), per una [[Imprevisto|imprevista]] deviazione sulla [[Autostrada Salerno-Reggio Calabria|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 [[Renna|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 [[Mela cotogna|mele cotogne]]) risparmiando circa 37 chilometri, nonostante le fucilate del collerico contadino.