C'est chouette comme défi alors je me lance
Je vais commencer par les limites, il faut donc définir le "max" de la chose.
Pour connaître le nombre de combinaisons possibles avec 250 villes il "suffit" de calculer la factorielle de 250 (càd 250!).
Le nombre est hallucinant, il fait 493 chiffres de long.
Autant dire que faire chaque combinaison prendra du temps.
Pour calculer la distance d'un parcours on fait joujou avec pythagore, rien de complexe.
D'ailleurs ici il est relativement simple et pas trop coûteux en cpu de calculer toutes les segments entre deux points et les mettre dans une matrice (tableau en 2 dimensions). Il y a 250 points qui chacun peuvent être reliés à 249 autres points ce qui nous fait 62250 segments.
Il y aura des doubles (ex: 1->250 et 250->1) mais ce n'est qu'une histoire d'optimisation.
Le principe est donc de prendre la meilleure combinaison de ces 62250 valeurs.
LA question c'est de savoir si on peut définir facilement la distance la plus courte sans forcément connaître le chemin histoire de voir la pertinance de nos algorithmes.
La réponse est OUI, mais (ben vi) au plus le nombre de villes est grand au plus cela demandera de cpu et à l'heure actuelle quand on arrive avec des centaines ou milliers de villes cela prendrait des années.
Par contre il existe des algorithmes pour estimer la distance (heuristique, génétique etc...) mais cela reste des estimations même si on approche des 100% il y a toujours une possibilité qu'il y ait un chemin plus court.
Essayons de faire un algorithme "basique".
La forme extrême est le cercle, car si l'on prend tous les points d'un cercle on peut affirmer que le chemin le plus court est de "suivre" le cercle, ce qui donne son périmètre.
Si je prends 5 points sur le cercle, je peux affirmer que la meilleure méthode est de prendre le plus petit segment, puis le plus petit suivant etc... jusqu'au dernier.
Cet algorithme a une particularité, c'est de pouvoir connaître la distance "superminimale" (j'ai pas trouvé mieux désolé).
En gros, on peut affirmer que la distance à parcourir sera TOUJOURS plus grande que la somme du plus petit segment de chaque point.
J'illustre un peu:
En dessinant un hexagone parfait (6 côtés) on a 6 points (les coins) que l'on va numéroter de 1 à 6 dans le sens horlogique.
Maintenant si je prends le chemin 1-4-2-5-3-6 on voit clairement que ça ne sera pas le plus court. Par contre le chemin 1-2-3-4-5-6 a l'air d'être le plus court car c'est la forme du cercle.
Le problème c'est qu'on a pas un cercle ni une forme parfaite.
Mon idée d'algorithme pour résoudre ça :p
Je pense que le seul moyen d'être certain de résoudre (pas d'estimer) le défi c'est d'énumérer toutes les combinaisons faute de formule magique pour calculer la plus petite distance.
Je l'ai dit plus haut ça prendrait des années, par contre il y a moyen d'optimiser la chose.
Si je prends tous les plus grands segments je suis certain de ne pas avoir la plus courte (la distance hein
).
Faisons l'inverse !
On va donc commencer avec la "superminimale" et on va regarder si tous les points sont dans notre calcul et si il n'y a pas de point en double.
Si tous les points sont dedans et pas de double on a trouvé, ce qui est peu probable dans le défi250.
Mantenant on change chaque segment par le second plus petit.
On check de nouveau les doubles et si tous les points y sont.
Enfin, on boucle en changeant un des segments par le suivant plus petit jusqu'à la fin.
On répète jusqu'à ce qu'on ait plus de doubles et que tous les points soient dedans.
Ce n'est probablement pas la méthode la plus optimisée mais c'est certainement la méthode qui permet d'être certain d'avoir la plus courte distance.
Voilà j'ai fini ma tartine :p
(LOGIN)
