Discussion :

[elloh]

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.

[Flodelarab]

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.

[elloh]

Ahah ! :-) Oui c'est facile ... Mais il faut que tous les groupes de travail jouent les morceaux qu'ils ont étudiés !

[Flodelarab]

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

[valentin03]

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

[elloh]

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