Discussion :

[Alikendarfen]

L'algo donc :
Il y a très peu de modif par rapport à l'algo par combinaisons précédent. Les différences :
- Pré calcul des dominantes et dominées
- Suppression de l'optim qui consistait à ajouter les mines par 2
- et c'est tout, car le calcul de la libération des dominées est fait dans Chemin.AjouterMine.

Partie principale :

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
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
 
        public Chemin Traiter( List<Mine> mines, double p )
        {
            //Algo0 algo0 = new Algo0();
            //Chemin cheminReference = algo0.Traiter( mines, p );
 
            // Création du chemin initial vide mais comprenant la liste des mines d'origine
            Chemin cheminInitial = new Chemin();
 
            cheminInitial.Production = p;
 
            // Calcul des dominances
            Dictionary<Mine, List<Mine>> dominantes = CalculerDominantes( mines );
            // Table des dominees
            Dictionary<Mine, int> dominees = CalculerDominees( dominantes );
 
            cheminInitial.Dominantes = dominantes;
            cheminInitial.Dominees = dominees;
 
            // Affectation initiale avec les mines n ayant aucune dominante
            cheminInitial.MinesNonTraitees.AddRange( CalculerNonDominees( mines, dominees ) );
 
            cheminInitial.Positions = new BitVector( mines.Count );
 
            // Initialisation pour la détection des chemins ayant les mêmes mines
            int i = 0;
            foreach ( Mine mine in mines )
            {
                mine.Position = cheminInitial.Positions.CreatePosition( i );
                i++;
            }
 
            Stopwatch sw = new Stopwatch();
            sw.Start();
 
            // Liste pour les résultats finaux
            List<Chemin> resultats = new List<Chemin>();
            // Liste pour les chemins calculés en intermédiaire
            List<Chemin> chemins = new List<Chemin>() { cheminInitial };
 
            // Tant qu'on a des chemins à traiter
            while ( chemins.Count > 0 )
            {
                // On va calculer des nouveaux chemins et les mettre dans cette liste
                List<Chemin> nouveauxChemins = new List<Chemin>();
 
                foreach ( Chemin chemin in chemins )
                {
                    // S'il ne reste qu'une mine à placer
                    if ( chemin.MinesNonTraitees.Count == 1 )
                    {
                        Chemin nouveauChemin = chemin.CreateCopy();
                        nouveauChemin.AjouterMine( chemin.MinesNonTraitees[0] );
 
                        // Ajout à la liste des nouveaux chemins
                        nouveauxChemins.Add( nouveauChemin );
                    }
                    else
                    {
                        // Sinon, pour chaque mine parmi les mines non traitées
                        foreach ( Mine nonTraitee in chemin.MinesNonTraitees )
                        {
                            // Création du nouveau chemin et ajout de sa nouvelle mine
                            Chemin nouveauChemin = chemin.CreateCopy();
 
                            nouveauChemin.AjouterMine( nonTraitee );
 
                            // Ajout à la liste des nouveaux chemins
                            nouveauxChemins.Add( nouveauChemin );
                        }
                    }
                }
 
                // Les anciens chemins peuvent être oubliés
                chemins.Clear();
 
                // Ici on va stocker en vis à vis de chaque clé une liste de chemins ayant les mêmes mines
                Dictionary<BitVector, List<Chemin>> combinaisons = new Dictionary<BitVector, List<Chemin>>();
 
                // On place chaque nouveau chemin en vis à vis de sa clé (appelée 'Positions')
                foreach ( Chemin nouveauChemin in nouveauxChemins )
                {
                    List<Chemin> combinaison;
                    if ( combinaisons.TryGetValue( nouveauChemin.Positions, out combinaison ) == false )
                    {
                        combinaison = new List<Chemin>();
                        combinaisons.Add( nouveauChemin.Positions, combinaison );
                    }
                    combinaison.Add( nouveauChemin );
                }
 
                // Puis on reprend chacune des listes de chemins ayant les mêmes mines
                foreach ( List<Chemin> combinaison in combinaisons.Values )
                {
                    // On calcule le meilleur d'entre eux
                    Chemin meilleurChemin = MeilleurChemin( combinaison );
 
                    // Si ce chemin contient toutes les mines : c'est un résultat.
                    // Sinon il faut poursuivre
                    if ( meilleurChemin.MinesNonTraitees.Count == 0 )
                        resultats.Add( meilleurChemin );
                    else
                        chemins.Add( meilleurChemin );
                }
            }
 
            sw.Stop();
            long elapsed = sw.ElapsedMilliseconds;
 
            //double delta = cheminReference.DateFin - resultats[0].DateFin;
 
            return resultats[0];
        }

Comparaison de chemins ayant les mêmes mines afin de ne garder que le meilleur d'entre eux :

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
 
        Chemin MeilleurChemin( List<Chemin> chemins )
        {
            double d = double.MaxValue;
            Chemin meilleur = null;
 
            foreach ( Chemin chemin in chemins )
            {
                if ( chemin.DateFin < d )
                {
                    meilleur = chemin;
                    d = chemin.DateFin;
                }
            }
 
            return meilleur;
        }

Calcul des dominantes (admet les égalitées, d'où c1 <= c2 et p1 >= p2) :

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
 
        Dictionary<Mine, List<Mine>> CalculerDominantes( List<Mine> mines )
        {
            Dictionary<Mine, List<Mine>> result = new Dictionary<Mine, List<Mine>>();
 
            foreach ( Tuple<Mine, Mine> paire in mines.Paires() )
            {
                if ( paire.Item1.Cout <= paire.Item2.Cout && paire.Item1.Production >= paire.Item2.Production )
                {
                    List<Mine> dominees;
                    if ( result.TryGetValue( paire.Item1, out dominees ) == false )
                    {
                        dominees = new List<Mine>();
                        result.Add( paire.Item1, dominees );
                    }
                    dominees.Add( paire.Item2 );
                }
                else if ( paire.Item2.Cout <= paire.Item1.Cout && paire.Item2.Production >= paire.Item1.Production )
                {
                    List<Mine> dominees;
                    if ( result.TryGetValue( paire.Item2, out dominees ) == false )
                    {
                        dominees = new List<Mine>();
                        result.Add( paire.Item2, dominees );
                    }
                    dominees.Add( paire.Item1 );
                }
            }
 
            return result;
        }

Constitution de la table des dominées :

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
 
        Dictionary<Mine, int> CalculerDominees( Dictionary<Mine, List<Mine>> dominantes )
        {
            Dictionary<Mine, int> result = new Dictionary<Mine, int>();
 
            foreach ( List<Mine> dominees in dominantes.Values )
            {
                foreach ( Mine dominee in dominees )
                {
                    int n;
                    if ( result.TryGetValue( dominee, out n ) == false )
                        result.Add( dominee, 1 );
                    else
                        result[dominee] = n + 1;
                }
            }
 
            return result;
        }

Identification des mines non dominées (qui constitue les mines possibles pour la toute première itération de l'algo)

Code :

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

1
2
3
4
5
6
7
8
9
 
        IEnumerable<Mine> CalculerNonDominees( List<Mine> mines, Dictionary<Mine, int> dominees )
        {
            foreach ( Mine mine in mines )
            {
                if ( dominees.ContainsKey( mine ) == false )
                    yield return mine;
            }
        }

[Alikendarfen]

pour comparer il faudrait mettre en commun le fichier de data, par exemple :
n TAB p0
c1 TAB p1
…
cn TAB pn

Oui. Le voici ci-dessous.

La forme que j'utilise est la suivante :
- 1ere ligne : p
- Lignes suivantes : <nom de la mine>;<cout>;<production>

Pour info : la fonction de lecture que j'utilise s'arrête quand une ligne est vide, ce qui permet de choisir facilement le nombre de mines qu'on souhaite traiter juste en ajoutant un retour chariot dans la liste.
> les mines du test dont j'ai indiqué les résultats incluent toutes les mines jusqu'à Z1

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
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
5
A0;5;3
B0;2;4
C0;6;4
D0;1;1
E0;7;10
F0;50;200
G0;3;6
H0;3;10
I0;4;8
J0;5;1
K0;5;15
L0;4;8
M0;5;1
N0;5;15
O0;2;15
P0;14;15
Q0;15;10
R0;22;16
S0;7;8
T0;6;5
U0;4;12
V0;27;22
W0;3;14
X0;6;9
Y0;1;1
Z0;22;4
A1;6;13
B1;6;18
C1;8;2
D1;10;7
E1;9;18
F1;3;3
G1;9;11
H1;115;125
I1;16;14
J1;18;66
K1;22;24
L1;2;2
M1;44;52
N1;12;11
O1;3;3
P1;8;49
Q1;9;49
R1;10;22
S1;9;22
T1;4;18
U1;45;44
V1;14;7
W1;16;9
X1;22;3
Y1;24;6
Z1;26;8
 
A2;4;6
B2;5;32
C2;15;4
D2;22;12
E2;4;21
F2;1;9
G2;36;45
H2;12;6
I2;96;3
J2;8;78
K2;45;9
L2;77;45
M2;32;6
N2;69;36
O2;21;2
P2;36;7
Q2;7;89
R2;15;4
S2;2;1
T2;99;65
U2;3;4
V2;66;11
W2;45;21
X2;9;3
Y2;66;88
Z2;3;76

Je n'ai pas donné le code pour la fonction de lecture. Mais si l'un d'entre vous utilise aussi C#, dites moi et je vous transmet tout le projet.

[JeitEmgie]

Ce n'est qu'une première impression mais un algorithme en 0(n) qui semble donner de bons résultats est simplement le tri des mines par ordre croissant de :

Code :

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

1
2
 
PI/2 - ATAN2( cost, production/cost )

en français : on balaie comme un radar à partir de 90° (de l'axe Y donc) dans le sens des aiguilles d'une montre et on construit dans l'ordre de rencontre des mines posées sur le graphique "axe des X : le coût, axe des Y : le rendement".

[Alikendarfen]

on balaie comme un radar à partir de 90° (de l'axe Y donc) dans le sens des aiguilles d'une montre et on construit dans l'ordre de rencontre des mines posées sur le graphique "axe des X : le coût, axe des Y : le rendement".

Ca marche pas mal mais voici un contre exemple (qu'on a déjà du donner) :

p = 1
M1 : c1=1, p1=1
M2 : c2=10, p2=200

atan2( c1, p1/c1 ) = 0.83
atan2( c2, p2/c2 ) = 1,11

et pourtant T(M1M2) < T(M2M1)

[JeitEmgie]

Ca marche pas mal mais voici un contre exemple (qu'on a déjà du donner) :

p = 1
M1 : c1=1, p1=1
M2 : c2=10, p2=200

atan2( c1, p1/c1 ) = 0.83
atan2( c2, p2/c2 ) = 1,11

et pourtant T(M1M2) < T(M2M1)

Certes, mais les heuristiques en 0(n) ne montrent des différences significatives que sur des ensembles importants : pour le moment celle-ci - appelons-la en "theta" - donne toujours le meilleur résultat des différentes O(n) sur des N grands (au minimum 500…) dont les composants sont aléatoires sur base d'une distribution normale (coût et productivité : le générateur aléatoire calcule la production à partir d'un paramètre sur la productivité maximum),
et n'oubliez pas que si elles permettent de donner des résultats acceptables sur des ensembles de plusieurs ordres de grandeur au-delà de ce que peuvent faire les algorithmes exploratoires, ce n'est déjà pas mal…
(on peut les utiliser sur 1 million de mines alors que l'on peine à dépasser la 100aine avec les combinatoires améliorées… et en moins de temps que le calcul combinatoire sur votre exemple de 52 : au passage l'algorithme en "theta" donne 2.1737096 sur ce jeu… qui n'est pas nécessairement un bon exemple : beaucoup de mines ont des productivités > 1 ce qui est donc aussi une topologie où les rendements n'ont pas une distribution normale - au sens statistique)

On en a déjà parlé avant aussi : l'aspect statistique de la topologie du jeu joue un rôle, mais il faut un N minimum pour que le mot "statistique" ait un sens… et 50 ce n'est pas assez…
Et un autre exemple qui provoque des dégénérescences de certaines des 0(n): si toutes les mines sont sur une droite…
(les (Ci,Pi) multiples entre eux…)

Le but poursuivi par la recherche sur les heuristiques en O(n) n'est pas de donner une solution définitive pour l'ensemble du problème de départ mais de trouver des solutions acceptables en O(n) qui pourront être mises en œuvre sur des sous-ensembles de la solution de départ, sous-ensembles qui auront été déterminés par une première phase de "ventilation" topologique qui devrait être conçue pour garantir
a. un comportement non dégénéré des 0(n) sur les sous-ensembles qu'elle produit,
b. que l'exploration combinatoire sur le sous-ensemble n'apporte pas de solution suffisamment meilleure pour justifier son surcoût sur une O(n) …
c. dans l'idéal aussi : déterminer les caractéristiques topologiques qui favorisent une heuristique sur une autre, sinon on pourrait aussi imaginer un système de vote entre les 3 O(n) qui pour le moment donnent les meilleurs résultats : dominance/productivité, dominance/coût et theta …
d. et évidemment si la ventilation topologique a produit des sous-ensembles dont le N est ≤ au N critique pour l'utilisation du calcul combinatoire optimisé : on utilise celui-ci sur ces derniers : P x 0(≈N^2) sera toujours moins cher que O( (somme des P[N])^2).

et finalement de ne garder les explorations combinatoires que dans les zones frontières entre ces sous-ensembles : là où les O(n) risquent de dégénérer : donc au lieu d'avoir le coût combinatoire sur des valeur de l'ordre de N^2, on ne l'aurait plus que sur X fois sur des n (très) petits par rapport au N de départ.

Ceci devant au final permettre de résoudre de manière acceptable des problèmes en milliers de mines… au lieu de se limiter à des problèmes de quelques dizaines, avec une probabilité élevé que si une solution meilleure existe elle ne soit meilleure que dans une proportion très faible.

[DonQuiche]

Je pense avoir trouvé un algorithme convergent opérant par permutations qui aboutirait à une solution optimale et dont la pire complexité serait o(n!) mais qui, en général, offrirait plutôt une complexité o(n^k), avec k = 3 ou 4, et avec possibilité d'interrompre le traitement en se satisfaisant d'une solution approximative.


Soit une liste ordonnée de façon quelconque de mines. A chaque étape nous notons dt(i) le temps entre la construction de la mine (i-1) et de la mine (i).
dt0 = c0 / p
dt1 = c1 / (p + p0)
dt2 = c2 / (p + p0 + p1)
dt3 = c3 / (p + p0 + p1 + p2)

Propriété remarquable (et déjà remarquée par Baruch) : la permutation des mines 1 et 2 n'affecte pas les dt suivants (dt3, dt4, ...). En généralisant, la permutation de deux éléments connexes (i) et (j) n'affecte pas les temps de production de ces mêmes éléments.



Maintenant, penchons-nous sur l'effet d'une permutation de (1) et (2). Soient dt1' et dt2' les temps obtenus après permutation.
dt1' = c2 / (p + p0)
dt2' = c1 / (p + p0 + p2)

La différence de temps résultant de la permutation de (1) et (2) est alors :
D(1,2) = (dt1' + dt2') - (dt1 + dt2)
D(1,2) = (c2 - c1) / (p + p0) + c1 / (p + p0 + p2) - c2 / (p + p0 + p1)

Généralisons en introduisant la notation Qn = p + p0 + ... + p(n-1). Pour tous éléments connexes (i) et (j), i étant la n-ème mine, une permutation aboutit à une différence notée :
Dn(i,j) = (cj - ci) / Qn + ci / (Qn + pj) - cj / (Qn + pi)



Cette formule nous donne un prédicat pour le choix des permutations : si Dn(i, j) est inférieur à 0, j doit être placé avant i. Sinon, j doit être placé après.

Il découle de cette formule plusieurs autres propriétés.
(1) : Dn(i, j) dépend de Qn, donc en particulier de n. En conséquence, si à un tour t l'élément (i) doit être placé avant (j), cela peut être différent à un autre tour. Cela élimine tous les algorithmes de tri.

(2) : la permutation de deux éléments connexes (i) et (j) n'affecte pas l'ordonnancement idéal des éléments successifs, puisque Qn est, pour n > j, invariant au cours de cette permutation. si 3, 4, 5, 6 forment un agencement optimal, permuter 1 et 2 n'y change rien.

(3) : Dn(i, j) possède un seul zéro par rapport à Qn. Cela veut dire que si (i) < (j) (ou inversement) au début de la liste, la comparaison peut s'inverser une fois pour devenir (i) > (j) quand Qn augmente (ou inversement) mais elle ne pourra pas s'inverser à nouveau si Qn continue à augmenter.

(4) : la comparaison reste transitive : si à la n-ème position i < j et j < k, alors i < k.




L'idée est simple : on fait plusieurs passes. Tant que la dernière passe a produit des changements, on en relance une. Pour une liste de 50 éléments, à chaque passe on part du 50ème élément, on le fait redescendre par permutations deux à deux. Puis on tente de faire descendre le 49ème, etc...

[Alikendarfen]

...
L'idée est simple : on fait plusieurs passes. Tant que la dernière passe a produit des changements, on en relance une. Pour une liste de 50 éléments, à chaque passe on part du 50ème élément, on le fait redescendre par permutations deux à deux. Puis on tente de faire descendre le 49ème, etc...

Le problème est que ce qu'on a appelé l'idéalité 2 à 2 (donc Dn(i, i+1) supérieur à 0) ne garantit pas l'idéalité du chemin dans son ensemble.

Un exemple (généré aléatoirement, d'où les nombres un peu tordus et arrondis) :

Code :

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

1
2
3
4
5
6
7
8
 
p	0.52667815355895	
	Cout                     Production
M0	0.016159108847453776     0.42800309109874213
M1	0.80035475026832648      0.70652579642204838
M2	0.6683271670100871       0.055542444836135227
M3	0.89281878661961234      0.85329203719892166
M4	0.79431426422405715      0.69812319693068192

Code :

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

1
2
3
 
Meilleur chemin : M0/M4/M3/M1/M2
	Temps final : 1.930280511417046

Code :

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

1
2
3
 
Chemin idéal 2 à 2 : M0/M1/M3/M4/M2
	Temps final : 1.9304059534807303

Si le chemin optimal alors Dn(i,i+1) > 0
Mais l'inverse n'est pas vrai

[Baruch]

Oula ya beaucoup de posts ^^

@ prgasp77

Quelle est la dominance partielle la plus fine qui ait été mise en œuvre pour l'instant ?

Il est toujours plus avantageux de permuter M1 et M2 de façon à mettre M1 avant M2, quelles que soient les autres mines, leur ordre, et p0
<=> M1 domine absolument M2
<=> c1<=c2 et p1>=p2
=> Dans la liste idéale, M1 est avant M2

Dans la ligne au-dessus on a bien seulement une implication.

La démo est ici.

A vrai dire, j'ai trouvé une dominance un tout petit peu mieux qui est :

c1 <= p1/p2 * (p0+p2)/(p0+p1) * c2
et
p1 >= p2

(en prenant en compte le fait que les valeurs de p sont bornées)

Pour le reste de tes questions, je confirme ce qu'a dit Alikendarfen.


Ah trop bien Alikendarfen, 52 mines c'est quand même beaucoup mieux que les 15 mines atteintes sans les dominances

Je n'ai pas le temps d'étudier le post de JeitEmgie ni de DonQuiche, je regarderai ça plus tard

[Alikendarfen]

Certes, mais les heuristiques en 0(n) ne montrent des différences significatives que ...

Je suis d'accord avec l'approche, d'autant que cette démarche pourrait par exemple permettre de donner une population de départ pour une amélioration par AG (par exemple).

J'avais donné les résultats de l'algo par insertion (en n²) testé sur des tirages aléatoires (simple random) pour 5 mines (pour info la-dessus voir le post #63 page 4) :
- 40000 tirages
- 154 chemins trouvés non optimaux (soit 4 pour 1000)
- Et parmi ces 154, 13 cas sont malgré tout idéaux 2 à 2 (donc on sait de façon sûre que 141 cas sont améliorables)

... donc effectivement, une approche dégradée peu s'avérer intéressante.

Mais la vraie question de fond est "doit on arrêter de se prendre la tête avec un problème insoluble ?" (insoluble au sens n'ayant aucune solution qu'on puisse affirmer optimale en un temps de calcul raisonnable).

[Alikendarfen]

...
On en a déjà parlé avant aussi : l'aspect statistique de la topologie du jeu joue un rôle
...

Oui et là, on a peut-être deux principales catégories de problème :

- Un cas 'réel' : où on peut imaginer que le coût et proportionnel de la production

- Un cas avec distribution normale


... quant aux topologies, topologies globales, locales ou partielles : encore faut-il les identifier

[Alikendarfen]

Dans l'esprit de ce qu'indiquait JeitEmgie (efficacité d'algos en o(n)), voici un petit benchmark.

Les algos testés :

A- Algo naïf :
Test exhaustif des arrangements.
Algo exact : cet algo donne une des solutions ayant le meilleur temps.
Complexité : n!

B- Algo par combinaisons avec dominances :
A chaque étape réduction de la recherche en comparant les chemins ayant exactement les mêmes mines et en gardant le meilleur d'entre eux.
Utilisation des dominances, en libérant chaque mine dominée lorsque toutes ses dominantes sont placées.
Algo exact : cet algo donne une des solutions ayant le meilleur temps.
Complexité : non calculée du fait des dominances (sans dominance en n * 2^n)

C- Algo par insertion :
Tri des mines par c/p croissant et en cas d'égalité c croissant.
Puis intégration progressive de chaque mine M dans le chemin en construction en insérant M à l'endroit le plus efficace parmi les mines déjà placées du chemin.
Algo inexact.
Complexité : n² (+ nlog(n) pour le tri)

D- Algo par simple tri :
Tri des mines par c/p croissant et en cas d'égalité c croissant.
Puis constitution d'un chemin avec ces mines dans l'ordre.
Algo inexact.
Complexité : n (+ nlog(n) pour le tri)

Trois séries de tests S1, S2 et S3:

Chaque test comporte 10000 tirages aléatoires de p (0 < p < 1) et de N mines (0 < ci < 1 ; 0 < pi < 1).

Pour chaque test et chaque algo non exact, je donne :
- Le nombre d'erreurs (sur 10000)

- L'écart moyen total qui est :
somme des différences de temps pour les cas en erreur
divisé par
somme des temps de l'algo exact

- L'écart moyen en cas d'erreur qui est :
somme des différences de temps pour les cas en erreur
divisé par
somme des temps de l'algo exact pour les cas en erreur

- S1. N = 5, pour les algos A, B, C, D

A et B donnent les mêmes résultats (simple vérif).

C :
Nombre d'erreurs : 36
Ecart moyen total : 6 pour cent mille (5,94614E-05)
Ecart moyen en cas d'erreur : 1% (0,00991153)

D :
Nombre d'erreurs : 3079
Ecart moyen total : 10% (0,10108981)
Ecart moyen en cas d'erreur : 30% (0,297929859)

- S2. N = 10, pour les algos B, C, D

C :
Nombre d'erreurs : 74
Ecart moyen total : 3 pour cent mille (2,74596E-05)
Ecart moyen en cas d'erreur : 1,2 pour mille (0,001228921)

D :
Nombre d'erreurs : 5811
Ecart moyen total : 3% (0,030270476)
Ecart moyen en cas d'erreur : 7% (0,071396913)

- S3. N = 20, pour les algos B, C, D

C :
Nombre d'erreurs : 123
Ecart moyen total : 2 pour cent mille (2,11068E-05)
Ecart moyen en cas d'erreur : 1,2 pour mille (0,001151772)

D :
Nombre d'erreurs : 8570
Ecart moyen total : 4% (0,035706574)
Ecart moyen en cas d'erreur : 4% (0,040649924)


Conclusions ?

Pour les algos inexacts, on remarque que :
- Plus le nombre de mines augmente, plus le nombre d'erreurs est grand
- Mais plus le nombre de mines augmente, plus la valeur de l'erreur est faible en moyenne


... reste à identifier les raisons pour lesquelles les algo de faible complexité échouent

[Alikendarfen]

Dans la série des algos non optimaux mais performant, en voici un en o(n3) !

D'où ça vient :
J'ai fait un comparatif des solutions mauvaises trouvées par l'algo par insertion avec chaque solution optimale (qq cas sur 10000 tirages).

Et j'ai remarqué que dans ces exemples (mais on verra par la suite que ça n'est pas toujours vrai), la première mine de l'algo par insertion était toujours la bonne...

D'où l'idée de créer un algo par insertion avec remise (en o(n3)).
Le principe :
- Appliquer l'algo par insertion
- Garder la première mine M1
- Appliquer l'algo par insertion sans M1
- Garder la première mine M2 à la suite de M1
- ... et ainsi de suite

Les résultats en termes de bench (mêmes conditions que précédemment) :

- Sur S1 (N = 5) :

Nombre d'erreurs : 3
Ecart moyen total : 2,98172E-07
Ecart moyen en cas d'erreur : 0,000765

- Sur S2 (N = 10) :

Nombre d'erreurs : 10
Ecart moyen total : 2,10477E-06
Ecart moyen en cas d'erreur : 0,001702704

- Sur S3 (N = 20) :

Nombre d'erreurs : 11
Ecart moyen total : 1,02467E-06
Ecart moyen en cas d'erreur : 0,000946085


... amélioration sensible, donc
... même si ça n'est pas encore le graal

[Alikendarfen]

@Baruch

Il y a une partie de ta démo que je ne vois toujours pas.

A un moment tu dis :

1/(p + pa + somme(1;i-1;pj)) <= 1/(p + pb + somme(1;i-1;pj))

<=>

pa >= pb

... or, rien n'indique que les mines Mj soient dans le même ordre et donc les "somme(1;i-1;pj)" à droite et à gauche de l'inégalité ne sont pas nécessairement les mêmes. Et donc notamment, il manque dans la somme l'une d'entre elle Mx à droite et une autre My à gauche.

... ou plutôt, la démo est vraie seulement si les Mj sont dans le même ordre, ce qui ne me semble pas être ce qu'on souhaite !


Qu'en penses tu ? ? ?

[Alikendarfen]

Suite au post précédent :

Pour le dire autrement, c'est la clause (1) qui est (serait ?) mal formulée :

Ma domine Mb

<=>

pour tout ensemble de mines { Mi } déterminé entre A et B et quel que soit l'ordre assigné aux Mi, T(Lab) < T(Lba)


... pour être honnête, j'écris ces lignes et pourtant tout cela est contre intuitif... donc pour le dire autrement : cela n'induit pas que la conclusion de la démo soit fausse


Edit : je ne suis pas sûr qu'on ait le droit de faire tendre ci vers oo en l'occurence : les ensembles sont finis et les courbes ne sont pas continues donc je ne vois pas le sens que cela a ?

[Baruch]

Quelques clarifications :

Ma démonstration ne trouve pas la meilleure dominance qui existe (ou si c'est le cas elle ne le prouve pas).

En effet, voici la définition de la "vraie" dominance :

On a E l'ensemble des mines à ordonner, parmi lesquelles on a M1 et M2.
Soient F12 l'ensemble des listes dans lesquelles M1 est avant M2, et F21 l'ensemble des listes dans lesquelles M2 est avant M1.

M1 domine "vraiment" M2, ça veut dire que dans la liste idéale, M1 est avant M2.
La liste idéale de E est soit min(F12), soit min(F21) (minimum au sens de l'évaluation du temps de construction T d'une liste).
M1 domine "vraiment" M2 équivaut à dire que la liste idéale est dans F12, c'est-à-dire que min(E)=min(F12).
Donc M1 domine "vraiment" M2 équivaut à min(F12) <= min(F21), ce qui équivaut à :

Pour toute L dans F21, T(L) >= min(F12)


Ca c'était pour la définition de la "vraie" dominance.

Qu'est-ce que je fais dans ma démonstration ?

Je considère en vérité une condition plus forte que la "vraie" dominance :

Pour tout L dans F21, il existe L' dans F12, tel que T(L) >= T(L')
(ce qui implique la vrai dominance)

Dans ma démonstration, je prends L' = f(L), où f est la permutation de M1 et M2.

J'aurais pu prendre n'importe quelle fonction f qui va de F21 dans F12, mais la permutation permet d'obtenir des calculs simplifiés, et qui aboutissent à un résultat simple.


Donc, dans ma démonstration, je cherche une équivalence à la relation :
T(L) >= T(f(L)) où L est dans F21.

Donc pour faire simple, je prends une liste L dans F21, quelconque, c'est-à-dire que l'ordre des mines est fixé. Puis je compare son temps de construction à celui de f(L), la liste L avec M1 et M2 permutées.

J'ai donc une relation, au début de ma démonstration, qui est assez lourde. Or je veux que cette relation soit vérifiée pour tout L dans F21. Ici je prends une condition plus forte, qui est qu'au lieu de considérer seulement les listes de F21, je considère toutes les listes imaginables dans lesquelles M2 est avant M1. C'est-à-dire que le nombre de mines entre M1 et M2, l'ordre des autres mines, les valeurs de Ci, de Pi et de P, sont quelconques.

C'est avec toutes ces simplifications (des conditions plus fortes que nécessaire), que j'obtiens une relation finale, simple (comparaison des productions, et des coûts).
Je l'obtiens en éliminant progressivement les paramètres Ci,P,Pi.

On peut bien étudier l'équivalence dans des conditions moins fortes que celles dans lesquelles on se place.
On peut soit réviser la deuxième simplification que je fais (dans quels intervalles varient les paramètres). Par exemple, j'ai par la suite retouché la démonstration, en considérant que P ne prenait que des valeurs entre P0 et P0+somme des Pi, et j'ai trouvé une condition un peu moins forte.
On peut aussi changer la fonction f utilisée : j'ai pris la permutation parce-que c'est simple, mais on peut imaginer d'autres fonctions (rotation, renversement, etc.).


Ce qu'il faut aussi prendre en compte, c'est que dans les différentes conditions dans lesquelles on peut se placer, on n'a pas nécessairement à la fin une "formule" (s'il faut trouver la liste idéale pour savoir si M1 domine M2 ou pas, c'est moyen... ^^).

[Alikendarfen]

Donc pour faire court et pour résumer:

c1 <= c2 et p1 >= p2 est une condition suffisante (mais pas forcément nécessaire) pour la dominance (la vraie).


... mais dans la démo que tu as communiquée, il vaut mieux que tu sois extrêmement clair là-dessus, car tu démontres une équivalence pour un cas particulier plus fort et dans la version de cette démo que j'ai pu lire, ça n'est nulle par indiqué (et ça ne saute pas à mes yeux à moi, pauvre lecteur !).


Pour le reste et pour info,

Actuellement, je n'ai pas de nouveaux résultats, mais je cherche selon une approche qu'on n'a pas encore exploré (si j'ai bien tout lu) :

Plutôt que de partir "du début", partons de "la fin", pour voir ce que ça donne.

La différence notable est que la production de la dernière mine ne participe de rien, ne contribue à rien....

C'est peut être une piste : je vous tiens au courant de ce que j'obtiens.

[elentarion]

Bonjour tout le monde.

Cela fait un moment que je suis ce sujet. Le problème posé est très intéressant, je ne prétendrai pas avoir compris toutes les considérations mathématiques des dernières pages mais j'ai voulu essayé de résoudre le problème également.

J'ai implémenté un algorithme génétique en C++ pour résoudre le problème. Après plusieurs essais (en faisant varier la population de départ et le nombre de génération) il semble que je converge vers une solution de 78 jours pour le jeu de test donné au dessus et avec P=5.

Je le redonne ici (un peu moddé pour avoir des noms plus sympas - les valeurs restent les mêmes):

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
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
Aphrodite A0;5;3
Apollo B0;2;4
Ares C0;6;4
Artemis D0;1;1
Athena E0;7;10
Cronus F0;50;200
Demeter G0;3;6
Dyonisus H0;3;10
Eos I0;4;8
Gaia J0;5;1
Hades K0;5;15
Hebe L0;4;8
Hecate M0;5;1
Helios N0;5;15
Hephaestus O0;2;15
Hera P0;14;15
Hermes Q0;15;10
Hestia R0;22;16
Selene S0;7;8
Uranus T0;6;5
Zeus U0;4;12
Anshar V0;27;22
Anu W0;3;14
Apsu X0;6;9
Ashur Y0;1;1
Damkina Z0;22;4
Ea A1;6;13
Enlil B1;6;18
Enuda C1;8;2
Hadad D1;10;7
Ishtar E1;9;18
Kingu F1;3;3
Kishar G1;9;11
Marduk H1;115;125
Mummu I1;16;14
Nabu J1;18;66
Nintu K1;22;24
Shamash L1;2;2
Sin M1;44;52
Tiamat N1;12;11
Aegir O1;3;3
Baldur P1;8;49
Bragi Q1;9;49
Freyr R1;10;22
Freya S1;9;22
Frigg T1;4;18
Heimdall U1;45;44
Hodur V1;14;7
Idun W1;16;9
Loki X1;22;3
Niord Y1;24;6
Odin Z1;26;8
Sif A2;4;6
Thor B2;5;32
Tyr C2;15;4
Vali D2;22;12
Belenus E2;4;21
Bran F2;1;9
Brigit G2;36;45
Ceridwen H2;12;6
Cernuros I2;96;3
Dagda J2;8;78
Danu K2;45;9
Epona L2;77;45
Gwydion M2;32;6
Lug N2;69;36
Lyr O2;21;2
Manannan mac Lir P2;36;7
Morrigan Q2;7;89
Nemain R2;15;4
Nuadha S2;2;1
Ogma T2;99;65
Anubis U2;3;4
Aten V2;66;11
Atum W2;45;21
Bast X2;9;3
Bet Y2;66;88
Geb Z2;3;76

Je pense pouvoir affiner mon algorithme notamment au niveau de la fonction de reproduction (pour l'instant extrêmement basique).

Pour finir, est-ce que quelqu'un a fais des tests sur les mêmes données que l'on puisse comparer nos performances/qualité des résultats/chemins trouvés ?

EDIT 1: J'avais honteusement oublié la possibilité d'acheter plusieurs mines (si les fonds sont suffisants) par jour. Avec cette rectification, mon algo arrive à trouver des solutions en 5 jours (population=10000, générations=50).

EDIT 2: Quelques exemples de solutions:

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
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
Jour 1 (totalIncome=5, totalMoney=5)
	Achat de la mine Thor B2 (cost=5, income=32)
Jour 2 (totalIncome=37, totalMoney=37)
	Achat de la mine Belenus E2 (cost=4, income=21)
	Achat de la mine Bran F2 (cost=1, income=9)
	Achat de la mine Geb Z2 (cost=3, income=76)
	Achat de la mine Dagda J2 (cost=8, income=78)
	Achat de la mine Morrigan Q2 (cost=7, income=89)
Jour 3 (totalIncome=310, totalMoney=324)
	Achat de la mine Nemain R2 (cost=15, income=4)
	Achat de la mine Atum W2 (cost=45, income=21)
	Achat de la mine Anshar V0 (cost=27, income=22)
	Achat de la mine Damkina Z0 (cost=22, income=4)
	Achat de la mine Ares C0 (cost=6, income=4)
	Achat de la mine Lug N2 (cost=69, income=36)
	Achat de la mine Sin M1 (cost=44, income=52)
	Achat de la mine Anu W0 (cost=3, income=14)
	Achat de la mine Brigit G2 (cost=36, income=45)
	Achat de la mine Hades K0 (cost=5, income=15)
	Achat de la mine Hephaestus O0 (cost=2, income=15)
	Achat de la mine Ea A1 (cost=6, income=13)
	Achat de la mine Odin Z1 (cost=26, income=8)
	Achat de la mine Enlil B1 (cost=6, income=18)
Jour 4 (totalIncome=581, totalMoney=593)
	Achat de la mine Nabu J1 (cost=18, income=66)
	Achat de la mine Anubis U2 (cost=3, income=4)
	Achat de la mine Loki X1 (cost=22, income=3)
	Achat de la mine Artemis D0 (cost=1, income=1)
	Achat de la mine Helios N0 (cost=5, income=15)
	Achat de la mine Hodur V1 (cost=14, income=7)
	Achat de la mine Kingu F1 (cost=3, income=3)
	Achat de la mine Ogma T2 (cost=99, income=65)
	Achat de la mine Hadad D1 (cost=10, income=7)
	Achat de la mine Frigg T1 (cost=4, income=18)
	Achat de la mine Selene S0 (cost=7, income=8)
	Achat de la mine Aegir O1 (cost=3, income=3)
	Achat de la mine Aphrodite A0 (cost=5, income=3)
	Achat de la mine Ceridwen H2 (cost=12, income=6)
	Achat de la mine Baldur P1 (cost=8, income=49)
	Achat de la mine Mummu I1 (cost=16, income=14)
	Achat de la mine Vali D2 (cost=22, income=12)
	Achat de la mine Aten V2 (cost=66, income=11)
	Achat de la mine Gwydion M2 (cost=32, income=6)
	Achat de la mine Hecate M0 (cost=5, income=1)
	Achat de la mine Tiamat N1 (cost=12, income=11)
	Achat de la mine Heimdall U1 (cost=45, income=44)
	Achat de la mine Nintu K1 (cost=22, income=24)
	Achat de la mine Kishar G1 (cost=9, income=11)
	Achat de la mine Lyr O2 (cost=21, income=2)
	Achat de la mine Cronus F0 (cost=50, income=200)
	Achat de la mine Niord Y1 (cost=24, income=6)
	Achat de la mine Danu K2 (cost=45, income=9)
	Achat de la mine Eos I0 (cost=4, income=8)
	Achat de la mine Zeus U0 (cost=4, income=12)
Jour 5 (totalIncome=1210, totalMoney=1212)
	Achat de la mine Idun W1 (cost=16, income=9)
	Achat de la mine Nuadha S2 (cost=2, income=1)
	Achat de la mine Hera P0 (cost=14, income=15)
	Achat de la mine Cernuros I2 (cost=96, income=3)
	Achat de la mine Marduk H1 (cost=115, income=125)
	Achat de la mine Athena E0 (cost=7, income=10)
	Achat de la mine Uranus T0 (cost=6, income=5)
	Achat de la mine Hermes Q0 (cost=15, income=10)
	Achat de la mine Demeter G0 (cost=3, income=6)
	Achat de la mine Enuda C1 (cost=8, income=2)
	Achat de la mine Bragi Q1 (cost=9, income=49)
	Achat de la mine Sif A2 (cost=4, income=6)
	Achat de la mine Bet Y2 (cost=66, income=88)
	Achat de la mine Apollo B0 (cost=2, income=4)
	Achat de la mine Shamash L1 (cost=2, income=2)
	Achat de la mine Epona L2 (cost=77, income=45)
	Achat de la mine Manannan mac Lir P2 (cost=36, income=7)
	Achat de la mine Gaia J0 (cost=5, income=1)
	Achat de la mine Freya S1 (cost=9, income=22)
	Achat de la mine Hebe L0 (cost=4, income=8)
	Achat de la mine Tyr C2 (cost=15, income=4)
	Achat de la mine Freyr R1 (cost=10, income=22)
	Achat de la mine Dyonisus H0 (cost=3, income=10)
	Achat de la mine Bast X2 (cost=9, income=3)
	Achat de la mine Ashur Y0 (cost=1, income=1)
	Achat de la mine Apsu X0 (cost=6, income=9)
	Achat de la mine Ishtar E1 (cost=9, income=18)
	Achat de la mine Hestia R0 (cost=22, income=16)

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
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
Jour 1 (totalIncome=5, totalMoney=5)
	Achat de la mine Geb Z2 (cost=3, income=76)
Jour 2 (totalIncome=81, totalMoney=83)
	Achat de la mine Dagda J2 (cost=8, income=78)
	Achat de la mine Heimdall U1 (cost=45, income=44)
	Achat de la mine Ea A1 (cost=6, income=13)
	Achat de la mine Tyr C2 (cost=15, income=4)
	Achat de la mine Kishar G1 (cost=9, income=11)
Jour 3 (totalIncome=231, totalMoney=231)
	Achat de la mine Loki X1 (cost=22, income=3)
	Achat de la mine Demeter G0 (cost=3, income=6)
	Achat de la mine Enlil B1 (cost=6, income=18)
	Achat de la mine Manannan mac Lir P2 (cost=36, income=7)
	Achat de la mine Hera P0 (cost=14, income=15)
	Achat de la mine Frigg T1 (cost=4, income=18)
	Achat de la mine Bran F2 (cost=1, income=9)
	Achat de la mine Nemain R2 (cost=15, income=4)
	Achat de la mine Apsu X0 (cost=6, income=9)
	Achat de la mine Atum W2 (cost=45, income=21)
	Achat de la mine Aegir O1 (cost=3, income=3)
	Achat de la mine Gaia J0 (cost=5, income=1)
	Achat de la mine Sin M1 (cost=44, income=52)
	Achat de la mine Niord Y1 (cost=24, income=6)
Jour 4 (totalIncome=403, totalMoney=406)
	Achat de la mine Cronus F0 (cost=50, income=200)
	Achat de la mine Shamash L1 (cost=2, income=2)
	Achat de la mine Hades K0 (cost=5, income=15)
	Achat de la mine Freyr R1 (cost=10, income=22)
	Achat de la mine Hadad D1 (cost=10, income=7)
	Achat de la mine Dyonisus H0 (cost=3, income=10)
	Achat de la mine Kingu F1 (cost=3, income=3)
	Achat de la mine Anshar V0 (cost=27, income=22)
	Achat de la mine Eos I0 (cost=4, income=8)
	Achat de la mine Nabu J1 (cost=18, income=66)
	Achat de la mine Lug N2 (cost=69, income=36)
	Achat de la mine Thor B2 (cost=5, income=32)
	Achat de la mine Selene S0 (cost=7, income=8)
	Achat de la mine Hodur V1 (cost=14, income=7)
	Achat de la mine Morrigan Q2 (cost=7, income=89)
	Achat de la mine Apollo B0 (cost=2, income=4)
	Achat de la mine Cernuros I2 (cost=96, income=3)
	Achat de la mine Hermes Q0 (cost=15, income=10)
	Achat de la mine Ashur Y0 (cost=1, income=1)
	Achat de la mine Brigit G2 (cost=36, income=45)
Jour 5 (totalIncome=993, totalMoney=1015)
	Achat de la mine Epona L2 (cost=77, income=45)
	Achat de la mine Bragi Q1 (cost=9, income=49)
	Achat de la mine Aphrodite A0 (cost=5, income=3)
	Achat de la mine Aten V2 (cost=66, income=11)
	Achat de la mine Ogma T2 (cost=99, income=65)
	Achat de la mine Helios N0 (cost=5, income=15)
	Achat de la mine Anu W0 (cost=3, income=14)
	Achat de la mine Tiamat N1 (cost=12, income=11)
	Achat de la mine Lyr O2 (cost=21, income=2)
	Achat de la mine Athena E0 (cost=7, income=10)
	Achat de la mine Hephaestus O0 (cost=2, income=15)
	Achat de la mine Gwydion M2 (cost=32, income=6)
	Achat de la mine Ares C0 (cost=6, income=4)
	Achat de la mine Hestia R0 (cost=22, income=16)
	Achat de la mine Nintu K1 (cost=22, income=24)
	Achat de la mine Nuadha S2 (cost=2, income=1)
	Achat de la mine Odin Z1 (cost=26, income=8)
	Achat de la mine Zeus U0 (cost=4, income=12)
	Achat de la mine Anubis U2 (cost=3, income=4)
	Achat de la mine Baldur P1 (cost=8, income=49)
	Achat de la mine Belenus E2 (cost=4, income=21)
	Achat de la mine Bast X2 (cost=9, income=3)
	Achat de la mine Bet Y2 (cost=66, income=88)
	Achat de la mine Idun W1 (cost=16, income=9)
	Achat de la mine Ishtar E1 (cost=9, income=18)
	Achat de la mine Vali D2 (cost=22, income=12)
	Achat de la mine Hebe L0 (cost=4, income=8)
	Achat de la mine Danu K2 (cost=45, income=9)
	Achat de la mine Marduk H1 (cost=115, income=125)
	Achat de la mine Freya S1 (cost=9, income=22)
	Achat de la mine Ceridwen H2 (cost=12, income=6)
	Achat de la mine Artemis D0 (cost=1, income=1)
	Achat de la mine Hecate M0 (cost=5, income=1)
	Achat de la mine Mummu I1 (cost=16, income=14)
	Achat de la mine Enuda C1 (cost=8, income=2)
	Achat de la mine Sif A2 (cost=4, income=6)
	Achat de la mine Uranus T0 (cost=6, income=5)
	Achat de la mine Damkina Z0 (cost=22, income=4)

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
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
Jour 1 (totalIncome=5, totalMoney=5)
	Achat de la mine Geb Z2 (cost=3, income=76)
Jour 2 (totalIncome=81, totalMoney=83)
	Achat de la mine Dyonisus H0 (cost=3, income=10)
	Achat de la mine Cronus F0 (cost=50, income=200)
	Achat de la mine Hestia R0 (cost=22, income=16)
Jour 3 (totalIncome=307, totalMoney=315)
	Achat de la mine Nintu K1 (cost=22, income=24)
	Achat de la mine Aphrodite A0 (cost=5, income=3)
	Achat de la mine Ea A1 (cost=6, income=13)
	Achat de la mine Dagda J2 (cost=8, income=78)
	Achat de la mine Kingu F1 (cost=3, income=3)
	Achat de la mine Demeter G0 (cost=3, income=6)
	Achat de la mine Zeus U0 (cost=4, income=12)
	Achat de la mine Hermes Q0 (cost=15, income=10)
	Achat de la mine Sin M1 (cost=44, income=52)
	Achat de la mine Odin Z1 (cost=26, income=8)
	Achat de la mine Ceridwen H2 (cost=12, income=6)
	Achat de la mine Helios N0 (cost=5, income=15)
	Achat de la mine Danu K2 (cost=45, income=9)
	Achat de la mine Enlil B1 (cost=6, income=18)
	Achat de la mine Uranus T0 (cost=6, income=5)
	Achat de la mine Frigg T1 (cost=4, income=18)
	Achat de la mine Nabu J1 (cost=18, income=66)
	Achat de la mine Gaia J0 (cost=5, income=1)
	Achat de la mine Damkina Z0 (cost=22, income=4)
	Achat de la mine Hera P0 (cost=14, income=15)
	Achat de la mine Anu W0 (cost=3, income=14)
	Achat de la mine Hecate M0 (cost=5, income=1)
Jour 4 (totalIncome=688, totalMoney=722)
	Achat de la mine Atum W2 (cost=45, income=21)
	Achat de la mine Anubis U2 (cost=3, income=4)
	Achat de la mine Niord Y1 (cost=24, income=6)
	Achat de la mine Cernuros I2 (cost=96, income=3)
	Achat de la mine Shamash L1 (cost=2, income=2)
	Achat de la mine Heimdall U1 (cost=45, income=44)
	Achat de la mine Hephaestus O0 (cost=2, income=15)
	Achat de la mine Ogma T2 (cost=99, income=65)
	Achat de la mine Mummu I1 (cost=16, income=14)
	Achat de la mine Vali D2 (cost=22, income=12)
	Achat de la mine Bast X2 (cost=9, income=3)
	Achat de la mine Kishar G1 (cost=9, income=11)
	Achat de la mine Idun W1 (cost=16, income=9)
	Achat de la mine Bet Y2 (cost=66, income=88)
	Achat de la mine Tiamat N1 (cost=12, income=11)
	Achat de la mine Eos I0 (cost=4, income=8)
	Achat de la mine Ishtar E1 (cost=9, income=18)
	Achat de la mine Lug N2 (cost=69, income=36)
	Achat de la mine Hodur V1 (cost=14, income=7)
	Achat de la mine Freyr R1 (cost=10, income=22)
	Achat de la mine Enuda C1 (cost=8, income=2)
	Achat de la mine Aten V2 (cost=66, income=11)
	Achat de la mine Manannan mac Lir P2 (cost=36, income=7)
	Achat de la mine Sif A2 (cost=4, income=6)
	Achat de la mine Anshar V0 (cost=27, income=22)
	Achat de la mine Ares C0 (cost=6, income=4)
	Achat de la mine Ashur Y0 (cost=1, income=1)
Jour 5 (totalIncome=1140, totalMoney=1142)
	Achat de la mine Lyr O2 (cost=21, income=2)
	Achat de la mine Epona L2 (cost=77, income=45)
	Achat de la mine Selene S0 (cost=7, income=8)
	Achat de la mine Freya S1 (cost=9, income=22)
	Achat de la mine Tyr C2 (cost=15, income=4)
	Achat de la mine Nuadha S2 (cost=2, income=1)
	Achat de la mine Hebe L0 (cost=4, income=8)
	Achat de la mine Loki X1 (cost=22, income=3)
	Achat de la mine Apsu X0 (cost=6, income=9)
	Achat de la mine Hadad D1 (cost=10, income=7)
	Achat de la mine Gwydion M2 (cost=32, income=6)
	Achat de la mine Athena E0 (cost=7, income=10)
	Achat de la mine Nemain R2 (cost=15, income=4)
	Achat de la mine Aegir O1 (cost=3, income=3)
	Achat de la mine Baldur P1 (cost=8, income=49)
	Achat de la mine Marduk H1 (cost=115, income=125)
	Achat de la mine Brigit G2 (cost=36, income=45)
	Achat de la mine Hades K0 (cost=5, income=15)
	Achat de la mine Bran F2 (cost=1, income=9)
	Achat de la mine Belenus E2 (cost=4, income=21)
	Achat de la mine Morrigan Q2 (cost=7, income=89)
	Achat de la mine Bragi Q1 (cost=9, income=49)
	Achat de la mine Apollo B0 (cost=2, income=4)
	Achat de la mine Thor B2 (cost=5, income=32)
	Achat de la mine Artemis D0 (cost=1, income=1)

[Baruch]

Attention !

Le temps est continu :

Il n'y a pas de tours : on n'étudie pas la question d'acheter ou pas une mine chaque jour (par exemple). On étudie cette question continûment. Ceci n'implique bien évidemment pas qu'on achète n'importe qu'elle mine dès qu'on peut la payer. En revanche, cela implique qu'après chaque achat de mine, on n'a plus d'argent.

[elentarion]

Ok, je vais essayer de revoir ça avec un temps continu. C'est à dire que l'income reste par jour mais qu'il est gagné au fur et à mesure ? Au bout d'une heure on aura accumulé 1/24 de l'income ? et une seconde plus tard on aura 1/86400 de l'income en plus ?

[Baruch]

Ouép, exactement