Discussion :

[ben53]

Bonjour à tous,

L'algorithme dont j'ai besoin existe certainement déjà, mais malgré mes recherches, je n'ai rien trouvé

Alors je dispose d'une grille constituée de carrés de côté A, où A est la longueur du côté.
Je dispose aussi d'un certain nombre de carrés ("briques") de côté N*A, où N peut valoir 1,2,3 ou 4.
L'algorithme que je recherche doit placer dans la grille toutes mes briques, de sorte qu'il n'y ait aucun trou sous n'importe quelle brique (sauf au sommet de mon "mur" de briques).
Ai-je été clair?

[ToTo13]

Bonjour,

c'est un problème du sac à dos.

[Obsidian]

Je dispose aussi d'un certain nombre de carrés ("briques") de côté N*A, où N peut valoir 1,2,3 ou 4.

Tes briques sont-elles réellement carrées (toujours de côté N×A), ou bien rectangulaires ( A × nA ) ? Dans le second cas, as-tu le droit de les placer verticalement ?

[ben53]

Merci pour vos réponses, elles m'ont orienté vers les problèmes de bin-packing et les algorithmes associés.
Pour répondre à la question, les briques sont toujours carrées.

[cedriku]

Bonjour,

saches que ce probleme est NP-Difficile, c'est à dire qu'il n'existe pas d'algorithme (connu) polynomial pour le résoudre (que des algorithmes exponentiels).
Dans ton cas, à quel problème précis t'interesses-tu ?

Problème de décision : Existe-t-il un placement de mes carres dans la grille ?
Problème d'optimisation : En supposons que tous les carres ne rentrent pas dans la grille, quel est le sous-ensemble de mes carres pouvant rentrer dans la grille qui maximise un critère donné (par exemple la surface) ?

Autre problème d'optimisation dans le cas où ta grille a une largeur fixe mais une hauteur infinie (probleme de Strip-Packing):

Quelle est la hauteur minimum pour placer mes carres dans la grille ?

Enfin, un probleme d'optimisation encore plus general (probleme du bin-packing) :

Quel est le nombre minimum de grilles (de largeur et hauteur fixées) pour pouvoir placer tous mes carres ?

Une fois que tu as identifié ton probleme, il va falloir choisir le type d'algorithme qui t'interesse :

Les algorithmes complets : Dans le pire des cas, ils vont essayer toutes les possibilités, donc sont en général tres complexes (en terme de complexité algorithmique) mais t'assurent de trouver une solution s'il y en a une (et de trouver la meilleure s'ils sont optimaux).

Les algorithmes incomplets : Ils sont utiles lorsque l'espace de recherche est gigantesque (là ou les algorithmes complets sont impossibles a appliquer) car ont en général une faible complexité (donc sont rapides), mais n'assurent ni de trouver une solution si elle existe, ni de trouver la meilleure.

Donc si ton programme doit retourner un résultat tres rapidement dans tous les cas ou bien que les problemes sont tres gros (beaucoup de carres a placer par exemple), il faut t'orienter vers un algorithme incomplet (par contre, si le programme ne trouve aucune solution au probleme de décision par exemple, ca ne veut pas dire qu'il n'y en a pas, et si le programme trouve une solution, ca ne veut pas dire qu'elle est optimale). Il existe des algos incomplets pour ce genre de probleme qui ont une complexité polynomiale !

Par contre, si c'est la qualité de la solution trouvée qui compte alors il faut t'orienter vers les algos complets.

Je pense qu'avant de choisir un algorithme, tu dois d'abord te poser toutes ces questions (questions recurrentes lorsque les problemes sont dans cette classe de complexite).

[ben53]

Merci pour cette réponse très complète!
Je vais reformuler le problème en répondant aux questions posées jusqu'à maintenant.

Il s'agit bien d'un problème d'optimisation.

Il n'y a qu'une seule grille, qui est de largeur fixe et de hauteur infinie.
Je dispose de N briques carrées à placer dans cette grille à partir du bas de la grille (autrement dit, la grille à un fond, une "altitude 0".

Prenons une valeur quelconque A : la plus petite brique est de côté A, tous les autres types de brique ont pour côté un multiple de A, et la largeur de la grille est également un multiple de A.

La contrainte : Il ne doit exister aucun trou dans le mur constitué par le placement des briques, sauf bien sûr au sommet du mur. Autrement dit, il n'existe aucun espace non rempli en dessous de n'importe quelle brique.

Concernant les quantités, on ne dépassera jamais quelques centaines de briques, et la largeur du mur vaut 50*A.

J'ai deux ou trois pistes, mais si vous avez des choses à me proposer, n'hésitez pas!

[cedriku]

Ton problème est assez spécifique et donc peut être il serait interessant d'utiliser sa spécificité pour améliorer des algos déjà existants qui traitent le cas général (cas ou l'on a des rectangles et pas des carres...).

En plus, apparemment tu ne cherches pas forcément à optimiser un critère (hauteur minimum...) puisque la seule contrainte que tu veuilles satisfaire c'est l'espace vide entre les briques qui doit etre nul.

Donc je me pose deux questions :

1) Est-t-il toujours possibles de trouver un arrangement (sans espace vide entre les briques) ?

A priori je pense que oui car tu as que des carres et pas des rectangles. Donc il suffirait de trier tes carres par ordre decroissant de leur taille (leur cote) et de les mettre un dessus l'autre... Certes la hauteur sera maximale mais bon ca respecte la contrainte que tu pose : pas d'espace vide en dessous des briques.

Donc ceci m'amene à la deuxième question :

2) As-tu des contraintes supplémentaires que celle de ne pas avoir de trou dans ton mur ?

Car sinon, comme je l'ai dit, tu poses toutes les briques une dessus l'autre dans l'ordre décroissant de leur taille et c'est finit !

Donc peut etre veux-tu minimiser la hauteur du mur ? ou bien maximiser la largeur occupée par le mur ? (ces deux optimisations ne sont pas forcement equivalentes, maximiser la largeur du mur ne minimise pas forcement la hauteur !).

[ben53]

Effectivement, j'ai oublié de préciser la contrainte selon laquelle il faut maximiser la largeur occupée par le mur! La hauteur du mur n'est pas une contrainte.
Sans cela, la solution était en effet toute trouvée

Autre précision : les briques peuvent faire A, 2A, 3A, 4A ou 5A de côté.

[cedriku]

Ok donc c'est dejà plus clair (enfin pour moi).
Le problème de vouloir utiliser des algos dejà existant c'est que tu as une contrainte que je n'ai pas vu souvent qui est de ne pas avoir de trou dans ton mur.

Donc une premiere idee, pour moi ce serait de construire "couche par couche" ton mur. L'idée serait alors de construire une premiere couche en placant 3 objets de cote 5A puis 3 de coté 4A... puis 3 de coté A tous côte à côte, horizontalement quoi (bien sur s'il y a moins de 3 objets d'une categorie donnée, par exemple que deux objets de coté 5A alors on en choisit que deux...). Le total fait donc 45A, il reste 5A de libre sur la largeur. S'il reste un objet 5A on le place, sinon on doit résoudre un probleme annexe qui est comment remplir au mieux les 5A restant qui sont libres. On pourrait se dire que l'on va tester toutes les possibilités (il n'y en a pas un million) : y-a-t-il un 4A et 1A, 3A et 2A, deux 2A et 1A, cinq 1A ?
Le probleme en faisant ca c'est la hauteur car l'on aura des carres de hauteurs differentes et pour la suite de la méthode ca posera probleme pour satisfaire la contraintes des trous dans le mur.

Donc une alternative serait plutot de chercher a construire (avec les objets restant) un rectangle de largeur 5A et de hauteur quelconque et qui serait composé de plusieurs carres (soient A,2A,3A et 4A). Notons qu'un tel rectangle n'est pas forcément possible suivant les objets restants, et dans ce cas la on cherchera un rectangle de largeur 4A...
Pour construire le rectangle de largeur 5A, il faut envisager toutes les possibilités sur la largeur (4A+A, 3A+2A, 2A+2A+A, A+A+A+A) mais avec une contrainte a respecter. Par exemple, on placera un carre 4A et A côte a côte uniquement s'il existe 3 autres carres A (que l'on place dessus le carre A qui est a coté du 4A). Dans ce cas on aura construit un rectangle de 5A en largeur et 4A en hauteur (un carre 4A et quatre carres 1A).

Ensuite on peut passer au niveau superieur et on continue la procédure : on place trois carres 5A au dessus des 5A deja en dessous, puis trois carres 4A au dessus des 4A....il restera a nouveau 5A d'espace libre horizontalement. Et comme l'on a fait un rectangle plein au niveau inferieur on est sur de ne pas avoir de trou.

Voila c'est une premiere idée, je ne sais pas si j'ai été tres clair.

Pour résumé, on remplit 45A en largeur en placant trois examplaire de chaque type de carres (A,2A,3A,4A et 5A) et ensuite, on execute une procédure annexe, qui se charge de construire un rectangle plein de largeur maximale (au mieux de largeur 5A) composé de plusieurs carrés (ou d'un seul). Enfin, on reitère ce processus sur les couches superieures. En faisant ca on peut assurer la contrainte du trou vu que l'on place des 5A sur des 5A, des 4A sur des 4A... et le principale probleme se situe sur la derniere colonne de largeur 5A. Mais comme l'on fait a chaque fois un rectangle plein de largeur maximale, on est certain que : d'une part le mur est de largeur maximale et d'autre part on n'aura pas de trou.

[ben53]

Eh bien merci pour ces réflexions et indications!!
Je vais continuer à réfléchir à tout ça, je vous tiendrai au courant.

[Creative Convergence]

Bonjour Ben,

il me semble que tu souhaites reproduire l'algorithme qui est utilisé pour le mur du site d'information rue89 je me trompe ?

Je cherche également à reproduire cet algorithme.

As-tu fais des progrès ? Es tu prêt à partager ce que tu as découvert ?

CC.

[Creative Convergence]

Bonsoir,

c'est pas la solution mais une piste:

http://code.activestate.com/recipes/442299/

http://www.blackpawn.com/texts/lightmaps/default.html

Si quelqu'un a mieux ça m'intéresse.