Labo Algo
Labo Algo
Si vous participez au défi des 250 villes, cette applet permet de visualiser les résultats de votre algorithme sans avoir à développer un afficheur spécifique.
NB : l'applet ne résoud pas le problème, elle affiche un parcours sous forme graphique.
Il s'agit d'un logiciel libre (GPL) dont code source est disponible ici : DisplayTsp.java (version html pour lecture)
(Ce n'est pas un modèle de programmation, mais ça marche bien :) - toute amélioration est la bienvenue !)
Merci d'ailleurs à Xavier Clarist pour sa correction dans la version 0.37 !
Code "exécutable" : DisplayTsp.class (fichier/enregister sous)
Code source : DisplayTsp.java
Si vous avez récupéré la version source, vous pouvez le compiler (générer le .class) avec la commande suivante :
javac DisplayTsp.java
Si vous avez le fichier .class, il suffit de l'installer dans le répertoire de la page html utilisant l'applet.
Meilleur parcours du défi des 250 villes |
Premier exemple : l'affichage du meilleur parcours du défi des 250 villes. Les villes sont matérialisées sur l'image ci-dessous par les points rouges. Il y en a 250, vous pouvez compter ! En bleu le parcours, c'est à dire le trajet que doit faire le voyageur de commerce pour aller le plus rapidement d'une ville à l'autre. Il est possible de zoomer sur l'image avec un clic droit puis en déplaçant la souris vers la droite (zoom) ou la gauche (dézoom). On peut aussi bouger l'image avec un clic gauche. Pour utiliser l'applet c''st simple, il suffit d'intégrer le code suivant dans votre page html :
<html>
<applet code="DisplayTsp.class" width=400 height=400>
<param name="Problem" value="default">
<param name="Parcours" value="0-85-24-202-51-05-61-92-37-06-153-32-242-suite de votre parcours...">
</applet>
</html>
Dans le même répertoire, placez le fichier DisplayTsp.class (l'applet Java).
|
Problème à 100 villes |
On peut se servir de cette applet pour afficher d'autres problèmes que le défi des 250 villes. Pour cela il faut mettre le paramètre "Problem" à la valeur "custom", et indiquer dans les paramètres CitiesPosX et CitiesPosY les coordonnées des points. Exemple :
<html>
<applet code="DisplayTsp.class" width=300 height=300>
<param name="Problem" value="custom">
<param name = CitiesPosX value = "1;3;5;7;4;6;8;9;10;2">
<param name = CitiesPosY value = "4;8;7;2;1;3;5;6;10;9">
<param name="Parcours" value="0-4-5-3-6-7-8-2-1-9">
</applet>
</html>
|
Problème à 10 villes |
Il suffit d'ajouter le paramètre ShowCityNumber :
<html>
<applet code="DisplayTsp.class" width=300 height=300>
<param name="Problem" value="custom">
<param name = CitiesPosX value = "1;3;5;7;4;6;8;9;10;2">
<param name = CitiesPosY value = "4;8;7;2;1;3;5;6;10;9">
<param name = ShowCityNumber value = "true">
<param name="Parcours" value="0-4-5-3-6-7-8-2-1-9">
</applet>
</html>
|
Deux trajets du défi des 250 villes |
Pour afficher les 2 solutions séparément, cliquer sur l'applet. Le code à intégrer à la page html est le suivant :
<html>
<applet code="DisplayTsp.class" width=400 height=400>
<param name="Problem" value="default">
<param name="Parcours" value="0-85-24-202-51-05-61-92-37-06-153-32-242-suite de votre parcours...">
<param name="Parcours2" value="0-85-24-202-51-05-61-92-37-06-153-32-242-suite de votre parcours...">
</applet>
</html>
|
TSPLIB est une bibliothèque de problèmes du voyageur de commerce.
Le format de fichier est différent de celui que j'utilise pour le défi du voyageur de commerce.
L'avantage est que l'on peut comparer les résultats de son algorithme avec ceux des chercheurs en informatique...
Pour l'utiliser avec l'applet avec la TSPLIB, modifiez le paramètre "ProblemType" :
<html>
<applet code="DisplayTsp.class" width=400 height=400>
<param name="ProblemType" value="tsplib">
<param name="Problem" value="custom">
<param name = CitiesPosX value = "1;3;5;7;4;6;8;9;10;2">
<param name = CitiesPosY value = "4;8;7;2;1;3;5;6;10;9">
<param name="Parcours" value="0-5-8-2-7-10-1-3-6-4">
</applet>
</html>
Vous pouvez télécharger les fichiers de problèmes sur : ftp://ftp.zib.de/pub/Packages/mp-testdata/tsp/tsplib/tsp/index.html
eil76.tsp |
ch150.tsp |
d198.tsp |
lin318.tsp |
pcb442.tsp |
rat783.tsp |
Labo Algo
Alexandre Aupetit, Mai 2004