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 :

Algo de placement


Sujet :

Algorithmes et structures de données

  1. #1
    Membre averti
    Homme Profil pro
    Responsable de service informatique
    Inscrit en
    Août 2005
    Messages
    37
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : Responsable de service informatique
    Secteur : Industrie

    Informations forums :
    Inscription : Août 2005
    Messages : 37
    Par défaut Algo de placement
    Bonjour a toutes et a tous,

    Je viens ici demander un coup de main au cas ou certain(e)s auraient déjà vu ca quelquepart...

    Je vais expliquer mon probleme

    J'ai une surface (S) de forme rectangle et je possède les coordonnées du dit rectangle (x1,y1,x2,y2)

    Je possède a coté de ca des formes rectangulaires (F1,F2,F3) de grandeur diverses toujours plus petites que la surface S
    Mon but est celui ci :

    Je donne ces indications a l'algo :
    F1 : 30% de la surface S
    F2 : 10% de la surface S
    F3 : 15% de la surface S

    Il faudrait que l'algo pose aléatoirement ces formes sur la surface afin qu'elles remplissent les taux de la surface aléatoirement sans se toucher...

    Existe t il un algo connu qui pourrait m'aider a faire ceci ?

    merci d'avance de votre aide et de vos conseils

    a++
    Nico

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par leghola
    (1). J'ai une surface (S) de forme rectangle et je possède les coordonnées du dit rectangle (x1,y1,x2,y2)

    (2). Je possède a coté de ca des formes rectangulaires (F1,F2,F3) de grandeur diverses toujours plus petites que la surface S

    (3). F1 : 30% de la surface S
    (1) -> S: surface rectangulaire donnée
    (2) -> F1: forme rectangulaire donnée => surface donnée
    (3) -> F1/S: ratio surface donné

    Heu... il faut laisser un degré de liberté au systeme. Si tu imposes (1) et (2), tu ne peux pas imposer (3)
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2

  4. #4
    Membre averti
    Homme Profil pro
    Responsable de service informatique
    Inscrit en
    Août 2005
    Messages
    37
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : Responsable de service informatique
    Secteur : Industrie

    Informations forums :
    Inscription : Août 2005
    Messages : 37
    Par défaut
    Merci des réponses,

    J'avais déjà regardé ce post et ce n'est pas totalement ce que je recherche mais je vais continuer a y réfléchir et si je trouve une combine je vous en reparlerai.

    Merci encore

  5. #5
    Membre averti
    Homme Profil pro
    Responsable de service informatique
    Inscrit en
    Août 2005
    Messages
    37
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : Responsable de service informatique
    Secteur : Industrie

    Informations forums :
    Inscription : Août 2005
    Messages : 37
    Par défaut
    Comme promis je reviens car j'ai réussi a faire ce que je souhaitai ...


    Le générateur de placement d´objets aléatoire

    Lors de la création d´un map, il est saoulant de poser les 30 arbres qui vont composer la foret, ou bien de créer le petit oasis au milieu du désert, etc.

    Cet outil va vous permettre de s'affranchir de cette tache.

    1. Délimitez une zone avec la souris
    2. Choisissez dans la bibliothèque d´objets ceux que vous souhaitez générer dans la zone
    3. dites à l´outil, je veux 10% de cet objet, 20% de celui la et 5% de ce dernier.
    4. cliquez sur Générer !

    Et bingo, en moins de 2 secondes l´outil créé et place aléatoirement les objets dans les proportions demandées sur la zone sans qu´aucun ne se touche !!


    http://i20.servimg.com/u/f20/11/39/61/92/screen21.jpg

  6. #6
    Membre chevronné
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Par défaut
    Je suis convaincu que ton algorithme marche parce que tu ne veux couvrir qu'une petite partie de ta région (1+3+5+10+5=24% dans ton exemple). Si tu veux couvrir une grande partie (voire la totalité) c'est un problème difficile (NP-difficile car c'est une généralisation du packing 2D).

    Je te conseille d'essayer ton code en demandant de couvrir environ 95% de la région. Cela permettra de voir si ton algorithme est robuste.

    Tu peux aussi créer des instances difficiles en voulant mettre des objets 450x5 et 5*450 dans une zone 500x500.

  7. #7
    Membre averti
    Homme Profil pro
    Responsable de service informatique
    Inscrit en
    Août 2005
    Messages
    37
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : Responsable de service informatique
    Secteur : Industrie

    Informations forums :
    Inscription : Août 2005
    Messages : 37
    Par défaut
    Hello,

    Devant tant de certitudes, je me devais de répondre

    Donc voici un exemple avec une génération a 85% (je suis monté a 95 sans probleme...)



    Et un exemple avec un objet de taille spéciale...



    Info, petit probleme de refresh la zone ne fait pas 100x100 mais 500x500 .. je suis aussi monté a 1500x1500 pour tester... ca fonctionne sans probleme.

    a++
    Nico

  8. #8
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par leghola
    Hello,

    Devant tant de certitudes, je me devais de répondre

    Donc voici un exemple avec une génération a 85% (je suis monté a 95 sans probleme...)
    Oui, ce probleme peut etre resolu sans trop de difficulté (recuit simulé ou autre).

    Je pense que FrancisSourd a confondu avec les problemes de 2d packing ou l'on recherche une solution OPTIMALE (1), ou la on rentre dans du NP-hard.

    (1) par exemple minimiser le perimetre de la zone occupée, ou maximiser l'espace entre les formes, ...
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  9. #9
    Membre averti
    Homme Profil pro
    Responsable de service informatique
    Inscrit en
    Août 2005
    Messages
    37
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : Responsable de service informatique
    Secteur : Industrie

    Informations forums :
    Inscription : Août 2005
    Messages : 37
    Par défaut
    Hello,

    Oui, je parlais dès mon 1er post de placement "aléatoire", il est bien sur implicitement expliqué que je ne parle pas de solution optimum... L'optimum chercherait des solutions de placement et j'en perdrai une notion de hasard certaine..

    Oui, ce probleme peut etre resolu sans trop de difficulté (recuit simulé ou autre).
    Je suis étonné de lire cette phrase Pseudocode étant donné que ton premier post m'annonce qu'avec les contraintes que je souhaite, ce n'est pas possible.
    D'un coup, ca devient un probleme relativement simple...

    Faudra m'expliquer là j'ai perdu une roue de la charette durant le trajet..

    a++
    Nico

  10. #10
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par leghola
    Je suis étonné de lire cette phrase Pseudocode étant donné que ton premier post m'annonce qu'avec les contraintes que je souhaite, ce n'est pas possible.
    D'un coup, ca devient un probleme relativement simple...

    Faudra m'expliquer là j'ai perdu une roue de la charette durant le trajet..
    Citation Envoyé par Dutronc
    Je ne sais faire qu'un seul geste
    Celui de retourner ma veste, de retourner ma veste
    Toujours du bon côté
    Non, mon 1er post reste vrai. Tel que tu as posé le probleme dans le P.O, ton probleme est (generalement) insoluble car il manque un degré de liberté.

    Je pense que dans ton programme, le "%" de remplissage est approximatif.

    Par exemple si je te donne des objets 100x100 a mettre dans un espace 200x200, tu ne peux mettre que 0,1,2,3 ou4 objets. Donc les seuls "ratio d'occupation" possibles sont 0%, 25%, 50%, 75%, 100%

    Si j'en demande pour 85%, ca n'est pas possible.

    a++
    Nico
    @+
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  11. #11
    Membre chevronné
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Par défaut
    Citation Envoyé par leghola
    Devant tant de certitudes, je me devais de répondre
    Merci c'est très instructif. Je suis assez mauvais joueur, je le reconnais mais tes instances sont toujours assez facile:

    Pour ton premier exemple, c'est facile car il y a énormément de petits rectangles. En d'autres termes, c'est plus facile de remplir un camion à 95% avec du sable qu'avec des réfrigérateurs...

    Pour le second exemple, je te suggérais d'utiliser à la fois des rectangles horizontaux et verticaux.

  12. #12
    Membre chevronné
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Par défaut
    Citation Envoyé par pseudocode
    Je pense que FrancisSourd a confondu avec les problemes de 2d packing ou l'on recherche une solution OPTIMALE (1), ou la on rentre dans du NP-hard.
    Non, pas tout à fait. Le problème de savoir si un 2D packing est faisable (sans notion d'optimisation) est déjà difficile.
    Si tu considère un tel problème de 2D packing est que tu demandes, dans le problème de leghola, des pourcentages de manière à ce que chaque rectangle soit présent une seule fois tu es exactement dans le cas du problème de packing 2D.

    Pour qu'il n'y ait pas de malentendu, cela ne veut pas dire que l'algo de leghola n'est pas satisfaisant mais je veux insister sur le fait qu'on peut créer des instances difficiles à résoudre, en particulier où il est difficile de trouver des solutions (même s'il en existe). Symétriquement, il est difficile d'assurer qu'il n'existe pas de solution à un problème (et cela peut arriver même si la somme des pourcentages est inférieure à 100%)

  13. #13
    Membre averti
    Homme Profil pro
    Responsable de service informatique
    Inscrit en
    Août 2005
    Messages
    37
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : Responsable de service informatique
    Secteur : Industrie

    Informations forums :
    Inscription : Août 2005
    Messages : 37
    Par défaut
    Hello,

    Je pense que dans ton programme, le "%" de remplissage est approximatif.
    Effectivement, c'est un taux maximum d'occupation... Comme je le repete, ce systeme n'est pas destiné a "ranger" des objets mais bien de les poser aléatoirement.

    Je travaille en tant qu'informaticien dans une usine faisant des panneaux de bois. Les fabricants de cuisines nous demandent souvent des paquets pour leurs fabrications... Quand des paquets sont fabriqués et qu'il faut en ranger un max dans un camion, j'ai un algo pour ca qui calcule les emplacements pour un cubage "optimum"...

    Pour le second exemple, je te suggérais d'utiliser à la fois des rectangles horizontaux et verticaux.
    OK, je teste ca cet aprem et je vous redis

    A++
    Nico

  14. #14
    Membre chevronné
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Par défaut
    Tiens, j'ai trouvé sur le web ce petit example pour mettre des rectangles 5x9 dans un rectangle 86x52:

    Solution (optimale) à plus de 99% de densité:

  15. #15
    Membre chevronné
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Par défaut
    Citation Envoyé par leghola
    Comme je le repete, ce systeme n'est pas destiné a "ranger" des objets mais bien de les poser aléatoirement.
    Effectivement, quand on demande des taux de remplissage très élevés, il y a beaucopu moins de manières de placer les objets et la notion de placement aléatoire est certainement moins pertinente (cela dépend évidemment des besoins...)

  16. #16
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par FrancisSourd
    ..Pour ton premier exemple, c'est facile car il y a énormément de petits rectangles. En d'autres termes, c'est plus facile de remplir un camion à 95% avec du sable qu'avec des réfrigérateurs...
    ...


    Les gros cailloux

    Un jour, un vieux professeur de l'École nationale d'administration
    publique (ENAP) fut engagé pour donner une formation sur la
    planification efficace de son temps à un groupe d'une quinzaine de
    dirigeants de grosses compagnies nord-américaines. Ce cours constituait
    l'un des cinq ateliers de leur journée de formation. Le vieux prof
    n'avait donc qu'une heure pour "passer sa matière".

    Debout, devant ce groupe d'élite (qui était prêt a noter tout ce que
    l'expert allait enseigner), le vieux prof les regarda un par un,
    lentement, puis leur dit : "Nous allons réaliser une expérience".

    De sous la table qui le séparait de ses élèves, le vieux prof sortit
    un immense pot Masson d'un gallon (pot de verre de plus de 4 litres)
    qu'il posa délicatement en face de lui. Ensuite, il sortit environ une
    douzaine de cailloux a peu près gros comme des balles de tennis et les
    plaça délicatement, un par un, dans le grand pot.
    Lorsque le pot fut rempli jusqu'au bord et qu'il fut impossible d'y
    ajouter un caillou de plus, il leva lentement les yeux vers ses élevés
    et leur demanda : "Est-ce que ce pot est plein?". Tous répondirent :
    "Oui". Il attendit quelques secondes et ajouta : "Vraiment?".

    Alors, il se pencha de nouveau et sortit de sous la table un
    Récipient rempli de gravier. Avec minutie, il versa ce gravier sur les gros
    cailloux, puis remua légèrement le pot. Les morceaux de gravier
    s'infiltrèrent entre les cailloux... jusqu'au fond du pot.
    Le vieux prof leva a nouveau les yeux vers son auditoire et
    redemanda: "Est-ce que ce pot est plein?". Cette fois, ses brillants élèves
    commençaient à comprendre son manège. L'un d'eux répondit :"Probablement pas!". "Bien!" répondit le vieux prof.

    Il se pencha de nouveau et cette fois, sortit de sous la table un
    Seau de sable. Avec attention, il versa le sable dans le pot. Le
    sable alla remplir les espaces entre les gros cailloux et le gravier.
    Encore une fois, il demanda :"Est-ce que ce pot est plein?". Cette fois, sans
    hésiter et en chœur, les brillants élèves répondirent :"Non!".
    "Bien!" répondit le vieux prof.

    Et comme s'y attendaient ses prestigieux élèves, il prit le pichet
    d'eau qui était sur la table et remplit le pot jusqu'à ras bord. Le vieux
    prof leva alors les yeux vers son groupe et demanda :"Quelle grande
    vérité nous démontre cette expérience?"

    Pas fou, le plus audacieux des élèves, songeant au sujet de ce
    cours, répondit :"Cela démontre que même lorsque l'on croit que notre
    agenda est complètement rempli, si on le veut vraiment, on peut y ajouter
    plus de rendez-vous, plus de choses à faire".

    "Non" répondit le vieux prof. "Ce n'est pas cela. La grande vérité
    que nous démontre cette expérience est la suivante : si on ne met pas
    les gros cailloux en premier dans le pot, on ne pourra jamais les faire
    entrer tous, ensuite".

    Il y eut un profond silence, chacun prenant conscience de l'évidence
    de ces propos.

    Le vieux prof leur dit alors : "Quels sont les gros cailloux dans
    Votre vie?" "Votre santé?" "Votre famille?" "Vos ami(e)s?" "Réaliser vos
    rêves?" "Faire ce que vous aimez?" "Apprendre?" "Défendre une cause?"
    "Relaxer?" "Prendre le temps...?" "Ou... toute autre chose?"
    "Ce qu'il faut retenir, c'est l'importance de mettre ses GROS
    CAILLOUX en premier dans sa vie, sinon on risque de ne pas réussir...sa vie.
    Si on donne priorité aux peccadilles (le gravier, le sable), on
    remplira sa vie de peccadilles et on n'aura plus suffisamment de temps précieux
    a consacrer aux éléments importants de sa vie.
    Alors, n'oubliez pas de vous poser a vous-même la question : "Quels
    sont les GROS CAILLOUX dans ma vie?" Ensuite, mettez-les en premier dans
    votre pot (vie)"

    D'un geste amical de la main, le vieux professeur salua son
    auditoire et lentement quitta la salle.

  17. #17
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    TOTAL RESPECT
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Algo de placement par rapport à des périodes données
    Par romfret dans le forum Algorithmes et structures de données
    Réponses: 17
    Dernier message: 28/04/2011, 17h11
  2. Algo de dessin/placement de grafcet
    Par tio dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 01/09/2009, 19h33
  3. cherche algos Delphi pour : Huffman, R.S.A, D.E.S.
    Par X-Delphi dans le forum Débuter
    Réponses: 3
    Dernier message: 24/08/2002, 18h51
  4. Cherche l'algo crc 16 bits
    Par icepower dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 21/08/2002, 13h27
  5. Recherche algo tree
    Par Anonymous dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 24/05/2002, 13h44

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