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

  1. #1
    Membre expérimenté Avatar de nathieb
    Homme Profil pro
    Chef de projet/Architecte
    Inscrit en
    mai 2004
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France

    Informations professionnelles :
    Activité : Chef de projet/Architecte
    Secteur : Service public

    Informations forums :
    Inscription : mai 2004
    Messages : 1 036
    Points : 1 467
    Points
    1 467

    Par défaut Algorithme de répartition avec condition

    Bonjour,

    J'ai un ensemble d'éléments A, B, C, D ....
    chaque éléments est soumis à une ou plusieurs conditions

    A ne peut être à côté de B
    B ne peut être à côté de J et H
    etc


    la solution doit être disposée sur une carte dont les dimensions sont n*n
    Il peut y avoir plusieurs A ou B ou C ...

    Je cherche des pistes de réflexion sur le sujet, des bases Arbres de décision, etc ...

    Avez-vous des pistes que je pourrais exploiter ?

    Olivier
    Architecte destructurant,
    be cool, be free

    Il nous reste Debian bien sûr

  2. #2
    Nouveau membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    juillet 2018
    Messages
    17
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juillet 2018
    Messages : 17
    Points : 35
    Points
    35

    Par défaut

    Bonjour,
    En données du problème, tu as le nombre de chaque élément que tu veux placer ?
    En réponse au problème, tu veux une répartition quelconque des éléments ? L'ensemble des possibilités ?
    On considère que ces contraintes sont sous forme d'un graphe ?

  3. #3
    Membre expérimenté Avatar de nathieb
    Homme Profil pro
    Chef de projet/Architecte
    Inscrit en
    mai 2004
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France

    Informations professionnelles :
    Activité : Chef de projet/Architecte
    Secteur : Service public

    Informations forums :
    Inscription : mai 2004
    Messages : 1 036
    Points : 1 467
    Points
    1 467

    Par défaut réponse

    Bonjour,


    Oui normalement j'ai le nombre d'éléments de départ et le nombre de cases prévues.
    Effectivement, j'ai pensé à un arbre pour les contraintes, il existe les algos
    de programmation par contraintes.

    Est ce que cela peut correspondre ?

    Olivier
    Architecte destructurant,
    be cool, be free

    Il nous reste Debian bien sûr

  4. #4
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 023
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 023
    Points : 4 230
    Points
    4 230

    Par défaut

    Prenons un exemple précis, ça permettra de mieux dialoguer.
    On a une grille 10x10,
    A : 25 éléments, ne peut pas être à côté de B C E ni H
    B : 18 éléments, ne peut pas être à côté de D F ni J
    C : 12 éléments, ne peut pas être à coté de E ni F
    D : 10 éléments, ne peut pas être à coté de E F ni G
    E : 8 éléments, ne peut pas être à coté de E F ni J
    F : 8 éléments, ne peut pas être à coté de F ni G ni H
    G : 7 éléments, ne peut pas être à coté de H ni I
    H : 6 éléments, ne peut pas être à coté de H ni J
    I : 3 éléments, pas de contrainte
    J : 3 éléments, pas de contrainte

    1er point, Les éléments J n'ont pas de contrainte, mais en fait, ils en ont. Les éléments J ne peuvent pas être à côté des éléments B E ou H.

    Si l'objectif est de recenser toutes les combinaisons possibles, c'est ""facile"". C'est du parcours d'arbre. Mais qu'on prenne l'arbre par un bout ou par l'autre, peu importe, il faudra de toutes façons parcourir tout l'arbre.

    Le cas le plus intéressant est si on cherche une solution.

    Pour chaque élément , on calcule son nombre de voisins possible (99 - nombre d'interdits) Pour chaque élément de type J, on a donc 99-18-8-6=67 voisins possibles. Et on va ordonner les éléments : du plus contraint au moins contraint. On va d'abord essayer de caser les éléments incasables, et on va garder les éléments faciles à caser pour la fin. Comme ça, si un scénario conduit à une impasse, on devrait le détecter assez tôt.

    L'autre piste, c'est de parcourir la grille en spirale : on essaie de remplir le milieu de la grille, et on finit par les coins. Ainsi, on commence par les case avec 4 voisins ( lles plus copliquées à gérer, car 4 contraintes, puis les cases des bords, et enfin, les 4 coins. Là aussi, l'idée, c'est de détecter au plu vite les scénarios qui mènent à des impasses.

    En faisant du parcours d'arbre, et en combinant ces 2 règles, tu devrais avoir une solution optimale.
    Eventuellement, il faut recalculer la fonction 'nombre de contraintes' à chaque étape, mais je ne pense pas que ce soit utile.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  5. #5
    Membre expérimenté

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    719
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 72
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 719
    Points : 1 420
    Points
    1 420
    Billets dans le blog
    5

    Par défaut Algorithme de répartition avec condition

    Bonjour,

    Je crois que deux outils de type tableau sont indispensables:

    a) la liste des éléments disponibles, soit ici:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    CONST Ne = 10;
    TYPE ListeE = ARRAY[1..Ne] OF Byte;
    NombreE: ListeE;
    initialsée aux valeurs indiquées:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    CONST NiniE: ListeE = (25, 18, 12, 10, 8, 8, 7, 6, 3, 3);
    NombreE:= NiniE;
    b) la matrice de non-adjacence, où sont consignées touts les proximités interdites:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    TYPE TabNN = ARRAY[1..Ne, 1..Ne] OF Bool;
    VAR A: TabNN;
    Cette matrice est symétrique en raison de la réciprocité des interdictions; on aura ainsi:
    A ne peut pas être à côté de B C E ni H
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    A[1, 2]:= False; A[2, 1]:= False;
    A[1, 3]:= False; A[3, 1]:= False;
    A[1, 5]:= False; A[5, 1]:= False; 
    A[1, 8]:= False; A[8, 1]:= False;
    Un remplissage de la grille ne pourrait-il résulter simplement d'un remplissage aléatoire ligne par ligne, ou colonne par colonne ?
    On aurait ainsi pour tout élément interne (i, j) , en progressant de la gauche vers la droite, quelque chose comme:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    TYPE Grille = ARRAY[1..Ne, 1..Ne] OF Byte;
    VAR G: Grille; 
          h: Byte; Test1, Test2: Bool;
    ...
    h:= Random(Ne) + 1;       
    Test1:= A[G[i, j - 1], h]; Test2:= A[G[i - 1, j], h]; 
    IF (Test1 AND Test2) THEN G[i, j];= h;
    L'emplacement des cases à remplir pourrait lui-même faire l'objet d'un tirage aléatoire, en plus de leur contenu, après initialisation de celui-ci à zéro.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  6. #6
    Membre actif
    Homme Profil pro
    Consultant informatique
    Inscrit en
    septembre 2012
    Messages
    150
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Maroc

    Informations professionnelles :
    Activité : Consultant informatique
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : septembre 2012
    Messages : 150
    Points : 204
    Points
    204

    Par défaut

    Bonjour,

    Très intéressant comme sujet.J'ai malheureusement pas pu tout lire par contrainte de temps mais cela me rappelle le problème des neufs reines que j'avais résolu grâce au fameux "backtraking" algo(ou retour sur trace)
    Tu pourras même trouver toutes les combinaisons possibles existantes.

    C'est parti pour une bonne session de recherches et de boulot.....
    Bon courage!!

    N'oublie pas les diagonales dans ta matrice M[i,i] ...
    Bonne chance.

Discussions similaires

  1. [XL-2010] Répartition aléatoire avec conditions
    Par sa-lyly dans le forum Excel
    Réponses: 7
    Dernier message: 08/09/2016, 10h54
  2. Sélection multi table avec condition
    Par iuz dans le forum Langage SQL
    Réponses: 8
    Dernier message: 05/05/2004, 15h04
  3. ALTER VIEW avec condition
    Par yan77 dans le forum MS SQL-Server
    Réponses: 2
    Dernier message: 05/04/2004, 17h22
  4. Index avec conditions
    Par marhnix dans le forum MS SQL-Server
    Réponses: 4
    Dernier message: 29/03/2004, 10h48
  5. boucle avec condition d'arret changeante
    Par NicoH dans le forum Langage
    Réponses: 3
    Dernier message: 10/06/2003, 11h48

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