Voyager par exemple de vendeur avec optimum global connu

Question

J'ai fait un algorithme mémétique en Python pour problème du voyageur de commerce . Cependant, toutes les données de test (liste des distances entre les villes) que j'ai rencontrés ne disposent pas des informations de la meilleure solution, donc je ne peux pas savoir à quelle distance optimum global mon algorithme obtient.

Quelqu'un sait où je peux trouver des données de test de TSP (de préférence sous forme de matrice, mais la bonne de quoi que ce soit) avec la meilleure solution connue?

Answer 1

Avez-vous Google?

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

Cette page fournit que plusieurs cas-tests de 16 a une solution optimale.

Answer 2

Peut-être que vous pouvez générer vos propres données de test?

Ce ne sera certainement pas des tests complets, mais il pourrait aider. Remarque: le dessous est sur le chemin hamiltonien, et si vous êtes à la recherche des cycles, ce travail de volonté semblable

.

Vous pouvez faire ce qui suit:

Dites que vous donne un graphe non orienté G avec n nœuds.

Vous créez maintenant un graphe pondéré G «en réglant le poids des arêtes de G à 1, et en ajoutant les bords non G, et en leur donnant un poids aléatoire> 1, à savoir G » est un graphe complet avec des poids attribué à tous ses bords.

Maintenant, si vous exécutez un algorithme de TSP valide sur G » et génère un chemin de taille n-1, alors G a un chemin hamiltonien. Dans le cas contraire G ne dispose pas d'un chemin hamiltonien.

Alors maintenant, vous pouvez utiliser des graphiques que vous connaissez qui ont / ne pas avoir des chemins hamiltonien (par exemple: Hypercube a des pistes hamiltonien) et générer des données de test pour votre algorithme TSP.

Cette page a des conditions suffisantes qui pourraient se révéler utiles pour générer des graphiques qui ont des chemins hamiltoniens: http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html

Je suppose que vous n'aurez du mal à trouver des données sur les graphiques avec / sans chemins hamiltonien.

it helps. Bonne chance!

Answer 3

TSPLIB est une bibliothèque d'échantillons pour le cas TSP (et les problèmes connexes) provenant de diverses sources et de différents types.

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