Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Ordre de construction de mines


Sujet :

Algorithmes et structures de données

  1. #101
    Membre confirmé
    Une idée, comme ça :

    Si on trace une courbe où X = date et Y = la production totale, quelle serait la forme de notre chemin idéal ?

    Par exemple, une parabole ? Ou en tout cas une courbe dont la dérivée est le plus fortement croissante ? Ou peut-être la courbe la plus continue possible ?

    Si on vise une certaine courbe, ou du moins le respect de propriétés liées à cette courbe, peut être aura-t-on la possibilité de séquencer les mines pour respecter sa forme générale ?

  2. #102
    Candidat au Club
    Hmm bonne question...

    En tout cas ce qui se passe globalement dans une liste idéale, c'est que les productions sont décroissantes et les coûts croissants.

    Mais attention : on pourrait en effet peut-être trouver des méthodes qui permettent de trier "globalement" la liste, mais :

    - ceci ne fournit pas la liste idéale
    - on n'a pas algorithme qui est plus rapide lorsque la liste est "à peu près" triée

    Enfin bon, dans le style on peut reprendre l'idée de JeitEmgie avec des probabilités.

    Comme j'ai pas posté depuis longtemps, voilà ce que j'ai fait entre temps :

    - J'ai revu ma démo de la dominance :

    Je l'ai renommée "dominance absolue", car elle ne nécessite la connaissance que des 2 mines, pas du contexte dans lequel on les place (les autres mines, et p0).
    J'ai grandement simplifié la démo, j'ai honte d'avoir publié une version aussi moche ^^. Voici la démo simplifiée (et donc bien plus compréhensible).

    J'ai réfléchi à l'idée de "dominance" : les conditions de dominance absolue (p1>p2 et c1<c2) peuvent être affinées car dans le problème on connaît les autres mines et la production initiale p0. On peut ainsi donner des conditions un peu moins fortes.
    J'ai commencé à faire la démo de la dominance simple, mais j'en suis à la moitié et le plus dur reste à faire.
    Ce qui est très intéressant dans cette dominance, c'est qu'on peut recalculer les relations de dominance à chaque fois qu'on change la liste ou le p0, on peut donc l'appliquer à chaque sous-liste étudiée, ce qui me paraît très intéressant.

    - L'implémentation en Caml :

    Je n'arrive pas à trouver une bonne implémentation pour l'algo naïf avec dominance absolue (et d'ailleurs celle que j'ai fait ne marche pas)
    Il faut que je remanie l'algo par combinaisons pour pouvoir par la suite ajouter les dominances (car si on veut un algo efficace, ce n'est pas avec l'algo naïf qu'il faut travailler).

  3. #103
    Membre expert
    Attention à votre dominance absolue : il est facile de concevoir des jeux de données dans lesquels aucune mine ne domine une autre selon votre définition, et dans ceux-là il faut une autre approche.

    Une définition plus souple serait déjà celle dans laquelle vous substituez le rendement à la production.
    M1(60;13) et M2(109;21) n'a pas de relation de dominance selon votre définition alors qu'avec le rendement au lieu de la production M1 domine M2.
    (0.2167 > 0.1927 et 60 < 109 …)

    Par contre si vous avez un graphe suffisamment dense en relations de dominance, les mines qui n'ont pas de relation orientées seraient probablement les seules qu'il faut faire bouger dans l'exploration combinatoire, ce qui peut réduire très fortement l'arbre.

    Exemple si on a un graphe (1->2),(1->3),(1->4),(2->4), les 2 seules combinaisons à comparer seraient 1,2,3,4 et 1,3,2,4.

    Maintenant reste à trouver une méthode efficace pour les îlots de mines sans dominance entre elles…
    (avec le cas extrême évoqué au début : quand l'îlot est tout le problème initial…)


    Quant à votre démo : j'ai un doute sur votre

    "La permutation de Mi et Mj dans L ne modifie pas le temps d’attente pour les mines M1,...,Mi&#8722;1 ni pour les mines Mj+1, ... , Mn, puisque la production générée par la liste L&#8242; = (Mi, ... , Mj ) ne varie pas. Aussi, il convient de n’étudier que la liste L&#8242;."

    qu'on atteigne le même niveau de production est une chose, qu'on l'atteigne dans le même délai en est une autre…

  4. #104
    Candidat au Club
    Attention à votre dominance absolue : il est facile de concevoir des jeux de données dans lesquels aucune mine ne domine une autre selon votre définition, et dans ceux-là il faut une autre approche.
    Tout à fait d'accord. Les dominances sont assez fréquentes sur des listes aléatoires, mais effectivement il y a des cas où il n'y en a pas.

    Une définition plus souple serait déjà celle dans laquelle vous substituez le rendement à la production.
    Oui mais à quoi servirait cette définition de la dominance ? Comparer les coûts et le rendement est une condition plus faible que la dominance absolue : comparer les coûts et les productions entre eux. En effet il peut y avoir une relation de dominance au sens que vous définissez, mais pas de dominance absolue.
    Or, j'ai démontré qu'une mine est toujours avant une autre, quelles que soient les autres mines, leur ordre, et la production initiale, si et seulement si il y a une dominance absolue entre ces 2 mines (au sens de la comparaison entre les coûts et entre les productions).
    On peut donc avoir une dominance au sens que vous définissez, mais trouver des cas où l'ordre relatif des 2 mines est différent, ce qui n'apporte pas grand chose je pense (à moins de parler de probabilités peut-être...)

    Maintenant reste à trouver une méthode efficace pour les îlots de mines sans dominance entre elles…
    (avec le cas extrême évoqué au début : quand l'îlot est tout le problème initial…)
    Oui, bien entendu ce problème reste inchangé (le meilleur algorithme qu'on ait trouvé est en 2^n).

    Quant à votre démo : j'ai un doute sur votre

    "La permutation de Mi et Mj dans L ne modifie pas le temps d’attente pour les mines M1,...,Mi&#8722;1 ni pour les mines Mj+1, ... , Mn, puisque la production générée par la liste L&#8242; = (Mi, ... , Mj ) ne varie pas. Aussi, il convient de n’étudier que la liste L&#8242;."

    qu'on atteigne le même niveau de production est une chose, qu'on l'atteigne dans le même délai en est une autre…
    Oui ce n'est pas très clair :

    On veut comparer le temps de construction des listes :
    Lij = (M1,...,Mi&#8722;1,Mi,Mi+1,...,Mj-1,Mj,Mj+1,...,Mn)p0 et Lji = (M1,...,Mi&#8722;1,Mj,Mi+1,...,Mj-1,Mi,Mj+1,...,Mn)p0

    Le temps de construction d'une concaténation de sous-listes est la somme des temps de construction des sous-listes (initialisées avec la bonne valeur de p0).

    Le temps de construction d'une liste donnée ne dépend que de ses mines, de leur ordre, et de la production initiale.

    Ainsi dans les listes Lij et Lji, le temps de construction de la sous-liste (M1,...,Mi&#8722;1) ne varie pas.

    De plus, le temps de construction de la sous-liste (Mj+1,...,Mn) dépend de la production résultante juste avant l'occurrence de cette sous-liste. Or cette production étant la somme de p0 et de la production de chaque mine déjà construite, la permutation des mines Mi et Mj ne modifie pas cette somme. Aussi, que ce soit pour les listes Lij ou Lji, le temps de construction de la sous-liste (Mj+1,...,Mn) est invariant.

    La variation du temps de construction total entre les listes Lij et Lji n'est donc dû qu'à la variation du temps de construction de la sous-liste du milieu :
    (Mi,Mi+1,...,Mj-1,Mj) ou (Mj,Mi+1,...,Mj-1,Mi).

    Il suffit donc dans ce problème d'étudier la différence entre les temps de construction de ces 2 sous-listes.

  5. #105
    Membre expert
    Citation Envoyé par Baruch Voir le message
    Oui mais à quoi servirait cette définition de la dominance ?
    Tout simplement à avoir plus souvent des relations orientées dans le graphe donc réduire encore plus l'arbre des combinaisons à explorer.

  6. #106
    Membre confirmé

    Il faut que je remanie l'algo par combinaisons pour pouvoir par la suite ajouter les dominances (car si on veut un algo efficace, ce n'est pas avec l'algo naïf qu'il faut travailler).
    Pour ajouter les dominances dans l'algo par combinaisons :

    - dans la version actuelle de l'algo, chaque chemin exploré est complété des mines non encore traitée par paires de mines : c'est une petite optim qu'il faut abandonner si on veut traiter les dominances (trop compliqué)

    - ensuite il faut pour chaque mine la liste des mines qu'elle domine : c'est une table T1 stable tout au long du déroulement de l'algo

    - puis pour chaque chemin en cours d'exploration une table T2 des mines dominées associées chacune à un compteur des dominantes restant à traiter pour cette dominée dans le cadre de ce chemin :
    Quand on ajoute une mine lors de l'exploration, on regarde si elle est dans T.
    Puis pour chaque mine dominée en vis à vis d'elle dans T, on décrémente son compteur dans T2 : si le compteur tombe à 0, la mine dominée est libérée car toutes ses dominantes sont déjà placées et elle peut rejoindre la liste des mines non traitées du chemin.
    La mine ainsi libérée rentre alors 'naturellement' dans le cadre de l'algo.

    La table T1 est de la forme : Dictionary<Mine, List<Mine>>
    La classe chemin devient :

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
     
        class Chemin
        {
            public List<Mine> MinesNonTraitees = new List<Mine>();
            public List<MineDatee> MinesDatees = new List<MineDatee>();
            public double Production;
            public double DateFin;
     
            public BitVector Positions;
     
            public Dictionary<Mine, int> Dominees;
            ...
         }


    C'est ce qui me semble le plus efficace (?)

    Pour info, un 'Dictionary' est une table de hashage (accès en lecture écriture à un élément en o(1)).

    L'algo que j'avais posté est essentiellement itératif (et pas forcément le plus naturel pour un langage fonctionnel).
    J'essaye de vous donner une version (C#) asap (mais pas sûr que j'ai le temps à court terme).

  7. #107
    Candidat au Club
    Tout simplement à avoir plus souvent des relations orientées dans le graphe donc réduire encore plus l'arbre des combinaisons à explorer.
    Bon, regardez, ce que j'ai montré dans ma démonstration, c'est :

    Soit une liste aléatoire de mines, initialisée avec une valeur de p0 aléatoire. Si dans cette liste on a Mj avant Mi, mais avec Mi qui domine absolument Mj, alors il existe une meilleure liste : la liste de départ dans laquelle on permute Mi et Mj.

    Dans ces conditions, la seule relation de dominance qui marche est de comparer les productions entre elles et les coûts entre eux.

    Pour votre dominance (comparer les coûts et comparer les rendements) :

    M1 : p1 = 3 , c1 = 1
    M2 : p2 = 4 , c2 = 2

    on a c1 < c2 et p1/c1 > p2/c2

    Soit M : p , c

    Pour la liste M1,M,M2 , T = 1/p0 + c/(p0+3) + 2/(p0+3+p)
    Pour la liste M2,M,M1 , T = 2/p0 + c/(p0+4) + 1/(p0+4+p)

    Or si c tend vers l'infini, la liste M2,M,M1 est meilleure. Votre dominance ne permet pas de garantir que placer M1 avant M2 est toujours mieux.

    MAIS, et sur ce point peut-être avez-vous raison (après démonstration bien entendu) :

    Peut-être que dans la liste idéale, M1 est nécessairement avant M2.
    Dans le cadre de ma dominance absolue, on est certain que dans la liste idéale les dominances sont respectées.
    Dans la vôtre, c'est peut-être le cas (peut-être, à démontrer ou à réfuter).
    En effet ici la liste M2,M,M1 n'est pas idéale je pense si c devient très grand (il est plus probable que la liste idéale soit M1,M2,M, à moins que p soit très grand également, peut-être).

    Comme après tout seul l'ordre des mines dans la liste idéale est intéressant, il est vrai que la dominance absolue que je définis n'est peut-être pas la seule à garantir la propriété de bon ordre dans la liste idéale. Néanmoins je n'accepterai pas d'autres relations sans démonstration ^^

    @ Alikendarfen

    ok je regarde ça

  8. #108
    Membre confirmé
    Autre (pseudo) relation de dominance locale ?

    Partant de p, soit deux mines M1, M2 :

    Si c1 < c2, on ne sait décider de l'ordre de ces mines dans le cas où p1 < p2.

    Dans ce cas, il y a un intervalle de temps (partant de p) entre les achats potentiel de ces mines : dt = c2/p - c1/p.

    Proposition :
    Si pendant dt, avec donc une production de base p+p1, il est possible d'acquérir une ou plusieurs autres mines (éventuellement incluant M2) telles que à t = c2/p la production soit supérieure ou égale à p+p2 [et le cout total d'achat soit >= à c2], alors nécessairement M1 avant M2.
    Sinon, M2 avant M1.

    Je ne sais si la partie entre crochet [] est nécessaire (sans doute ?).

    ... dans la pratique ça apporte quoi ? Une approche récursive d'exploration !
    Car sur dt, avec toutes les autres mines (hors M1) on recommence, mais l'intérêt est qu'on ne travaille que sur les dt successifs.

    A l'issue d'une exploration :
    - Soit M1 > M2
    - Soit M2 < M1
    - Soit pas de décision

    Mais si on décide (par ex M1 > M2), il n'est plus utile d'effectuer la même opération avec M2 versus les autres Mi.


    -------------------

    Autre remarque complémentaire de tous les algos (mais qui est dans la même idée, en fait) :

    Dans le cadre de l'exploration des solutions, on peut appliquer la relation de dominance aux chemins en cours eux-mêmes.
    Par exemple (ça n'est qu'un exemple : il faudrait trouver si possible des conditions plus faibles), soit deux chemins E1, E2 : si temps(E1) < temps(E2) et production(E1) > production(E2) et cout(E1) > cout(E2) alors E1 domine E2.

  9. #109
    Membre confirmé
    Je disais :

    Citation Envoyé par Alikendarfen Voir le message

    A l'issue d'une exploration :
    - Soit M1 > M2
    - Soit M2 < M1
    - Soit pas de décision
    Mais en fait ça devrait être


    A l'issue d'une exploration :
    - Soit M1 > M2
    - Soit M2 < M1
    car ça amène toujours à une décision, non ?

  10. #110
    Membre expert
    Citation Envoyé par Alikendarfen Voir le message
    Proposition :
    Si pendant dt, avec donc une production de base p+p1, il est possible d'acquérir une ou plusieurs autres mines (éventuellement incluant M2) telles que à t = c2/p la production soit supérieure ou égale à p+p2 [et le cout total d'achat soit >= à c2], alors nécessairement M1 avant M2.
    Sinon, M2 avant M1.
    Il est plus que temps de remettre clairement les règles du jeu noir sur blanc…
    car ici il me semble que l'on mélange un raisonnement discret avec un vocabulaire continu.

    En continu cela implique que l'on travaille sur une limite pour dt -> 0
    (au passage vous voyez bien qu'il y a toujours un delta t… je n'avais pas répondu car c'est trivial à partir du moment où l'on parle de production comme quantité par unité de temps… )
    mais dans ce cas à l'instant t il n'y a jamais plusieurs mines à acheter en même temps (mais on peut avoir un choix trivial entre plusieurs mines de même coût…)
    tandis qu'en approche discrète alors oui il peut avoir plusieurs mines à acheter à un temps t car il y aura un montant résiduel potentiel après un achat qui permettra ou non d'acheter une mine supplémentaire, montant résiduel qui est reporté (ajouté à P courant au tour suivant si on n'a pas pu le dépenser…).

    Par ailleurs, n'y-t-il pas contradiction avec la règle énoncée quelque part plus avant qui voudrait qu'on achète obligatoirement une mine dès que possible et le fait que l'on puisse attendre pour acheter une mine plus chère mais qui donnerait un meilleur résultat : il faut réécrire les règles clairement pour lever cette ambiguïté.

  11. #111
    Candidat au Club
    Bon, soyons clair (c'est moi qui fixe les règles, c'est mon post ! :p)

    Il n'y a pas de tours : on n'étudie pas la question d'acheter ou pas une mine chaque jour (par exemple). On étudie cette question continûment. Ceci n'implique bien évidemment pas qu'on achète n'importe qu'elle mine dès qu'on peut la payer. En revanche, cela implique qu'après chaque achat de mine, on n'a plus d'argent.

    On a un nombre fini de mines.

    Est-ce clair ?

  12. #112
    Membre émérite
    Bonjour tout le monde,
    j'aimerais revenir vous donner un coup de main, maintenant que mes exams sont passés, j'aurais plus de temps à vous accorder. Je pense que le problème est très intéressant, il est possible que le problème du Built Order ne soit pas encore traité dans la littérature.


    Pourriez-vous me faire un résumé du problème tel qu'il est maintenant connu ? J'ai parfaitement compris les règles initiales (notamment concernant la continuité en temps mais la discrétion en solutions). En revanche, qu'en est-il des outils mis en place :
    • Quelle est la dominance partielle la plus fine qui ait été mise en œuvre pour l'instant ?
    • Une solution par insertion serait-elle valide (Insérer les mines une à une &#8722; dans un ordre prédéfini selon une règle générale &#8722; à la meilleur place ; cela donne-t-il une liste idéale) ?
    • Ce problème se rapproche-t-il d'un problème connu ?
    • Si une liste (L,p0) contient une sous liste L'=[A...], (L',p0') est-elle idéale pour p0' vallant la production totale de L avant la construction de A ?
    • Si oui, la réciproque est-elle vraie ?



    N'hésitez pas à me donner des informations supplémentaires.
    Cordialement,
    -- Yankel Scialom

  13. #113
    Membre confirmé
    Eh ! Ne vous fachez pas les gars !

    On est en temps continu. Mais une mine s'achète d'un seul coup.

    Pour le dt dont je parlais, il ne faut pas qu'il y a ait de confusion : c'est l'écart entre la date possible d'achat d'une mine plus chère par rapport à la date possible d'achat d'une mine moins chère partant d'une production p (aucune notion faisant tendre dt vers 0 ou autre dans ce cadre).

    dt = c2/p - c1/p
    Maintenant si néanmoins p2 > p1, l'algo que je proposais peut permettre de discriminer le meilleur choix parmi acheter M1 tout de suite ou acheter M2 tout de suite.
    Ce 'sous calcul' comporte également une combinatoire.
    Cependant, cette combinatoire est réduite car elle est bornée dans le temps par dt.

    D'où le gain potentiel sur la complexité globale.
    Maintenant, il va falloir approfondir l'algo pour concrétiser tout ça.

  14. #114
    Membre confirmé
    Du renfort !
    Bon retour prgasp. Et j'espère que tes exams se sont bien passés.

    Alors, quelques réponses (et je pense Baruch corrigera/complètera) :


    Quelle est la dominance partielle la plus fine qui ait été mise en œuvre pour l'instant ?
    Dominance globale : p1 > p2 et c1 < c2
    Locale : meilleur choix M1M2 ou M2M1 (selon p et indépendamment de la suite)

    Et par ailleurs, l'idéalité 2 à 2 n'implique pas une idéalité globale.


    Une solution par insertion serait-elle valide (Insérer les mines une à une &#8722; dans un ordre prédéfini selon une règle générale &#8722; à la meilleur place ; cela donne-t-il une liste idéale) ?
    Une solution par insertion a été trouvée, mais elle ne donne pas toujours le meilleur résultat. Je n'ai plus les chiffres en tête, mais en ordre de grandeur : elle est correcte dans 95% des cas et quand elle n'est pas optimale elle est proche de la meilleure solution à < 10% près. Mais évidemment les limites de ce comparatif sont liées au fait de pouvoir calculer les solutions avec un algo exact.


    Ce problème se rapproche-t-il d'un problème connu ?
    Pas à ma connaissance.


    Si une liste (L,p0) contient une sous liste L'=[A...], (L',p0') est-elle idéale pour p0' vallant la production totale de L avant la construction de A ?
    Si oui, la réciproque est-elle vraie ?
    Edit : oui si L est idéale. Et pour la réciproque non (l'idéalité 2 à 2 n'implique pas un chemin global idéal).
    Je ne suis pas totalement sûr mais je pense que non. A moins que L' termine L.
    Pourquoi ? Parce que le problème est quasi symétrique : on peut aussi le prendre en partant de la fin.
    Etes vous d'accord sur ce point ?

  15. #115
    Membre confirmé
    Petit complément sur la dernière question :



    Si une liste (L,p0) contient une sous liste L'=[A...], (L',p0') est-elle idéale pour p0' vallant la production totale de L avant la construction de A ?
    Si oui, la réciproque est-elle vraie ?
    Edit : oui si L est idéale. Et pour la réciproque non (l'idéalité 2 à 2 n'implique pas un chemin global idéal).
    en fait, c'est grâce à cela qu'on a pu produire un algo "par combinaisons" :

    Partant du principe d'une exploration globale, on réduit à chaque étape les cas possibles en ne gardant qu'un meilleur chemin E parmi les chemins comprenant exactement les mêmes mines que E.

  16. #116
    Membre expert
    Citation Envoyé par Baruch Voir le message
    …cela implique qu'après chaque achat de mine(s), on n'a plus d'argent.
    ok,
    donc si on met en parallèle votre notion de dominance absolue on peut se poser la question : existent-ils des cas où des mines prises séparément n'ont pas de relation de dominance absolue avec une mine tierce mais mises ensemble, elles en auraient une, auquel cas selon votre critère absolu il faudrait les mettre ensemble…

    pour que M1 et M2 puissent être mises ensemble et dominer M3 alors qu'elles ne la dominent pas séparément il faut que la dominance ne soit pas respectée uniquement à cause du test sur P (C1+C2< C3 ne peut pas être vrai si déjà C1 ou C2 > C3…)
    donc
    not(p1 &#8805; p3) and not(p2 &#8805; p3) and (p1+p2 &#8805; p3)
    doit être vérifié.

    M1=(10;4) M2=(5;4) M3=(15.1;7.9)
    ni M1, ni M2 prises séparément ne dominent M3 puisque p1 et p2 < p3 mais ensemble oui : 10+5 < 15.1 et 4+4 > 7.9

    donc si on a une situation M1(c1; p1) M2(c2;p2) M3(c1+c2+d1;p1+p2-d2) (d1, d2 > 0) dans laquelle ni M1 ni M2 ne domine M3 séparément,
    quelles sont les conditions sur d1 et d2 pour que M3 puisse se glisser entre M1 et M2 (ou M2 et M1) dans la meilleure solution ?

    si les conditions sur d1 et d2 conduisent à une contradiction avec les hypothèses alors vous aurez renforcé votre notion de dominance absolue car elle s'étendra aux groupements (ils font un bloc soudé face à un indéterminé qu'ils dominent ensemble) dans le cas contraire vous aurez de nouvelles conditions pour déterminer quand la fusion conduit à une relation absolue.

  17. #117
    Membre confirmé
    Citation Envoyé par JeitEmgie Voir le message


    M1=(10;4) M2=(5;4) M3=(15.1;7.9)
    ni M1, ni M2 prises séparément ne dominent M3 puisque p1 et p2 < p3 mais ensemble oui : 10+5 < 15.1 et 4+4 > 7.9

    donc si on a une situation M1(c1; p1) M2(c2;p2) M3(c1+c2+d1;p1+p2-d2) (d1, d2 > 0) dans laquelle ni M1 ni M2 ne domine M3 séparément,
    quelles sont les conditions sur d1 et d2 pour que M3 puisse se glisser entre M1 et M2 (ou M2 et M1) dans la meilleure solution ?

    si les conditions sur d1 et d2 conduisent à une contradiction avec les hypothèses alors vous aurez renforcé votre notion de dominance absolue car elle s'étendra aux groupements (ils font un bloc soudé face à un indéterminé qu'ils dominent ensemble) dans le cas contraire vous aurez de nouvelles conditions pour déterminer quand la fusion conduit à une relation absolue.
    C'est exactement l'esprit du dernier algo que j'ai proposé !!

    A la variante près que ce calcul de dominance multiple est défini dynamiquement et contextuellement.

  18. #118
    Membre confirmé
    J'ai fait un petit test avec l'algo par combinaison et l'exploitation des dominances (c1 < c2 et p1 > p2).

    C'est plutôt pas mal en termes de perf :
    52 mines (quelconques)
    44 dominantes (pouvant chacune éventuellement être dominée par une autre)
    46 dominées (dominées 1 ou plusieurs fois)

    Temps de calcul : 62s
    Nombre de chemins calculés : 4 147 377 (ce qui est plutôt pas mal comparé aux 2^52 chemins possibles de l'algo par combinaisons).

    Je vous transmets l'algo dans les prochains posts.
    Comme l'autre fois, en deux parties (car c'est un peu long) :
    - Les données de base
    - L'algo lui même

    Pour résumé, il y a eu, au final, très peu de modif par rapport à l'algo par combinaisons.

    Encore une fois, ça sera du C# : si vous avez des questions n'hésitez pas.

    PS : j'ai comparé avec l'algo naïf pour valider les résultats. Tout semble ok (ce qui n'exclut cependant pas un bug...)

  19. #119
    Membre confirmé
    Données de base :

    Les classes Mine et MineDatee n'ont pas changé :

    Mine :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
        class Mine
        {
            public string Nom { get; set; }
            public double Cout { get; set; }
            public double Production { get; set; }
     
            public BitVector.Position Position { get; set; }
        }


    MineDatee :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
        class MineDatee
        {
            public Mine Mine { get; set; }
            public double Date { get; set; }
        }


    La classe Chemin est complétée de la gestion des dominances :

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
     
        class Chemin
        {
            // Les mines non encore traitées pour ce chemin
            public List<Mine> MinesNonTraitees = new List<Mine>();
            // Les mines déjà traitées et donc datées
            public List<MineDatee> MinesDatees = new List<MineDatee>();
            // La production courante (incluant les mines traitées)
            public double Production;
            // La date courante
            public double DateFin;
     
            // Donnée technique pour identifier les chemins ayant exactement les mêmes mines
            public BitVector Positions;
     
            // Les dominantes : tous les chemins partagent cette donnée globale 
            // qui est précalculée et invariante au cours du déroulement de l'algo
            public Dictionary<Mine, List<Mine>> Dominantes = new Dictionary<Mine,List<Mine>>();
            // Les dominées avec le nombre de dominantes qui les 'bloquent' encore
            public Dictionary<Mine, int> Dominees;
     
            static int _nombreTotal = 0;
            public Chemin()
            {
                _nombreTotal++;
            }
     
            // Créer un nouveau chemin par copie
            public Chemin CreateCopy()
            {
                Chemin copy = new Chemin();
                copy.MinesNonTraitees.AddRange( MinesNonTraitees );
                copy.MinesDatees.AddRange( MinesDatees );
                copy.Production = Production;
                copy.DateFin = DateFin;
     
                if ( Positions != null )
                    copy.Positions = new BitVector( Positions );
     
                copy.Dominantes = Dominantes;
     
                if ( Dominees != null )
                    copy.Dominees = new Dictionary<Mine, int>( Dominees );
     
                return copy;
            }
     
            // Ajout d'une mine
            public MineDatee AjouterMine( Mine mine )
            {
                // On la retire des mines non traitées
                MinesNonTraitees.Remove( mine );
     
                // Calcul de la date et de la production avec cette nouvelle mine
                DateFin += mine.Cout / Production;
                Production += mine.Production;
     
                // Mise à jour de la donnée technique (cf ci-avant)
                if ( Positions != null )
                    Positions[mine.Position] = true;
     
                // Si on a des dominées
                if ( Dominees != null )
                {
                    // Cette nouvelle mine est-elle dominante ?
                    List<Mine> dominees;
                    if ( Dominantes.TryGetValue( mine, out dominees ) )
                    {
                        // Si oui, pour chaque dominée
                        foreach ( Mine dominee in dominees )
                        {
                            // Récupération du nombre de mines non placées qui la domine encore
                            int n;
                            if ( Dominees.TryGetValue( dominee, out n ) )
                            {
                                // Diminution de 1 du fait de cette nouvelle mine qu'on place actuellement
                                n--;
                                if ( n == 0 )
                                {
                                    // Si c'était la dernière dominante, la mine n'est plus dominée
                                    Dominees.Remove( dominee );
                                    // elle est donc traitable à son tour
                                    MinesNonTraitees.Add( dominee );
                                }
                                else
                                    // Si ça n'était pas la dernière dominante, il reste une dominante de moins
                                    Dominees[dominee] = n;
                            }
                        }
                    }
                }
     
                // Création de la mine datée
                MineDatee mineDatee = new MineDatee() { Mine = mine, Date = DateFin };
     
                // et ajout
                MinesDatees.Add( mineDatee );
     
                return mineDatee;
            }
        }


    A suivre, l'algo lui-même

  20. #120
    Membre expert
    Citation Envoyé par Alikendarfen Voir le message
    J'ai fait un petit test avec l'algo par combinaison et l'exploitation des dominances (c1 < c2 et p1 > p2).

    C'est plutôt pas mal en termes de perf :
    52 mines (quelconques)
    44 dominantes (pouvant chacune éventuellement être dominée par une autre)
    46 dominées (dominées 1 ou plusieurs fois)
    pour comparer il faudrait mettre en commun le fichier de data, par exemple :
    n TAB p0
    c1 TAB p1

    cn TAB pn