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
    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

    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.
    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
    Et pour les curieux, le tome 3 qui aborde le problème du voyageur de commerce.
    Le tome 4 est consacré à la cryptologie en VBA et satisfera ceux qui ont besoin de confidentialité.
    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.
    N'oubliez pas de consulter les FAQ EXCEL et les cours et tutoriels comme par exemple celui de Jean-Marc RABILLOUD qui est très complet.

  3. #3
    Membre régulier
    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



    Ç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 ou PyQt (tutoriels, FAQ, traductions), 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 habitué
    Comme tu dois passer partout et dans le même sens, c'est pas ça le plus rapide ?
    Savoir pour comprendre et vice versa.

  6. #6
    Membre éclairé
    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

    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 ou PyQt (tutoriels, FAQ, traductions), 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 éclairé
    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
    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

###raw>template_hook.ano_emploi###