Le problème du voyageur de commerce est de trouver le cycle le plus court passant par toutes les villes qu'il doit visiter.
C'est un problème NP-complet, ce qui veut dire que pour l'instant, pour prouver qu'on a la meilleure solution, on doit tester toutes les solutions ou presque. On a une complexité de (n-1)!/2 avec n le nombre de ville.
Le problème de tester toutes les solutions, c'est que ça prend un temps considérable, je n'ai pas reussi à faire mieux que 20 villes (environ 80 millions de milliard de possibilité), ça m'a prit 6h sur un Q6600 (quad core de chez intel). Pour arriver à ce résultat, je droppe souvent en plus milieux du calcul du chemin car il y a des moyens de savoir si ce chemin a des chances d'être le meilleur ou pas. Par exemple, si le chemin à un croisement, alors il n'est pas optimal.
Bon, c'est bien beau, mais 20 villes, c'est pas bien compliqué, même pour un humain.
Donc, qu'est ce qu'on peut faire de mieux ?
C'est là que l'algorithme génétique à été employé (tout comme plusieurs sources ici).
Il y a 2 programmes, un qui permet de construire des graphes et un autre qui essaye de le résoudre.
Qu'apporte de plus ma source ? je pense un meilleur résultat et de plus, on peut l'exploiter (du moins, avec le mode sans décroisement car ce mode me fait planter aléatoirement le programme quand la population de chemin converge, et je n'ai pas le temps ni la motivation pour le modifier maintenant que mon projet est rendu).