Bin-packing et contraintes

Bonjour à tous, après grande réflexions, je me trouve dans une impasse.
Dans le cadre d'un petit projet personnel, je souhaite réaliser un programme d'optimisation d'espace mais ayant tout de même une contrainte (sinon cela serais trop simple :P)

On admet une carte 2D (une matrice) constituer de case, ayant une longueur et largeur infini pour commencé puis fini par la suite (là n'est pas le problème). Sur cette carte viendra s'y mettre des rectange ou carre de différente longueur et largeur. Le but et de toute les placer sur la carte de la manière la plus optimiser possible MAIS, elle doivent toute être relier(c'est a dire qu'une de ces case adjacentes forme un chemin) à un rectangle appeler ALIM de longueur et largeur a définir ultérieurement. Et c'est là que je coince...


J'ai vue vite fait sur internet le bin packing sans trop m'y pencher même si je pense que cela peux être la solitons, mais je n'ai pas trouver avec de tel contrainte.


Pouvez vous m'aider à me mettre sur la bonne voie ?

Bonjour,

proposition:
Si le nombre d'objets n'est pas très important, on teste tous les cas possibles. Pour les placer, on trie par ordre décroissant et on place le plus gros au centre. Le second dans le premier quadrant. Et les autres, partout ailleurs. Les 2 premiers sont placés ainsi pour éviter les placements identiques par rotation.

Je n'ai pas compris ce que tu voulais dire par 1er quadrant....



Quand aux objet a calsser, je pense pas que cela dépasse 2500, mais même là, s'il calcul toutes les possibilité sa va grimpé très vite. Si le calcul se fait sous forme d'arbe binaire, il y aurais moyen de ne pas calculer les branche ayant un poids plus fort (comme l'algo Alpha-Beta) après je ne sais pas si cela est applicable a mon pb...

Dans un problème d'optimisation, on cherche en général à minimiser une certaine fonction.
J'imagine qu'ici, la fonction à minimiser, c'est la surface du rectangle 'enveloppe' , c'est à dire le plus petit rectangle pouvant contenir la base ALIM, et les 2500 rectangles autour.

Déjà,c'est à peu près évident que la solution, ce sera avec une base ALIM très longue , un peu comme un long couloir.
à chaque extrémité du couloir, à priori une seule porte, qui donne sur un très grand rectangle.
Sur un des côtes du couloir, 400 à 800 grands rectangles, et de l'autre coté du rectangle ALIM, les rectangles les plus petits.

A part les 2 ou 3 rectangles qui sont aux extrémités du couloir, les options pour un rectangle sont donc :
côté droit ou coté gauche,
Orienté horizontalement ou verticalement.

Comme toujours, trouver LA solution optimale sera très coûteux.
Mais trouver une solution proche de l'optimal, ça doit être jouable.