Le defi du moi. - Page 1

Un petit défi sympa.

On a un rectangle R de taille qu'on peut définir.
On a un ensemble E de rectangles, il peut y avoir un nombre illimité de rectangles (minimum 1 rectangle), chacun a une taille définissable.
Il s'agit donc dans ce défi de caser et organiser tous les rectangles de E dans le rectangle R, les rectangles de E ne peuvent pas se superposer. Pour re-expliquer le problème plus simplement, on a des planches, il faut les faire rentrer dans une grande boite (à plat uniquement bien sur!), il peut n'y avoir qu'une seule couche. Pour simplifier, les rectangles ne peuvent pas êtres tournés de 90° ni de quelconque angle.
Il faut que le maximum de rectangles de E tiennent dans R, cad aussi trouver la meilleur organisation possible pour en faire tenir le maximum. La meilleur solution doit être trouvé en un temps raisonnable.

shéma d'exemple:

A vos neurones !

PS : si certains ont des problèmes très simples tel celui-ci mais qui cassent des dents aux matheux, merci de me les communiquer (je connais juste le "problème du voyageur de commerce" et celui-ci que j'ai "inventé" moi même)
[edit]Edité par segaman le 13-06-2001 à 20:06:11[/edit]

je comprends rien ...

C'est un defi sympa, ca

c quoi les input et les output? l'output doit être graphique?

On peut le faire sur PC, et en Pascal ?

le défi de toi ou le défi du mois ???

->en entrée, taille (longeur et largeur) R, tailles (longeur et largeur) des rectangles de E.

->en sortie, par exemple positions des rectangles de E organisés, une sortie graphique serait bien adaptée.

le nom "défi du moi" c'est juste un nom "commercial", en fait c'est juste un probleme que je pose pour lancer un sujet de discussion pas trop débile et vous faire reflechir pour certains(pour les durs), pour d'autres appliquer un algorithme acquis d'un livre ou d'un cours.

on peut faire ça dans nimporte quel langage.

je crois qu'un prog de ce genre existe deja sur ticalc.org

de se genre... de quel genre, et c'est quoi ce prog?
sinon personne trouve ? c'est pas dur pourtant.

c'est pas dur, c'est pas dur...

.

J'ai pas bien pigé mais je pense qu'il suffi de mettre un rectangle à l'intérieur de même taille ou de divisé l'aire de ce rectangle R et d'y mettre des rectangles tant que R>E1+E2+E3+...

Si j'ai bien compris ça doit pas être ça vu ke c'est trop facile!

pollux mouhaha merci tu viens de m'ouvrir une porte sur une de tes failles. maintenant je doutes que tu ai interet à te vanter sur gtool ou autre, c'est à tes risques et périls.

allez je te reroute, on considere 10000 rectangles a organiser, voyons voir si on teste toute les possibillités ? au mieux tu t'en tires pour 10^200 années de calcul sur un p4 a 2 ghz (c'est pas juste bien sur mais juste indicatif et à mon avis c'est bien plus.) le sujet indique de boucler le calcul en un temps raisonnable je doute que ce soit le cas

elephant boy > ben en fait tu te rendra compte que l'organisation des rectangles générée par ton prog est minable , ps ton smiley est copyright Yahoo.

pour les autres j'ai trouvé une solution rien qu'a la reflexion, en plus on m'a dit qu'il existe un algorithme qui peut etre appliqué à ce probleme et ça coïncide avec ce que j'ai pensé.

tu as mal lu le sujet, j'ai tout bien expliqué pourtant, enfin j'ai essayé.

voici la reponse à ta premiere question : "il peut y avoir un nombre illimité de rectangles (minimum 1 rectangle)"
voici le but : "Il faut que le maximum de rectangles de E tiennent dans R, cad aussi trouver la meilleur organisation possible pour en faire tenir le maximum. La meilleur solution doit être trouvé en un temps raisonnable."
je crois que c'est clair non ? il n'y a donc qu'un seul algo a faire, qu'on se le dise... pour le temps raisonnable c'est juste pour dire que ça doit etre moin long que de le faire a la main.

sinon essai de faire ton algo qui teste toute les solutions, (avec le compilo le plus performant du monde si tu veux) si tu sais lequel c'est (sur PC). et je vais le tester avec 20 rectangles à organiser. ça marche ? tu me fait ça ?

je t'explique vite fait, a partir du moment ou l'idée te vient de tester toutes les solutions pour un probleme c'est que tu ne sais pas reflechir ou que tu n'as pas reflechis pour trouver un algo. c'est pas mon point de vue a la base mais nimporte quel prof ou autre te le dira.

je tien a noter aussi que dans ce probleme si tu utilise ta méthode, le nombre de solutions possibles est égal a l'infini dans tous les cas, en effet chaque rectangle peut prendre une infinité de postions dans l'espace R.
[edit]Edité par segaman le 19-06-2001 à 18:06:05[/edit]

Le sac à dos (Knapsack Problem) :

On dispose de n objets, de poids pi, de valeur vi. On ne peut porter un sac pesant plus de P, et bien sûr on voudrait y mettre ce qui maximise la valeur totale du sac.
[...]
Ceci fait, constatez qu'il y a 2^n cas possibles (on prend ou non le premier objet, puis dans chaque cas, etc... - une illustration naturelle sera de représenter les possibilités en arbre). Soit... O(n*2^n) pour calculer toutes les sommes.


Voilà, la méthode brute donne un algorithme en O(n*2^n), en personne ne connaît mieux pour le moment.
Avec le problème du voyageur de commerce, il constitue l'un des plus importants problèmes d'informatique algorithmique.

JM > Il y a bien mieux! rien qu'a la reflexion (je suis nul en algorithmie, pourtant) j'ai trouvé une méthode efficace.
Allez voici 3 methodes qui doivent pouvoir s'appliquer ici :

- recuit simulé: L'idée est que si on a un problème contenant beaucoup de conditions et qu'on a une idée de la meilleure solution, on prend une solution au hasard, puis on teste toutes les conditions. à chaque fois qu'une condition n'est pas respectée, on modifie légèrement la solution pour qu'elle la respecte, puis on reteste toutes les conditions jusqu'à ce que ce soit bon (ou qu'on ait dépassé le temps imparti). L'expérience montre qu'on tend ainsi très rapidement vers un minimum local proche de la meilleure solution.

- convergence par algorithme génétique d'interpolation : ici pareil que le recuit simulé, on prend comme base de nombreuses solutions trouvées au hazard, puis on les fait converger avec un algorithme génétique, chaque solution représente un genome a coupler avec un autre, ici la mise en oeuvre se révele enfantine.

- methode que j'ai inventé : chaque rectangle représente un animal doué d'un faible logique et dont le but dans la vie est de réussir à se caser dans le gros rectangle R. D'abord tous ces pseudo-animaux s'entassent dans R, ils se remuent, les plus gros se posent le plus vite puis les plus petits commencent a cherche une place pour rentrer. si la place n'est pas assez grande ils essayent de rentrer de force en poussant les autres ! a chaque fois qu'un individu essai de rentrer cela remue tous les autres qui le touchent. ici bien sur on simule l'aspect physique de ce mini-monde.

voila une idée en apparence très faitaisiste mais qui risque d'en étonner plus d'un car je n'ai pratiquement pas réflechi pour trouver cette methode, je l'ai élaborée presque en temps réel ou j'écris ce message. et pourtant cette methode propose de trouver une solution correcte avec une rapidité impressionnante, temps de calcul non-exponentielle, cad en n*log(n), de plus c'est facililement améliorable en rajoutant de la logique a chaque individu.

alors?

voila pourquoi je dit que ça casse les dents au matheux... et oui y a des limites au maths, c'est pour ça que je ne les utilise pas !

Enfin, je suis bien déçu que personne n'ai réussi à donner la moindre bonne idée...

bon je vais reflechir.. mais je suis en vacance.. alors (

bon voila ce que je pensse:

1: Classer les rectangles en 2 cathegorie: les rectangle de type | et ceux de type -.

2: Trier les rectangle de chaque cathegorie par ordre croissant.

3: Prendre le rectangle qui a la longueur la plus longue et le placer au coordonnées (0;0).

4: Prendre un rectangle de l'autre cathegorie et tester celui dont la longueur complete au maximum le cote du carre avec l'autre rectangle.

Puis continuer ainsi de suite...

AH! enfin une idée un peu plus interressante!
mais l'organisation générée n'est pas encore très correcte.

segaman ta methode du 'les plus gros d'abord ' ne peut pas s'appliquer ici car si'l'on ne peut pas mettre tous les rectangles ce sont les plus gros que on laissera sur le cote car l'interet et de faire rentrer le plus grand nombre de rectangle dans le gros rectangle .Ta methode pourrait s'ppliquer que si on est sur de pouvoir les faire tous rentrer.

A mon avis la methode de classement par hauteur et par longueur peut mener plus loin

erf il faut preciser.. parce que si on veut en faire tenire un max.. il est alors logique que l'on commance par les plus petits...

Bon je vais faire un petit prog basic pour voir...

oula.... je ne sais pas si l'on peut faire un algorithme pour ca...
parce que moi j'ai dessiner un rectangle A, puis je l'ai diviser en plusieurs.. pour aoir l'ensemble E...
mais j'ai trouve aucune logique pour retrouve le rectangle A

jibax > tu n'as pas tout a fait compris ma methode
je n'ai pas insinué de placer les gros rectangle en premier! je dit simplement que les gros qui sont plus lourd tombent plus vite au sol, mais étant donnée la logique et physique qu'on peut attribuer a chaque individu, si par exemple 3 petits rectangles veulent rentrer ils font pression sur un plus gros qui lui revien a la case départ.
mais je vous laisse trouver la logique qu'on peut assigner a chaque individu pour la meilleur solution possible, ansi que les racourcis éventuels... moi je donne juste des idées, je fait pas le défi, vous n'etes pas obligés de suivre ces idées.
je précise aussi de nouveau qu'il faut faire tenir le maximum de rectangle tout en occupant la surface au maximum.

nhdpp > ben je vois pas comment tu veux faire. chaque rectangle de E est défini en entrée par 2 réels: largeur, auteur, en sortie par 2 nouveaux réels: position x, position y, donc par exemple tu fait un tableau, une liste ou une structure..

segaman, ton défi n'est pas vraiment le problème du sac à dos.
Et je pensais que tu voulais une solution exacte : la meilleure solution.

JM > en plus par définition c'est impossible de trouver la meilleur solution ici
eh oui chaque rectangle a une position exprimée en réels, pas en pixels..

arf moi je croyait que l'on etait dans N )))

J'ai peut-etre une idée:

On pourrair prendre les plus grand au plus petit (paire Aire, ou pas perimetre), et essayer de les ranger de facon a ce qu'il aient le plus de pêrimetre en contact avec les bords ou avec d'autres rectangles ...

deja pensé.. mais ca marche pas

allllez!!!!
- c'est un probleme de débutant
- je vous oriente sur des idées
et vous trouvez toujours pas?
faut il tout vous macher comme à l'école ???