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. #181
    Candidat au Club
    Désolé de redemander, mais tu pourrais expliquer exactement ce que fais ton algo NDO stp ?

    Donc... il faut sans doute revenir à une solution de type permutations partant de la liste complète des mines...
    Je pense qu'il faut partir de la liste triée par rendements décroissants

  2. #182
    Membre confirmé
    Citation Envoyé par Baruch Voir le message
    Désolé de redemander, mais tu pourrais expliquer exactement ce que fais ton algo NDO stp ?
    Bah, j'ai déjà tout expliqué aux posts 152 et 153 (explication de l'algo, code commenté). C'est l'algo que tu as décrété faux sans apporter de justification.
    Donc voir ces posts.

    Tu as également indiqué un peu plus haut que l'algo par combinaison était meilleur.
    Or c'est faux.
    Il y a deux raisons à cela :

    - La première que j'ai déjà indiquée est qu'en termes de consommation mémoire max, NDO est en n, alors que l'algo par combinaison est en C(n, n/2)

    - La seconde c'est que NDO inclut "naturellement" la notion de combinaison parce qu'étant donné un ensemble de mines, il y a très peu de chemins dont les mines sont optimales 2 à 2 (ce qui rend quasi inutile d'étudier l'aspect combinaisons)

    Reste que je suis persuadé qu'on peut encore améliorer l'approche exacte...

  3. #183
    Candidat au Club
    Oui oui bon dsl j'ai juste du mal à comprendre ton code.
    Bon j'étudie de près ton code avant de reposter, promis ^^

  4. #184
    Membre confirmé
    Donc, voilà ce qu'on pourrait tenter : une autre approche par insertion (approx. en o(n2)).

    On part de la liste des mines (pour le moment non triée, mais on verra après : ça sera une optimisation du principe).

    L'idée est d'avoir en sortie tous les chemins possibles dont les mines sont optimales 2 à 2. La meilleure solution fait partie de ces chemins et ces chemins sont peu nombreux (par exemple 1 seul dans le jeu d'essai elentarion).

    Donc, comment ça marche :

    On a d'une part la liste des mines non encore placées et d'autre part une liste LCO de chemins optimaux 2 à 2 (c'est une liste vide au début et qui contient des chemins lorsqu'on déroule l'algo).

    On prend l'une des mines non placées.

    Pour chaque chemin de LCO, on va placer cette nouvelle mine. Donc pour chacun de ces chemins on aura comme résultat au moins 1 nouvel élément à mettre dans LCO.

    Donc on a une nouvelle mine M et un chemin C de l'actuel LCO : comment placer la nouvelle mine telle que le(s) nouveau(x) chemin(s) C' soi(en)t optimal(aux) 2 à 2 ?

    Si C est vide : le résultat est C' = ( M ).

    Si C = ( M0 ) : le résultat est C' = ( M M0 ) ou C' = ( M0 M )

    Si C = ( M0... Mi ... Mk ), M doit se placer avant l'une des Mi ou en dernier

    Si c'est en dernier : C' = C + M

    Sinon M trouve sa place après chacune des mines Mi de C, telle que (Mi M) soit optimal. C' est alors C' = (M0... Mi M) + réévalutation de C après Mi (soit l'application du même algo pour ces mines après Mi et partant de la production totale après M).
    Edit (précision) : on réévalue car du fait de M, la production courante a changé après M

    Voilà pour le principe !

    Ensuite, il faut voir comment faire en sorte de ne pas passer son temps à réévaluer les chemins après Mi : pour ça, il faut partir d'une liste de mines triée au mieux. Donc très probablement triée par ci/pi croissant et ci croissant...


    Merci de vos retours ou remarques !

    En fonction, on passe à l'implémentation...

    Edit : il y a quelques petites imprécisions dans les histoires de M avant ou après Mi, mais je pense que le principe est clair malgré tout.

  5. #185
    Membre confirmé
    Citation Envoyé par Baruch Voir le message
    Oui oui bon dsl j'ai juste du mal à comprendre ton code.
    Bon j'étudie de près ton code avant de reposter, promis ^^
    Bah, je ne t'en veux pas, vas !

    Edit : reste que si ce code n'est pas clair pour toi, n'hésite pas à poser des questions

  6. #186
    Membre confirmé
    Un petit aparté :

    On va bientôt fêter les deux mois d'échanges divers sur ce sujet des mines.

    Au cours de ces deux mois, on a réussi plusieurs fois à améliorer l'algo (soit dans une approche "exacte" (le graal ), soit en utilisant des heuristiques ou méta-heuristiques).

    Mais une question se pose : comment savoir que le dernier algo trouvé est le meilleur possible (je parle de l'approche "algo exact") ???

    Peut-être certains lecteurs spécialistes pourront apporter quelques éclairages sur ce plan ?

  7. #187
    Membre confirmé
    Ca marche !!

    L'algo par insertion décrit plus haut donne sur les 324 mines :
    - 2.1556776803280098 jours
    - en 1,789 secondes !

    Donc je crois que ça vaut le coup de vérifier ensemble qu'il est bien juste cet algo !

    Je rappelle / reformule son principe : collecter tous les chemins optimaux 2 à 2, puis garder le meilleur.

    Pour ça :
    - Insérer progressivement chaque mine dans le chemin en cours et garder toutes les possibilités où le placement de cette mine et optimal par rapport à la mine d'après.
    - Quand c'est le cas, le début du chemin ainsi constitué est préservé jusqu'à la mine qu'on vient d'insérer. Et toute la fin du chemin est remise en cause et recalculée par récursion.

    Le code est un petit peu plus complexe que "d'habitude"... il est sans doute améliorable.

    Le voici :

    Partie principale :
    Code C# :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 Chemin Traiter( List<Mine> minesOrigine, double p, Action<Chemin> trace = null )
            {
                //Algo8c algo8 = new Algo8c();
                //Chemin reference = algo8.Traiter( minesOrigine, p );
     
                List<Mine> mines = new List<Mine>( minesOrigine );
     
                Stopwatch sw = new Stopwatch();
                sw.Start();
     
                // Initialisation de la récursion avec un chemin vide
                List<Chemin> resultats = new List<Chemin>( Traiter( new Chemin( p ), mines ) );
     
                resultats.Sort( ( a, b ) => a.DateFin.CompareTo( b.DateFin ) );
                Chemin meilleur = resultats[0];
     
                sw.Stop();
     
                long elapse = sw.ElapsedMilliseconds;
     
                //double delta = meilleur.DateFin - reference.DateFin;
     
                return meilleur;
            }


    Point d'entrée de la récursion :
    Code C# :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
     
            IEnumerable<Chemin> Traiter( Chemin origine, List<Mine> mines )
            {
                // Tri des mines par rendement et cout
                mines.Sort( ( a, b ) =>
                {
                    double ca = a.Cout / a.Production;
                    double cb = b.Cout / b.Production;
                    int compare = ca.CompareTo( cb );
                    if ( compare == 0 )
                        return a.Cout.CompareTo( b.Cout );
                    else
                        return compare;
                } );
     
                List<Chemin> resultats = new List<Chemin>();
                resultats.Add( new Chemin( origine.Production ) );
     
                // Création des (sous) résultats partant de la production du chemin d'origine
                foreach ( Mine mine in mines )
                {
                    resultats = new List<Chemin>( Inserer( mine, resultats ) );
                }
     
                // Si l'origine est vide, ces chemins sont les résultats finaux
                if ( origine.MinesDatees.Count == 0 )
                    foreach ( Chemin resultat in resultats )
                        yield return resultat;
     
                // Sinon, on concatène l'origine avec ces chemins, à condition que la jonction entre les deux
                // soit optimale
                else
                    foreach ( Chemin resultat in resultats )
                    {
                        Mine derniereMine = origine.MinesDatees[origine.MinesDatees.Count - 1].Mine;
                        Mine premiereMine = resultat.MinesDatees[0].Mine;
     
                        if ( Optim( derniereMine, premiereMine, origine.Production - derniereMine.Production ) )
                            yield return Concatener( origine, resultat );
                    }
            }


    Fonctions d'insertion :
    Code C# :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
     
            IEnumerable<Chemin> Inserer( Mine mine, List<Chemin> chemins )
            {
                // Insertion de la mine dans chaque chemin
                foreach ( Chemin chemin in chemins )
                    foreach ( Chemin resultat in Inserer( mine, chemin ) )
                        yield return resultat;
            }
     
            IEnumerable<Chemin> Inserer( Mine mine, Chemin chemin )
            {
                // Si le chemin est vide, il suffit d'ajouter la mine
                if ( chemin.MinesDatees.Count == 0 )
                {
                    Chemin resultat = chemin.CreateCopy();
                    resultat.AjouterMine( mine );
                    yield return resultat;
                }
                else
                {
                    Chemin baseResultat = new Chemin( chemin.ProductionInitiale );
                    Mine mineCourante = null;
     
                    // A toutes les positions possibles...
                    for ( int i = 0 ; i < chemin.MinesDatees.Count ; i++ )
                    {
                        mineCourante = chemin.MinesDatees[i].Mine;
     
                        // ... telles que cette position est optimale pour l'insertion
                        if ( Optim( mine, mineCourante, baseResultat.Production ) )
                        {
                            // Collecte des mines 'après' l'insertion
                            List<Mine> mines = new List<Mine>();
                            for ( int j = i ; j < chemin.MinesDatees.Count ; j++ )
                                mines.Add( chemin.MinesDatees[j].Mine );
     
                            // Création de la base du chemin (toutes les mines avant insertion)
                            Chemin nouveauChemin = baseResultat.CreateCopy();
                            // Insertion
                            nouveauChemin.AjouterMine( mine );
     
                            // Puis concaténation de ce nouveau chemin de base avec les organisation optimales
                            // des mines restantes
                            foreach ( Chemin resultat in Traiter( nouveauChemin, mines ) )
                                yield return resultat;
                        }
     
                        baseResultat.AjouterMine( mineCourante );
                    }
     
                    // Test du cas où on insère la mine à la fin du chemin
                    if ( Optim( mineCourante, mine, baseResultat.Production - mineCourante.Production ) )
                    {
                        baseResultat.AjouterMine( mine );
                        yield return baseResultat;
                    }
                }
            }


    Fonction de concaténation :
    Code C# :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
            Chemin Concatener( Chemin origine, Chemin chemin )
            {
                Chemin resultat = origine.CreateCopy();
     
                foreach ( MineDatee mineDatee in chemin.MinesDatees )
                    resultat.AjouterMine( mineDatee.Mine );
     
                return resultat;
            }


    Test de l'optimalité M1 avant M2 :
    Code C# :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
            bool Optim( Mine m1, Mine m2, double p )
            {
                double t12 = (m1.Cout / p) + (m2.Cout / (p + m1.Production));
                double t21 = (m2.Cout / p) + (m1.Cout / (p + m2.Production));
     
                return t12 <= t21;
            }


    J'ai fait différents tests en comparaison du précédent meilleur algo exact : tout semble ok...
    ... mais n'hésitez pas à chercher les failles !!

    Edit :
    PS : les classes et fonctions de base sont les mêmes qu'avant

  8. #188
    Membre confirmé
    Voici un petit exemple du principe, pour éclairer les choses :

    On a un chemin en cours (déjà constitué optimal) = [A B C D E]
    Il reste des mines Mi à placer = {M1, M2, M3}

    On prend M1 :

    Si M1 A optimal alors
    - Garder M1, puis recalculer [M1] + même algo sur {A B C D E}

    Si M1 B optimal alors
    - Garder A M1, puis recalculer [A M1] + même algo sur {B C D E}

    ...etc

    On prend M2 (M1 est déjà placée dans au moins un chemin) et on recommence

    Puis M3 idem



    Dans la pratique, chaque calcul retourne un ensemble de chemins, car il y a éventuellement plus d'un chemin dont toutes les mines sont optimales 2 à 2.

  9. #189
    Candidat au Club
    Soit un chemin ABCD.

    ABCD est optimal 2 à 2 équivaut à :
    [A,B] optimal
    [B,C] optimal
    [C,D] optimal

    C'est ça ?

    Dans ce cas c'est l'idéalité 2 à 2 que j'avais évoquée non ? ^^

    Bon je crois avoir compris ton algo (ben oui dsl mais je suis pas très fort )

    Comme on parle d'optimalité 2 à 2, je me ramène avec mes p* :

    Quand tu insères une mine, il faut appliquer l'algorithme sur l'ensemble des mines suivantes, car la production initiale pour cet ensemble de mines a changé. Là je crois qu'on peut pas mal creuser :

    On a un ensemble E de mines.
    On a, pour une production initiale p0, un chemin optimal 2 à 2 (ce n'est pas forcément le seul, et ce n'est pas forcément le meilleur).
    On change cette production initiale en p0' , où p0' = p0 + p(M) , avec la mine qui a été insérée.

    L'idée que j'avais, c'était de trouver les chemins idéaux 2 à 2 non pas par insertion comme tu le fais, mais en permutant des couples de mines dans la liste.

    [M1,M2] est optimale à p équivaut à :

    [p <= p*(M1,M2) ] = [la mine la moins rentable est avant]

    L = ABCD est optimale 2 à 2 pour p0 équivaut à
    [A,B] est optimale 2 à 2 pour p0
    [B,C] est optimale 2 à 2 pour p0+p(A)
    [C,D] est optimale 2 à 2 pour p0+p(A)+p(B)

    p0 augmente et devient p0'. Donc toutes les productions ci-dessus augmentent.
    Quels sont les couples affectés ?

    Soit une liste de 2 mines [M1,M2], avec une production p avant son occurrence, qui devient p'.

    Si M1 est plus rentable que M2, alors on a nécessairement p >= p*(M1,M2), donc l'augmentation de p en p' ne change rien.
    (ce qui montre que si L est optimale 2 à 2 et triée par rendement décroissant, tout augmentation de p0 laisse L optimale 2 à 2)

    Si M1 est moins rentable que M2, il peut y avoir un basculement du couple si p' >= p*(M1,M2).
    càd si p(M) >= p*(M1,M2) - p

    Donc on peut ainsi connaître tous les couples qui ne sont plus bien ordonnés suite à l'augmentation de p en p'.

    La question est : quelles permutations effectuer pour obtenir une solution idéale 2 à 2, voire toutes les solutions idéales 2 à 2 ?



    Bon en fait je me rends compte que ton algo est vraiment très bien ^^

    J'avais pensé à faire une recherche dans un arbre pour trouver les chemins optimaux 2 à 2, mais en fait ton algo est mieux.

    Je confirme, il faut auparavant trier les mines par rendements décroissants, et pour les rendements égaux, par coûts (ou production) croissants.

    Je ne comprends pas quelque chose :

    On prend M1 :

    Si M1 A optimal alors
    - Garder M1, puis recalculer [M1] + même algo sur {A B C D E}

    Si M1 B optimal alors
    - Garder A M1, puis recalculer [A M1] + même algo sur {B C D E}

    ...etc

    On prend M2 (M1 est déjà placée dans au moins un chemin) et on recommence

    Puis M3 idem
    Au niveau du sens de ton algo, je ne comprends pas pourquoi tu ne fais pas plutôt :

    [A M1] optimal -> garder [A M1] + même algo sur {B C D E}
    [A B M1] optimal -> garder [A B M1] + même algo sur {C D E}
    etc.

    Et surtout, pourquoi faire comme tu le fais convient ?


    Je pense qu'il faudrait maintenant tester quelque chose :

    Tu as un chemin, et une mine à insérer. Dans le cas où tu trouves plusieurs endroits où insérer la mine, peut-être qu'au lieu d'étudier chacune de ces positions, il suffirait d'en étudier qu'une seule. Je pense au cas où on a trié les mines par rendements décroissants, peut-être que seule l'insertion la plus loin possible dans la liste est à étudier ? Je m'explique :

    Soit L = ABCDE, on veut insérer M

    M B est optimal et M D est optimal
    Peut-être que seul M D est à retenir ? (en partant du constat qu'au final la liste idéale est globalement triée par rendement décroissant)

  10. #190
    Candidat au Club
    J'ai réfléchi à ton algo, et je n'arrive toujours pas à comprendre :

    Supposons qu'on veut trier 3 mines A B C.

    On place A : on a [A]

    On place B dans [A] : on a soit [AB], soit [BA].
    Supposons que [AB] soit le bon ordre.

    On place C dans [AB] : les chemins potentiels sont :
    CAB ou CBA,
    si [AC] est optimale 2 à 2 pour p0, ACB
    si [BC] est optimale 2 à 2 pour p0+p(A), ABC

    Et la liste [BCA] ? Pourquoi ne pourrait-elle pas être optimale 2 à 2 ?

  11. #191
    Rédacteur

    Sacrément "minante", cette discussion!
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

  12. #192
    Candidat au Club
    Ce message n'a pas pu être affiché car il comporte des erreurs.

  13. #193
    Membre confirmé
    Bon... je rentre d'un week-end sans internet

    Je lirai vos posts ce soir ou demain.

    Cela dit, j'ai un peu amélioré l'algo que j'ai donné jeudi matin (week end sans internet, mais pas sans ordi...) : maintenant on arrive aux 324 mines en environ 25 millièmes de secondes !!



    J'ai gardé le même principe exactement mais mieux fignolé les "bords" !

    Je lis attentivement les posts récents et vous dis tout ça asap !


    Edit : cependant, pour répondre rapido à Baruch : cet algo par insertion est exact car il récupère tous les chemins optimaux 2 à 2... donc parmi eux nécessairement la meilleure soluce (je vous dis plus précisément bientôt)

  14. #194
    Membre confirmé
    Citation Envoyé par Baruch Voir le message

    Soit un chemin ABCD.

    ABCD est optimal 2 à 2 équivaut à :
    [A,B] optimal
    [B,C] optimal
    [C,D] optimal

    C'est ça ?

    Dans ce cas c'est l'idéalité 2 à 2 que j'avais évoquée non ? ^^
    Oui, c'est ça

    Citation Envoyé par Baruch Voir le message

    Quand tu insères une mine, il faut appliquer l'algorithme sur l'ensemble des mines suivantes, car la production initiale pour cet ensemble de mines a changé. Là je crois qu'on peut pas mal creuser :
    C'est bien ce que fait l'algo ! ... et puis creuser, c'est normal pour des mines

    Citation Envoyé par Baruch Voir le message

    Au niveau du sens de ton algo, je ne comprends pas pourquoi tu ne fais pas plutôt :

    [A M1] optimal -> garder [A M1] + même algo sur {B C D E}
    [A B M1] optimal -> garder [A B M1] + même algo sur {C D E}
    etc.

    Et surtout, pourquoi faire comme tu le fais convient ?
    Effectivement, la version que j'ai donnée jusque là n'est pas complètement optimale : elle marche mais identifie beaucoup trop de chemins possibles.

    Je donne la nouvelle version et son explication dans un prochain post.


    Citation Envoyé par Baruch Voir le message

    Tu as un chemin, et une mine à insérer. Dans le cas où tu trouves plusieurs endroits où insérer la mine, peut-être qu'au lieu d'étudier chacune de ces positions, il suffirait d'en étudier qu'une seule. Je pense au cas où on a trié les mines par rendements décroissants, peut-être que seule l'insertion la plus loin possible dans la liste est à étudier ? Je m'explique :

    Soit L = ABCDE, on veut insérer M

    M B est optimal et M D est optimal
    Peut-être que seul M D est à retenir ? (en partant du constat qu'au final la liste idéale est globalement triée par rendement décroissant)
    Je réfléchissais aussi à quelque chose comme ça... mais je n'ai pas abouti jusque là.

  15. #195
    Membre confirmé
    Citation Envoyé par Baruch Voir le message
    J'ai réfléchi à ton algo, et je n'arrive toujours pas à comprendre :

    Supposons qu'on veut trier 3 mines A B C.

    On place A : on a [A]

    On place B dans [A] : on a soit [AB], soit [BA].
    Supposons que [AB] soit le bon ordre.

    On place C dans [AB] : les chemins potentiels sont :
    CAB ou CBA,
    si [AC] est optimale 2 à 2 pour p0, ACB
    si [BC] est optimale 2 à 2 pour p0+p(A), ABC

    Et la liste [BCA] ? Pourquoi ne pourrait-elle pas être optimale 2 à 2 ?
    Exact... il faut que je réfléchisse à ça...

  16. #196
    Membre confirmé
    Citation Envoyé par FR119492 Voir le message
    Sacrément "minante", cette discussion!
    Et dire que la solution était là, comme le nez au milieu du visage : proéminente !

  17. #197
    Membre confirmé
    Ce message n'a pas pu être affiché car il comporte des erreurs.

  18. #198
    Membre confirmé
    Bon, je donne l'algo optimisé (malgré la remarque de Baruch sur [BCA]) :

    Dans l'ensemble, voici les modifs par rapport au précédent :
    - Moins d'utilisation de mes "classes de base" pour rendre les choses plus lisibles pour tout le monde
    - Renforcement du test d'idéalité 2 à 2 : on peut insérer M entre A et B (consécutifs) si t(AM) <= t(MA) et t(MB) < t(BM). L'aspect '<=' et '<' est important pour générer beaucoup moins de chemins dans le cas où 2 ou plusieurs mines sont identiques.

    Côté perf, comme dit plus haut : env. 25 millièmes de secondes pour les 324 mines.

    Partie principale :
    Code C# :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
     
            public Chemin Traiter( List<Mine> minesOrigine, double p, Action<Chemin> trace = null )
            {
                //Algo9a algo9a = new Algo9a();
                //Chemin reference = algo9a.Traiter( minesOrigine, p );
     
                // Copie pour ne pas modifier l'ordre des données entrantes
                List<Mine> mines = new List<Mine>( minesOrigine );
     
                Stopwatch sw = new Stopwatch();
                sw.Start();
     
                // Tri des mines par cout/production et cout
                mines.Sort( ( a, b ) =>
                {
                    double ca = a.Cout / a.Production;
                    double cb = b.Cout / b.Production;
                    int compare = ca.CompareTo( cb );
                    if ( compare == 0 )
                        return a.Cout.CompareTo( b.Cout );
                    else
                        return compare;
                } );
     
                // Récupération des résultats (ensemble de séquences de mines)
                List<List<Mine>> resultats = Traiter( p, mines );
     
                // Traduction des résultats en chemins
                List<Chemin> chemins = new List<Chemin>();
                resultats.ForEach( r => chemins.Add( new Chemin( p, r ) ) );
     
                // Tri des chemins par date de fin croissante
                chemins.Sort( ( a, b ) => a.DateFin.CompareTo( b.DateFin ) );
                // Le meilleur est le premier de la liste
                Chemin meilleur = chemins[0];
     
                sw.Stop();
     
                long elapse = sw.ElapsedMilliseconds;
     
                //double delta = meilleur.DateFin - reference.DateFin;
     
                return meilleur;
            }


    Fonction de traitement (appelée récursivement par la fonction d'insertion) :
    Code C# :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
     
            List<List<Mine>> Traiter( double p, List<Mine> mines )
            {
                // Les résultats sont des séquences de mines
                // Initialement (ou par défaut) le résultat contient une séquence vide
                List<List<Mine>> resultats = new List<List<Mine>>() { new List<Mine>() };
     
                // Création des (sous) résultats partant de la production d'origine
                // Chaque mine va être insérée partout où cela est optimal dans chaque séquence en cours de construction
                foreach ( Mine mine in mines )
                {
                    // Pour chaque mine, on constitue de nouvelles séquences partant des séquences d'origine
                    // et avec cette mine en plus
                    List<List<Mine>> nouveauxResultats = new List<List<Mine>>();
     
                    // Pour chaque séquence en cours
                    foreach ( List<Mine> resultat in resultats )
                        // Insérer la mine et ajouter les séquences résultantes aux nouvelles séquences construites
                        nouveauxResultats.AddRange( Inserer( p, mine, resultat ) );
     
                    resultats = nouveauxResultats;
                }
     
                return resultats;
            }


    Fonction d'insertion :
    Code C# :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
     
            IEnumerable<List<Mine>> Inserer( double p, Mine mine, List<Mine> chemin )
            {
                Mine courante = null, precedente = null;
     
                // Insertion des mines avant chacune de celles de la séquence
                for ( int i = 0 ; i < chemin.Count ; i++ )
                {
                    courante = chemin[i];
     
                    // C'est après la précédente (s'il y en a une) et que l'insertion après celle ci est optimale
                    // et avant la mine courante si l'insertion avant celle ci est optimale
                    // Note :
                    //      Les limites sont testées sur "un intervalle semi ouvert" :
                    //          t(precedente, mine) <= t(mine, precedente) et t(mine, courante) < t(courante, mine)
                    //      Sinon, on génère une combinatoire importante si plusieurs mines sont identiques
                    if ( (precedente == null || Optim( precedente, mine, p - precedente.Production ) <= 0) && Optim( mine, courante, p ) < 0 )
                    {
                        // Récupération de toutes les mines arpès la mine courante (et y compris celle ci)
                        List<Mine> mines = new List<Mine>( chemin.Skip( i ) );
     
                        // Pour chaque sous chemins optimaux constitué de ces mines avec la production après la mine insérée
                        foreach ( List<Mine> sousChemin in Traiter( p + mine.Production, mines ) )
                        {
                            // Si la concaténation du chemin avant et du sous chemin est optimale
                            if ( Optim( mine, sousChemin[0], p ) <= 0 )
                            {
                                // Constitution du chemin complet constitué...
                                // ...de toutes les mines avant...
                                List<Mine> resultat = new List<Mine>( chemin.Take( i ) );
                                // ...de la mine en cours...
                                resultat.Add( mine );
                                // ...et du sous chemin
                                resultat.AddRange( sousChemin );
     
                                yield return resultat;
                            }
                        }
                    }
     
                    p += courante.Production;
                    precedente = courante;
                }
     
                // enfin ajout de la mine en dernier, si cela est optimal
                if ( precedente == null || Optim( precedente, mine, p - precedente.Production ) <= 0 )
                {
                    List<Mine> resultat = new List<Mine>( chemin );
                    resultat.Add( mine );
     
                    yield return resultat;
                }
            }


    Test de l'optimalité 2 à 2 :
    Code C# :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
            // Partant d'une production p, le test d'optimalité retourne :
            //      -1 : si t(m1, m2) < t(m2, m1)
            //       0 : si t(m1, m2) = t(m2, m1)
            //       1 : si t(m1, m2) > t(m2, m1)
            int Optim( Mine m1, Mine m2, double p )
            {
                double tm1m2 = (m1.Cout / p) + (m2.Cout / (p + m1.Production));
                double tm2m1 = (m2.Cout / p) + (m1.Cout / (p + m2.Production));
     
                return tm1m2.CompareTo( tm2m1 );
            }

  19. #199
    Membre confirmé
    Citation Envoyé par Baruch Voir le message
    J'ai réfléchi à ton algo, et je n'arrive toujours pas à comprendre :

    Supposons qu'on veut trier 3 mines A B C.

    On place A : on a [A]

    On place B dans [A] : on a soit [AB], soit [BA].
    Supposons que [AB] soit le bon ordre.

    On place C dans [AB] : les chemins potentiels sont :
    CAB ou CBA,
    si [AC] est optimale 2 à 2 pour p0, ACB
    si [BC] est optimale 2 à 2 pour p0+p(A), ABC

    Et la liste [BCA] ? Pourquoi ne pourrait-elle pas être optimale 2 à 2 ?
    ... tu as raison !

  20. #200
    Membre confirmé
    @Baruch : une question concernant l'algo par permutations dont tu as donné le code.

    Si le vecteur d'origine est [ABC] et que :
    - [BA] n'est pas optimal pour p (au sens t[BA] > t[AB])
    - [CB] n'est pas optimal pour p + pA (au sens t[CB] > t[BC])

    ... alors aucune chance de trouver BCA ?

    Donc l'argument que tu as donné pour le dernier algo que j'ai présenté vaut aussi ici ?