Discussion :

[anzalaya]

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é

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

[souviron34]

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

[ToTo13]

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.

[anzalaya]

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

[souviron34]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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...

[pseudocode]

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 ?

[anzalaya]

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