minimisation d'espace occupé

On m'a tout récemment posé un probleme que je trouve intéressant et pour lequel je n'ai pas d'algo évident qui me vienne à l'esprit...
on dispose de N rectangles de dimensions (x,y) et on veut les mettre de sorte que si X est la longueur totale et Y la hauteur totale on minimise sqrt(X^2+Y^2).
Voila l'exemple qu'il m'a envoyé
http://82.244.59.21/pbmaths.jpg
A part tester toutes les solutions possible je ne vois rien qui me donne une solution optimale...
Donc si vous avez des idées merci d'avance

Probleme traite maintes fois ici-meme...

Exemples :

http://www.developpez.net/forums/sho...d.php?t=473928

ou

http://www.developpez.net/forums/sho...d.php?t=425402

Bonsoir,

c'est exact, ce problème est un problème dit NP-complet.
Il n'y a pas à ce jour d'algorithme "solution", donc on utilise des heuristiques ou méta-heuristiques.
Comme il vient de te l'être conseillé, fais une recherche sur ce que je viens de citer.

NP-complet carrement?
Bon bah il me reste plus qu'à essayer de mettre au point des heuristiques qui me donnent des résultats potables
Au fait pour souviron34, il me semble avoir bien lu les liens que tu m'as donné mais ce que j'y ai lu ne m'a pas aidé pour mon problème, parce que ici je n'ai pas de "contrainte" sur les objets à placer (si j'en avais il me suffirait de placer les objets contraints les un après les autres) et je ne veux pas non plus occuper les maximum d'espace, je veux juste qu'à la fin le plus petit carré qui contient toutes mes images soit d'aire minimale. Ca se trouve il y'a effectivement un lien que je n'ai pas vu, donc si tu repasses par ici et que tu as le courage de détailler...
PS: J'arrive pas du tout à imaginer comment on peut prouver que ce problème est NP-complet, montrer qu'il est NP tout cours non plus d'ailleurs...
Bonne soirée

c'est assez simple de se ramener au meme probleme que les autres...

Tes N rectangles ont une surface totale de M.

La plus petite surface correspondra donc a un carre de

Code:

---

1 2 3

_ /M V

---

de cote.

Tu prends donc le probleme pose par les autres, avec la contrainte que la "fenetre" doit faire cette dimension...

Citation:

---

Envoyé par anzalaya

Bon bah il me reste plus qu'à essayer de mettre au point des heuristiques qui me donnent des résultats potables

---

D'après ce papier, une approche basique par l'algorithme glouton a l'air de donner de bons resultats. Sinon, sur le meme site tu trouveras plein d'heuristiques sur le "2D rectangular bin packing". ;)


@souviron: c'est quoi ton ascii-art ? une racine carrée ? :mrgreen:

Merci... en suivant la piste des liens que souviron lache parcimonieusement sur chaque thread j'etais arrivé sur ce site aussi :lol:
Je vais garder ce site il a l'air vraiment bien...

Citation:

---

Envoyé par pseudocode

@souviron: c'est quoi ton ascii-art ? une racine carrée ? :mrgreen:

---

:aie: c'est le plus rapide que j'ai trouve :oops:

Citation:

---

Envoyé par anzalaya

en suivant la piste des liens que souviron lache parcimonieusement sur chaque thread j'etais arrivé sur ce site aussi ...

---

8O je me trouve pas si parcimonieux que ca :roll:

c'est juste que je ne suis pas en recherche ni dans l'enseignement, donc pas grand temps (ni grand interet d'ailleurs) pour chercher des choses "exterieures" a ce que je fais :P

Et d'ailleurs ce site je l'avais pas ... :piou:

Bonjour,

la première heuristique toute bête que tu peux implémenter c'est de trier tes rectangle en fonction de leurs surfaces.
Comme ça tu commenceras à traiter les plus gros en premier car ce sont en général les plus dur à placer.
Sinon, regardes du coté des méthodes "recuit simulé" ou "recherche tabou".