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
Désolé de redemander, mais tu pourrais expliquer exactement ce que fais ton algo NDO stp ?
Je pense qu'il faut partir de la liste triée par rendements décroissantsDonc... il faut sans doute revenir à une solution de type permutations partant de la liste complète des mines...
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.Envoyé par Baruch
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...
Oui oui bon dsl j'ai juste du mal à comprendre ton code.
Bon j'étudie de près ton code avant de reposter, promis ^^
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.
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
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 ?
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25public 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
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
41IEnumerable<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
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
58IEnumerable<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
2
3
4
5
6
7
8
9
10Chemin 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
2
3
4
5
6
7
8bool 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
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.
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 :
Au niveau du sens de ton algo, je ne comprends pas pourquoi tu ne fais pas plutôt :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
[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)
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 ?
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)
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
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
32type 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] } ; ... |]
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)
Oui, c'est ça
C'est bien ce que fait l'algo ! ... et puis creuser, c'est normal pour des mines
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.
Je réfléchissais aussi à quelque chose comme ça... mais je n'ai pas abouti jusque là.
Exact... il faut que je réfléchisse à ça...
Et dire que la solution était là, comme le nez au milieu du visage : proéminente !
Yep, je vais voir... si j'ai le temps (donc dès que possible)
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
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
44public 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25List<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
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
53IEnumerable<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
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 ); }
...tu as raison !
@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 ?
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager