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 :

Optimisation des entrées / sorties de musiciens sur une scène


Sujet :

Algorithmes et structures de données

  1. #1
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : septembre 2019
    Messages : 8
    Points : 4
    Points
    4
    Par défaut Optimisation des entrées / sorties de musiciens sur une scène
    Bonjour,

    Je suis nouveau sur ce forum. J'ai découvert pendant mes recherches sur google que ce forum parlait aussi d'algorithmie !

    Voici l'exposé du problème:

    Un groupe de travail est une association de un ou plusieurs musiciens. Un musicien peut appartenir à un ou plusieurs groupes de travail. Un groupe de travail joue une ou plusieurs chansons ensemble sur scène. Il y a beaucoup de groupes de travail et donc beaucoup de chansons à jouer et de musiciens.

    Le but de l'algorithme que je cherche est de faire en sorte qu'il y ait le moins possible d'entrées / sorties de musiciens sur la scène tout en faisant jouer toutes les chansons étudiées par les groupes de travail. Dans un premier temps, pour simplifier le problème, je ne prendrai pas en compte les changements d'instruments car certains musiciens jouent de plusieurs instruments ainsi que leurs horaires de dispos et le style des chansons jouées qui doivent s'enchaîner dans une certaine logique (en attribuant un poid représentant l’agressivité du morceau par exemple)...

    J'ai cherché vainement un nom d'algorithme qui résoudrait des problèmes similaires mais je n'ai pas trouvé.

    Quelqu'un aurait une idée de l'algorithme à utiliser ?

    Toute aide est la bienvenue.

  2. #2
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 934
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 934
    Points : 9 586
    Points
    9 586
    Par défaut
    Bonjour

    Le but de l'algorithme que je cherche est de faire en sorte qu'il y ait le moins possible d'entrées / sorties de musiciens sur la scène.
    Facile. Zéro entrée, zéro sortie.

    Next.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  3. #3
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : septembre 2019
    Messages : 8
    Points : 4
    Points
    4
    Par défaut
    Ahah ! :-) Oui c'est facile ... Mais il faut que tous les groupes de travail jouent les morceaux qu'ils ont étudiés !

  4. #4
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 934
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 934
    Points : 9 586
    Points
    9 586
    Par défaut
    Les morceaux sont des villes et la distance entre les morceaux est la différence de musiciens entre les morceaux. Ta question est donc "quel est le parcours passant dans toutes les villes avec le trajet le plus court ?". C'est le célébrissime problème du voyageur de commerce qui n'a aucune solution théorique absolue.

    Cela ne veut pas dire que le-dit voyageur de commerce ne va pas travailler. Il va limiter la casse.

    Renseigne-toi autour du thème du "voyageur de commerce".
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

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

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

    Informations forums :
    Inscription : février 2013
    Messages : 198
    Points : 145
    Points
    145
    Par défaut
    Comme pour l'instant, la seule contrainte est le "poids" des chansons, il faut classer les musiciens-chansons par "poids"; et plus il y aura de contraintes, plus ce sera compliqué.
    Savoir pour comprendre et vice versa.

  6. #6
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : septembre 2019
    Messages : 8
    Points : 4
    Points
    4
    Par défaut
    Merci beaucoup pour votre aide !

    Le voyageur du commerce en anglais, ça donne Traveller Salesman Problem.

    J'ai trouvé une librairie en python qui résoud le problème du TSP mais il n'y a pas bcp d'explications sur l'algoriithme utilisé.

    Le module pip3 s'appelle tsp. L'implémentation du module est relativement complexe ... pour mon niveau en python mais son utilisation est plutôt simple.

    Je vais faire des tests sur mon programme simplifié avant de réfléchir, si c'est concluant, à comment ajouter d'autres contraintes sur l'enchaînement des morceaux, la disponibilité des musiciens ...

  7. #7
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 794
    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 : 24 794
    Points : 168 365
    Points
    168 365
    Par défaut
    Prépare-toi au pire pour ajouter des contraintes au TSP : à part modifier le graphe et les poids des arêtes, tu n'as pas beaucoup de possibilités (tout autre changement impliquera de grosses évolutions algorithmiques...).

    Sinon, pas sûr que le module tsp soit si approprié, vu son niveau de développement. (Tu parles d'algorithme : au vu des dépendances, ça utilise au moins de la programmation linéaire, probablement en nombres entiers. https://fr.wikipedia.org/wiki/Optimi..._lin%C3%A9aire https://fr.wikipedia.org/wiki/Optimi...ombres_entiers) En Python, regarde du côté de OR-Tools https://developers.google.com/optimization/routing/tsp (ça a beau être du Google, c'est très loin d'être le meilleur logiciel) ; sinon, Concorde est la référence actuelle, mais pas si facilement utilisable 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 !

  8. #8
    Rédacteur

    Homme Profil pro
    Administrateur de base de données
    Inscrit en
    août 2013
    Messages
    386
    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 : 386
    Points : 1 797
    Points
    1 797
    Par défaut
    Bonjour.
    Pour comprendre le principe du problème du voyageur de commerce il y a aussi cette documentation : https://laurent-ott.developpez.com/t...el-vba-tome-3/
    Avec un code source en VBA.
    Ça peut donner des idées si le but de "elloh" est d'écrire quelque chose de personnel et non pas de récupérer un programme tout fait.
    Tout dépend de l'objectif suivi.
    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.

  9. #9
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : septembre 2019
    Messages : 8
    Points : 4
    Points
    4
    Par défaut
    Merci pour vos liens, c'est vraiment cool de votre part.

    J'ai trouvé deux autres modules Python pip3:

    Tsp-solver2 (pure Python) et pyconcorde (wrapper autour de concorde).

    J'ai adapté facilement mon programme pour utiliser les modules tsp et tsp-solver2 mais pyconcorde est plus compliqué... Je ne vois pas comment faire. Je cherche.

    En ce qui concerne l'évolution de l'algorithme, ça me paraît assez complexe effectivement.

    Pour les contraintes de temps, il faudrait qu'à chaque morceau, on associe une durée et qu'en fonction du temps écoulé depuis le début du concert certains musiciens et donc groupes de travail deviennent disponibles. Mais est-ce que l'algorithme tsp sera toujours pertinent ?

    Ensuite pour la contrainte sur l'enchaînement des morceaux, un algorithme déciderait en fonction d'un poids de musicalité et de sa répartitions sur l'ensemble des chansons à traiter et de la musicalité des chansons déjà jouées, la musicalité souhaitable pour le morceau suivant. Ce sont la des choix qui ne vont pas forcément dans le sens de l'optimisation de la solution...

  10. #10
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 934
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 934
    Points : 9 586
    Points
    9 586
    Par défaut
    L'optimisation c'est comme le tri d'un fichier texte en colonnes. Il y a une hiérarchie entre les colonnes.
    Tu tries dans l'ordre 2,1,3,4,5, puis tu dis que tu veux des contraintes sur la colonne 5. L'ordre est déjà bien figé quand tu arrives à ce moment-là. Si cette colonne a plus d'importance, c'est que tu t'es menti sur l'ordre des priorités. C'était peut-être 2,1,5,3,4.

    Tu dois faire le ménage dans tes idées pour définir ce que tu veux vraiment.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  11. #11
    Membre expérimenté
    Profil pro
    chercheur
    Inscrit en
    avril 2004
    Messages
    797
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : avril 2004
    Messages : 797
    Points : 1 304
    Points
    1 304
    Par défaut
    Il y a au moins une différence avec le classique TSP, c'est qu'on ne revient pas au point de départ.
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  12. #12
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : septembre 2019
    Messages : 8
    Points : 4
    Points
    4
    Par défaut
    J'ai créé une position de départ virtuelle avec le même poids vers tous les autres noeuds de la matrice.

    Le problème reste le même il faut jouer toutes les chansons en faisant le moins de changements de plateau possible (entrées / sorties de musiciens).

    Je pense que la contrainte sur la disponibilité des musiciens est jouable mais je n'ai pas les compétences pour calculer la performance d'un tel algorithme ...

    En ce qui concerne l'enchaînement des morceaux, c'est plus flou ... Il faut que ça mûrisse.

  13. #13
    Membre expérimenté
    Profil pro
    chercheur
    Inscrit en
    avril 2004
    Messages
    797
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : avril 2004
    Messages : 797
    Points : 1 304
    Points
    1 304
    Par défaut
    Le problème du voyageur est très difficile ... pour un grand nombre de villes.
    Mais dans ton problème, le nombre de chansons ne peut pas être très grand, une solution de force brute est peut être réaliste. Combien de chansons au plus peuvent être programmées ?
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  14. #14
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : septembre 2019
    Messages : 8
    Points : 4
    Points
    4
    Par défaut
    Je pense entre 10 et 20 pt être un peu plus... J'ai testé sur 14 et ça me donne un résultat en quelques secondes.

    Je vais faire des tests sur le max supposé

  15. #15
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : septembre 2019
    Messages : 8
    Points : 4
    Points
    4
    Par défaut
    Finalement pour les contraintes d'heure d'arrivée des musiciens, j'ai décomposé en sous graphes : un ou il n'y a pas de musiciens en retard et un pour chaque musicien en retard et ensuite je reconstitue une setlist globale en concatenant les résultats pour chaque graphe.

  16. #16
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : septembre 2019
    Messages : 8
    Points : 4
    Points
    4
    Par défaut
    Si j'insère un modification du poids en fonction de la musicalité du morceau (n-1 -> n) la matrice représentant le graphe n'est plus symétrique...

    De même dans l'idéal il faudrait compter le nombre d'entrées sur chaque morceau (se calcule sur le morceau n-1 et n) et ajouter le nombre de sorties (se calcule sur le morceau n et le n+1) pour le calcul du poids. Pour le moment, ma formule de poids s'appuie sur le nombre maximum de participants à un groupe - le nombre de participants en commun (se calcule donc sur le morceau n-1 et n) mais ce poids est le même dans les deux sens de parcours. C'est donc une approximation de la solution vu que le calcul du poids n'est pas exact.

    J'abondonne la possibilité de définir la musicalité sur le tsp. De plus, je pense que poser des jalons : "commencer par morceau untel" et en "9ème position jouer morceau untel" serait plus pertinent.

    Quelqu'un aurait un nom d'algorithme qui permettrait de gérer l'optimisation des entrées/sorties avec positionnement de jalons ?

  17. #17
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 794
    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 : 24 794
    Points : 168 365
    Points
    168 365
    Par défaut
    Citation Envoyé par elloh Voir le message
    Si j'insère un modification du poids en fonction de la musicalité du morceau (n-1 -> n) la matrice représentant le graphe n'est plus symétrique...
    Ce n'est pas un problème pour le TSP (même s'il existe des algorithmes plus efficaces dans le cas où la matrice est symétrique).

    Citation Envoyé par elloh Voir le message
    Quelqu'un aurait un nom d'algorithme qui permettrait de gérer l'optimisation des entrées/sorties avec positionnement de jalons ?
    Ton problème a l'air assez spécifique, il n'existe probablement pas d'algorithme spécifique qui fasse exactement ce que tu souhaites. (Déjà, il faudrait définir ta notion de jalon...) Au risque de prêcher pour ma paroisse : quid d'approches comme l'optimisation mathématique et la programmation par contraintes ? Ce serait super facile d'ajouter de nouvelles contraintes au fur et à mesure de ton développement, tu aurais des algorithmes déjà très efficaces pour résoudre le problème, il "suffirait" de le formuler de la bonne manière (avec un paradigme plus flexible que le TSP).

    Sinon, la force brute, c'est normalement assez facile à coder et ça pourrait suffire dans ton cas !
    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 !

Discussions similaires

  1. Réponses: 6
    Dernier message: 24/08/2018, 07h33
  2. Réponses: 4
    Dernier message: 09/01/2015, 08h15
  3. Tester que la touche entrée a été préssee sur une cellule précise
    Par azerty53 dans le forum Macros et VBA Excel
    Réponses: 2
    Dernier message: 18/10/2006, 08h25
  4. concaténation des status d'un détail sur une ligne
    Par orafrance dans le forum Oracle
    Réponses: 11
    Dernier message: 02/06/2006, 09h13

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