-
Edité par Heziode 8 avril 2015 à 7:48:49

Ça veut dire quoi "la manière la plus optimisée possible" ?

Avant de regarder si ton problème ressemble à des trucs connus, as-tu essayé de programmer ta propre solution ? Il est probable que cela suffira, ou que ça t'aidera à y voir plus clair.

LeLoup22 a écrit:

Ça veut dire quoi "la manière la plus optimisée possible" ?

Avant de regarder si ton problème ressemble à des trucs connus, as-tu essayé de programmer ta propre solution ? Il est probable que cela suffira, ou que ça t'aidera à y voir plus clair.

Ce que j'entend par "la manière la plus optimisée possible", c'est le plus "économique" possible, c'est à dire, que cela prennent le moins de place possible d'où l'idée du bin-packing).

Avant de regardé si mon problème exister déjà, j'ai essayez par moi même de le dev MAIS avant de pouvoir codé il faut déjà avoir un algo et comme je coince sur l'élaboration de l'algo je suis coincé...

Fais au plus simple : as-tu essayé de faire un algorithme qui teste toutes les possibilités et garde la plus économe ?

Pourquoi penses-tu avoir besoin de « faire un algo d'optimisation » pour mettre en place la solution que LeLoup22 vient de te proposer ?

Tout simplement que comme il peux y avoir jusqu'a 2500 rectangle, calculer toutes les possibilité prendrais énormément de temps,  du coup il faudrais coupler l'algo avec un "Alpha-Beta". Et c'est aussi car je n'ai aucune idée de comment réaliser un tel Algo.

Je ne peux pas codé un truc que je ne connais ou comprend pas aussi

Ok ok tu as très bien compris le problème : 2500 rectangles c'est beaucoup, tester toutes les possibilités ça va te prendre énormément de temps. Si je te conseille de quand même implémenter une solution naïve, c'est parce que ça te permettra d'y voir plus clair, et de voir si, en améliorant ta solution naïve (par exemple en identifiant que certaines branches de calcul ne donneront rien de bon) tu ne peux pas obtenir un algorithme satisfaisant "en moyenne".

Ne va pas croire que comprendre le bin packing va miraculeusement résoudre tous tes problèmes : c'est un problème NP-complet, l'algorithme a une complexité exponentielle. Si en plus tu te plantes en réduisant ton problème vers le bin packing, ça ne t'apportera rien du tout. Autant partir sur la solution naïve et l'étudier.

Ok je vais essayer cela même si je ne sais absolument pas comment m'y prendre niveau structure de l'algo. Je n'ai jamais fait d'algo aussi complexe (même un naif avec recherche en arbre binaire comme un algo min-max, jamais fait). Donc cela risque de me prendre un peux de temps...

Mais pas grave

Je posterais l'avancé de l'algo pour aider tout le monde.

Tu peux schématiser ton algorithme comme ça :

a) Générer une solution b) Tester la solution (est-ce qu'elle respecte les contraintes ?) c) Calculer le coût de la solution

Et tu itères pour parcourir toutes les solutions.

On est d'accord, toutes les solutions ça fait beaucoup, surtout si tu génères et testes aussi des solutions invalides. Commence par tester des petits exemples artificiels. Après, on pourra se demander si on peut directement générer des solutions correctes (et donc économiser la génération de toutes les solutions incorrectes), puis comment aiguiller pour directement générer les moins chères.