Discussion :

[Baruch]

L'avantage de garder le potentiel sous cette forme :

cM (1 + p/pM)

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

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

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

[Alikendarfen]

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

Oui. Voici le contexte et les règles utilisées pour cet algo de type NDO.

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

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

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

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

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

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

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



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

[Baruch]

Je ne comprends pas :

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

Bj appartient à B équivaut à :

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

C'est ça ?

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

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

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

?

[Alikendarfen]

Je ne comprends pas :

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

Bj appartient à B équivaut à :

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

C'est ça ?

oui, c'est ça

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

il peut y avoir plusieurs Bj cependant (y compris des mines de c et p différents)... je n'utilise pas d'autres règles pour les discriminer pour le moment.

[Baruch]

il peut y avoir plusieurs Bj cependant (y compris des mines de c et p différents)... je n'utilise pas d'autres règles pour les discriminer pour le moment.

Euh non c'est pas possible :

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

Ca implique que :

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

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


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

[Alikendarfen]

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

Non ! C'est moi !! mea culpa

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

[Baruch]

Ben donc t'es certain que c'est bien la propriété qu'utilise ton algo ?

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

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

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

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

alors B est la mine à placer.

[Alikendarfen]

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

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

Mais par contre il ne marche pas comme tu l'indiques :

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

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

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

alors B est la mine à placer.

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


Edit :
Voici le code de la fonction (le reste de l'algo a été publié avant) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
        public static List<Mine> MeilleuresMinesAp( List<Mine> mines, double p )
        {
            List<Mine> resultat = new List<Mine>();
 
            foreach ( Mine m1 in mines )
            {
                bool toujoursMeilleure = true;
                foreach ( Mine m2 in mines )
                {
                    double pPrime = p + Math.Max( m1.Production, m2.Production );
 
                    if ( Optimales2a2( m1, m2, p ) == false || Optimales2a2( m1, m2, pPrime ) == false )
                    {
                        toujoursMeilleure = false;
                        break;
                    }
                }
 
                if ( toujoursMeilleure )
                    resultat.Add( m1 );
            }
 
            return resultat;
        }

[Alikendarfen]

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

Pourquoi ?

Parce que sur cet exemple :

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

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

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

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

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

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

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

Qu'en pensez vous ?

[Sharcoux]

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

[Triton972]

Bonsoir,

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

[Baruch]

Bonsoir !

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

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

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

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

Euh c'est pas croissant plutôt ?

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

[Triton972]

Bonjour Baruch,

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