- Giro
- Più breve trovato
- Partenza
| Metodo | Lunghezza | Sopra il più breve | Passi |
|---|---|---|---|
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - |
Problema del commesso viaggiatore
Un commesso viaggiatore deve visitare ogni città una volta e tornare a casa. Quale ordine rende il viaggio più breve? La domanda è facile da porre ma, al crescere del numero di città, rispondere provando tutti gli ordini diventa impossibile: già 30 città permettono circa 4,4 × 10³⁰ giri. Sparpaglia le città su una mappa o aggiungi le tue con un clic, poi guarda semplici regole empiriche, miglioramenti ingegnosi e un metodo esatto costruire i loro giri passo dopo passo, e scopri quanto si avvicinano quelli veloci. Scegli come sono disposte le città e quante sono, scegli un metodo e premi Risolvi per vederlo costruire un giro passo dopo passo, oppure Passo per avanzare di una mossa alla volta. Fai clic sulla mappa per aggiungere una città o su una città per rimuoverla. Confronta tutti esegue ogni metodo sulle stesse città e mostra quanto ciascuno si discosta dal giro più breve trovato. La città rossa è il punto di partenza del viaggio.
Come funziona
- Scegli una disposizione e il numero di città, oppure fai clic sulla mappa per posizionare le tue e su una città per rimuoverla.
- Scegli un metodo e premi Risolvi per seguirlo passo dopo passo, oppure Passo per avanzare di una mossa alla volta.
- Premi Confronta tutti per eseguire ogni metodo sulle stesse città e leggi di quanto ciascun giro supera il più breve trovato.
Perché è difficile
Con n città esistono (n − 1)! / 2 giri diversi, perché non importa da dove si parte né in quale verso si percorre il giro. Sono 12 per 5 città, 181.440 per 10 e circa 6 × 10¹⁶ per 20. Non si conosce alcun metodo che trovi il viaggio più breve per ogni mappa in un tempo che cresca solo come una potenza di n: il problema è NP-difficile. Il miglior metodo esatto di questa app, la programmazione dinamica di Held–Karp del 1962, richiede comunque circa n² · 2ⁿ passi, perciò qui è limitato a 12 città.
Buoni giri in fretta
In pratica i giri quasi più brevi si trovano in fretta. Il vicino più prossimo va sempre alla città non visitata più vicina e di solito finisce circa il 25% sopra il giro migliore. L'inserimento più economico fa crescere un anello e aggiunge la città che lo allunga di meno. 2-opt prende un giro qualsiasi e continua a sostituire due archi con due più corti, il che elimina ogni incrocio e di solito arriva entro il 5% circa. La ricottura simulata fa mosse 2-opt casuali e, finché è ancora «calda», ne accetta alcune che allungano il giro, così può risalire dai vicoli ciechi prima di assestarsi.
Domande frequenti
Esiste una formula per il percorso più breve?
No. Il giro più breve dipende dalle posizioni esatte di tutte le città, e nessun metodo noto lo trova per ogni mappa senza, nel caso peggiore, una quantità di lavoro che cresce in modo esponenziale. Per qualche centinaio o migliaio di città, risolutori esatti specializzati come Concorde dimostrano comunque giri ottimali combinando la programmazione lineare con potature ingegnose, e l'istanza più grande risolta esattamente finora ha 85.900 punti.
Perché 2-opt elimina ogni incrocio?
Se due archi di un giro si incrociano, le quattro città che collegano formano un quadrilatero le cui diagonali sono i due archi. Sostituirli con due lati opposti del quadrilatero è sempre più corto, per la disuguaglianza triangolare, e inverte il tratto di giro compreso tra loro. 2-opt continua a fare scambi di questo tipo finché nessuno aiuta più, quindi il suo giro finale non si incrocia mai.
Che cos'è la temperatura nella ricottura simulata?
Regola quanto il metodo è disposto ad accettare una mossa che allunga il giro. Una mossa che aggiunge d alla lunghezza viene accettata con probabilità e^(−d/T). A una temperatura T alta passa quasi tutto, il che permette al giro di sfuggire a una disposizione scadente; man mano che T scende il metodo diventa avido e si assesta. Il nome deriva dal raffreddamento lento dei metalli, che permette ai loro atomi di trovare una disposizione a bassa energia.
Perché il metodo esatto è limitato a 12 città?
Held–Karp memorizza il cammino più breve per ogni sottoinsieme di città e ogni possibile ultima città, cioè circa n · 2ⁿ numeri, e calcola ciascuno con n confronti. Per 12 città sono qualche centinaio di migliaia di passi; per 25 città sarebbero miliardi. È comunque enormemente più veloce che provare tutti gli (n − 1)! / 2 giri: per 12 città sarebbero quasi 20 milioni.
Viene inviato qualcosa a un server?
No. Le città e tutti e cinque i metodi vengono eseguiti nel tuo browser. Le città che aggiungi con un clic restano nella memoria locale di questo browser.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor