Dal 2010 · Oltre 2 milioni di utilizzi degli strumenti ogni mese
Dal 2010
Aggiungi a Chrome

La Mia Cassetta Degli Attrezzi

Modalità Automatica

Nessuno strumento salvato.

Aggiorna alla Versione Premium
Strumenti correlati
Generatore di SpirografoGeneratore di Labirinti
Pagina Iniziale > Matematica > Operazioni matematiche avanzate
 

Risolutore del Commesso Viaggiatore (TSP)

Trova il tour più breve che visita ogni città una volta e torna al punto di partenza. Usa la programmazione dinamica esatta di Held-Karp per istanze piccole e il vicino più prossimo con 2-opt per quelle più grandi, da coordinate o matrice.

Utilizzo gratuitoSenza registrazioneRisultati istantanei
Risolutore del Commesso Viaggiatore (TSP)Provalo ora — gratis ▼
Esempi rapidi:
Quadrato + punta 5 città 8 città casuali 8 capitali UE Matrice 4×4 Benchmark 10 città Triangolo (percorso aperto)
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 separate da virgola o spazio, una per ogni riga della matrice. Default A, B, C… se omesso.

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=1n-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) = mink ∈ S \ {j} [ C(S \ {j}, k) + d(k, j) ]

Il costo del tour ottimale è quindi minj [C({1,...,n}, j) + d(j, 1)]. Held–Karp gira in tempo O(2n · n²) e memoria O(2n · 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(2n · n²) O(2n · 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

  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:

Applicazioni nel Mondo Reale

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(2n · n²) e memoria O(2n · 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.

Operazioni matematiche avanzate:

Strumenti popolari e aggiornati:

Risolutore di Programmazione LineareRisolutore di Mappa di Karnaugh (K-Map)Risolutore del Problema del Matrimonio StabileVedi tutti →
Pagina Iniziale > Matematica > Operazioni matematiche avanzate > Risolutore del Commesso Viaggiatore (TSP)