Ho scritto un semplice algoritmo genetico che può risolvere il problema del commesso viaggiatore in 5 città. Voglio vedere come funziona su un problema con più città, qualcosa come 10, 25, 50, 100, ma non riesco a trovare una data di esempio per il problema per provarlo. Fondamentalmente, sto cercando liste 2D o matrici con distanze tra città. Sarebbe bello se ci fosse una soluzione. Dove dovrei guardare?Dati per TSP semplice
ringraziare in anticipo
Non sono sicuro, ma a quanto pare, la pagina "Read or Write Traveling Salesman Problem (TSP) Files" avere alcuni file di dati di input, ad esempio, this one.
Inoltre, "TSP Test Data" è una buona fonte.
Grazie, sì, il tuo primo collegamento sembra quello che sto cercando. Ho visto cose "TSP TEST TEST", ma sembrano contenere troppe città. – Akavall
Una nota libreria di benchmark per il TSP con istanze che vanno da un minimo di 14 a quasi 100.000 città è la TSPLIB. Le istanze sono state risolte in ottimalità, per alcuni casi è disponibile anche la soluzione ottimale.
Molte delle istanze hanno uno sfondo del mondo reale come viaggi in città in Germania, Svizzera, Stati Uniti o nel mondo intero. Alcune delle istanze rappresentano problemi di perforazione per il layout della scheda del computer. C'è anche un'istanza che rappresenta il viaggio di Ulisse.
Le fonti che ho trovato online sono piuttosto enormi. Potrei fare qualcosa di sbagliato, ma 10 luoghi (città) prendono ~ 0.6 secondi e 11 luoghi prendono ~ 7 secondi. Il set di dati con la più piccola soluzione conosciuta che ho trovato era di 15 posti (e considerato "piccolo", il "classico" di 48 posti) ma forse quelli per gli algoritmi ottimizzati (forza non bruta). Alla fine ho fatto la mia propria tabella con le città del mondo reale:
m
a
a h
s h s u
t a e i g l
r a e t e s
i c r t l e b b a e
c h l a e c o e n o p
h e e r e h n r n h e
t n n d n t n g e e n
maastricht 0 29 20 21 16 31 100 12 4 31 18
aachen 29 0 15 29 28 40 72 21 29 41 12
heerlen 20 15 0 15 14 25 81 9 23 27 13
sittard 21 29 15 0 4 12 92 12 25 13 25
geleen 16 28 14 4 0 16 94 9 20 16 22
echt 31 40 25 12 16 0 95 24 36 3 37
bonn 100 72 81 92 94 95 0 90 101 99 84
hulsberg 12 21 9 12 9 24 90 0 15 25 13
kanne 4 29 23 25 20 36 101 15 0 35 18
ohe 31 41 27 13 16 3 99 25 35 0 38
epen 18 12 13 25 22 37 84 13 18 38 0
Optimal (by program): cities 0-7-4-3-9-5-2-6-1-10-8-0 = 253km
maastricht -> hulsberg -> geleen -> sittard -> ohe -> kanne -> echt
-> heerlen -> bonn -> aachen -> epen -> kanne -> maastricht
Il formato dei dati leggibili dal programma è una tabella parziale (perché è simmetrica):
29 20 21 16 31 100 12 4 31 18
15 29 28 40 72 21 29 41 12
15 14 25 81 9 23 27 13
4 12 92 12 25 13 25
16 94 9 20 16 22
95 24 36 3 37
90 101 99 84
15 25 13
35 18
38
Per me questo richiede ~ 6,7 secondi per l'elaborazione su un terzo gen i7 (i7-3630QM). Il programma è scritto in C++, single-threaded e semplicemente brute-forza le possibilità. Per testare potrebbe essere più pratico rimuovere un posto, quindi occorrono ~ 660ms (0,7s) che sono ancora sufficienti per vedere se le modifiche al codice fanno la differenza.
Ho testato il mio solutore TSP e ottengo lo stesso percorso: D Sono molto contento :) – Kamil
Grazie :) Mi ha aiutato e ho avuto la stessa risposta :) –
Desideri dati con soluzioni esatte o solo dati? Puoi sempre creare i tuoi set di dati, se lo desideri. Inoltre, stai cercando istanze TSP euclidee o istanze TSP arbitrarie? – templatetypedef
Se le soluzioni sono incluse, sarebbe bello. Non so quali siano le istanze TSP Euclide e Arbitrarie. Sto solo iniziando. – Akavall
È anche possibile creare set con soluzioni note per iniziare, ad esempio creare n punti su una circonferenza. La soluzione migliore è attraversarli in ordine e puoi approssimare la lunghezza del percorso ideale in base alla lunghezza del cerchio. – Mathias