Risolutore del Commesso Viaggiatore (TSP)

Trova il percorso più breve che visita ogni città esattamente una volta e torna all'inizio. Programmazione dinamica esatta (Held-Karp) per istanze piccole ed euristiche nearest-neighbor + 2-opt per quelle più grandi. Accetta coordinate o una matrice di adiacenza e genera un tour animato in SVG.

Esempi rapidi:

Quadrato + punta 5 città 8 città casuali 8 capitali UE Matrice 4×4 Benchmark 10 città Triangolo (percorso aperto)

⌖ Coordinate (x, y) ▦ Matrice di distanza

Città o matrice

Linee coordinate: A, 10, 20 o 10 20. Righe matrice: 0 10 15 20 — una riga per linea, quadrata, non negativa. Max 40 città.

Etichette matrice (opzionale)

Etichette separate da virgola o spazio, una per ogni riga della matrice. Default A, B, C… se omesso.

Algoritmo

Tipo di tour

Embed Risolutore del Commesso Viaggiatore (TSP) Widget

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:

minimizza Σ_i=1^n-1 d(π(i), π(i+1)) + d(π(n), π(1))

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:

C(S, j) = min_{k ∈ S \ {j}} [ C(S \ {j}, k) + d(k, j) ]

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:

Prima: ... a — b ... c — d ... Dopo lo scambio 2-opt: ... a — c ... b — d ... Se d(a,c) + d(b,d) < d(a,b) + d(c,d) → accetta lo scambio, inverti il subtour b..c

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.

A, 10, 20 B, 40, 70 C, 75, 30 Parigi: 2.35, 48.86 10 20 ← auto-etichettata C1

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.

0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0

Confronto tra Algoritmi

Algoritmo	Complessità temporale	Memoria	Qualità del risultato	Dimensione pratica
Forza bruta	O(n!)	O(n)	Ottimale	n ≤ 10
Held–Karp DP	O(2ⁿ · n²)	O(2ⁿ · n)	Ottimale	n ≤ 20
Nearest-Neighbor	O(n²)	O(n)	~25% peggiore dell'ottimale	n ≤ migliaia
NN + 2-opt	O(n² · passaggi)	O(n)	~2–5% peggiore dell'ottimale	n ≤ centinaia

Come Usare Questo Risolutore

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

Cita questo contenuto, pagina o strumento come:

"Risolutore del Commesso Viaggiatore (TSP)" su https://MiniWebtool.com/it/risolutore-del-commesso-viaggiatore-tsp/ di MiniWebtool, https://MiniWebtool.com/

dal team di miniwebtool. Aggiornato: 21 apr 2026

Puoi anche provare il nostro Risolutore di Matematica AI GPT per risolvere i tuoi problemi matematici attraverso domande e risposte in linguaggio naturale.

Altri strumenti correlati:

Calcolatore del Valore AssolutoNuovo

Calcolatore di Matrice di AdiacenzaNuovo

Verificatore di Numeri AmicabiliNuovo

Visualizzatore di Riporto e PrestitoNuovo

Verificatore di Cammino HamiltonianoNuovo

Calcolatore di Ordinamento TopologicoNuovo

Risolutore del Commesso Viaggiatore (TSP)

Risolutore del Commesso Viaggiatore (TSP)

Cos'è il Problema del Commesso Viaggiatore?

Come Funziona Questo Risolutore

Programmazione Dinamica Held–Karp (Esatta)

Nearest-Neighbor + 2-opt (Euristico)

Formati di Input

Modalità coordinate (x, y)

Modalità matrice di distanza

Confronto tra Algoritmi

Come Usare Questo Risolutore

Esempio Svolto

Applicazioni nel Mondo Reale

Domande Frequenti

Cos'è il Problema del Commesso Viaggiatore?

Cos'è l'algoritmo Held–Karp?

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

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

La soluzione 2-opt è ottimale?

Questo strumento supporta matrici di distanza asimmetriche?

Ulteriori Approfondimenti

Altri strumenti correlati:

Operazioni matematiche avanzate:

Strumenti in primo piano: