Discussion :

[Morgann]

Bonjour,

Je cherche à résoudre un problème de placement de plusieurs formes rectangulaires de dimensions et quantités différentes, dans un ou plusieurs rectangles.

Ce problème est lié au domaine de l'imprimerie.
Par exemple, soit :
10 000 modèles 21x29,7
5 000 modèles 15x21
3 000 modèles 18x24
Il s'agit de trouver comment combiner les différents modèles sur une ou plusieurs formes (dont le format est limité soit par le format maximum d'impression, soit par le format de la feuille elle-même), pour obtenir au final la quantité voulue pour chaque modèle, en minimisant la chute de matière et le nombre de formes.

Je cherche à savoir si ce problème s'apparente à un type d'algorithme connu (la cerise sur le gâteau serait bien sûr d'en trouver un exemple) ou sinon où trouver des informations pour le résoudre.

Merci d'avance pour vos réponses

[souviron34]

ça semble se rapprocher du "labelling" de cartes...

Tu as une carte. Chaque élément distinct dans la carte porte un nom (par exemple une ville, une rivière). Mais les afficher tels quels, toujours à la même position, et TOUS, peut générer des recouvrements.

Donc un tel algo est utilisé (en général en fonction du zoom), pour d'une part prioriser les affichages, et d'autre part éviter les recouvrements.

Cherche donc "labelling map" sur Google...

[pseudocode]

Cherches aussi "bin-packing 2d" ou "strip-packing", tant que tu y es...


Edit: un lien -> http://www.csc.liv.ac.uk/~epa/surveyhtml.html

[ToTo13]

Bonjour,

cela ressemble à un problème du sac à dos, qui est malheureusement NP-Complet.
Regardes du coté de méta-heuristiquesk comme le tabou ou le recuit simulé.