IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
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
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    décembre 2007
    Messages
    162
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : décembre 2007
    Messages : 162
    Points : 4
    Points
    4
    Par défaut
    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é
    Profil pro
    Inscrit en
    avril 2008
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 54
    Localisation : France

    Informations forums :
    Inscription : avril 2008
    Messages : 415
    Points : 486
    Points
    486
    Par défaut
    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
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    décembre 2007
    Messages
    162
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : décembre 2007
    Messages : 162
    Points : 4
    Points
    4
    Par défaut
    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é
    Profil pro
    Inscrit en
    avril 2008
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 54
    Localisation : France

    Informations forums :
    Inscription : avril 2008
    Messages : 415
    Points : 486
    Points
    486
    Par défaut
    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é
    Profil pro
    Inscrit en
    avril 2008
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 54
    Localisation : France

    Informations forums :
    Inscription : avril 2008
    Messages : 415
    Points : 486
    Points
    486
    Par défaut
    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é
    Profil pro
    Inscrit en
    avril 2008
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 54
    Localisation : France

    Informations forums :
    Inscription : avril 2008
    Messages : 415
    Points : 486
    Points
    486
    Par défaut
    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é
    Profil pro
    Inscrit en
    avril 2008
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 54
    Localisation : France

    Informations forums :
    Inscription : avril 2008
    Messages : 415
    Points : 486
    Points
    486
    Par défaut
    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é
    Profil pro
    Inscrit en
    avril 2008
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 54
    Localisation : France

    Informations forums :
    Inscription : avril 2008
    Messages : 415
    Points : 486
    Points
    486
    Par défaut
    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
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    décembre 2007
    Messages
    162
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : décembre 2007
    Messages : 162
    Points : 4
    Points
    4
    Par défaut
    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
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    décembre 2007
    Messages
    162
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : décembre 2007
    Messages : 162
    Points : 4
    Points
    4
    Par défaut
    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

    Homme Profil pro
    Comme retraité, des masses
    Inscrit en
    avril 2007
    Messages
    2 978
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 80
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : avril 2007
    Messages : 2 978
    Points : 5 151
    Points
    5 151
    Par défaut
    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
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    décembre 2007
    Messages
    162
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : décembre 2007
    Messages : 162
    Points : 4
    Points
    4
    Par défaut
    Héhé ^^

    Je crois que tout algorithme fondé sur l'insertion de mines, même si on insère les mines dans un ordre donné, n'est pas exact.
    Je n'arrive pas à comprendre pourquoi il le serait...
    Voir le cas BCA dans mon précédent post. Je pense qu'on peut trouver des mines A B C ordonnées par rendement décroissant, avec [AB] meilleur que [BA], telles que la configuration BCA est idéale. Dans ce cas, un processus par insertion n'est pas correct, même si l'on recalcule l'ordre des mines suivantes, comme le fait Alikendarfen.

    @Alikendarfen

    Est-on bien d'accord que :

    si on insère les mines A B C successivement,
    et que [AB] est meilleur que [BA] à p0,
    ton algorithme n'étudie pas la configuration [BCA] ?



    De mon côté, j'ai essayé un autre algorithme :

    On a une liste L de mines triée par rendements décroissants.
    Pour chaque couple de mines adjacentes, on calcule le gain qu'on aurait à permuter ce couple.
    On permute le couple au gain maximal.
    On réitère le processus jusqu'à ce que le gain maximal soit négatif ou nul.

    Cet algorithme fournit en fait une solution idéale 2 à 2.
    Je n'ai pas prouvé que cet algorithme fournit la solution idéale, mais j'ai l'intuition que parmi toutes les solutions idéales 2 à 2, la solution idéale est celle qui est la plus "proche" de la liste triée par rendements décroissants.
    C'est un algorithme rapide, puisque je trie 300 mines en ~3,5 s.

    Reste à étudier s'il est correct ou pas... Il faudrait le tester mais en Caml c'est pas très pratique ^^

    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
    type mine = { cout : float ; prod : float } ;; (* on crée le type mine *)
    
    let tri_rent v = (* la fonction qui trie le vecteur par rentabilité décroissante avec un tri rapide *)
                    let rent m = m.prod /. m.cout in
    		let rec qsort = function
    			| [] -> []
    			| x :: list -> let rec coupelist = function
    					| [] -> [], []
    					| y :: m -> let a , b = coupelist m in
    							if rent y > rent x then y :: a , b else (
    								if rent y = rent x & y.prod < x.prod then y :: a , b else a , y :: b
    	 						) ;
    					in let debut , fin = coupelist list
    			in (qsort debut) @ [x] @ (qsort fin);
    		in vect_of_list (qsort (list_of_vect v)) ;;
    
    let tri_permut vect p0 =
    	let rec arrange v =
    		let gain = ref 0. in (* gain courant lors du parcours du vecteur *)
    		let p = ref p0 in (* production courante *)
    		let indice = ref 0 in (* indice du couple à permuter *)
    		for k = 0 to vect_length v - 2 do (* on parcours le vecteur pour trouver le gain maximal *)
    			let gain' = v.(k).cout /. !p +. v.(k+1).cout /. (!p +. v.(k).prod) -. v.(k+1).cout /. !p -. v.(k).cout /. (!p +. v.(k+1).prod) in
    			if gain' > !gain then (gain := gain' ; indice := k) ;
    		done ;
    		if !gain > 0. then ( (* si on a rencontré au moins un couple qu'il faut permuter, on le permute, et on relance la fonction *)
    			let m = v.(!indice) in
    			v.(!indice) <- v.(!indice + 1) ;
    			v.(!indice + 1) <- m ;
    			arrange v  ) else v ; (* sinon on retourne le vecteur *)
    	in arrange (tri_rent vect) ;;

    Quelqu'un pourrait tester cet algorithme sur la liste des 324 mines données plus haut ? Ou alors transformer cette liste sous la forme :

    [| { cout = [coût de la mine] ; prod = [production de la mine] } ; ... |]

  13. #193
    Membre confirmé
    Profil pro
    Inscrit en
    avril 2008
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 54
    Localisation : France

    Informations forums :
    Inscription : avril 2008
    Messages : 415
    Points : 486
    Points
    486
    Par défaut
    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é
    Profil pro
    Inscrit en
    avril 2008
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 54
    Localisation : France

    Informations forums :
    Inscription : avril 2008
    Messages : 415
    Points : 486
    Points
    486
    Par défaut
    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é
    Profil pro
    Inscrit en
    avril 2008
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 54
    Localisation : France

    Informations forums :
    Inscription : avril 2008
    Messages : 415
    Points : 486
    Points
    486
    Par défaut
    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é
    Profil pro
    Inscrit en
    avril 2008
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 54
    Localisation : France

    Informations forums :
    Inscription : avril 2008
    Messages : 415
    Points : 486
    Points
    486
    Par défaut
    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é
    Profil pro
    Inscrit en
    avril 2008
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 54
    Localisation : France

    Informations forums :
    Inscription : avril 2008
    Messages : 415
    Points : 486
    Points
    486
    Par défaut
    Citation Envoyé par Baruch Voir le message
    Quelqu'un pourrait tester cet algorithme sur la liste des 324 mines données plus haut ? Ou alors transformer cette liste sous la forme :

    [| { cout = [coût de la mine] ; prod = [production de la mine] } ; ... |]
    Yep, je vais voir... si j'ai le temps (donc dès que possible)

  18. #198
    Membre confirmé
    Profil pro
    Inscrit en
    avril 2008
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 54
    Localisation : France

    Informations forums :
    Inscription : avril 2008
    Messages : 415
    Points : 486
    Points
    486
    Par défaut
    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é
    Profil pro
    Inscrit en
    avril 2008
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 54
    Localisation : France

    Informations forums :
    Inscription : avril 2008
    Messages : 415
    Points : 486
    Points
    486
    Par défaut
    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é
    Profil pro
    Inscrit en
    avril 2008
    Messages
    415
    Détails du profil
    Informations personnelles :
    Âge : 54
    Localisation : France

    Informations forums :
    Inscription : avril 2008
    Messages : 415
    Points : 486
    Points
    486
    Par défaut
    @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 ?

Discussions similaires

  1. Ordre de construction des membres de classe
    Par camboui dans le forum C++
    Réponses: 7
    Dernier message: 14/01/2010, 17h22
  2. [JBuilder 7] Construction d'executable natif
    Par renaudfaucon dans le forum JBuilder
    Réponses: 3
    Dernier message: 24/11/2006, 22h28
  3. ORDER BY dans un ordre inhabituel
    Par Riam dans le forum SQL Procédural
    Réponses: 2
    Dernier message: 21/03/2003, 13h29
  4. Ordre de parcours de l'arbre...
    Par Sylvain James dans le forum XML/XSL et SOAP
    Réponses: 3
    Dernier message: 01/12/2002, 18h41
  5. [] Tri d'un tableau par ordre alphabétique
    Par cafeine dans le forum VB 6 et antérieur
    Réponses: 3
    Dernier message: 17/09/2002, 08h43

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo