Le defi du moi. - Page 2

Tient ca c'est marrand alors
j'ai comme l'impression que personne ici n'a jamais fait de routage...
essayer donc un jours (si jamais vous avez le temps ou si vous voulez des idées, de regarder le travail d'un logiciel d'autoplacement (comme Spectra/dans PCAD 2000 par exemple)
Sinon pour le fait de savoir s'y il faut placer le maximum de "rectangle" ou occuper l'aire la plus importante, cela reste a mon avis 2 problemes different (quoiqu'il soit possible de trouver un possible compromi)
[edit]Edité par Bill Barouf le 28-06-2001 à 22:41:47[/edit]

segaman: le probleme ici est plus algorithmique que mathematiques: les maths seront à utiliser pour fournir des objets utilisables; en effet, un rectangle avec une position dans l'espace n'est pas utilisable tel quel. Et là les maths deviendront quasiment indispensables, pas avant.
Une idée qui peut etre à creuser:
_on commence par eliminer tous les rectangles trop gros pour rentrer dans la surface
_on range tous les rectangles par ordre de hauteur croissante
_ en prenant la plus grande hauteur trouvée, on essaye en prenant les rectangle par ordre decroissant de largeur de former une ligne complete: on les places cote à cote jusqu'à ce que la ligne soit formée ou que l'on aie un rectangle trop large: dans ce cas on le laise de coté et on continue en prenant celui qui est immediatement moins large.
_ une fois qu'on a reussit à former une ligne, on tente de remplecer nos gros rectangle par des plus petits issu de la meme hauteur en repartant dans le sens opposé...
_ puis on passe à la ligne suivante.... etc

Euh, à mon avis personne ne va comprendre ce que j'ai écrit Mais c'est trop compliqué à expliquer, et à programmer encore plus. Bien sur il y a des cas à revoir en detail comme quand on est obligé de crée une marche par un manque de rectangle, mais je pense qu'il y a un petit peu de bon dans cette idée...

Bill Barouf > parles nous un peu du fonctionnement de cela si tu le sais, ça pourrait sans doute nous interresser

chickensaver_john > que penses tu d'un nombre quelconque de polygones tridimensionnels ayant un nombre quelconque de faces a ranger dans un polygone tridimensionnel lui aussi quelconque. la ça devient sérieux, LOL
sinon oublie le n*ln(n), si tu trouve un algo pas trop exponentiel c déja pas mal genre pas n^n^n

Zewoo > oui je comprend rien lol, j'ai l'impression que tu fait de l'optmisation avant d'avoir un truc qui fonctionne bien, est-ce qu'on t'apprend ça en cours ?

euh, nan: j'ai pas de cours d'infos...
et ya pas d'optimisation: mais tu veux le moins d'operations posssibles alors...

>>De plus, si on considère que l'on jette les rectangles dans l'espace le plus grand, ils peuvent se casser, et compliquer un tant soit peu le problème
je comprend pas ...

Zewoo > euh non-non-non je veux pas le moindre d'opération possibles simplement j'ai dit que la solution doit etre trouvée dans un temps raisonnable principalement pour exclure de tester toutes les configuration possibles, tu vois y a de la marge

allez les gars la... personne n'a encore donné d'idée vraiment interressante !
pour ceux qui m'ont sorti des calculs, je comprend pas bien, essayez d'expliquer le concept de vôtre algorithme de manière plus naturelle. (ex: je pose un rectangle au hazard sur (0,0), je trouve le rectangle le mieux adapté pour tenir a droite de celui ci.. etc)

Problème intéressant.... Mais quand on parle de complexité, je pense que cela s'applique à un algo non bruité (il te donne la meilleur solution à chaque fois... toujours la même) mais là le problème à une complexité hyper-exponentielle (style le voyageur de commerce) si on cherche à le résoudre exhaustivement... il est donc impossible d'avoir une complexité en O(N.ln(N)) à mon avis...
Par contre qq'un a-t-il essayé par des voies moins classiques (c'est à dire algo génétique, recuit simulé...) Parce que je suis en Maths Spé et mon sujet de TIPE c'était les algos génétiques!!! Ils permettent d'obtenir une "bonne solution dans un temps raisonnable" normalement (c'est ce que tu cherches SegaMan???) Moi, mon problème, c'était l'approximation polygonale et les résultats obtenus sont plutôt bons!!! A essayer donc sur ce problème...
A suivre....

Oui bonne idée pere nono, j'en ai déja parlé plus haut en plus.
Reste plus qu'a implémenter et tester !

j'avais pas vut segaman, je vais voir pour reflechir un peu koi :'p