IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Recherche d'optimisation de parcours


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Femme Profil pro
    Développeur informatique
    Inscrit en
    février 2011
    Messages
    260
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 31
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : février 2011
    Messages : 260
    Points : 82
    Points
    82
    Par défaut Recherche d'optimisation de parcours
    Bonjour,

    Dans le cadre d’un projet ayant pour but de contrôler des moteurs, je souhaiterais avoir votre aide pour optimiser mes temps en mouvement.
    Je vous explique.

    Aujourd’hui je reçois une succession de trajectoire à effectuer sur des moteurs XY. Ces trajectoires n’ont pas besoin d’être exécutés dans un ordre précis. Et je souhaiterais réorganiser ces trajectoires pour que le temps de mouvement total soit le plus court possible.

    Je vais vous imager ça. Voici un exemple de trajectoires que je peux recevoir.



    Si je les écris dans l’ordre de réception voici ce que ça donne.



    Et maintenant voici un exemple d’optimisation possible.



    Donc vous le comprendrez la seconde façon est plus rapide que la première.
    Je souhaiterais donc trouver un algorithme me permettant de faire cela. J’ai pensé à l’algorithme utilisant les graphes, mais j’avoue ne pas savoir si c’est la meilleure solution ni lequel utiliser.
    Dans mes recherches j’ai pu voir l’algorithme de dijkstra qui recherche le plus court chemin entre deux sommets mais moi je cherche surtout la manière de faire en sorte que le parcours entre TOUS les sommets soit le plus court.
    J’ai vu également que le terme de graphe hamiltonien pouvait correspondre à ma définition mais je n’ai rien vu concernant le parcours le plus rapide dans ce genre de graphe.

    J’espère que vous pourrez m’aider, et je vous remercie d’avance pour cela.

  2. #2
    Rédacteur

    Homme Profil pro
    Administrateur de base de données
    Inscrit en
    août 2013
    Messages
    578
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Administrateur de base de données
    Secteur : Finance

    Informations forums :
    Inscription : août 2013
    Messages : 578
    Points : 2 580
    Points
    2 580
    Par défaut
    Bonjour.
    Ça ressemble un peu au problème du voyageur de commerce.
    Voir dans ma signature le tome 3 qui reprend certaines techniques.
    Bonne continuation.
    Débutants, n'hésitez pas à consulter mon mémento sur la programmation en VBA pour EXCEL tome 1.
    Ou le tome 2 qui aborde la programmation en mode graphique avec un exemple de programmation d'un jeu d'arcade en VBA.
    Pour les curieux, le tome 3 explique le problème du voyageur de commerce.
    Le tome 4 est consacré à la cryptologie en VBA.
    Vous découvrirez dans le tome 5 les fonctions SQL pour gérer les tableaux de données et l'application Sentinelle qui veille sur vos fichiers.
    Le tome 6, dernier de la série, vous apprendra à créer des fonctions pour simplifier la vie des utilisateurs.
    Le Crible Quadratique donne toutes les fonctions pour les opérations sur les grands nombres en VBA.
    En bonus : Programmation en VBA de menus personnalisés pour Excel, Manipuler les données des bases Access depuis Excel et Transférer des fichiers volumineux avec Outlook.

  3. #3
    Membre régulier
    Femme Profil pro
    Développeur informatique
    Inscrit en
    février 2011
    Messages
    260
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 31
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : février 2011
    Messages : 260
    Points : 82
    Points
    82
    Par défaut
    En effet ça y ressemble beaucoup. Je vais regarder ça de plus prêt.

    Je reviendrais ici après l'avoir lu si il me reste des questions.

    Merci de ton aide ^^.

  4. #4
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    25 932
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 25 932
    Points : 181 506
    Points
    181 506
    Par défaut


    Ça ressemble effectivement à un cas très particulier du TSP : le cas euclidien, vu que tu travailles dans le monde "réel", les distances entre tes points correspondant à des distances au sens mathématique. Dans ce cas, l'algorithme de Chrystofides (https://fr.wikipedia.org/wiki/Algori...e_Christofides) semble tout adapté. Certes, tu n'auras pas de solution optimale à tous les coups, mais c'est raisonnablement facile à implémenter (utilise des bibliothèques de graphes comme Boost Graph Library, Lemon en C++ : la plupart des étapes correspond à des algorithmes classiques). Contrairement aux "algorithmes" évolutionnaires de Laurent, tu es sûr que tu auras une assez bonne solution, peu importe la forme de ton entrée. Si tu veux une solution réellement optimale, regarde Concorde (http://www.math.uwaterloo.ca/tsp/concorde.html).
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  5. #5
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    283
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 283
    Points : 211
    Points
    211
    Par défaut
    Comme tu dois passer partout et dans le même sens, c'est pas ça le plus rapide ?
    Nom : a.JPG
Affichages : 192
Taille : 40,9 Ko
    Savoir pour comprendre et vice versa.

  6. #6
    Membre éprouvé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 369
    Points : 1 254
    Points
    1 254
    Par défaut Quantité
    Bonjour,

    Quelle quantité de points de passage ?

    Si la volumétrie est faible (de l'ordre d'une quarataine, par exemple, les solutions exactes restent accessibles car de l'ordre de l'heure).

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  7. #7
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    25 932
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 25 932
    Points : 181 506
    Points
    181 506
    Par défaut
    Citation Envoyé par Guesset Voir le message
    Si la volumétrie est faible (de l'ordre d'une quarataine, par exemple, les solutions exactes restent accessibles car de l'ordre de l'heure).
    Pour un TSP classique, on peut atteindre une solution exacte pour une quarantaine de points en quelques secondes, pour des cas pathologiques, avec des machines et algorithmes d'avant 2000… (http://www.math.uwaterloo.ca/tsp/con...s/bench99.html)
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  8. #8
    Membre éprouvé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 369
    Points : 1 254
    Points
    1 254
    Par défaut Pas vu
    Bonsoir,

    Citation Envoyé par dourouc05 Voir le message
    Pour un TSP classique, on peut atteindre une solution exacte pour une quarantaine de points en quelques secondes, pour des cas pathologiques, avec des machines et algorithmes d'avant 2000… (http://www.math.uwaterloo.ca/tsp/con...s/bench99.html)
    J'ai été voir la page de ce lien mais je n'ai rien trouvé de tel mais je n'ai pas cherché outre cette page (il est tard).

    Par ailleurs, travailler sur un seul coeur sur une machine moderne peut s'avérer moins efficace que sur une vieille machine mono coeur.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  9. #9
    Membre régulier
    Femme Profil pro
    Développeur informatique
    Inscrit en
    février 2011
    Messages
    260
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 31
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : février 2011
    Messages : 260
    Points : 82
    Points
    82
    Par défaut
    Désolé pour le retard pour les réponses. je viens tout juste de rentrer de congé.

    Comme tu dois passer partout et dans le même sens, c'est pas ça le plus rapide ?
    C'est possible. je t'avoue que j'ai fait ça a main lever sans aucun calcul.

    Quelle quantité de points de passage ?
    Tout dépend des motif. Ça peut aller de quelques un à quelques centaine de milliers.

    En tout cas merci pour vos réponses et votre intérêt pour ma problématique

Discussions similaires

  1. Recherche et optimisation
    Par crashtib dans le forum C
    Réponses: 1
    Dernier message: 03/06/2009, 19h37
  2. [Débutant] Optimisation de parcours dans une image
    Par MaximeL dans le forum Images
    Réponses: 4
    Dernier message: 22/05/2009, 09h56
  3. Algo optimisation de parcours dans un graphe
    Par egu07 dans le forum Intelligence artificielle
    Réponses: 1
    Dernier message: 11/09/2008, 10h20
  4. [DOM] Besoin d'optimiser le parcours d'un fichier XML
    Par stardeus dans le forum Format d'échange (XML, JSON...)
    Réponses: 19
    Dernier message: 08/04/2007, 17h04
  5. Réponses: 1
    Dernier message: 15/08/2006, 01h35

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo