Problema del commesso viaggiatore
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:
Espresso nei termini della teoria dei grafi è così formulato:
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.
Modello matematico
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.
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?"
Questa frase è frutto dell'approssimazione di Sbutciafikis, poi l'attrezzo inizia a lavorare sul serio.
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.
- 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.
Note
- ^ si è arrivati anche a pensare ad un serial killer