Idees pour resoudre un probleme

La question :

Bonjour,

Je recherche une ligne directrice pour trouver un algo efficace pour
resoudre le probleme suivant:

"Etant donne une liste de rectangles (decrit par leur longueur et leur
largeur), trouver un rectangle dont l'aire est la plus petite possible
et recouvrant tous les rectangles donnes en entree."

A part le methode basique d'enumerer toutes les combinaisons
possibles, je seche.

Est ce que quelqu'un aurait une bonne idee ?

Merci

Poser votre question sur le forum Programmation

Les 5 réponses :

On Fri, 29 Oct 2010 08:02:16 -0700 (PDT), Francis Moreau
:


Subject: Idees pour resoudre un probleme


Ce serait bien de choisir un sujet ayant un rapport avec le contenu du
message.


"Etant donne une liste de rectangles (decrit par leur longueur et leur
largeur), trouver un rectangle dont l'aire est la plus petite possible
et recouvrant tous les rectangles donnes en entree."

A part le methode basique d'enumerer toutes les combinaisons
possibles, je seche.


Tu as raison, c'est la seule solution pour obtenir la solution
optimale. S'il s'agit d'un exercice pour l'école, tu peux t'arrêter
là.

Il existe toutefois des algorithmes efficaces pour trouver une
solution approchée, i.e. un arrangement "pas trop mauvais", qui
suffira en pratique.


Pour utiliser la technique des "sprites CSS" (cf Google), il me
fallait concaténer plein de petits PNG dans un grand PNG. J'ai donc
implémenté un algorithme basique :

1/ Décider d'une largeur pour le grand rectangle. Généralement, je
prends la racine carrée de l'aire totale des petits rectangles. Ou
bien, la largeur maximum d'un petit rectangle, si elle est supérieure.

2/ Prendre le petit rectangle "le plus grand". Pour comparer la taille
des rectangles, on peut prendre l'aire, le périmètre, ou une
combinaison des deux.
Le placer en haut à gauche.

3/ Tant qu'il reste des petits rectangles à placer, prendre le plus
grand parmi ceux qui restent. Le placer le plus haut possible : soit
on trouve un trou quelque part, soit on le place en-dessous des
autres.

Il existe bien sûr d'autres algorithmes :
http://www.google.com/search?q=Rectangular%20packing
http://www.google.com/search?q=bottom-left+algorithm

Le 29/10/2010 18:10, Fabien LE LEZ répondait à Francis Moreau :



1/ Décider d'une largeur pour le grand rectangle. Généralement, je
prends la racine carrée de l'aire totale des petits rectangles. Ou
bien, la largeur maximum d'un petit rectangle, si elle est supérieure.


Si je ne m'abuse, la racine carrée de l'aire totale des petits
rectangles sera toujours supérieure à la largeur de chacun de
ces rectangles. Et même strictement supérieure, sauf s'il n'y a
qu'un seul rectangle et que ce rectangle est un carré.

Peut-être voulais-tu écrire « la longueur » (ce qui est un autre
choix possible) ?

Ou alors je me trompe ?

--
Olivier Miakinen

On Fri, 29 Oct 2010 18:34:06 +0200, Olivier Miakinen
<om+>:


Peut-être voulais-tu écrire « la longueur »


Comme je l'expliquais, j'ai utilisé cet algorithme pour concaténer des
images. Chaque image a une hauteur et une largeur, non
interchangeables.

Si des rotations sont autorisées, il faudra utiliser un algo plus
complexe.

Le 29/10/2010 20:08, Fabien LE LEZ a écrit :



Peut-être voulais-tu écrire « la longueur »


Comme je l'expliquais, j'ai utilisé cet algorithme pour concaténer des
images. Chaque image a une hauteur et une largeur, non
interchangeables.


Ah, d'accord. La largeur d'une image peut effectivement être plus grande
que sa hauteur.


Si des rotations sont autorisées, il faudra utiliser un algo plus
complexe.


Sans même penser aux rotations, j'avais juste cru que tu parlais de la
largeur et de la longueur d'un rectangle, avec longueur > largeur.
Désolé de la méprise.

--
Olivier Miakinen

On 29 oct, 18:10, Fabien LE LEZ <grams...@gramster.com> a écrit :


Pour utiliser la technique des "sprites CSS" (cf Google), il me
fallait concat ner plein de petits PNG dans un grand PNG. J'ai donc
impl ment un algorithme basique :

1/ D cider d'une largeur pour le grand rectangle. G n ralement, je
prends la racine carr e de l'aire totale des petits rectangles. Ou
bien, la largeur maximum d'un petit rectangle, si elle est sup rieure.

2/ Prendre le petit rectangle "le plus grand". Pour comparer la taille
des rectangles, on peut prendre l'aire, le p rim tre, ou une
combinaison des deux.
Le placer en haut gauche.

3/ Tant qu'il reste des petits rectangles placer, prendre le plus
grand parmi ceux qui restent. Le placer le plus haut possible : soit
on trouve un trou quelque part, soit on le place en-dessous des
autres.

Il existe bien s r d'autres algorithmes :http://www.google.com/search?q=Rectangular%20packinghttp://www.google.com/search?q=bottom-left+algorithm


Super, il me manquait les mots clefs pour ce genre de probleme.

J'ai maintenant plein de pistes pour resoudre ce probleme.

Merci !

Poser votre question sur le forum Programmation

Questions similaires :

Petit problème de géographie.

Bonjour. "dvanhee" a écrit dans le message de news J'avais ébauché un truc de ce genre il y a longtemps, à base de géométrie constructive... De mémoire: on parcours les points du contour (polygone) en considérant pour chaque nouveau point: - le triangle qu'il forme avec les...

Autre problème graphisme

Bonjour à tous Me revoilà avec un nouveau petit problème : J'ai une image couleur codée sur 24 bits (8 bits pour le Rouge, 8 bits pour le Vert et 8 bits pour le Bleu) Je dois arriver à réduire le nombre de couleurs dans l'image finale car chaque pixel est codé sur un nombre de bits variable de 1 bit...

Génération uniforme de solutions d'un problème NP-difficile

Bonjour, Je veux générer une solution d'un problème NP-difficile avec une probabilité uniforme. Le problème NP-difficile se présente sous la forme d'un vecteur booléen de longueur n vérifiant des contraintes de cardinalité de la forme (x_1 + x_3 + x_6 <= 2, respectivement ==, >=) Comme je ne vois...

problème de 3 couleurs

Bonjour messieurs, Voici un algorithme pour 3 couleurs : Soit G un graphe planaire qui a 3-clique comme clique maximum, on note chaque 3-clique par triangle. G contient plusieurs triangles, placer les un à coter des autres, ou séparer par des arrêts. 1) Zone de colorisation obligatoire simple : Si...

probleme d'emploi du temps.

Bonjour, Je m'intéresse à l'aspect théorique des algorithmes permettant d'obtenir un emploi du temps en fonction de contraintes. J'ai bien trouvé quelques références éparses sur google, le problème semble NP-complet, peut se résoudre par le coloriage d'un graphe (cela n'est pas clair pour...