Ordre de construction de mines

Version imprimable

Voir 40 message(s) de cette discussion en une page

29/09/2011, 17h48
Baruch

J'ai trouvé la démonstration ! La tienne était fausse, mais ça m'a bien aidé pour trouver la solution ^^

Voici tes omissions :

Citation:

(b) t(MC) > t(CM) à p', car sinon C serait dans D'

A condition que C soit déjà dans D.

Citation:

Donc on peut trier ABC par rendement croissant

Seulement si p*(A,C) < p également !

Citation:

Supposons qu'on ait D'={A,B} , A + rentable que B, et C une mine hors de D'. On a p0 > p*(A,B).

Les chemins possibles sont :

ABC
ACB
BCA

Pourquoi BCA peut-il être éliminé ?

Supposons [BCA] idéale.

1) Si C n'est pas dans D

Alors D = {A,B}.
donc comme je l'ai montré précédemment, le chemin idéal commence par A, puisque A est plus rentable que B, et que A est dans D'.
D'où la contradiction.

2) Si C est dans D

A respecte l'optimalité avec M, mais pas C, on a donc :

cM (1+p'/pM) < cA (1+p'/pB)
et
cM (1+p'/pM) > cC (1+p'/pC)

Donc on a :

cC (1+p'/pC) < cA (1+p'/pB)

ce qui revient à dire :

[CA] optimal à p'

Or [BCA] idéal à p, donc [CA] optimal à p+pB, et cB (1+p/pB) < cC (1+p/pC)

Par hypothèse, on a p > p*(A,B), donc cA (1+p/pA) < cB (1+p/pB), car A est plus rentable que B

On a donc cA (1+p/pA) < cC (1+p/pC)

Donc [AC] optimal à p

On a p' < p < p+pB, avec :

à p', [CA] est optimal
à p, [AC] est optimal
à p+pB, [CA] est optimal

Ce qui est absurde.

Pour revenir sur ta démo :

Citation:

Donc on peut trier ABC par rendement croissant

J'ai dit qu'il fallait que p*(A,C) < p, mais en réalité on n'a pas cette inégalité.

On a p*(A,C) > p + pB, si on oublie l'hypothèse sur le P*max, qui rend tout absurde.
29/09/2011, 17h51
Alikendarfen

Un complément à cette démo, le calcul que je n'ai pas détaillé concernant :

Si t(MB) < t(BM) et t(MC) > t(CM) à p'=p-pM
Alors t(BC) > t(CB) à p'

t(MB) < t(BM) et t(MC) > t(CM) (1)
<=>
cM/p' + cB/p < cB/p' + cM/(p'+pB)
et
cM/p' + cC/p > cC/p' + cM/(p'+pC)

(1)
<=>
cM(1/p' - 1/(p'+pB)) < cB(1/p' - 1/p)
et
cM(1/p' - 1/(p'+pC)) > cC(1/p' - 1/p)

On a (1/p' - 1/(p'+pC) > 0
(1)
<=>
cM < cB(1/p' - 1/p)/(1/p' - 1/(p'+pB))
et
cM > cC(1/p' - 1/p)/(1/p' - 1/(p'+pC))

Donc (1) =>
cC(1/p' - 1/p)/(1/p' - 1/(p'+pC)) < cB(1/p' - 1/p)/(1/p' - 1/(p'+pB))

On a (1/p' - 1/p) > 0
Donc (1) =>
cC/(1/p' - 1/(p'+pC)) < cB/(1/p' - 1/(p'+pB))

En multipliant par les deux dénominateurs (qui sont > 0)
(1) =>
cC(1/p' - 1/(p'+pB)) < cB(1/p' - 1/(p'+pC))

(1) =>
cC/p' + cB/(p' + pC) < cB/p' + cC/(p'+pB)

On reconnait les expressions de t(CB) et t(BC) à p'
(1) =>
t(CB) < t(BC)
29/09/2011, 17h52
Baruch

Ah je vois que tu as édité le p*(A,C).

Effectivement, ta démo marche, tout dépend des hypothèses qu'on utilise. Le système d'hypothèses étant absurde, on peut trouver la contradiction un peu là où on veut.

Finalement je pense que ton approche est plus intéressante, puisqu'elle donne une piste pour la démo générale :

Montrer que les p* sont tous inférieurs à p.

Edit : Pour la démo que tu viens de faire :

Oui effectivement c'est ça, dans ma démo j'ai considéré ça comme acquis ^^.

[AB] optimal à p équivaut à

cA (1+p/pA) < cB (1+p/pB)
29/09/2011, 17h53
Alikendarfen

Citation:

Envoyé par Baruch

J'ai dit qu'il fallait que p*(A,C) < p, mais en réalité on n'a pas cette inégalité.

Si c'est dans ma démo... je l'ai mis en 'edit' avant que tu postes...

Je pense donc que la démo que j'ai proposée est correcte.
29/09/2011, 17h54
Alikendarfen

Ben ok... nos posts se croisent... ;)
29/09/2011, 17h57
Alikendarfen

Citation:

Envoyé par Baruch

A condition que C soit déjà dans D.

Juste pour info : on a vu avant que si C n'est pas dans D, alors C est dominé et qu'une mine dominée ne rentre pas en ligne de compte pour ce calcul.
29/09/2011, 18h16
Alikendarfen

Histoire de conclure (temporairement !), on est donc bien d'accord avec tout ça qu'on peut appliquer l'algo suivant et qu'il est exact :

Partant d'un chemin C de production actuelle p.

On détermine les mines dominantes D restant à placer de C.

On isole le sous ensemble D' des mines de D qui sont également optimales 2à2 avec la dernière mine de C.

Si p >= p*max(D') alors on peut placer la plus rentable de D' à la suite de DC (et en cas d'égalité celle qui produit le plus)

Sinon, C peut être complété par n'importe quelle mine de D' (et on retiendra plus tard la meilleure hypothèse).
29/09/2011, 18h21
Baruch

Bah c'est pas encore démontré...

On a montré le cas ABC, mais reste le cas général.

Mais sinon oui, c'est ça qu'on veut pouvoir faire.
29/09/2011, 18h35
Alikendarfen

Citation:

Envoyé par Baruch

Bah c'est pas encore démontré...

On a montré le cas ABC, mais reste le cas général.

Mais sinon oui, c'est ça qu'on veut pouvoir faire.

Ben en fait, prenons D'={A, Bi}, pour avoir plus de deux mines dans D' avec par notation A la plus rentable.

On a démontré qu'il ne peut y avoir de chemin de type Chemin+[Bi;Cj;A] (qui est le seul cas pour 3 mines où A perd sa première place).

Si on avait Chemin+[Bu;Bv;...Bw;Cj;A], la démo serait la même car on pourrait formuler les mêmes hypothèses (contradictoires) avec Bu, Cj et A.

Il nous reste donc Chemin+[Bu;...;Cj;Bv;...;A] ?
Mais après Cj (car déjà après le Chemin), A est forcément devant Bv. Donc on revient au cas d'avant.

Autres possibilités ?
29/09/2011, 18h45
Baruch

... et [B,C1,...,Cn,A] ? ^^
29/09/2011, 18h49
Alikendarfen

Citation:

Envoyé par Baruch

... et [B,C1,...,Cn,A] ? ^^

Rapido (car je dois partir) : on réapplique les hypothèses (contradictoires) sur B Cn et A.
30/09/2011, 00h05
Sharcoux

Je suis nouveau sur le sujet. Arrêtez-moi si je me trompe mais, comme vous l'avez remarqué,

T[A,B]<T[B,A] équivaut à cA (1+p/pA) < cB (1+p/pB)
où p est ma production totale actuelle.

Ca veut dire que calculer le "potentiel" ci . (1 + p/pi) de chaque mine restante permet de déterminer la prochaine mine à construire (celle de potentiel minimum). L'algo est en
n . (n -1) / 2
C'est polynomial et donc certainement pas NP-difficile

Voilà. Arrêtez-moi si j'ai dit de la merde
30/09/2011, 00h17
Baruch

Et pourquoi la meilleure prochaine mine à construire serait celle de "potentiel" minimum ? ^^

(eh eh Ali t'as vu c'est moi qui ramène des gens :aie:)
30/09/2011, 00h27
Sharcoux

Je pense que tu n'as pas compris toute la portée de cette équivalence :

T[A,B]<T[B,A] équivaut à cA (1+p/pA) < cB (1+p/pB)

si parmi une liste de mine [M1 ... Mn] la mine Mi est celle de potentiel minimum, ça veut dire que pour tout j,

ci (1+p/pi) < cj (1+p/pj)

càd

T[Mi,Mj]<T[Mj,Mi]

Ce qui veut dire littéralement qu'il vaut mieux construire Mi avant Mj quelque soit j
30/09/2011, 00h43
Baruch

Attention, il ne faut pas oublier la production :

Citation:

ci (1+p/pi) < cj (1+p/pj)

càd

T[Mi,Mj]<T[Mj,Mi]

Ce qui veut dire littéralement qu'il vaut mieux construire Mi avant Mj quelque soit j

Non, ça veut dire que si Mi et Mj sont côte à côte, et que la production est à p avant ce couple, alors il est préférable de placer Mi avant Mj.
30/09/2011, 00h58
Baruch

Bon j'ai codé la fonction... et ça marche xD

Bon ben merci, tu m'as bien mis la honte ! :aie:

Edit : Et effectivement ya pas plus bête...

Edit2 :

N'empêche pour ce qui est du multi-ressource, le potentiel n'existe pas, donc c'est autrement difficile.
30/09/2011, 04h16
Sharcoux

Malgré tout ta remarque est correcte : ma justification n'est pas bonne. Du moins elle n'est valable que lorsque la courbe d'évolution de p ne croise aucun des p*(Mi,Mj). En effet, sur ces intervalles, l'ordre des potentiels ci.(1+p/pi) reste identique.

En revanche, ce n'est plus vrai si la courbe d'évolution de p croise l'un des p*(Mi,Mj). En effet, dans ce cas, on a T(Mi,Mj)<T(Mj,Mi) avant l'intersection, et T(Mj,Mi)<T(Mi,Mj) après.
Mais en fait, si on regarde plus en détail ce qu'il se passe dans ce cas, on va voir que l'algo fonctionne qd même, et ceci pour une raison très précise : c'est que traverser un p* ne fait que permuter deux potentiels consécutifs. Ainsi, les choix déjà fait ne sont jamais impactés par ce changement.

En d'autres termes, le potentiel d'une mine déjà choisie n'a aucune chance de s'améliorer par la suite. Choisir une mine plus tard qu'au moment où son potentiel est le plus faible n'a aucune chance de rendre ce choix "encore meilleur". Par contre, ne pas la choisir a de grandes chances de générer des pertes.

Je suis probablement pas très clair. Je suis pas doué pour formaliser

Oula... il semble que les choses aient bougé cette nuit !! :)

Je reformule pour voir si j'ai bien compris :

S'il existe à p une mine Mi telle que pour j t(MiMj) <= t(MjMi) alors cette mine Mi doit être placée en premier.

Mettons que cette mine existe toujours et que f({Mi}, p) soit la fonction qui trouve cette mine.

Alors l'algo serait :
Code:

1 2 3 4 5 6 7 8 9 10 resultat = un chemin vide production = p initiale tant que {Mi} non vide M = f( {Mi}, production ) Retirer M de {Mi} Ajouter M à résultat Ajouter p(M) à production fin tant
C'est ça ?

30/09/2011, 14h08
Baruch

Ouép c'est tout à fait ça

Citation:

Envoyé par Baruch

Ouép c'est tout à fait ça

Ben alors si c'est ça (et sauf erreur de ma part, bien entendu), ça ne fonctionne pas... :?

D'un côté, c'est dommage... de l'autre côté ça me rassure ! :D

En fait, il y a plusieurs choses :

1- Il semble que cette mine existe toujours (mais ça n'est pas complètement évident)

2- Par contre, la meilleure mine n'est pas nécessairement unique (ex : à p = 20, M1(15;45), M2(5;6))... et donc le choix de l'une ou l'autre aurait une influence sur la suite

3- et puis un contre exemple pour 3 mines :
p=19
M0;32;23
M1;48;84
M2;55;57
Meilleur chemin 3,26029637199796 avec M1M2M0
et pour cet algo : 3,26357560568087 avec M0M1M2

A noter : l'algo 'se trompe' même si le point 2 n'est pas rencontré

Donc... fausse joie !

Je vous donne le code afin de vérifier que je n'ai pas commis d'erreur.
Pour info, je n'utilise pas le "potentiel", mais simplement l'optimalité 2 à 2 (donc le temps le plus court entre MaMb et MbMa), mais c'est équivalent.

Code:

1
2
3
4
5
6
7
8
9
10
 
            while ( mines.Count > 0 )
            {
                Mine mine = PlusCourt( mines, chemin.Production );
 
                mines.Remove( mine );
 
                // Pour info, la mise à jour de la prod totale du chemin est réalisée dans la fonction AjouterMine
                chemin.AjouterMine( mine );
            }

Code:

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
 
        Mine PlusCourt( List<Mine> mines, double p )
        {
            // On présume que plusieurs mines peuvent répondre au critère
            List<Mine> resultat = new List<Mine>();
 
            foreach ( Mine mine1 in mines )
            {
                bool ok = true;
                foreach ( Mine mine2 in mines )
                {
                    double t12 = mine1.Cout / p + mine2.Cout / (p + mine1.Production);
                    double t21 = mine2.Cout / p + mine1.Cout / (p + mine2.Production);
 
                    if ( t12 > t21 )
                    {
                        // Si t12 > t21, mine1 n'est pas la bonne mine
                        ok = false;
                        break;
                    }
                }
 
                // Si la valeur 'ok' n'est pas passée à 'false'
                if ( ok )
                {
                    // mine1 est avant toute autre à p
                    resultat.Add( mine1 );
                }
            }
 
            if ( resultat.Count > 1 )
            {
                // Il arrive qu'on ait des solutions multiples
                return resultat[0];
            }
            else if ( resultat.Count > 0 )
            {
                return resultat[0];
            }
 
            // Pas de cas rencontré
            return null;
        }

(note : dans cette implémentation rapide, je n'ai pas approfondi le cas où plusieurs mines satisfont la contrainte... mais pour ce test, pas grave)

Pour info, sur 100000 tirages aléatoires de 5 mines, l'algo se trompe env. 230 fois.

Voir 40 message(s) de cette discussion en une page