Peut-être pouvez-vous générer vos propres données de test?
Ce ne sera certainement pas un test complet, mais cela pourrait aider. Note: le chemin ci-dessous concerne le chemin hamiltonien, et si vous cherchez des cycles, quelque chose de similaire fonctionnera.
Vous pouvez effectuer les opérations suivantes:
Dites que vous êtes donné un graphe non orienté G avec n nœuds. Vous créez maintenant un graphe pondéré G ', en définissant le poids des arêtes dans G sur 1, et en ajoutant les arêtes non dans G, et en leur donnant un poids aléatoire> 1, c'est-à-dire que G' est un graphe complet avec poids assignés à tous ses bords.
Maintenant, si vous exécutez un algorithme TSP valide sur G 'et qu'il génère un chemin de taille n-1, alors G a un chemin hamiltonien. Sinon, G n'a pas de chemin hamiltonien.
Alors maintenant, vous pouvez utiliser des graphiques que vous savoir qui ont/ne pas avoir des chemins hamiltoniens (pour par exemple: Hypercube a des chemins hamiltoniens) et générer des données de test pour votre algorithme de 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 sans chemins hamiltoniens avec /.
Espérons que ça aide. Bonne chance!
Il vend toujours sur eBay, qui est apparemment O (1). :-P http://xkcd.com/399/ –