Viaggiando esempio venditore con nota ottimale globale

Question

Ho fatto un algoritmo memetica in Python per problema del commesso viaggiatore . Tuttavia, tutti i dati di test (elenco delle distanze tra le città) che ho incontrato non hanno le informazioni della soluzione migliore, quindi non posso sapere come vicino alla ottimale globale il mio algoritmo ottiene.

Qualcuno sa dove posso trovare alcuni dati di test cucchiaino (preferibilmente in forma matriciale, ma buona di nulla) con la migliore soluzione nota?

Answer 1

Hai Google?

http://www.tsp.gatech.edu/data/index.html

Tale pagina fornisce diversi test-casi di cui 16 ha una soluzione ottimale.

Answer 2

Forse è possibile generare i propri dati di test?

Questo sicuramente non sarà la prova completa, ma potrebbe aiutare. Nota: Il sotto è di circa percorso hamiltoniano, e se siete alla ricerca di cicli, qualcosa di simile opera volontà

.

È possibile effettuare le seguenti operazioni:

Di 'si è dato un grafo non orientato G con n nodi.

Ora creare un grafo pesato G 'fissando il peso di spigoli in G di essere 1, e aggiungendo i bordi non in G, e dando loro un peso random> 1, cioè G' è un grafico completo con pesi assegnato a tutti i suoi bordi.

Ora, se si esegue un algoritmo di TSP valida su G' e genera un percorso di dimensione n-1, allora G ha un percorso hamiltoniano. In caso contrario, G non ha un percorso hamiltoniano.

Così ora è possibile utilizzare i grafici si sa che hanno / non hanno cammini hamiltoniani (per esempio: Hypercube ha cammini hamiltoniani) e generare dati di test per il vostro algoritmo di TSP.

Questa pagina ha alcune condizioni sufficienti che potrebbero rivelarsi utile per generare grafici che hanno percorsi hamiltoniani: http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html

suppongo non si avrà difficoltà a trovare i dati su grafici con / senza percorsi hamiltoniani.

La speranza aiuta. Buona fortuna!

Answer 3

TSPLIB è una libreria di istanze di esempio per il TSP (e problemi connessi) da varie fonti e di vario tipo.

http://comopt.ifi.uni-heidelberg.de/software/ TSPLIB95 /