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. #421
    Candidat au Club
    L'avantage de garder le potentiel sous cette forme :

    cM (1 + p/pM)

    ça permet d'avoir une fonction affine de p, qui est finalement la seule chose qui bouge.

    Mais effectivement, on se fiche un peu de comment on l'écrit.

    Alikendarfen, tu peux énoncer clairement la propriété que tu utilises stp (et à laquelle on n'a pas trouvé de c-e) ?

  2. #422
    Membre confirmé
    Citation Envoyé par Baruch Voir le message

    Alikendarfen, tu peux énoncer clairement la propriété que tu utilises stp (et à laquelle on n'a pas trouvé de c-e) ?
    Oui. Voici le contexte et les règles utilisées pour cet algo de type NDO.

    On dispose d'un chemin hypothèse C se terminant par une mine M.
    p' est la production avant M
    p celle après M

    On cherche à déterminer des mines pour poursuivre C.

    1/ Les mines prises en compte ne sont que les mines Ai dominantes (par rapport à l'ensemble des mines restant à placer) et optimales 2 à 2 avec M à p' : (M < Ai)(p')

    2/ On identifie un sous ensemble Bj de Ai tel que : pour tout Ai, (Bj < Ai)(p) et (Bj < Ai)(p + max(p(Bj), p(Ai)))

    Pour rappel (Bi < Ai)(p) est équivalent à t(BiAi) <= t(AiBi) à p.

    3/ On trouve des Bi (mettons n mines), on constitue alors n chemins hypothèses C+Bi et on poursuit l'algo

    4/ On ne trouve aucune Bi, on constitue alors les chemins hypothèses C+Ai et on poursuit



    Edit : un point complémentaire, pour information
    Il y a quelques problématiques d'arrondis dans les calculs qui s'ajoutent à tout ça : je viens de le voir apparaitre en utilisant la notion de potentiel à la place du calcul de type t(AB)... ce qui ne veut pas dire qu'un calcul est mieux que l'autre (ça c'est à étudier) mais simplement que cela induit une différence.

  3. #423
    Candidat au Club
    Je ne comprends pas :

    Soit A l'ensemble des mines dominantes et optimales 2 à 2 avec M.

    Bj appartient à B équivaut à :

    Pour tout Ai dans A, (Bj < Ai)(p) et (Bj < Ai)(p + max(p(Bj), p(Ai)))

    C'est ça ?

    Du coup le seul Bj possible est celui qui a le potentiel minimum à p, non ?

    Edit : Peut-être as-tu voulu dire :

    Pour tout Ai dans A, si (Bj < Ai)(p), alors (Bj < Ai)(p + max(p(Bj), p(Ai)))

    ?

  4. #424
    Membre confirmé
    Citation Envoyé par Baruch Voir le message
    Je ne comprends pas :

    Soit A l'ensemble des mines dominantes et optimales 2 à 2 avec M.

    Bj appartient à B équivaut à :

    Pour tout Ai dans A, (Bj < Ai)(p) et (Bj < Ai)(p + max(p(Bj), p(Ai)))

    C'est ça ?
    oui, c'est ça

    Citation Envoyé par Baruch Voir le message

    Du coup le seul Bj possible est celui qui a le potentiel minimum à p, non ?
    il peut y avoir plusieurs Bj cependant (y compris des mines de c et p différents)... je n'utilise pas d'autres règles pour les discriminer pour le moment.

  5. #425
    Candidat au Club
    il peut y avoir plusieurs Bj cependant (y compris des mines de c et p différents)... je n'utilise pas d'autres règles pour les discriminer pour le moment.
    Euh non c'est pas possible :

    Pour tout Ai dans A, (Bj < Ai)(p) et (Bj < Ai)(p + max(p(Bj), p(Ai)))

    Ca implique que :

    Pour tout Ai dans A, (Bj < Ai)(p)

    Et donc Bj est nécessairement le minimum de potentiel à p de A.


    Ou alors je dis n'importe-quoi...

  6. #426
    Membre confirmé
    Citation Envoyé par Baruch Voir le message

    Ou alors je dis n'importe-quoi...
    Non ! C'est moi !! mea culpa

    Effectivement, on ne peut pas avoir t(AB) = t(BA) à p ET t(AB) = t(BA) à p', sauf à ce que ces mines soient strictement équivalentes.

  7. #427
    Candidat au Club
    Ben donc t'es certain que c'est bien la propriété qu'utilise ton algo ?

    Soit A l'ensemble des mines dominantes et optimales 2 à 2 avec M.

    Soit B la mine de A ayant le plus petit potentiel à p.

    Si pour tout Ai dans A, Ai différent de B, on a :

    (Bj < Ai)(p + max(p(Bj), p(Ai)))

    alors B est la mine à placer.

  8. #428
    Membre confirmé
    L'algo fait ce que j'ai dit plus haut. Le fait qu'il puisse accepter plusieurs mines Bi et n'en récupère qu'une seule dans la pratique ne change rien.

    L'algo n'utilise cependant pas le potentiel : comme je l'ai indiqué plus haut, utiliser à la fois le potentiel et des expressions de type t(AB) ne marche pas du fait des problèmes d'arrondis de calculs.

    Mais par contre il ne marche pas comme tu l'indiques :
    Citation Envoyé par Baruch Voir le message

    Soit B la mine de A ayant le plus petit potentiel à p.

    Si pour tout Ai dans A, Ai différent de B, on a :

    (Bj < Ai)(p + max(p(Bj), p(Ai)))

    alors B est la mine à placer.
    Parce qu'on peut avoir plusieurs mines qui ont le plus petit potentiel à p, mais par contre une seule peut vérifier en plus (Bj < Ai)(p + max(p(Bj), p(Ai)))


    Edit :
    Voici le code de la fonction (le reste de l'algo a été publié avant) :
    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
     
            public static List<Mine> MeilleuresMinesAp( List<Mine> mines, double p )
            {
                List<Mine> resultat = new List<Mine>();
     
                foreach ( Mine m1 in mines )
                {
                    bool toujoursMeilleure = true;
                    foreach ( Mine m2 in mines )
                    {
                        double pPrime = p + Math.Max( m1.Production, m2.Production );
     
                        if ( Optimales2a2( m1, m2, p ) == false || Optimales2a2( m1, m2, pPrime ) == false )
                        {
                            toujoursMeilleure = false;
                            break;
                        }
                    }
     
                    if ( toujoursMeilleure )
                        resultat.Add( m1 );
                }
     
                return resultat;
            }

  9. #429
    Membre confirmé
    J'ai en partie résolu mes problèmes d'arrondis de calculs. En partie, parce que j'ai simplement utilisé un type de donné plus précis (28 décimales significatives plutôt que 14), mais ça reste une limite.

    Pourquoi ?

    Parce que sur cet exemple :

    p=22
    M0;51;29
    M1;63;9
    M2;100;32
    M3;24;36
    M4;95;95

    NDO me donnait deux résultats :
    M3M4M0M2M1 > 3.9060165315402191
    M3M0M4M2M1 > 3.9060165315402182

    Avec une précision plus grande, on obtient :
    M3M4M0M2M1 > 3.9060165315402182949717593611
    M3M0M4M2M1 > 3.9060165315402182949717593611

    ... tout ça ne serait pas très grave (à la limite, c'est juste pour info).

    Par contre, le NDO avec la méthode du potentiel (ce dont on parlait juste avant), ne donne quant à lui qu'un seul résultat : M3M4M0M2M1

    Ce qui est logique par rapport à ce dont on vient de parler...

    ... cependant la règle utilisée est donc 'arbitraire' (même si elle s'avère juste au final -pas de contre exemple jusque là) et ça me dérange un peu.

    Qu'en pensez vous ?

  10. #430
    Membre averti
    Je vois pas bien ce qu'il y a d'arbitraire. La plupart des algorithmes d'optimisation cherchent à fournir une solution optimale en un minimum de temps. Dailleurs, souvent ces algo ne sont même pas exacts.
    S'il existe deux solutions possible, je ne trouve pas choquant que l'algo n'en fournisse qu'une. Pour moi, un algo qui donne les deux réponses répond à un problème plus large que le problème étudié.

  11. #431
    Membre actif
    Bonsoir,

    Je me permets d'intervenir sur ce post très intéressant. Je n'ai pas lu toutes les réponses et peut-être que mon intervention sera inutile voire dépassée. Mais bon ...
    J'ai retrouvé la règle de Baruch (#201 du 19/07/11) :
    t12 < t21 <=> c1(1 + P0/P1) < c2(1 + P0/P2)
    J'ai calculé ce coefficient Kn = cn(1+P0/Pn) pour chacune des n mines et trié les couples (Kn, Mn) en ordre décroissant. Cela donnerait l'ordre des mines à construire dans un temps minimum.
    J'ai fait des tests sur des jeux d'essais sous SWI-PROLOG qui sont concluants.
    Il reste à démontrer que :
    L'ordre optimal de construction des mines correspond à l'enchainement de tous les couples optimisés de mines et réciproquement.
    J'ai bien quelques pistes mais je dois y réfléchir.
    @+

  12. #432
    Candidat au Club
    Bonsoir !

    Ca me fait plaisir que quelqu'un s'intéresse au sujet, j'avoue que je l'ai laissé tomber, faute de temps et de motivation.

    Je crois comprendre que ton idée se rapproche de celle de Sharcoux (voir son 1er post).

    Or trier les mines dans l'ordre des Kn (ou potentiels) croissants, ne donne pas toujours la solution optimale (voir les tests qui ont été faits par Alikendarfen).

    J'ai calculé ce coefficient Kn = cn(1+P0/Pn) pour chacune des n mines et trié les couples (Kn, Mn) en ordre décroissant.
    Euh c'est pas croissant plutôt ?

    Je t'invite à regarder les quelques pages précédentes (à partir de l'intervention de Sharcoux), il me semble qu'on avait trouvé un algorithme qui marchait très bien, mais qui n'était pas démontré.

  13. #433
    Membre actif
    Bonjour Baruch,

    Oui erreur de moi, c'est bien par ordre croissant.
    Effectivement et apparemment (j'ai pas encore réussi à le démontrer ...) cettte règle "fonctionnerait" seulement si P0 >= max des Pi.
    Je continue à chercher à mes moments perdus !
    @+

###raw>template_hook.ano_emploi###