Aucune technique ne garantissant une solution optimale, votre kilométrage variera. Avec un peu de chance, chaque technique peut surpasser l'autre. Les deux techniques ont des avantages et des inconvénients.
voisin le plus proche: + rapide, + simple, -généralement pas optimale
algorithme génétique: -slower, complexe -Plus, + tendance solutions vers optimale au fil du temps
La grande différence est que les algorithmes probabilistes comme simulated annealing et les algorithmes génétiques peuvent continuer à s'améliorer avec le temps - plus vous les laissez courir, plus vous avez de chances d'obtenir une solution optimale (bien qu'il n'y ait aucune garantie).
Comme NN est rapide, rien ne vous empêche de combiner les techniques. Exécutez NN pour trouver une solution de démarrage éventuellement meilleure que aléatoire. Ensuite, alimentez cette solution dans votre algorithme génétique et laissez-la fonctionner aussi longtemps que vous le jugez approprié.
Si vous êtes intéressé par les solutions optimales, consultez les pages Lin-Kernighan heuristic et Linear Programming. Les deux ont été utilisés pour trouver des solutions optimales pour les grandes visites, y compris this solution pour un 85,900 city tour et un 24,978 city Sweden tour. Le Georgia Tech TSP site est une ressource géniale.
Applet intéressant ... –
Il semble que dans ce problème, le résultat n'est pas aussi important que le calcul lui-même. – Loki