Risolutore del Commesso Viaggiatore (TSP)

Risolutore del Commesso Viaggiatore (TSP)

Il Risolutore del Commesso Viaggiatore è un calcolatore pratico ed educativo per il classico Problema del Commesso Viaggiatore (TSP): dato un insieme di città e le distanze tra le coppie, trovare il tour più breve possibile che visiti ogni città esattamente una volta e torni alla partenza. Questo risolutore accetta sia coordinate planari che una matrice di distanza personalizzata, seleziona automaticamente il miglior algoritmo in base alla dimensione del problema e renderizza il tour risultante come una mappa SVG animata.

Cos'è il Problema del Commesso Viaggiatore?

Formalmente, dato un grafo pesato completo G = (V, E) con un insieme di vertici V = {1, 2, ..., n} e pesi degli archi d(i, j), il TSP cerca una permutazione π dei vertici che minimizzi:

L'ultimo termine chiude il ciclo. Il TSP è uno dei problemi più antichi e studiati nell'ottimizzazione combinatoria — è NP-hard nel caso generale, il che significa che non esiste un algoritmo noto che risolva ogni istanza in tempo polinomiale. Nonostante ciò, appare in innumerevoli applicazioni del mondo reale: routing di veicoli, foratura di circuiti stampati (PCB), sequenziamento del DNA, percorsi di prelievo nei magazzini, programmi di osservazione astronomica e persino consegna della posta rurale.

Come Funziona Questo Risolutore

Programmazione Dinamica Held–Karp (Esatta)

Per istanze piccole (fino a 12 città) il risolutore calcola il tour dimostrabilmente ottimale utilizzando l'algoritmo Held–Karp, pubblicato indipendentemente da Richard Bellman e Michael Held & Richard Karp nel 1962. La ricorrenza chiave, dove C(S, j) è il percorso più breve dal vertice 1 al vertice j visitando esattamente il sottoinsieme S:

Il costo del tour ottimale è quindi min_j [C({1,...,n}, j) + d(j, 1)]. Held–Karp gira in tempo O(2ⁿ · n²) e memoria O(2ⁿ · n) — un enorme miglioramento rispetto alla forza bruta n!, ma comunque esponenziale. Oltre le 20 città circa, l'impronta di memoria diventa impraticabile.

Nearest-Neighbor + 2-opt (Euristico)

Per istanze più grandi, il risolutore utilizza un'euristica a due fasi. Innanzitutto, il Nearest-Neighbor costruisce un tour rapido camminando avidamente verso la città non visitata più vicina da ogni vertice di partenza. Il risolutore prova molti vertici di partenza e mantiene il miglior tour. Successivamente, la ricerca locale 2-opt migliora il tour rimuovendo iterativamente due archi e ricollegando i due percorsi risultanti nell'unico altro modo possibile:

Geometricamente, il 2-opt rimuove ogni "incrocio" nel tour: due segmenti che si incrociano possono sempre essere disincrociati per ottenere una lunghezza totale inferiore. L'algoritmo si ferma a un ottimo locale dove nessuno scambio singolo aiuta, chiamato tour 2-ottimale. Su istanze euclidee realistiche, il 2-opt trova tipicamente tour entro il 2-5% del vero ottimo in millisecondi.

Formati di Input

Modalità coordinate (x, y)

Una città per riga. Ogni riga è etichetta, x, y — l'etichetta è opzionale. Il risolutore calcola automaticamente le distanze euclidee e visualizza le città nelle loro posizioni reali.

Modalità matrice di distanza

Una matrice quadrata n × n di distanze non negative, una riga per riga, valori separati da spazi o virgole. Le matrici possono essere simmetriche o asimmetriche — le matrici asimmetriche modellano strade a senso unico, prezzi dei voli con disponibilità variabile e viaggi dipendenti dal vento. È possibile fornire etichette nel campo Etichette matrice.

Confronto tra Algoritmi

Come Usare Questo Risolutore

1. Scegli una modalità di input. Coordinate se le tue città hanno posizioni (x, y) significative; Matrice di distanza se i costi non sono euclidei o sono asimmetrici.
2. Incolla o digita i tuoi dati. Una città o riga per riga. Clicca su un pulsante di esempio rapido sopra il modulo per precompilare un esempio valido.
3. Scegli l'algoritmo. Lascia su Auto per l'impostazione predefinita corretta: Held–Karp quando l'istanza è abbastanza piccola per l'ottimalità dimostrabile, NN + 2-opt altrimenti. Forza un algoritmo specifico se desideri fare un confronto.
4. Scegli chiuso o aperto. Un tour chiuso ritorna alla partenza — il TSP tradizionale. La modalità percorso aperto risolve il problema correlato del Cammino Hamiltoniano in cui il venditore finisce in una città diversa.
5. Clicca su Risolvi. La pagina dei risultati mostra la lunghezza totale del tour, un SVG animato del percorso (clicca "Riproduci animazione" per rivederlo), la sequenza completa delle città, un dettaglio per ogni arco e la matrice di distanza con gli archi del tour evidenziati.

Esempio Svolto

Consideriamo cinque città — un rettangolo più una punta: A (0, 0), B (4, 0), C (4, 3), D (0, 3), E (2, 5). Il risolutore restituisce:

• Tour: A → D → E → C → B → A
• Lunghezza: 3 + √8 + √8 + 3 + 4 ≈ 15.66
• Ottimale? Sì — Held–Karp dimostra che non esiste un tour più breve.
• Perché questo ordine? Il percorso traccia l'inviluppo convesso dei cinque punti (A → D → E → C → B → A). Una proprietà classica del TSP euclideo è che un tour ottimale visita i punti sull'inviluppo convesso nel loro ordine ciclico; i punti interni si inseriscono tra i vicini dell'inviluppo adiacenti. Qualsiasi tour che incrocia il proprio percorso, come A → C → B → D → E → A (lunghezza ≈ 21.8), può sempre essere disincrociato dal 2-opt per un risultato più breve.

Applicazioni nel Mondo Reale

• Logistica e consegne — ottimizzare il percorso giornaliero di un autista attraverso 15 fermate per ridurre carburante e tempo.
• Produzione — ordinare i fori che una punta CNC deve praticare su un PCB per ridurre al minimo lo spostamento della testina.
• Assemblaggio del genoma — ordinare i frammenti di DNA in base alla somiglianza di sovrapposizione, codificata come una matrice di distanza.
• Astronomia — programmare i movimenti del telescopio tra le stelle bersaglio per massimizzare il tempo di osservazione.
• Prelievo in magazzino — sequenziare le visite ai corridoi per evadere un ordine nel minor numero di passi.
• Pianificazione turistica — pianificare un viaggio multi-città che riduca al minimo il tempo di viaggio e il costo del biglietto.

Domande Frequenti

Cos'è il Problema del Commesso Viaggiatore?

Il Problema del Commesso Viaggiatore (TSP) richiede di trovare il tour più breve possibile che visiti ogni città esattamente una volta e torni alla città di partenza. È uno dei problemi più famosi nell'ottimizzazione combinatoria ed è NP-hard nel caso generale, il che significa che non esiste alcun algoritmo noto che risolva ogni istanza in tempo polinomiale.

Cos'è l'algoritmo Held–Karp?

Held–Karp è un algoritmo di programmazione dinamica che risolve il TSP esattamente in tempo O(2ⁿ · n²) e memoria O(2ⁿ · n). È drasticamente più veloce della forza bruta (n fattoriale) ma comunque esponenziale, quindi in pratica viene utilizzato solo per istanze fino a circa 20 città. Questo risolutore usa Held–Karp quando ci sono 12 o meno città.

Cos'è il 2-opt e perché viene usato?

Il 2-opt è un'euristica di ricerca locale che rimuove ripetutamente due archi dal tour corrente e ricollega i due percorsi risultanti nell'altro modo possibile. Quando il nuovo tour è più breve, lo scambio viene mantenuto. Il 2-opt gira in tempo polinomiale per iterazione e trova costantemente tour entro pochi punti percentuali dall'ottimale, motivo per cui è l'euristica classica di riferimento per istanze TSP più grandi.

Quando dovrei usare le coordinate rispetto a una matrice di distanza?

Usa le coordinate quando le tue città si trovano su un piano con distanze in linea retta — per esempio punti su una mappa, posizioni di magazzino o fori su un circuito stampato. Usa una matrice di distanza quando il costo a coppie non è euclideo — per esempio prezzi dei voli, tempi di viaggio con traffico, distanze stradali a senso unico o costi asimmetrici. La modalità matrice accetta qualsiasi distanza non negativa, anche asimmetrica.

La soluzione 2-opt è ottimale?

No, il 2-opt restituisce un tour 2-ottimale, il che significa che nessuna singola coppia di archi può essere scambiata per produrre un percorso più breve. Questo è un ottimo locale e solitamente si trova entro pochi punti percentuali dall'ottimo globale su istanze ben strutturate, ma non è garantito che sia il migliore in assoluto. Per un tour dimostrabilmente ottimale su istanze piccole, scegli Held–Karp.

Questo strumento supporta matrici di distanza asimmetriche?

Sì. Nella modalità Matrice di distanza puoi inserire qualsiasi matrice quadrata non negativa, incluse quelle asimmetriche dove D[i][j] differisce da D[j][i]. Sia Held–Karp che 2-opt gestiscono correttamente le matrici asimmetriche. Questo è utile per problemi di routing nel mondo reale con strade a senso unico, traffico o costi di volo dipendenti dal vento.

Ulteriori Approfondimenti

• Problema del commesso viaggiatore — Wikipedia
• Algoritmo Held–Karp — Wikipedia (Inglese)
• 2-opt — Wikipedia (Inglese)
• Algoritmo del vicino più prossimo — Wikipedia (Inglese)

Altri strumenti correlati:

Operazioni matematiche avanzate:

• Calcolatore di Antilogaritmo
• Calcolatore di funzione Beta
• Calcolatore del Coefficiente Binomiale
• Calcolatrice di distribuzione binomiale
• Calcolatore Bitwise
• Calcolatore del Teorema Centrale del Limite
• Calcolatore di combinazione In Primo Piano
• Calcolatore di Funzione di Errore Complementare
• Calcolatrice di Numeri Complessi
• Calcolatore di Entropia
• Calcolatore della funzione di errore
• Calcolatore di decadimento esponenziale
• Calcolatore della crescita esponenziale
• Calcolatore dell'Integrale Esponenziale
• calcolatore-di-esponenti-alta-precisione
• Calcolatrice del Fattoriale
• Calcolatore della Funzione Gamma
• Calcolatore del Rapporto Aureo
• Calcolatore del tempo di dimezzamento
• Calcolatore del Tasso di Crescita Percentuale
• Calcolatore di Permutazione
• Calcolatrice della Distribuzione di Poisson
• Calcolatrice delle Radici dei Polinomi con Passaggi Dettagliati
• Calcolatrice delle probabilità
• Calcolatrice di Distribuzione di Probabilità
• Calcolatore di Proporzioni
• Calcolatore di formula quadratica
• Calcolatrice Scientifica In Primo Piano
• Calcolatore di notazioni scientifiche
• Calcolatore di Cifre Significative Nuovo
• Calcolatore di Somme di Cubi
• Calcolatore di somme di numeri interi positivi
• Calcolatore di Somme di Quadrati
• Generatore di Tabella di Verità Nuovo
• Calcolatore di Teoria degli Insiemi Nuovo
• Generatore di Diagramma di Venn (3 Insiemi) Nuovo
• Calcolatore del Teorema Cinese del Resto Nuovo
• Calcolatore della Funzione Toziente di Eulero Nuovo
• Calcolatore dell'Algoritmo Euclideo Esteso Nuovo
• Calcolatore dell'Inverso Moltiplicativo Modulare Nuovo
• Calcolatore di Frazioni Continue Nuovo
• Calcolatore del Percorso più Breve di Dijkstra Nuovo
• Calcolatore dell'Albero Ricoprente Minimo Nuovo
• Validatore di Sequenza di Gradi di Grafo Nuovo
• Calcolatore di Derangement (Sottofattoriale) Nuovo
• Calcolatore di Numeri di Stirling Nuovo
• Calcolatore del Principio dei Cassetti Nuovo
• Calcolatore Distribuzione Stazionaria Catena di Markov Nuovo
• Calcolatore di Arrotondamento Nuovo
• Calcolatore Distribuzione Binomiale Negativa Nuovo
• Calcolatore Permutazioni con Ripetizione Nuovo
• Calcolatore Esponenziazione Modulare Nuovo
• Calcolatore Radice Primitiva Nuovo
• Semplificatore di Algebra Booleana Nuovo
• Risolutore di Mappa di Karnaugh (K-Map) Nuovo
• Calcolatore di Colorazione di Grafi Nuovo
• Calcolatore di Ordinamento Topologico Nuovo
• Calcolatore di Matrice di Adiacenza Nuovo
• Calcolatore Inclusione-Esclusione Nuovo
• Risolutore di Programmazione Lineare Nuovo
• Risolutore del Commesso Viaggiatore (TSP) Nuovo
• Verificatore di Cammino Hamiltoniano Nuovo