Devenu fou par l'optimisation de mon solveur TSP, je me suis mis à chercher différentes méthodes pour trouver une solution optimale de façon optimale. Après quelques hypothèses de distribution d'arbre dont je n'ai pas encore tiré profit dans mon solveur, je me suis demandé s'il n'était pas possible de déterminer le meilleur chemin d'un problème à n villes en se basant sur le même problème auquel on retire une ville pour calculer l'optimum et qu'on rajoute ensuite à l'emplacement idéal.
M. Dupas et M. Hsu m'ont indiqué qu'il ne semblait/n'était pas possible d'utiliser ce genre d'hypothèse pour garantir le meilleur chemin, mais sans trouver d'exemple qui me démontre le contraire.
J'ai donc passé ma soirée à coder une solution qui utiliserait cette hypothèse pour calculer le meilleur chemin. Et j'ai trouvé ... que mon hypothèse était bien foireuse :)
Pour passer d'un problème à 8 villes à un problème à 9 villes, on se rend compte qu'il faut ajouter un tronçon et en modifier 2 pour conserver l'optimalité.
J'ai aussi fini la première version de mon solveur TSP en JAVA. Celui-ci est beaucoup trop trop trop trop lent. J'ai commencé à virer tous les éléments non-primitifs comme les ArrayLists et les Vectors afin d'obtenir une version tout de même un peu plus rapide.
Le seul intéret de la version Java est d'avoir un apercu graphique immédiat qui se met à jour en fonction de la meilleure route trouvée actuelle.

Pour ce week-end je prévois de commencer à regarder comment utiliser les algos génétiques pour trouver une solution intéressante de façon assez rapide même pour un problème de grande taille.
Voici les points à voir :

comment trouver la population d'origine ? On cherche à trouver plusieurs "bonnes" populations ou on les tire au hasard ? Combien en faut-il ? Doit-on prendre des solutions obligatoirement très différentes ? comment muter en évitant de répéter les cycles de recherche (si l'on mute ou l'on croise plusieurs fois ne risque-t-on pas de voir apparaitre la même population qu'au départ ? comment muter/croiser les solutions dans des situations non-binaires mais d'ordres (ou il ne s'agit pas d'avoir ou non une caractérisque, mais d'ordonner celles-ci) ?

En ce moment, je prends bien plus de plaisir à coder des algos et à réfléchir sur ceux-ci plutôt que d'étudier ProActive et la distribution des programmes.