Les données pour la simple cuillère à thé
J'ai écrit un simple algorithme génétique pour résoudre problème du voyageur de commerce avec 5 villes. Je veux voir comment il le fait sur un problème avec plus de villes, de quelque chose comme 10, 25, 50, 100, mais je ne peux pas trouver un exemple de date pour le problème de l'essayer. En gros, je suis à la recherche pour la 2D des listes ou des matrices de distances entre les villes. Ce serait bien si il y a une solution. Où dois-je chercher?
Je Vous remercie à l'Avance
Voulez-vous des données avec des solutions exactes, ou simplement les données? Vous pouvez toujours construire votre propre ensembles de données si vous le souhaitez. Aussi, vous êtes à la recherche pour Euclidien c. à thé de cas, ou arbitraire c. à thé de cas?
Si des solutions sont inclus, ce serait sympa. Je ne sais pas ce Euclidienne et de l'Arbitraire c. à thé instances sont. Je suis juste de commencer.
Vous pouvez également créer des jeux avec les solutions connues pour commencer - par exemple, créer des n points sur un cercle. La meilleure solution est de les traverser dans l'ordre, et vous pouvez vous rapprocher de l'idéal de longueur de chemin d'accès par la longueur du cercle.
bonne idée. Merci.
Si des solutions sont inclus, ce serait sympa. Je ne sais pas ce Euclidienne et de l'Arbitraire c. à thé instances sont. Je suis juste de commencer.
Vous pouvez également créer des jeux avec les solutions connues pour commencer - par exemple, créer des n points sur un cercle. La meilleure solution est de les traverser dans l'ordre, et vous pouvez vous rapprocher de l'idéal de longueur de chemin d'accès par la longueur du cercle.
bonne idée. Merci.
OriginalL'auteur Akavall | 2012-06-13
Vous devez vous connecter pour publier un commentaire.
Je ne suis pas sûr, mais comme il semble, la page "De lecture ou d'Écriture Problème du voyageur de commerce (TSP) des Fichiers " avoir une entrée de données de fichiers, par exemple, cette une.
Aussi, "C. à thé de Données de Test" est une bonne source.
OriginalL'auteur gahcep
Une référence connue de la bibliothèque pour le TSP avec les instances allant de 14 à près de 100 000 villes est la TSPLIB. Les cas ont été résolus à l'optimalité, pour certains cas, la solution optimale est également disponible.
De nombreuses instances ont un fond comme les frais de déplacement été villes en Allemagne, en Suisse, aux états-unis ou dans le monde entier. Certains de ces cas représentent des problèmes de forage pour ordinateur tracé de la carte Il y a aussi une instance qui représente le voyage d'Ulysse.
OriginalL'auteur Andreas
Les sources que j'ai trouvé en ligne sont assez énormes. J'ai peut-être fait quelque chose de mal, mais 10 lieux (villes) de prendre ~0,6 s et 11 places de prendre ~7s. Le plus petit connu-solution dataset que j'ai pu trouver était de 15 places (et considéré comme "petit", le "classique" un être de 48 places), mais peut-être ceux qui sont pour l'optimisation de la (non-brute force) des algorithmes. En fin de compte j'ai fait ma propre table avec du monde réel villes:
Le format de données lisible par le programme est partielle d'un tableau (parce que c'est symétrique):
Pour moi, cela prend environ 6,7 secondes sur une 3ème génération i7 (i7-3630QM). Le programme est écrit en C++, single-threaded et simplement brute-forces les possibilités. Pour les tests, il peut être plus pratique de retirer un seul endroit, alors il faut ~660ms (0,7 s) ce qui est suffisant pour voir si le code change beaucoup de différence.
Merci 🙂 m'a Aidé et j'ai obtenu la même réponse 🙂
OriginalL'auteur Luc