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 :

Constitution de groupes [programmation par contrainte]


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Futur Membre du Club
    Profil pro
    Inscrit en
    Juin 2011
    Messages
    4
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2011
    Messages : 4
    Par défaut Constitution de groupes [programmation par contrainte]
    Bonjour à toutes et à tous,

    Je vous expose un problème d'algorithmique dont ne ne sais par quel bout le prendre.

    - J'ai un ensemble de N individus affectés d'une note. (N<150)
    - j'ai un ensemble de n classes (2<n<10)


    Je dois constituer les n classes en répartissant au mieux les N individus. C'est à dire de sorte que les classes comportent sensiblement le même nombre d'individus et que les classes soient globalement équivalente (disons même hétérogénéité et même moyenne).

    Jusque la je sais faire.

    Le problème, c'est que certains individus ont des contraintes supplémentaires.

    Par exemple :

    - être avec certains individus
    - ne pas être avec certains individus
    - appartenir à une classe précise
    - ne pas appartenir à une classe précise
    - appartenir à un groupe (groupe qui peut être réparti sur plusieurs classes)

    C'est la où je me perds un peu, j'ai bien cherché sur la programmation par contrainte qui correspond à la deuxième partie du problème mais je ne vois pas comment faire le lien avec la première partie.

    Si quelqu'un à une idée,

    Cordialement, merci d'avance, en espérant avoir été suffisamment clair.

    Laurent

    P.S Je programme sous Delphi-pascal et je n'ai pas trouvé de bibliothèque pour la programmation par contraintes.

  2. #2
    Membre expérimenté Avatar de Acrim
    Profil pro
    En recherche d'emploi
    Inscrit en
    Septembre 2010
    Messages
    134
    Détails du profil
    Informations personnelles :
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : En recherche d'emploi

    Informations forums :
    Inscription : Septembre 2010
    Messages : 134
    Par défaut
    Je vois trois manières de faire (par importance décroissante donnée à la répartition/moyenne) :
    1. tu traduis le fait que les classes doivent comporter le même nombre d’éléments/avoir la même moyenne en contraintes que tu rajoutes à ton problème.
    2. tu évalues la qualité de ta solution (répartition, moyenne etc) via une fonction objectif et tu t'en sers pour faire de l'optimisation.
    3. tu utilises une heuristique de choix variable/valeur qui va favoriser des solutions de la forme qui t’intéresse.


    Quant à une librairie en Delphi/pascal : aucune idée.

  3. #3
    Membre éclairé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mai 2008
    Messages
    54
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mai 2008
    Messages : 54
    Par défaut
    Deux trois questions pour clarifier certaines choses

    Citation Envoyé par lpecqueux Voir le message
    Le problème, c'est que certains individus ont des contraintes supplémentaires.

    Par exemple :

    - être avec certains individus
    - ne pas être avec certains individus
    - appartenir à une classe précise
    - ne pas appartenir à une classe précise
    - appartenir à un groupe (groupe qui peut être réparti sur plusieurs classes)
    "Certains", c'est combien par rapport à N ~ 150 ?

    Il y a un "ordre" dans les classes ? Que veut dire appartenir à une classe précise par rapport à être avec certains individus et pas avec d'autres ?
    De la même manière, j'ai pas trop compris la notion de groupe. Certains individus doivent être répartis dans un certain de classes en fait, indépendamment des "couples" d'invidus (qui doivent etre ensemble ou ne pas etre ensemble) ?
    Enfin, est-ce que les contraintes sont toute réalisables. Par exemple si tu ne dois former que deux classes et que trois individus ne peuvent être avec aucun des deux autres => problème !

    Merrci

  4. #4
    Futur Membre du Club
    Profil pro
    Inscrit en
    Juin 2011
    Messages
    4
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2011
    Messages : 4
    Par défaut
    Citation Envoyé par Vakhyw Voir le message
    Deux trois questions pour clarifier certaines choses



    "Certains", c'est combien par rapport à N ~ 150 ?

    Il y a un "ordre" dans les classes ? Que veut dire appartenir à une classe précise par rapport à être avec certains individus et pas avec d'autres ?
    De la même manière, j'ai pas trop compris la notion de groupe. Certains individus doivent être répartis dans un certain de classes en fait, indépendamment des "couples" d'invidus (qui doivent etre ensemble ou ne pas etre ensemble) ?
    Enfin, est-ce que les contraintes sont toute réalisables. Par exemple si tu ne dois former que deux classes et que trois individus ne peuvent être avec aucun des deux autres => problème !

    Merrci

    Je vais essayer d'être un peu plus clair sur un exemple (mais ce n'est qu'un exemple)

    Considérons 125 élèves de 5e à répartir sur 5 classes de 4e (A, B, C, D et E)

    Parmi ces élèves

    - une petite vingtaine fait de l'allemand les autres de l'espagnol
    - les germanistes seront répartis sur deux classes (A et B par exemple)
    - les hispanisants peuvent être dans toutes les classes

    les élèves peuvent avoir des options :
    - une petite vingtaine de latinistes, (faisant de l'allemand ou de l'espagnol) à répartir sur deux classes (A et C par exemple)

    - environ 25 faisant option Sport ( à répartir sur deux classes B et D par exemple)

    ainsi de suites pour d'autres options (Euro, Sciences)

    - certains élèves ne doivent pas être dans la même classe ( des groupes de moins de 5 élèves forcément)
    - certains élèves doivent être ensemble

    - enfin les classes doivent être hétérogènes en terme de résultats (moyenne ou autre à définir médiane écart type...) et avoir sensiblement le même nombre d'élèves (à 1 près)

    J'espère ainsi être plus clair.

    Je suis conscient qu'un tel problème n'est pas évident et que certaines situations sont impossibles dans ce cas il faudrait trouver une solution optimale ou indiquer les incompatibilités.

    Si quelqu'un a une piste,

    Merci d'avance


    Cordialement
    Laurent

  5. #5
    Membre très actif
    Profil pro
    chercheur
    Inscrit en
    Avril 2004
    Messages
    830
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : Avril 2004
    Messages : 830
    Par défaut
    IL est clair selon ton exemple que
    les germanistes latinistes seront en A
    les sportifs ne peuvent pas faire latin,
    etc
    Je commencerais par faire la liste des combinaisons possibles, et qui contiennent au moins un élève. Tu en auras un nombre relativement petit que tu auras ensuite à répartir dans tes 5 classes.

  6. #6
    Futur Membre du Club
    Profil pro
    Inscrit en
    Juin 2011
    Messages
    4
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2011
    Messages : 4
    Par défaut
    Citation Envoyé par Nebulix Voir le message
    IL est clair selon ton exemple que
    les germanistes latinistes seront en A
    les sportifs ne peuvent pas faire latin,
    etc
    Je commencerais par faire la liste des combinaisons possibles, et qui contiennent au moins un élève. Tu en auras un nombre relativement petit que tu auras ensuite à répartir dans tes 5 classes.

    Je dois mal comprendre ta remarque parce que juste en considérant la vingtaines de germanistes il y a environ 4*10^6 combinaisons possibles (sauf erreur de ma part) pour les répartir sur deux classes.

    Cordialement,
    Laurent

  7. #7
    Membre très actif
    Profil pro
    chercheur
    Inscrit en
    Avril 2004
    Messages
    830
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : Avril 2004
    Messages : 830
    Par défaut
    Si tu as environ la moitié des germanistes qui font du latin, tu les mets en A, les autres en B et tu as réduit la complexité de ton pb d'un facteur 4E6
    En construisant des groupes par option, tu te ramènes dans un premier temps à un pb de sac-à-dos de petite dimension que tu peux gérer de façon combinatoire, et affiner dans un deuxième temps pour satisfaire les autres conditions.

Discussions similaires

  1. programmation par contrainte
    Par ratrout dans le forum Langage
    Réponses: 5
    Dernier message: 09/12/2016, 21h51
  2. [SWI-Prolog][Débutant] Programmation par contrainte
    Par alexglvr dans le forum Prolog
    Réponses: 32
    Dernier message: 01/11/2008, 22h33
  3. Programmation par contrainte en Java
    Par domas_24 dans le forum API standards et tierces
    Réponses: 3
    Dernier message: 12/06/2008, 14h27
  4. Programmation par contrainte
    Par croc14 dans le forum API standards et tierces
    Réponses: 4
    Dernier message: 19/03/2007, 11h12

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