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

[dourouc05]

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.

[laurent_ott]

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.

[elloh]

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

[Flodelarab]

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.

[Nebulix]

Il y a au moins une différence avec le classique TSP, c'est qu'on ne revient pas au point de départ.

[elloh]

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.

[Nebulix]

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 ?

[elloh]

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é

[elloh]

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.

[elloh]

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 ?

[dourouc05]

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

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 !