Curriculum and Labs for Engineering Education
Bonjour à tous j’espère en forme pour un nouveau défi ! encore une certification de votre choix au catalogue passable gratuitement est en jeu. (CLAD, CLD, CLA, CTD...)
Comme tout le monde n’est pas un voyageur de commerce, donc nommer un problème du même nom n’est peut être pas adapté à ce défi…
Que pensez-vous plutôt de pouvoir optimiser vos déplacements quand vous avez plusieurs endroits à visiter pendant vos congés ? C’est plus séduisant…
Cela correspond à quoi en LabVIEW ? Passer par tous les points d’un tableau de coordonnées XY en utilisant que le chemin le plus court.
Voici le défi : Vous disposez d’un programme de départ d’exemple du problème du voyageur. (Pièce jointe en ZIP)
Il est demandé de renvoyer à mon adresse emmanuel.roset@ni.com le VI nommé « Plus court chemin_Votre Pseudo.vi », (avec le projet entier si vous voulez)
bien entendu avec votre vrai Pseudo et contenant l’algorithme de résolution votre choix.
Celui fourni est un exemple qui n’est pas forcément optimisé et au-delà de 10 points de passages le code devient très lent.
Le gagnant sera celui dont le VI fournit : les points du chemin le plus court, la distance la plus petite, ainsi que le point de départ/arrivée et qui effectue le calcul le plus rapidement.
Pour le test final, un tableau de points commun sera généré à tous les algorithmes afin de comparer les vitesses.
Le nombre de points généré sera ajusté en fonction de la vitesse de l’algorithme. La comparaison de vitesse sera effectuée avec un code différent qui ne teste que le Sous_VI.
N’hésitez pas à m’envoyer vos codes même si vous pensez qu’il n’est pas "super" optimisé, le but c’est de participer et de s’amuser !
Voici des liens Wikipédia comme piste d’algorithmes possibles : (fournis, génétique, Dijkstra…)
http://fr.wikipedia.org/wiki/Probl%C3%A8me_du_voyageur_de_commerce
Très bon site avec des graphes d’explication
http://en.wikipedia.org/wiki/Travelling_salesman_problem
http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
Bonne réflexion !
Emmanuel ROSET
****************************************************************************************************
Résulats au 01/04/2014
Pièce jointe ajoutée
Il est temps de faire les comparatifs et les tests des chemins les plus courts
Méthode :
- Vérification de l’utilisation de la dernière version des codes reçus
- Test d’une ligne aller-retour pour vérifier la distance identique pour tous
- Test du cercle pour vérifier la distance et la validité de l’algorithme
- Test du plus court chemin sur des tableaux de points aléatoires de 8 – 10 – 20 (suivant la durée de calcul effectuable dans un temps raisonnable.)
Tests :
Cisco : On analyse le plus court chemin au fur et à mesure, par la construction de l'arbre des trajets possibles.
Sous_VI testé : Plus court chemin_Cisco_v2.vi
Résultat pour 20 points : 3057,41 calculé en 140 secondes
Régis65 : On choisit le point le moins distant autour du point actuel
Sous_VI testé : Plus court chemin_regis65_V2_2.vi
Résultat pour 20 points : 3457,81 calculé en 0 ms
Micael : évaluation de la validité de l’étape ABCD en calculant que 2 distances à chaque itération
Sous_VI testé : Plus court chemin_Micael.vi
Résultat pour 20 points : 2708,95 calculé en 2 ms
Il semble que le plus court chemin soit celui calculé par Micael (dans un temps très court en plus). Le choix du compromis entre tout tester et évaluer la validité du segment proche est un bon choix.
Donc Micael est déclaré vainqueur !
En tout cas bravo à tous les 3 car les codes fonctionnent dans tous les cas dont celui du cercle qui permet de tester « l’intelligence » du code.
Voici les captures d'écran des tests et les chemins calculés :
Bon maintenant on va pouvoir partir en vacances en utilisant le plus court chemin pour les visites. Mieux que le GPS ?
En effet, les valeurs demandées des phrases, sont celles retournées simplement par le Sous VI du programme fourni. (cluster, variable,..)
La distance la plus petite est la somme de tous les segments de chemins. Et les points du chemin est un tableau de valeur par lesquel le voyageur doit passer (qui sera mis en noir sur le graphe)
C'était juste pour préciser de renvoyer le Sous VI "Plus court chemin_Votre Pseudo.vi" sans modifier les types d'E/S.
Les buts sont un aspect graphique du résultat dans la face avant et également d'obtenir tous les VI identiques afin de comparer les vitesses d'exécution des Sous-VI.
La formatage dans les valeurs demandées (cluster) implique un temps de traitement un peu plus long pour renvoyer les valeurs sur ce format mais le contenu des valeur (le chemin) est essentiel pour le voyageur.
Le point de départ et d'arrivée est arbitraire mais il est nécessaire également pour l'affichage, il peut tout a fait correspondre au premier point généré dans le tableau de points qui sera fourni
Pour l'inventivité, c'est en effet un challenge de reprendre un code et de le refondre afin de l'optimiser et de l'améliorer. C'est un exercice particuler auquel les développeurs sont parfois confrontés suite au départ d'un développeur précédent....
J'ai regardé les différentes méthodes aussi, à priori il serai possible d'aller beaucoup plus vite que le code fourni par notre donateur 
Merci à Regis65 qui m'a envoyé son code qui fonctionne extrêmement rapidement et passe par tous les points. Je remarque cependant que je ne crois pas que le programme prend tout le temps le chemin le plus court sur la totalité du parcours 
.
Hello, en effet j'ai appliqué un petit calcul sur le parcours total sur d'autres points. Et le chemin est plus court que dans l'exemple donné sur les valeurs testées. Pour l'instant c'est un peu de la magie, pourrez vous commenter votre algorithme afin de partager la méthode utilisée ? je ne la dévoilerai pas avant la fin. Pour l'instant je crois que je pars en vacances avec votre méthode... 
, à vérifier...
Par contre, il y avait bien un problème avec la mesure de distance dans le premier programme.
Par rapport à la demande de Cisco,
J'ai préparé des tableaux de points au hasard de 8, 10, 20, n, à valider. Le but final est de trouver le plus court chemin possible même par approximation et dans le temps d'exécution le plus court.
Un même tableau de points sera utilisé pour toutes les réponses afin de comparer les distances et temps. (Le plus réalisable dans un temps raisonnable par exemple < 5 min)
Le tableau des résulats est donc trié par la colonne chemin le plus court en priorité suivi par le temps de calcul le plus court.
Merci à _micael. Je confirme que j'ai bien reçu son code. Il est efficace et astucieux.
Regis_65, idem, le nombre de points de passages est n+1 (par ex 22 pour 20 points), je n'ai regardé pourquoi car la distance est bonne.
Pour info je procède en premier au test du cercle pour vérifier que tous les algorithmes sont corrects et donnent la même distance (nombre de points du cercle de 2 à n)
Oui, il faut qu'on change de méthode , ce mois ci on change.... sinon ca devient la certification de niveau "Univers".
C'est fait depuis hier avec le CLG
