Ordre de construction de mines

Version imprimable

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

11/07/2011, 13h55
Alikendarfen

Super ce nouveau jeu d'essai !

Citation:

Envoyé par elentarion

Me revoilà, j'ai recodé mon algo en Java. Alors, maintenant j'arrive avec une solution stable à 2.37 jours avec 400 individus sur 20k générations.

Là, tu parles bien du jeu d'essai d'avant ?

Citation:

Envoyé par elentarion

Je cherche toujours pourquoi je n'arrive pas à descendre en dessous de deux mais au moins j'ai le même résultat à chaque fois.

Il y a peut être une erreur (chez moi ou chez toi) ? Ou sinon, on ne parle pas des mêmes mines ??

Et sinon, j'ai pris les 101 premières mines de ton dernier jeu d'essai (jusqu'à "M0100 Alalkomene" incluse), avec p = 5 :
- 2.4714707568379404 jours
- 191 secondes de calcul
- 15 748 578 chemins intermédiaires générés

Edit : il y a beaucoup de dominantes dans ton nouveau jeu d'essai. Ca favorise considérablement mon algo !

... je vais également tenter de voir ce que ça donne de paralléliser... en C#, il y a http://dotnet.developpez.com/actu/32...-de-Microsoft/ : ça me donnera l'occasion d'essayer !

Pour répondre à Alikendarfen, oui j'ai utilisé l'ancien jeu d'essai. Ensuite, je pense que l'erreur est plutôt vers chez moi, je ne suis pas un pro des algos génétiques.

Sinon, avec le nouveau jeu d'essai, je pense qu'on a peut-être un problème. J'ai une solution moindre que la tienne avec mon algo génétique imparfait : 2.105900847183878.

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
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
 
M0097 Akesios;82,16;1,36 @ 0,27 / New income: 87,16
M0098 Akraia;57,44;5,20 @ 0,33 / New income: 144,61
M0013 Aton;57,38;5,81 @ 0,37 / New income: 201,99
M0078 Agdistis;97,77;11,56 @ 0,43 / New income: 299,75
M0067 Shu;65,60;9,83 @ 0,46 / New income: 365,35
M0038 Ma'at;99,64;16,54 @ 0,51 / New income: 464,99
M0029 Kauket;66,25;13,14 @ 0,53 / New income: 531,23
M0023 Hauhet;96,85;19,46 @ 0,57 / New income: 628,08
M0049 Nun;81,05;16,94 @ 0,60 / New income: 709,14
M0015 Bastet;46,51;10,44 @ 0,61 / New income: 755,64
M0055 Renenet;72,65;19,51 @ 0,64 / New income: 828,30
M0001 Amen;94,61;25,96 @ 0,67 / New income: 922,91
M0075 Aello;98,92;27,16 @ 0,70 / New income: 1021,83
M0066 Shu;75,09;20,68 @ 0,72 / New income: 1096,92
M0099 Aktaios;39,06;11,54 @ 0,73 / New income: 1135,98
M0051 Osiris;82,20;25,39 @ 0,75 / New income: 1218,18
M0018 Duamutef;35,51;11,04 @ 0,76 / New income: 1253,69
M0079 Ageleia;90,15;28,19 @ 0,78 / New income: 1343,84
M0064 Seth;78,68;25,24 @ 0,80 / New income: 1422,52
M0081 Agne;99,85;34,67 @ 0,83 / New income: 1522,37
M0002 Amon;81,93;29,15 @ 0,85 / New income: 1604,29
M0016 Bat;45,04;16,21 @ 0,86 / New income: 1649,34
M0091 Aigiokhos;52,66;21,90 @ 0,87 / New income: 1702,00
M0008 Anuket;70,67;30,70 @ 0,89 / New income: 1772,67
M0003 Amun;63,41;29,60 @ 0,90 / New income: 1836,08
M0052 Ptah;96,42;48,01 @ 0,93 / New income: 1932,50
M0036 Kuk;23,85;12,06 @ 0,94 / New income: 1956,35
M0028 Isis;21,18;11,58 @ 0,94 / New income: 1977,52
M0017 Buto;43,14;23,94 @ 0,96 / New income: 2020,67
M0043 Mut;18,44;10,36 @ 0,96 / New income: 2039,11
M0006 Antaios;70,86;40,12 @ 0,98 / New income: 2109,97
M0074 Acidalia;96,27;56,53 @ 1,01 / New income: 2206,24
M0085 Agreiphontes;37,66;23,77 @ 1,02 / New income: 2243,90
M0005 Anqet;88,39;58,46 @ 1,04 / New income: 2332,28
M0019 Duamutef;44,55;29,89 @ 1,06 / New income: 2376,83
M0090 Aidoneus;63,34;44,09 @ 1,07 / New income: 2440,17
M0027 Imset;66,84;47,51 @ 1,09 / New income: 2507,01
M0007 Anubis;87,91;62,52 @ 1,12 / New income: 2594,92
M0077 Agathe;70,92;50,65 @ 1,14 / New income: 2665,83
M0084 Agreie;94,05;68,99 @ 1,16 / New income: 2759,89
M0060 Sekhmet;52,50;41,49 @ 1,18 / New income: 2812,38
M0030 Kebechsenef;63,99;54,05 @ 1,20 / New income: 2876,37
M0086 Agreus;69,31;60,78 @ 1,22 / New income: 2945,68
M0004 Anat;71,43;63,45 @ 1,24 / New income: 3017,11
M0046 Neith;88,84;79,65 @ 1,27 / New income: 3105,95
M0047 Nekhbet;40,50;37,29 @ 1,28 / New income: 3146,45
M0094 Ainia;96,70;90,14 @ 1,31 / New income: 3243,16
M0063 Set;82,23;77,36 @ 1,33 / New income: 3325,38
M0012 Aten;85,10;83,24 @ 1,36 / New income: 3410,48
M0021 Har-pa-khered;42,84;42,12 @ 1,37 / New income: 3453,32
M0057 Satet;81,88;80,77 @ 1,39 / New income: 3535,20
M0053 Ra;46,11;45,72 @ 1,41 / New income: 3581,32
M0059 Seker;78,09;79,39 @ 1,43 / New income: 3659,41
M0095 Ainippe;97,00;99,04 @ 1,46 / New income: 3756,41
M0045 Nefertem;51,60;53,07 @ 1,47 / New income: 3808,01
M0014 Atum;81,98;86,33 @ 1,49 / New income: 3889,99
M0089 Aguieus;77,72;82,02 @ 1,51 / New income: 3967,71
M0068 Sia;58,22;61,63 @ 1,53 / New income: 4025,93
M0032 Khepri;76,65;81,30 @ 1,55 / New income: 4102,58
M0022 Hathor;77,00;85,71 @ 1,57 / New income: 4179,58
M0054 Re;65,86;75,35 @ 1,59 / New income: 4245,44
M0071 Tefnut;24,99;29,10 @ 1,59 / New income: 4270,43
M0026 Huh;53,88;63,06 @ 1,61 / New income: 4324,31
M0025 Horus;71,51;84,65 @ 1,63 / New income: 4395,82
M0093 Aigobolos;43,52;53,29 @ 1,64 / New income: 4439,34
M0100 Alalkomene;22,61;27,80 @ 1,65 / New income: 4461,95
M0031 Khensu;70,21;89,73 @ 1,67 / New income: 4532,16
M0092 Aigletes;54,40;70,56 @ 1,68 / New income: 4586,56
M0065 Shai;36,57;55,55 @ 1,70 / New income: 4623,14
M0010 Apis;38,56;59,47 @ 1,71 / New income: 4661,69
M0034 Khnum;51,11;79,56 @ 1,73 / New income: 4712,80
M0073 Thoth;60,08;95,19 @ 1,75 / New income: 4772,88
M0035 Khonsu;10,54;16,77 @ 1,75 / New income: 4783,42
M0096 Aithuia;53,50;87,00 @ 1,77 / New income: 4836,92
M0009 Apep;43,30;71,88 @ 1,78 / New income: 4880,22
M0042 Mnewer;38,50;64,06 @ 1,80 / New income: 4918,72
M0024 Heket;38,05;65,56 @ 1,81 / New income: 4956,77
M0082 Agoraia;48,00;86,87 @ 1,83 / New income: 5004,77
M0039 Mehen;26,73;49,03 @ 1,84 / New income: 5031,50
M0020 Hapi;51,23;99,57 @ 1,86 / New income: 5082,73
M0000 Amaunet;26,13;51,14 @ 1,87 / New income: 5108,86
M0033 Khnemu;45,24;97,00 @ 1,88 / New income: 5154,10
M0048 Nephthys;34,83;83,33 @ 1,90 / New income: 5188,93
M0061 Serapis;36,82;88,96 @ 1,92 / New income: 5225,75
M0011 Astarte;26,94;73,18 @ 1,93 / New income: 5252,69
M0088 Agrotera;17,77;50,96 @ 1,94 / New income: 5270,45
M0044 Naunet;15,11;49,20 @ 1,95 / New income: 5285,57
M0056 Sakhmet;22,20;76,63 @ 1,97 / New income: 5307,77
M0070 Sokar;25,83;90,88 @ 1,98 / New income: 5333,60
M0087 Agrios;24,92;90,34 @ 2,00 / New income: 5358,52
M0080 Aglauros;19,61;74,58 @ 2,01 / New income: 5378,13
M0037 Maahes;5,14;19,74 @ 2,02 / New income: 5383,27
M0062 Serket;7,15;27,57 @ 2,02 / New income: 5390,42
M0041 Min;10,17;40,25 @ 2,03 / New income: 5400,59
M0050 Nut;15,32;61,28 @ 2,04 / New income: 5415,91
M0069 Sobek;14,16;65,87 @ 2,05 / New income: 5430,07
M0058 Seb;9,50;56,25 @ 2,06 / New income: 5439,56
M0040 Meretseger;9,51;61,15 @ 2,07 / New income: 5449,07
M0072 Tem;8,93;58,37 @ 2,09 / New income: 5458,01
M0076 Aesculapius;4,63;40,15 @ 2,09 / New income: 5462,64
M0083 Agreia;1,37;71,33 @ 2,11 / New income: 5464,01
Time taken: 2328ms
Duration: 2.105900847183878 days.

Je n'ai arrondi que pour l'affichage, tous les calculs sont effectués sur les vraies valeurs.

Ensuite, pour les dominances plus nombreuses, je pense que ça vient de la répartition parfaitement aléatoire. D'où ma suggestion de corser un peu le jeu d'essai avec des valeurs extrêmes ou une répartition non linéaire.

Citation:

Envoyé par elentarion

Sinon, avec le nouveau jeu d'essai, je pense qu'on a peut-être un problème. J'ai une solution moindre que la tienne avec mon algo génétique imparfait : 2.105900847183878.

Pour vérifier, j'ai lancé ma version des AG sur le même jeu d'essai : j'obtiens 2.4714707568379404, soit exactement le même score.

J'ai pris p=5. C'est bien ton cas aussi ?

Voici le chemin que j'obtiens :

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
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
 
[0,27:M0083 Agreia/1/71]
[0,33:M0076 Aesculapius/5/40]
[0,41:M0072 Tem/9/58]
[0,47:M0040 Meretseger/10/61]
[0,51:M0058 Seb/9/56]
[0,55:M0069 Sobek/14/66]
[0,57:M0037 Maahes/5/20]
[0,59:M0062 Serket/7/28]
[0,61:M0041 Min/10/40]
[0,65:M0050 Nut/15/61]
[0,69:M0080 Aglauros/20/75]
[0,73:M0087 Agrios/25/90]
[0,77:M0070 Sokar/26/91]
[0,80:M0056 Sakhmet/22/77]
[0,81:M0044 Naunet/15/49]
[0,83:M0088 Agrotera/18/51]
[0,86:M0011 Astarte/27/73]
[0,90:M0061 Serapis/37/89]
[0,93:M0048 Nephthys/35/83]
[0,97:M0033 Khnemu/45/97]
[0,99:M0000 Amaunet/26/51]
[1,03:M0020 Hapi/51/100]
[1,05:M0039 Mehen/27/49]
[1,08:M0082 Agoraia/48/87]
[1,10:M0024 Heket/38/66]
[1,13:M0042 Mnewer/39/64]
[1,15:M0009 Apep/43/72]
[1,16:M0035 Khonsu/11/17]
[1,19:M0096 Aithuia/54/87]
[1,22:M0073 Thoth/60/95]
[1,24:M0010 Apis/39/59]
[1,26:M0034 Khnum/51/80]
[1,28:M0065 Shai/37/56]
[1,31:M0092 Aigletes/54/71]
[1,34:M0031 Khensu/70/90]
[1,35:M0100 Alalkomene/23/28]
[1,37:M0093 Aigobolos/44/53]
[1,38:M0071 Tefnut/25/29]
[1,41:M0025 Horus/72/85]
[1,43:M0026 Huh/54/63]
[1,45:M0054 Re/66/75]
[1,48:M0022 Hathor/77/86]
[1,50:M0068 Sia/58/62]
[1,53:M0032 Khepri/77/81]
[1,56:M0089 Aguieus/78/82]
[1,59:M0014 Atum/82/86]
[1,60:M0045 Nefertem/52/53]
[1,63:M0059 Seker/78/79]
[1,66:M0095 Ainippe/97/99]
[1,67:M0053 Ra/46/46]
[1,69:M0021 Har-pa-khered/43/42]
[1,71:M0057 Satet/82/81]
[1,73:M0012 Aten/85/83]
[1,76:M0063 Set/82/77]
[1,77:M0047 Nekhbet/41/37]
[1,80:M0094 Ainia/97/90]
[1,82:M0046 Neith/89/80]
[1,84:M0004 Anat/71/63]
[1,86:M0086 Agreus/69/61]
[1,87:M0030 Kebechsenef/64/54]
[1,88:M0060 Sekhmet/52/41]
[1,91:M0084 Agreie/94/69]
[1,93:M0077 Agathe/71/51]
[1,94:M0027 Imset/67/48]
[1,96:M0007 Anubis/88/63]
[1,98:M0090 Aidoneus/63/44]
[1,99:M0019 Duamutef/45/30]
[2,01:M0005 Anqet/88/58]
[2,02:M0085 Agreiphontes/38/24]
[2,04:M0074 Acidalia/96/57]
[2,05:M0006 Antaios/71/40]
[2,06:M0043 Mut/18/10]
[2,07:M0017 Buto/43/24]
[2,07:M0028 Isis/21/12]
[2,08:M0036 Kuk/24/12]
[2,10:M0052 Ptah/96/48]
[2,11:M0003 Amun/63/30]
[2,13:M0008 Anuket/71/31]
[2,14:M0091 Aigiokhos/53/22]
[2,15:M0016 Bat/45/16]
[2,17:M0002 Amon/82/29]
[2,19:M0081 Agne/100/35]
[2,20:M0064 Seth/79/25]
[2,22:M0079 Ageleia/90/28]
[2,23:M0018 Duamutef/36/11]
[2,25:M0051 Osiris/82/25]
[2,25:M0099 Aktaios/39/12]
[2,27:M0066 Shu/75/21]
[2,29:M0075 Aello/99/27]
[2,31:M0001 Amen/95/26]
[2,32:M0055 Renenet/73/20]
[2,33:M0015 Bastet/47/10]
[2,35:M0049 Nun/81/17]
[2,37:M0023 Hauhet/97/19]
[2,38:M0029 Kauket/66/13]
[2,40:M0038 Ma'at/100/17]
[2,41:M0067 Shu/66/10]
[2,43:M0078 Agdistis/98/12]
[2,44:M0013 Aton/57/6]
[2,46:M0098 Akraia/57/5]
[2,47:M0097 Akesios/82/1]

Dis, ton tableau c'est bien <nom>;<cout>;<production>, comme les données d'avant ?? (on remarque que tu commences par la mine par laquelle je termine...)

Méga OUPS ! :oops: :oops:

Effectivement, j'intervertissais les deux valeurs cost/income. Du coup j'ai une bonne valeur pour le premier jeu de test et aussi pour le nouveau.

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
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
 
Time taken: 2438ms
Duration: 2.4718830927961855 days.
---
M0083 Agreia;71,33;1,37 @ 0,27 / New income: 76,33
M0076 Aesculapius;40,15;4,63 @ 0,33 / New income: 116,49
M0072 Tem;58,37;8,93 @ 0,41 / New income: 174,86
M0040 Meretseger;61,15;9,51 @ 0,47 / New income: 236,00
M0058 Seb;56,25;9,50 @ 0,51 / New income: 292,25
M0069 Sobek;65,87;14,16 @ 0,55 / New income: 358,13
M0050 Nut;61,28;15,32 @ 0,60 / New income: 419,40
M0041 Min;40,25;10,17 @ 0,62 / New income: 459,66
M0062 Serket;27,57;7,15 @ 0,64 / New income: 487,22
M0037 Maahes;19,74;5,14 @ 0,65 / New income: 506,97
M0080 Aglauros;74,58;19,61 @ 0,69 / New income: 581,55
M0087 Agrios;90,34;24,92 @ 0,73 / New income: 671,90
M0070 Sokar;90,88;25,83 @ 0,77 / New income: 762,78
M0056 Sakhmet;76,63;22,20 @ 0,80 / New income: 839,41
M0044 Naunet;49,20;15,11 @ 0,81 / New income: 888,61
M0088 Agrotera;50,96;17,77 @ 0,83 / New income: 939,57
M0011 Astarte;73,18;26,94 @ 0,86 / New income: 1012,75
M0061 Serapis;88,96;36,82 @ 0,90 / New income: 1101,71
M0048 Nephthys;83,33;34,83 @ 0,93 / New income: 1185,03
M0033 Khnemu;97,00;45,24 @ 0,97 / New income: 1282,03
M0000 Amaunet;51,14;26,13 @ 0,99 / New income: 1333,17
M0020 Hapi;99,57;51,23 @ 1,03 / New income: 1432,74
M0039 Mehen;49,03;26,73 @ 1,05 / New income: 1481,78
M0082 Agoraia;86,87;48,00 @ 1,08 / New income: 1568,65
M0024 Heket;65,56;38,05 @ 1,10 / New income: 1634,22
M0042 Mnewer;64,06;38,50 @ 1,13 / New income: 1698,28
M0009 Apep;71,88;43,30 @ 1,15 / New income: 1770,16
M0096 Aithuia;87,00;53,50 @ 1,18 / New income: 1857,16
M0035 Khonsu;16,77;10,54 @ 1,19 / New income: 1873,93
M0073 Thoth;95,19;60,08 @ 1,22 / New income: 1969,12
M0034 Khnum;79,56;51,11 @ 1,25 / New income: 2048,68
M0010 Apis;59,47;38,56 @ 1,27 / New income: 2108,15
M0065 Shai;55,55;36,57 @ 1,28 / New income: 2163,70
M0092 Aigletes;70,56;54,40 @ 1,31 / New income: 2234,25
M0031 Khensu;89,73;70,21 @ 1,34 / New income: 2323,98
M0100 Alalkomene;27,80;22,61 @ 1,35 / New income: 2351,79
M0093 Aigobolos;53,29;43,52 @ 1,37 / New income: 2405,08
M0025 Horus;84,65;71,51 @ 1,40 / New income: 2489,73
M0026 Huh;63,06;53,88 @ 1,42 / New income: 2552,79
M0071 Tefnut;29,10;24,99 @ 1,43 / New income: 2581,88
M0054 Re;75,35;65,86 @ 1,45 / New income: 2657,24
M0022 Hathor;85,71;77,00 @ 1,48 / New income: 2742,94
M0032 Khepri;81,30;76,65 @ 1,51 / New income: 2824,24
M0068 Sia;61,63;58,22 @ 1,53 / New income: 2885,87
M0089 Aguieus;82,02;77,72 @ 1,56 / New income: 2967,90
M0014 Atum;86,33;81,98 @ 1,59 / New income: 3054,23
M0045 Nefertem;53,07;51,60 @ 1,60 / New income: 3107,30
M0059 Seker;79,39;78,09 @ 1,63 / New income: 3186,68
M0095 Ainippe;99,04;97,00 @ 1,66 / New income: 3285,73
M0053 Ra;45,72;46,11 @ 1,67 / New income: 3331,45
M0057 Satet;80,77;81,88 @ 1,70 / New income: 3412,22
M0021 Har-pa-khered;42,12;42,84 @ 1,71 / New income: 3454,34
M0012 Aten;83,24;85,10 @ 1,73 / New income: 3537,58
M0063 Set;77,36;82,23 @ 1,76 / New income: 3614,93
M0094 Ainia;90,14;96,70 @ 1,78 / New income: 3705,08
M0047 Nekhbet;37,29;40,50 @ 1,80 / New income: 3742,36
M0046 Neith;79,65;88,84 @ 1,82 / New income: 3822,01
M0004 Anat;63,45;71,43 @ 1,84 / New income: 3885,46
M0086 Agreus;60,78;69,31 @ 1,86 / New income: 3946,24
M0030 Kebechsenef;54,05;63,99 @ 1,87 / New income: 4000,29
M0060 Sekhmet;41,49;52,50 @ 1,89 / New income: 4041,78
M0084 Agreie;68,99;94,05 @ 1,91 / New income: 4110,76
M0077 Agathe;50,65;70,92 @ 1,93 / New income: 4161,41
M0007 Anubis;62,52;87,91 @ 1,95 / New income: 4223,93
M0027 Imset;47,51;66,84 @ 1,96 / New income: 4271,44
M0090 Aidoneus;44,09;63,34 @ 1,98 / New income: 4315,53
M0019 Duamutef;29,89;44,55 @ 1,99 / New income: 4345,41
M0005 Anqet;58,46;88,39 @ 2,01 / New income: 4403,87
M0085 Agreiphontes;23,77;37,66 @ 2,02 / New income: 4427,64
M0074 Acidalia;56,53;96,27 @ 2,04 / New income: 4484,17
M0006 Antaios;40,12;70,86 @ 2,05 / New income: 4524,29
M0043 Mut;10,36;18,44 @ 2,06 / New income: 4534,65
M0017 Buto;23,94;43,14 @ 2,07 / New income: 4558,58
M0028 Isis;11,58;21,18 @ 2,07 / New income: 4570,16
M0036 Kuk;12,06;23,85 @ 2,08 / New income: 4582,21
M0052 Ptah;48,01;96,42 @ 2,10 / New income: 4630,22
M0003 Amun;29,60;63,41 @ 2,11 / New income: 4659,83
M0008 Anuket;30,70;70,67 @ 2,13 / New income: 4690,52
M0091 Aigiokhos;21,90;52,66 @ 2,14 / New income: 4712,42
M0016 Bat;16,21;45,04 @ 2,15 / New income: 4728,63
M0002 Amon;29,15;81,93 @ 2,17 / New income: 4757,78
M0081 Agne;34,67;99,85 @ 2,19 / New income: 4792,45
M0064 Seth;25,24;78,68 @ 2,20 / New income: 4817,69
M0079 Ageleia;28,19;90,15 @ 2,22 / New income: 4845,89
M0018 Duamutef;11,04;35,51 @ 2,23 / New income: 4856,93
M0051 Osiris;25,39;82,20 @ 2,25 / New income: 4882,32
M0099 Aktaios;11,54;39,06 @ 2,25 / New income: 4893,86
M0066 Shu;20,68;75,09 @ 2,27 / New income: 4914,54
M0075 Aello;27,16;98,92 @ 2,29 / New income: 4941,70
M0001 Amen;25,96;94,61 @ 2,31 / New income: 4967,67
M0055 Renenet;19,51;72,65 @ 2,32 / New income: 4987,18
M0015 Bastet;10,44;46,51 @ 2,33 / New income: 4997,62
M0049 Nun;16,94;81,05 @ 2,35 / New income: 5014,56
M0023 Hauhet;19,46;96,85 @ 2,37 / New income: 5034,03
M0029 Kauket;13,14;66,25 @ 2,38 / New income: 5047,17
M0038 Ma'at;16,54;99,64 @ 2,40 / New income: 5063,71
M0067 Shu;9,83;65,60 @ 2,41 / New income: 5073,54
M0078 Agdistis;11,56;97,77 @ 2,43 / New income: 5085,10
M0013 Aton;5,81;57,38 @ 2,44 / New income: 5090,91
M0098 Akraia;5,20;57,44 @ 2,46 / New income: 5096,10
M0097 Akesios;1,36;82,16 @ 2,47 / New income: 5097,46

Avec le jeu en entier:

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
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
 
Time taken: 38031ms
Duration: 2.155770859925043 days.
---
M0231 Ekstatophoros;48,03;0,26 @ 0,05 / New income: 53,03
M0083 Agreia;71,33;1,37 @ 0,08 / New income: 124,37
M0311 Hermes;89,36;3,58 @ 0,11 / New income: 213,72
M0309 Herakles;63,95;4,03 @ 0,12 / New income: 277,67
M0258 Euanthes;99,21;7,04 @ 0,15 / New income: 376,88
M0132 Antimachos;92,67;7,43 @ 0,17 / New income: 469,55
M0139 Apollo;60,16;6,04 @ 0,18 / New income: 529,71
M0159 Aspheleios;82,53;8,96 @ 0,20 / New income: 612,24
M0076 Aesculapius;40,15;4,63 @ 0,21 / New income: 652,39
M0162 Athene;68,41;8,36 @ 0,22 / New income: 720,80
M0295 Hagnos;89,17;11,36 @ 0,24 / New income: 809,97
M0312 HerosTheos;70,68;9,02 @ 0,25 / New income: 880,65
M0246 Epitragidia;15,56;2,04 @ 0,25 / New income: 896,21
M0072 Tem;58,37;8,93 @ 0,26 / New income: 954,58
M0272 Euterpe;79,63;12,20 @ 0,27 / New income: 1034,22
M0040 Meretseger;61,15;9,51 @ 0,28 / New income: 1095,36
M0209 Delios;54,32;9,01 @ 0,29 / New income: 1149,68
M0200 Custos;72,87;12,15 @ 0,30 / New income: 1222,55
M0058 Seb;56,25;9,50 @ 0,31 / New income: 1278,80
M0107 Alexikakos;93,21;16,48 @ 0,32 / New income: 1372,01
M0144 Areopagite;75,10;13,40 @ 0,33 / New income: 1447,10
M0237 Enodios;81,30;15,41 @ 0,34 / New income: 1528,40
M0262 Euios;5,15;0,99 @ 0,34 / New income: 1533,55
M0323 Hippothoe;89,34;17,58 @ 0,35 / New income: 1622,90
M0285 giants;71,94;14,64 @ 0,36 / New income: 1694,84
M0069 Sobek;65,87;14,16 @ 0,37 / New income: 1760,71
M0260 Eubouleus;82,08;18,44 @ 0,38 / New income: 1842,80
M0274 Fortuna;18,23;4,17 @ 0,38 / New income: 1861,03
M0127 Anthroporraistes;49,54;11,66 @ 0,39 / New income: 1910,57
M0050 Nut;61,28;15,32 @ 0,40 / New income: 1971,84
M0041 Min;40,25;10,17 @ 0,40 / New income: 2012,09
M0062 Serket;27,57;7,15 @ 0,41 / New income: 2039,66
M0037 Maahes;19,74;5,14 @ 0,41 / New income: 2059,40
M0316 Hiksios;83,07;21,63 @ 0,42 / New income: 2142,47
M0080 Aglauros;74,58;19,61 @ 0,43 / New income: 2217,06
M0087 Agrios;90,34;24,92 @ 0,44 / New income: 2307,40
M0293 Gynnis;47,17;13,10 @ 0,45 / New income: 2354,57
M0070 Sokar;90,88;25,83 @ 0,46 / New income: 2445,46
M0182 Bythios;16,34;4,66 @ 0,46 / New income: 2461,80
M0302 Hekatos;69,10;19,84 @ 0,47 / New income: 2530,90
M0226 Doris;47,34;13,69 @ 0,47 / New income: 2578,23
M0056 Sakhmet;76,63;22,20 @ 0,48 / New income: 2654,86
M0177 Boulaia;69,57;20,76 @ 0,49 / New income: 2724,43
M0208 Delia;91,49;28,06 @ 0,50 / New income: 2815,92
M0044 Naunet;49,20;15,11 @ 0,50 / New income: 2865,12
M0300 Hegemonios;70,71;22,61 @ 0,51 / New income: 2935,83
M0112 Ambidexter;54,78;17,83 @ 0,52 / New income: 2990,61
M0141 Areia;33,92;11,20 @ 0,52 / New income: 3024,53
M0088 Agrotera;50,96;17,77 @ 0,53 / New income: 3075,50
M0266 Eumache;74,75;26,28 @ 0,54 / New income: 3150,25
M0011 Astarte;73,18;26,94 @ 0,54 / New income: 3223,42
M0220 Dindymene;89,23;32,92 @ 0,55 / New income: 3312,65
M0151 Aristomache;37,00;14,09 @ 0,56 / New income: 3349,66
M0161 Astraeos;71,31;27,38 @ 0,57 / New income: 3420,97
M0210 Delphic;81,64;31,85 @ 0,58 / New income: 3502,61
M0165 Axios;97,85;38,23 @ 0,59 / New income: 3600,46
M0308 Heraios;58,56;23,37 @ 0,59 / New income: 3659,02
M0061 Serapis;88,96;36,82 @ 0,60 / New income: 3747,97
M0048 Nephthys;83,33;34,83 @ 0,61 / New income: 3831,30
M0169 Basileus;52,65;22,02 @ 0,62 / New income: 3883,96
M0277 Galea;98,05;42,19 @ 0,63 / New income: 3982,01
M0216 Despoina;85,52;38,52 @ 0,64 / New income: 4067,53
M0288 Gorgons;88,37;40,04 @ 0,65 / New income: 4155,90
M0033 Khnemu;97,00;45,24 @ 0,66 / New income: 4252,90
M0000 Amaunet;51,14;26,13 @ 0,67 / New income: 4304,04
M0135 Aoide;99,34;51,02 @ 0,68 / New income: 4403,38
M0020 Hapi;99,57;51,23 @ 0,69 / New income: 4502,95
M0118 Anaxilea;71,27;37,62 @ 0,70 / New income: 4574,22
M0125 Antania;56,68;30,32 @ 0,70 / New income: 4630,90
M0256 Eris;66,42;35,75 @ 0,71 / New income: 4697,32
M0039 Mehen;49,03;26,73 @ 0,72 / New income: 4746,35
M0305 Hephaistia;72,65;39,93 @ 0,73 / New income: 4819,00
M0082 Agoraia;86,87;48,00 @ 0,74 / New income: 4905,87
M0321 Hippolyte;37,95;21,17 @ 0,74 / New income: 4943,82
M0101 Alasiotas;92,10;52,45 @ 0,75 / New income: 5035,92
M0264 Eukleia;95,33;54,69 @ 0,76 / New income: 5131,26
M0215 Derinoe;95,10;54,86 @ 0,77 / New income: 5226,36
M0024 Heket;65,56;38,05 @ 0,78 / New income: 5291,92
M0110 Alkaia;86,97;51,21 @ 0,79 / New income: 5378,90
M0286 Gigantophonos;32,48;19,51 @ 0,79 / New income: 5411,37
M0042 Mnewer;64,06;38,50 @ 0,80 / New income: 5475,43
M0109 Aliterios;41,20;24,78 @ 0,81 / New income: 5516,63
M0009 Apep;71,88;43,30 @ 0,81 / New income: 5588,52
M0096 Aithuia;87,00;53,50 @ 0,82 / New income: 5675,51
M0035 Khonsu;16,77;10,54 @ 0,82 / New income: 5692,28
M0218 Dimeter;63,03;39,65 @ 0,83 / New income: 5755,32
M0073 Thoth;95,19;60,08 @ 0,84 / New income: 5850,51
M0034 Khnum;79,56;51,11 @ 0,85 / New income: 5930,07
M0229 Echidna;70,79;45,76 @ 0,86 / New income: 6000,86
M0010 Apis;59,47;38,56 @ 0,86 / New income: 6060,33
M0065 Shai;55,55;36,57 @ 0,87 / New income: 6115,87
M0156 Artemis;61,98;42,27 @ 0,88 / New income: 6177,85
M0275 Gaia;32,03;22,03 @ 0,88 / New income: 6209,89
M0155 Arsenothelys;63,38;44,60 @ 0,89 / New income: 6273,26
M0148 Argus;90,50;66,00 @ 0,90 / New income: 6363,76
M0273 Fates;91,52;67,70 @ 0,91 / New income: 6455,28
M0291 griffin;34,41;25,64 @ 0,91 / New income: 6489,69
M0158 Asklepios;29,45;22,67 @ 0,92 / New income: 6519,14
M0092 Aigletes;70,56;54,40 @ 0,93 / New income: 6589,69
M0230 Eiraphiotes;39,96;30,85 @ 0,93 / New income: 6629,66
M0206 Deianeira;78,68;61,43 @ 0,94 / New income: 6708,34
M0031 Khensu;89,73;70,21 @ 0,95 / New income: 6798,07
M0192 Choreutes;85,48;66,98 @ 0,96 / New income: 6883,55
M0179 Bremusa;33,59;26,44 @ 0,96 / New income: 6917,15
M0255 Eriphos;63,08;49,84 @ 0,97 / New income: 6980,23
M0232 Eleemon;26,06;20,61 @ 0,97 / New income: 7006,29
M0120 Andromache;79,36;63,18 @ 0,98 / New income: 7085,65
M0222 Dionysos;74,66;59,71 @ 0,99 / New income: 7160,31
M0134 Antiopeia;47,91;38,35 @ 1,00 / New income: 7208,23
M0254 Eriounios;76,81;61,67 @ 1,01 / New income: 7285,04
M0245 Epipontia;99,36;80,70 @ 1,02 / New income: 7384,40
M0100 Alalkomene;27,80;22,61 @ 1,02 / New income: 7412,20
M0093 Aigobolos;53,29;43,52 @ 1,03 / New income: 7465,49
M0289 Gorgopis;52,11;42,67 @ 1,03 / New income: 7517,60
M0196 Clio;97,91;80,83 @ 1,04 / New income: 7615,51
M0163 Auxites;86,17;72,70 @ 1,05 / New income: 7701,68
M0025 Horus;84,65;71,51 @ 1,06 / New income: 7786,33
M0319 Hippios;83,61;71,42 @ 1,07 / New income: 7869,94
M0026 Huh;63,06;53,88 @ 1,08 / New income: 7933,00
M0292 Gynaikothoinas;16,72;14,34 @ 1,08 / New income: 7949,71
M0071 Tefnut;29,10;24,99 @ 1,08 / New income: 7978,81
M0199 Crataeis;66,89;57,62 @ 1,09 / New income: 8045,70
M0054 Re;75,35;65,86 @ 1,10 / New income: 8121,06
M0265 Eukles;84,45;74,33 @ 1,11 / New income: 8205,51
M0183 Caliope;95,18;84,57 @ 1,12 / New income: 8300,69
M0124 Antandre;74,91;66,60 @ 1,12 / New income: 8375,61
M0190 Chloe;55,29;49,48 @ 1,13 / New income: 8430,90
M0150 Aristaios;91,84;82,38 @ 1,14 / New income: 8522,74
M0152 Arkhegetes;77,27;69,32 @ 1,15 / New income: 8600,01
M0022 Hathor;85,71;77,00 @ 1,16 / New income: 8685,71
M0187 Charidotes;61,63;56,25 @ 1,16 / New income: 8747,34
M0217 Dikerotes;18,12;16,58 @ 1,17 / New income: 8765,46
M0128 Antianara;80,41;73,79 @ 1,17 / New income: 8845,87
M0032 Khepri;81,30;76,65 @ 1,18 / New income: 8927,17
M0068 Sia;61,63;58,22 @ 1,19 / New income: 8988,80
M0089 Aguieus;82,02;77,72 @ 1,20 / New income: 9070,83
M0252 Erinus;78,93;74,80 @ 1,21 / New income: 9149,76
M0014 Atum;86,33;81,98 @ 1,21 / New income: 9236,09
M0240 Enualios;99,97;95,24 @ 1,23 / New income: 9336,06
M0145 Ares;51,95;49,69 @ 1,23 / New income: 9388,00
M0283 Geryon;97,99;94,45 @ 1,24 / New income: 9485,99
M0296 Haides;77,05;74,42 @ 1,25 / New income: 9563,04
M0213 Dendrites;64,20;62,24 @ 1,25 / New income: 9627,24
M0045 Nefertem;53,07;51,60 @ 1,26 / New income: 9680,31
M0241 Eos;93,53;91,27 @ 1,27 / New income: 9773,84
M0095 Ainippe;99,04;97,00 @ 1,28 / New income: 9872,88
M0059 Seker;79,39;78,09 @ 1,29 / New income: 9952,27
M0194 Chthonios;65,08;65,33 @ 1,29 / New income: 10017,35
M0053 Ra;45,72;46,11 @ 1,30 / New income: 10063,07
M0219 Dimorphos;75,34;76,02 @ 1,31 / New income: 10138,41
M0057 Satet;80,77;81,88 @ 1,31 / New income: 10219,17
M0021 Har-pa-khered;42,12;42,84 @ 1,32 / New income: 10261,29
M0012 Aten;83,24;85,10 @ 1,33 / New income: 10344,53
M0239 Enorches;80,73;82,62 @ 1,33 / New income: 10425,26
M0287 Glaukopis;51,13;52,81 @ 1,34 / New income: 10476,39
M0314 Hestia;74,06;76,64 @ 1,35 / New income: 10550,46
M0171 Bassareus;64,76;67,49 @ 1,35 / New income: 10615,22
M0212 Demeter;36,92;39,03 @ 1,36 / New income: 10652,14
M0063 Set;77,36;82,23 @ 1,36 / New income: 10729,49
M0094 Ainia;90,14;96,70 @ 1,37 / New income: 10819,64
M0047 Nekhbet;37,29;40,50 @ 1,38 / New income: 10856,92
M0181 Byblis;71,87;78,23 @ 1,38 / New income: 10928,79
M0227 Dryope;43,18;47,37 @ 1,39 / New income: 10971,97
M0290 Graiae;30,37;33,34 @ 1,39 / New income: 11002,34
M0238 Enoplios;22,88;25,37 @ 1,39 / New income: 11025,22
M0149 Aridnus;81,52;90,72 @ 1,40 / New income: 11106,74
M0307 Hera;88,36;98,41 @ 1,41 / New income: 11195,10
M0160 Asteria;82,29;91,68 @ 1,42 / New income: 11277,39
M0046 Neith;79,65;88,84 @ 1,43 / New income: 11357,04
M0249 Ergane;45,89;51,48 @ 1,43 / New income: 11402,93
M0004 Anat;63,45;71,43 @ 1,44 / New income: 11466,38
M0102 Alcibie;59,50;67,10 @ 1,44 / New income: 11525,89
M0306 Hephaistos;68,32;77,28 @ 1,45 / New income: 11594,20
M0236 Enodia;77,55;87,85 @ 1,46 / New income: 11671,76
M0103 Alcinoe;39,68;44,98 @ 1,46 / New income: 11711,43
M0304 Hellotis;10,45;11,87 @ 1,46 / New income: 11721,88
M0086 Agreus;60,78;69,31 @ 1,47 / New income: 11782,66
M0154 Arretos;24,45;27,99 @ 1,47 / New income: 11807,11
M0153 Arktos;61,69;71,47 @ 1,48 / New income: 11868,79
M0244 Epikourios;73,81;85,65 @ 1,49 / New income: 11942,61
M0193 Choroplekes;21,89;25,53 @ 1,49 / New income: 11964,50
M0030 Kebechsenef;54,05;63,99 @ 1,49 / New income: 12018,55
M0269 Euros;15,40;18,31 @ 1,49 / New income: 12033,95
M0228 Echephyle;12,91;15,35 @ 1,50 / New income: 12046,86
M0178 Boulaios;62,53;74,68 @ 1,50 / New income: 12109,38
M0147 Areximacha;44,24;53,03 @ 1,51 / New income: 12153,62
M0297 Harmothoe;74,50;89,84 @ 1,51 / New income: 12228,12
M0138 Aphrodite;79,25;95,99 @ 1,52 / New income: 12307,37
M0243 Epidotes;49,55;60,48 @ 1,53 / New income: 12356,92
M0146 Areto;55,01;67,47 @ 1,53 / New income: 12411,93
M0166 AxiosTauros;63,90;79,89 @ 1,54 / New income: 12475,83
M0184 Cedreatis;37,94;47,70 @ 1,54 / New income: 12513,77
M0060 Sekhmet;41,49;52,50 @ 1,55 / New income: 12555,25
M0235 Ennosigaios;78,24;99,00 @ 1,55 / New income: 12633,49
M0301 Hekate;5,49;6,98 @ 1,55 / New income: 12638,99
M0164 Avaris;57,91;73,64 @ 1,56 / New income: 12696,90
M0276 Gaieokhos;69,45;88,32 @ 1,57 / New income: 12766,34
M0133 Antiope;59,45;76,06 @ 1,57 / New income: 12825,79
M0168 Bakchos;53,11;68,29 @ 1,58 / New income: 12878,90
M0172 Bauros;68,69;90,51 @ 1,59 / New income: 12947,59
M0119 Androdameia;71,83;94,68 @ 1,59 / New income: 13019,42
M0294 Hagisilaos;14,41;19,15 @ 1,59 / New income: 13033,83
M0142 Areia;53,24;70,92 @ 1,60 / New income: 13087,07
M0121 Andromeda;65,05;87,85 @ 1,61 / New income: 13152,12
M0084 Agreie;68,99;94,05 @ 1,61 / New income: 13221,11
M0203 Cyclops;32,00;43,76 @ 1,62 / New income: 13253,11
M0189 Chimera;26,54;36,42 @ 1,62 / New income: 13279,65
M0248 Erato;28,22;38,82 @ 1,62 / New income: 13307,87
M0315 Heteira;49,63;69,46 @ 1,63 / New income: 13357,50
M0077 Agathe;50,65;70,92 @ 1,63 / New income: 13408,15
M0007 Anubis;62,52;87,91 @ 1,64 / New income: 13470,67
M0027 Imset;47,51;66,84 @ 1,64 / New income: 13518,17
M0116 Anaea;42,24;59,85 @ 1,65 / New income: 13560,41
M0313 Hersos;23,81;33,86 @ 1,65 / New income: 13584,22
M0090 Aidoneus;44,09;63,34 @ 1,66 / New income: 13628,30
M0322 Hippomache;29,25;43,08 @ 1,66 / New income: 13657,55
M0143 Areion;25,37;37,37 @ 1,66 / New income: 13682,92
M0019 Duamutef;29,89;44,55 @ 1,67 / New income: 13712,81
M0259 Euaster;56,30;84,62 @ 1,67 / New income: 13769,11
M0005 Anqet;58,46;88,39 @ 1,68 / New income: 13827,56
M0140 Apotropaios;23,33;35,63 @ 1,68 / New income: 13850,89
M0185 Celaneo;62,15;96,27 @ 1,69 / New income: 13913,03
M0298 harpy;61,86;96,17 @ 1,69 / New income: 13974,90
M0085 Agreiphontes;23,77;37,66 @ 1,70 / New income: 13998,67
M0284 Gethosynos;56,60;90,22 @ 1,70 / New income: 14055,27
M0299 Hegemone;48,69;77,70 @ 1,71 / New income: 14103,95
M0174 Boreas;53,28;86,08 @ 1,72 / New income: 14157,23
M0105 Alcis;36,87;60,96 @ 1,72 / New income: 14194,10
M0225 Dithyrambos;18,84;31,25 @ 1,72 / New income: 14212,94
M0234 Eleutherios;38,16;63,76 @ 1,73 / New income: 14251,10
M0282 Genetullis;16,48;27,78 @ 1,73 / New income: 14267,58
M0198 cockatrice;50,68;85,56 @ 1,73 / New income: 14318,26
M0074 Acidalia;56,53;96,27 @ 1,74 / New income: 14374,79
M0104 Alcippe;33,25;56,68 @ 1,74 / New income: 14408,03
M0204 Daphnaia;51,56;87,93 @ 1,75 / New income: 14459,59
M0318 Hippia;47,03;81,39 @ 1,76 / New income: 14506,62
M0006 Antaios;40,12;70,86 @ 1,76 / New income: 14546,74
M0043 Mut;10,36;18,44 @ 1,76 / New income: 14557,10
M0017 Buto;23,94;43,14 @ 1,77 / New income: 14581,04
M0129 Antianeira;37,06;67,35 @ 1,77 / New income: 14618,10
M0224 Dissotokos;52,07;95,20 @ 1,78 / New income: 14670,17
M0028 Isis;11,58;21,18 @ 1,78 / New income: 14681,74
M0117 Anax;29,01;54,23 @ 1,78 / New income: 14710,75
M0108 Aligena;23,98;47,16 @ 1,79 / New income: 14734,73
M0036 Kuk;12,06;23,85 @ 1,79 / New income: 14746,79
M0221 Dioktoros;47,19;94,37 @ 1,79 / New income: 14793,98
M0052 Ptah;48,01;96,42 @ 1,80 / New income: 14841,99
M0207 Deinomache;40,84;84,69 @ 1,81 / New income: 14882,83
M0130 Antibrote;45,82;95,47 @ 1,81 / New income: 14928,65
M0180 Bromios;32,67;69,24 @ 1,82 / New income: 14961,32
M0281 Genetor;29,50;62,92 @ 1,82 / New income: 14990,81
M0003 Amun;29,60;63,41 @ 1,82 / New income: 15020,42
M0136 Apatouria;44,76;98,91 @ 1,83 / New income: 15065,18
M0263 Eukhaitos;30,98;69,34 @ 1,84 / New income: 15096,16
M0261 Euboulos;37,83;86,57 @ 1,84 / New income: 15133,99
M0113 Ambologera;27,92;64,22 @ 1,85 / New income: 15161,91
M0008 Anuket;30,70;70,67 @ 1,85 / New income: 15192,61
M0271 Euryleia;31,56;74,05 @ 1,86 / New income: 15224,16
M0106 Alea;24,58;58,09 @ 1,86 / New income: 15248,75
M0091 Aigiokhos;21,90;52,66 @ 1,86 / New income: 15270,64
M0191 Chloris;13,76;35,46 @ 1,87 / New income: 15284,41
M0280 Gamostolos;11,39;30,62 @ 1,87 / New income: 15295,80
M0131 Antimache;30,89;83,70 @ 1,87 / New income: 15326,69
M0126 Antheus;36,27;98,73 @ 1,88 / New income: 15362,96
M0250 Eribromios;9,06;25,15 @ 1,88 / New income: 15372,02
M0016 Bat;16,21;45,04 @ 1,88 / New income: 15388,23
M0002 Amon;29,15;81,93 @ 1,89 / New income: 15417,37
M0270 Eurybe;34,21;98,13 @ 1,90 / New income: 15451,58
M0081 Agne;34,67;99,85 @ 1,90 / New income: 15486,25
M0175 Botryophoros;14,79;45,01 @ 1,90 / New income: 15501,05
M0253 Eriobea;21,52;65,96 @ 1,91 / New income: 15522,57
M0202 Cybele;27,72;85,77 @ 1,91 / New income: 15550,28
M0279 Gamelios;30,87;95,62 @ 1,92 / New income: 15581,15
M0064 Seth;25,24;78,68 @ 1,93 / New income: 15606,40
M0268 Euplois;19,53;62,11 @ 1,93 / New income: 15625,93
M0176 Boukeros;26,23;83,76 @ 1,94 / New income: 15652,15
M0079 Ageleia;28,19;90,15 @ 1,94 / New income: 15680,35
M0018 Duamutef;11,04;35,51 @ 1,94 / New income: 15691,39
M0188 Charybdis;23,61;76,20 @ 1,95 / New income: 15715,00
M0051 Osiris;25,39;82,20 @ 1,95 / New income: 15740,39
M0223 Discordia;24,20;79,60 @ 1,96 / New income: 15764,59
M0099 Aktaios;11,54;39,06 @ 1,96 / New income: 15776,13
M0115 Anaduomene;10,70;36,41 @ 1,96 / New income: 15786,83
M0247 Epitumbidia;28,02;99,25 @ 1,97 / New income: 15814,85
M0066 Shu;20,68;75,09 @ 1,97 / New income: 15835,54
M0075 Aello;27,16;98,92 @ 1,98 / New income: 15862,69
M0001 Amen;25,96;94,61 @ 1,99 / New income: 15888,66
M0123 Anosia;22,79;84,78 @ 1,99 / New income: 15911,45
M0233 Eleuthereus;18,62;69,32 @ 2,00 / New income: 15930,07
M0055 Renenet;19,51;72,65 @ 2,00 / New income: 15949,58
M0137 Aphneius;19,15;72,04 @ 2,01 / New income: 15968,73
M0157 Asclepius;17,80;68,82 @ 2,01 / New income: 15986,53
M0122 Androphonos;19,29;83,52 @ 2,01 / New income: 16005,82
M0211 Delphinios;4,42;19,41 @ 2,02 / New income: 16010,24
M0015 Bastet;10,44;46,51 @ 2,02 / New income: 16020,69
M0170 Basilis;7,97;35,89 @ 2,02 / New income: 16028,65
M0049 Nun;16,94;81,05 @ 2,03 / New income: 16045,60
M0317 Hipp;4,58;22,10 @ 2,03 / New income: 16050,18
M0023 Hauhet;19,46;96,85 @ 2,03 / New income: 16069,64
M0029 Kauket;13,14;66,25 @ 2,04 / New income: 16082,79
M0111 Amaltheia;12,11;66,55 @ 2,04 / New income: 16094,90
M0205 Daphnephoros;14,30;85,48 @ 2,05 / New income: 16109,20
M0038 Ma'at;16,54;99,64 @ 2,05 / New income: 16125,74
M0303 Helios;13,41;81,51 @ 2,06 / New income: 16139,15
M0310 Herkeios;15,39;96,15 @ 2,06 / New income: 16154,54
M0067 Shu;9,83;65,60 @ 2,07 / New income: 16164,37
M0114 Amynomene;13,90;92,97 @ 2,07 / New income: 16178,28
M0267 Eunemos;14,32;96,68 @ 2,08 / New income: 16192,59
M0197 Clyemne;9,26;67,47 @ 2,08 / New income: 16201,85
M0167 Bakcheios;11,37;87,63 @ 2,09 / New income: 16213,21
M0078 Agdistis;11,56;97,77 @ 2,10 / New income: 16224,78
M0195 Clete;8,15;77,79 @ 2,10 / New income: 16232,92
M0013 Aton;5,81;57,38 @ 2,10 / New income: 16238,73
M0201 Cybebe;7,94;87,13 @ 2,11 / New income: 16246,68
M0098 Akraia;5,20;57,44 @ 2,11 / New income: 16251,87
M0173 Boophis;7,73;94,91 @ 2,12 / New income: 16259,60
M0320 HippoiAthanatoi;6,31;79,58 @ 2,12 / New income: 16265,90
M0257 Eros;7,60;98,25 @ 2,13 / New income: 16273,50
M0251 Erigdoupos;5,20;70,45 @ 2,13 / New income: 16278,71
M0186 Cerberus;5,14;72,69 @ 2,14 / New income: 16283,85
M0242 Epaine;3,47;98,43 @ 2,14 / New income: 16287,32
M0214 Derimacheia;0,61;23,09 @ 2,15 / New income: 16287,93
M0097 Akesios;1,36;82,16 @ 2,15 / New income: 16289,29
M0278 Gamelia;0,33;79,67 @ 2,16 / New income: 16289,61

Echantillon 101 - 324 (+220%), Temps 2438ms - 38031ms (+1460%). 8O :?

Assez efficace mais la complexité n'a pas l'air linéaire.

11/07/2011, 16h39
Alikendarfen

A noter de plus qu'on obtient le même résultat (2.4714707568379404) par l'algo par insertion ~~avec~~ sans remise... mais en 1,8 secondes. ;)

C'est simplement un cas où cet algo tombe juste... :?
11/07/2011, 16h54
Alikendarfen

Du coup, j'ai fait le test avec les 324 mines aussi.

Algo par insertion avec remise o(n3) :
- 2.1556776803280098 jours
- 210 secondes en temps de calcul (on commence à atteindre les limites de cet algo)

Algo par insertion sans remise o(n2) :
- 2.1556776803280098 jours (aussi, mais c'est par hasard)
- 3,16 secondes

... donc c'est un petit peu mieux que les AG (2.155770859925043) !

J'ai lancé l'algo avec dominance et optimalité 2 à 2... ça tourne encore...

(note : pour ceux qui n'étaient pas là avant, les deux algos par insertion ne sont pas exacts : voir les stat plubliées précédemment)
11/07/2011, 18h53
Baruch

Bon je pense avoir trouvé quelque chose de très intéressant ^^ :

Je me ramène encore avec mon histoire d'idéalité 2 à 2. Ou plutôt, j'utilise cette propriété :

Pour tout couple de mines (M1,M2), on a une valeur p* = (c2-c1) / (c1/p1 - c2/p2) telle que :

Soit p la production juste avant l'occurrence du couple,

p >= p* <=> la mine la plus rentable du couple doit être placée avant

On peut donc calculer une matrice contenant toutes les valeurs de p* (en n²).
On trouve le maximum Pmax de cette matrice.

Supposons qu'on ait un algorithme qui construit la liste idéale en ajoutant progressivement les mines à la fin d'un chemin, l'algorithme naïf par exemple, ou l'algo par combinaisons.
Une fois que la production du chemin dépasse Pmax, chaque couple de mines possible est ordonné par rentabilité. Il suffit donc de trier l'ensemble de mines restant par rentabilité décroissante.
Ca fait gagner beaucoup de temps je pense, surtout dans des cas où le Pmax est atteint rapidement. Bien entendu, certains trouveront des exemples où ce n'est pas efficace.

Quelques précisions :

Quand on construit la matrice des p*, on y voit des nombres positifs, négatifs (pas gênant), mais aussi des valeurs infinies. Ces infinis apparaissent si 2 mines ont la même rentabilité (cf l'expression de p*).

Comment ordonner 2 mines qui ont la même rentabilité ? On les ordonne par production croissante (ou par coût croissant, ça revient au même).

Donc dans le calcul de Pmax, il faut éliminer les infinis, pour que Pmax soit un réel.
Et dans le tri des mines restantes, on trie par rentabilité décroissante, puis par production croissante.

On peut éventuellement penser à recalculer Pmax à chaque fois que l'ensemble des mines restantes est réduit.
12/07/2011, 08h54
Alikendarfen

Bon, dans la pratique, cette idée est un précalcul pour éviter de faire à chaque fois ce que j'indiquais plus haut. A savoir :

Citation:

Etant donné un chemin en cours d'évaluation Ei = E(i-1) + M1,

On tente d'ajouter M2 à ce chemin.

Si T( E(i-1) + M1 + M2 ) > T( E(i-1) + M2 + M1 ), alors on laisse tomber la branche d'exploration Ei + M2.

Mais sinon, c'est le même algo : même complexité.

C'est une bonne piste, cependant on n'a pas besoin de Pmax (ni surtout de le recalculer) :

Dans le cadre de l'algo naïf (avec ou sans dominances), on peut simplement se contenter de comparer la production courante pc avant M1 (voir citation) avec p*(M1M2) précalculée dans le tableau : pc >= p*(M1M2) ou pas.
12/07/2011, 08h59
Alikendarfen

Une anecdote :

Je vous disais hier que je testerai l'algo avec dominances et optimalité 2 à 2 sur les 334 mines...

... et bien c'est fait ! :aie:

Après quelques heures mon pc avait trop chauffé et m'a fait un joli shut down tout seul... !

Donc, je peux seulement dire trois trucs :
- La dernière fois que j'ai regardé où ça en était, il avait calculé plus de 115 millions de chemins intermédiaires
- Il faut plus de 4 heures de calcul
- Je ne recommencerai pas !
12/07/2011, 10h01
elentarion

L'informatique, c'est magique.

Alors que je tripatouillais un peu les paramètres de mon algo génétique pour augmenter sa précision et/ou ses performances, j'ai découvert un moyen incongru d'augmenter les performances :

Augmenter le nombre de calculs ! 8O Plus précisément augmenter le nombre de swaps dans la fonction de reproduction.

Avant, je faisais un nombre de test entre 1 et N/20 (avec N le nombre total de mines. En en faisant 10x plus - entre 1 et N/2, je passe de 28 secondes à 6 secondes de calcul ! 8O

Quelqu'un aurait une idée du pourquoi ? Le nombre de génération et le nombre d'individu reste le même donc le temps de calcul devrais logiquement être supérieur ... à moins d'un bug. :roll:
12/07/2011, 10h11
Alikendarfen

Citation:

Envoyé par elentarion

Quelqu'un aurait une idée du pourquoi ? Le nombre de génération et le nombre d'individu reste le même donc le temps de calcul devrais logiquement être supérieur ... à moins d'un bug. :roll:

... je voterais pour une autre modif que tu as peut-être faite par ailleurs ??

Citation:

Envoyé par elentarion

L'informatique, c'est magique.

J'aimerais bien aussi :mrgreen:

Encore plus surprenant, le temps de calcul varie selon les données : j'ai fait un nouveau jeu d'essai avec le même nombre de mines mais avec un coût et une production suivant une distribution normale (100, 15) et (75, 15) respectivement.

Le temps de calcul passe de six secondes à 10 secondes ...

J'ai du rater quelque chose d'important.

Le jeu d'essai:

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
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
 
M0000 Amaunet;102.48801362907305;57.942857533946835
M0001 Amen;128.40025554000925;79.74181210282852
M0002 Amon;105.00899864315096;52.96704093034225
M0003 Amun;104.32366859748663;40.07760851409758
M0004 Anat;98.96945583561659;101.57663361272316
M0005 Anqet;93.105541323595;89.4792025579639
M0006 Antaios;93.71868639120633;93.74453542735665
M0007 Anubis;82.96907849348905;60.91854360137958
M0008 Anuket;114.782805668181;64.5416116980936
M0009 Apep;100.58485078713392;68.1136310384104
M0010 Apis;127.19295197446309;71.92576310187964
M0011 Astarte;96.77609521579434;48.441395007137324
M0012 Aten;138.85640514732492;61.032328848454966
M0013 Aton;109.86420498436064;82.24016314838713
M0014 Atum;98.54305056878191;56.37111187180362
M0015 Bastet;109.07388884660317;69.5545547357196
M0016 Bat;78.34283824848862;87.40286427266037
M0017 Buto;88.86905285539342;66.06746108962928
M0018 Duamutef;116.93767946329598;73.35250486457808
M0019 Duamutef;117.45410031436697;85.52261613742523
M0020 Hapi;100.58895399715848;85.51156859897473
M0021 Har-pa-khered;95.08777805140751;72.55493984012661
M0022 Hathor;67.9522918647342;74.8429260491579
M0023 Hauhet;92.1729241025643;71.80477853209185
M0024 Heket;90.60732342734727;108.12808141548155
M0025 Horus;108.83623902898876;84.58917382972967
M0026 Huh;119.9474722715876;46.21913524944149
M0027 Imset;94.65803406358673;67.30830827148864
M0028 Isis;116.0454465455177;73.45283332643051
M0029 Kauket;85.11578021672085;78.427101366758
M0030 Kebechsenef;91.08636154029806;93.33075483085437
M0031 Khensu;102.82234056408086;72.4540816766324
M0032 Khepri;91.02895342393401;60.82352132950719
M0033 Khnemu;109.96703141452524;93.53636631672356
M0034 Khnum;100.17979196287243;98.33887272751035
M0035 Khonsu;58.52020354907337;53.69483278232087
M0036 Kuk;136.6484257300491;81.25029728462975
M0037 Maahes;85.40423734302237;79.33529607687781
M0038 Ma'at;86.09036358786528;69.20511655934055
M0039 Mehen;90.56877420645027;57.19706904212951
M0040 Meretseger;139.0284861149078;72.19956699755315
M0041 Min;101.37944518175408;49.641307866638144
M0042 Mnewer;102.5167645366947;63.75285978742439
M0043 Mut;130.38831145792975;87.829297930543
M0044 Naunet;97.20233923674162;71.49002315081204
M0045 Nefertem;112.5530511202879;56.54172963406421
M0046 Neith;120.91217693894342;68.97199668743406
M0047 Nekhbet;111.6736507957568;56.53574622332894
M0048 Nephthys;102.87819471246402;59.85487450728658
M0049 Nun;99.93059446402309;77.78857265532152
M0050 Nut;108.93364559814451;74.87184052133972
M0051 Osiris;101.3895421168153;72.46365781836607
M0052 Ptah;99.33170939867392;72.25680402115852
M0053 Ra;108.12308037245327;99.76488432288124
M0054 Re;99.48095981812324;87.32147206417231
M0055 Renenet;109.21372791119512;53.186576886578386
M0056 Sakhmet;104.41566705619086;57.563437543500314
M0057 Satet;115.16125028481005;91.21057004610572
M0058 Seb;88.09126918441507;82.66978213530638
M0059 Seker;104.02990429648801;89.69225802445774
M0060 Sekhmet;114.240471723528;56.81346001577505
M0061 Serapis;98.35413592954838;38.26896669929354
M0062 Serket;99.17506281080419;74.16901325831462
M0063 Set;96.36403091574834;63.47748192666046
M0064 Seth;102.05364833662304;56.40139333876174
M0065 Shai;119.09902698619734;73.48824618575955
M0066 Shu;103.99447991458965;52.48809549177046
M0067 Shu;96.52591921537888;64.66228182027486
M0068 Sia;85.50230797000935;76.0889287022208
M0069 Sobek;120.4138412042003;94.84161102936159
M0070 Sokar;104.69970452203063;67.37702709757717
M0071 Tefnut;78.70723697176757;45.322358641441795
M0072 Tem;115.38783385054998;86.07316697874224
M0073 Thoth;97.99320754465893;86.84390341848713
M0074 Acidalia;109.22551758908011;63.45015563408226
M0075 Aello;84.57684474853166;75.24435792786109
M0076 Aesculapius;95.65987613441237;61.464568608247
M0077 Agathe;95.56598828849317;83.53647167559309
M0078 Agdistis;92.8503368445634;81.93714893038762
M0079 Ageleia;79.15842874573946;103.18165999629599
M0080 Aglauros;102.33054252293758;73.17776628856315
M0081 Agne;114.14767080044217;73.0185544183377
M0082 Agoraia;90.30452042979863;44.13516804331747
M0083 Agreia;108.70211175785465;87.85129758757616
M0084 Agreie;121.26245009879197;90.69537598062718
M0085 Agreiphontes;102.22317279744095;71.26523482895254
M0086 Agreus;115.48144395114943;62.61282603591885
M0087 Agrios;112.81183958650344;77.21299111661588
M0088 Agrotera;80.24667259840231;67.97560101012851
M0089 Aguieus;108.3864585613296;39.00105700871913
M0090 Aidoneus;116.0119797175201;69.88361162509986
M0091 Aigiokhos;103.2967465762341;56.28455415265271
M0092 Aigletes;93.356982423771;77.74961217556408
M0093 Aigobolos;92.74497513558526;71.54922083745201
M0094 Ainia;112.7367839062929;81.61332043808002
M0095 Ainippe;81.2871261730794;93.87018442300646
M0096 Aithuia;93.92643168735587;65.72081002858874
M0097 Akesios;103.64105473780272;77.29577167450383
M0098 Akraia;91.67884236826166;37.36025800920678
M0099 Aktaios;113.84201886239943;64.22446035177353
M0100 Alalkomene;94.50014329615021;85.06936593143021
M0101 Alasiotas;97.64327538936561;84.93980841888205
M0102 Alcibie;110.46623260500486;81.09671531825575
M0103 Alcinoe;102.71842731945966;58.94546293018055
M0104 Alcippe;75.22423783879675;71.10257577639419
M0105 Alcis;104.26394736734804;73.03509115862752
M0106 Alea;115.51434924726222;85.10841552764643
M0107 Alexikakos;112.35216204434776;68.85509356963547
M0108 Aligena;100.32998745302596;53.64843305926282
M0109 Aliterios;96.45284234460657;66.72838939635949
M0110 Alkaia;95.08163431813426;85.34834983200557
M0111 Amaltheia;95.19322184742096;82.03432038279597
M0112 Ambidexter;83.76044047634177;64.94238577266569
M0113 Ambologera;92.29114926890395;76.94799483309014
M0114 Amynomene;114.00233828346124;96.18327959164158
M0115 Anaduomene;115.44905188935226;91.35560445993592
M0116 Anaea;95.09757662992429;69.98012733568477
M0117 Anax;103.51851568435856;76.85227449970566
M0118 Anaxilea;96.35584742403381;55.299535306129144
M0119 Androdameia;91.34302076985333;70.61173440620021
M0120 Andromache;71.32121449623298;76.91494914858109
M0121 Andromeda;121.78331328515215;64.01357585057416
M0122 Androphonos;99.38221352729639;71.46906445735489
M0123 Anosia;89.98694288106742;62.040745371081876
M0124 Antandre;111.78399750377582;66.04450136853715
M0125 Antania;98.27571999931503;78.08871611903359
M0126 Antheus;81.70569741467031;81.82528603091352
M0127 Anthroporraistes;103.4407526416353;73.72822744985424
M0128 Antianara;105.18706357908516;54.14278051629771
M0129 Antianeira;114.67940226032935;37.722202650175866
M0130 Antibrote;98.06270340540277;42.60612027657919
M0131 Antimache;96.365473494584;56.14995733606902
M0132 Antimachos;103.94194427664591;75.89819433634396
M0133 Antiope;110.1684099433576;79.98641608202101
M0134 Antiopeia;113.16817734404377;67.88760967937004
M0135 Aoide;93.91588348382763;89.92817090361653
M0136 Apatouria;90.547222727925;49.22777978347111
M0137 Aphneius;82.14399020549641;67.73864285133901
M0138 Aphrodite;93.2831763401302;77.0913876549472
M0139 Apollo;88.89505196269954;95.26866897592276
M0140 Apotropaios;102.95705670892822;79.87177762862933
M0141 Areia;115.00841246237961;81.06202250547366
M0142 Areia;100.55394942606411;67.90215669729531
M0143 Areion;113.85146119826084;73.98139623953269
M0144 Areopagite;90.54143726153077;75.88751834328704
M0145 Ares;115.69380294274416;83.67218229929844
M0146 Areto;90.37759895956859;84.39279426386233
M0147 Areximacha;67.02549475308233;100.86992008786562
M0148 Argus;72.63458441002403;108.31952054493276
M0149 Aridnus;110.77872379513786;92.67914302229468
M0150 Aristaios;102.32162397286086;76.1198497659073
M0151 Aristomache;112.67888762041122;56.15612681651051
M0152 Arkhegetes;88.85104988217753;28.49949915190235
M0153 Arktos;94.5356507185407;75.82660279817084
M0154 Arretos;98.63873195466633;84.11116804165047
M0155 Arsenothelys;109.48849894573007;78.86223695688133
M0156 Artemis;94.11189662752814;100.89086411405611
M0157 Asclepius;97.28686446415755;73.1265131521693
M0158 Asklepios;98.94533674495437;90.0971927711415
M0159 Aspheleios;99.9673548786021;85.37133576137391
M0160 Asteria;108.76615735331458;53.44990339254798
M0161 Astraeos;91.09369742175889;84.29469094557078
M0162 Athene;130.03325561104742;60.26348026026804
M0163 Auxites;102.34378637402153;56.474527570441
M0164 Avaris;101.44439858477512;83.18107209008777
M0165 Axios;91.26892083743012;44.63757132112444
M0166 AxiosTauros;106.2130205860859;57.65854809254423
M0167 Bakcheios;119.53412864598583;66.4124212279769
M0168 Bakchos;114.40163749571335;68.91669317723623
M0169 Basileus;93.34426039427115;73.18354980720498
M0170 Basilis;110.50967684706627;97.9388387062946
M0171 Bassareus;93.48189092655973;74.64973438439696
M0172 Bauros;118.96606317403058;59.74560872427166
M0173 Boophis;68.3331683836021;92.32348333858805
M0174 Boreas;75.80306802932346;96.59051031431096
M0175 Botryophoros;86.08285656286978;68.65859439899057
M0176 Boukeros;103.51479158841238;85.98172402308536
M0177 Boulaia;124.20528157745764;56.16070698542894
M0178 Boulaios;123.47873921975136;56.20140179437675
M0179 Bremusa;100.80497081172517;57.596677816797325
M0180 Bromios;107.10049003647583;87.07430969355961
M0181 Byblis;113.73878286881154;97.41838529117877
M0182 Bythios;104.4921925402634;81.66726894855807
M0183 Caliope;90.73513737781481;62.61341711885696
M0184 Cedreatis;80.92118453036906;66.43176952396315
M0185 Celaneo;92.6331400876387;87.30423992819495
M0186 Cerberus;98.89409250561916;60.28239508991844
M0187 Charidotes;97.73729065127912;64.8438127294806
M0188 Charybdis;91.19403618178822;72.50822472600896
M0189 Chimera;138.95904968598137;77.20063048920514
M0190 Chloe;73.88080118554879;68.41069107561258
M0191 Chloris;91.50883815555375;57.51816165229111
M0192 Choreutes;101.7155835685012;89.24585770028446
M0193 Choroplekes;103.32552927258067;75.47886898208765
M0194 Chthonios;96.89149742528677;57.959012196921606
M0195 Clete;108.32819697316773;56.567468101763055
M0196 Clio;120.16892318533895;80.83822694249929
M0197 Clyemne;96.28151319991409;71.21335075060684
M0198 cockatrice;70.51208711626073;78.96600055750555
M0199 Crataeis;82.16964494083382;95.05790335172046
M0200 Custos;100.02125109401722;69.62139829243905
M0201 Cybebe;105.43963848062963;75.18438700005942
M0202 Cybele;94.82959649548626;102.94240398671845
M0203 Cyclops;107.07061726107544;77.52463454546756
M0204 Daphnaia;106.28007972510204;76.46180595177748
M0205 Daphnephoros;110.12701519981212;62.99207878670998
M0206 Deianeira;104.42971060915639;73.91717786848528
M0207 Deinomache;97.10268182664822;85.64869530936933
M0208 Delia;104.38497809758799;81.73537542609675
M0209 Delios;125.49697158552385;82.24140492276256
M0210 Delphic;76.28344072215245;65.50586859272721
M0211 Delphinios;95.3668066512;73.80213347845326
M0212 Demeter;101.2614173807196;95.94122852858354
M0213 Dendrites;136.76232061096056;90.8860266586363
M0214 Derimacheia;91.24763007515665;59.81378143716739
M0215 Derinoe;87.14375758185864;100.27583043628613
M0216 Despoina;108.51120100853969;80.85189443138452
M0217 Dikerotes;67.77490661799422;81.73628882048897
M0218 Dimeter;92.48088160929896;63.55715114366787
M0219 Dimorphos;108.99052089891116;79.38042061918875
M0220 Dindymene;119.99551895171885;91.8987808017116
M0221 Dioktoros;100.42829481667185;86.98496868578523
M0222 Dionysos;113.82885077848125;65.60617828421779
M0223 Discordia;82.57927370769303;69.06632991258378
M0224 Dissotokos;101.72230755033569;93.49788121912192
M0225 Dithyrambos;101.4799388311262;63.545985433096654
M0226 Doris;121.90621609798482;93.34569965447004
M0227 Dryope;123.47767495649153;70.41540268018802
M0228 Echephyle;75.723755104545;83.34422337307633
M0229 Echidna;90.39304268386896;55.14106476439427
M0230 Eiraphiotes;110.38607953406539;75.3730403734047
M0231 Ekstatophoros;96.53788037534329;74.46860441517114
M0232 Eleemon;107.47593210066138;74.79352696297452
M0233 Eleuthereus;72.23536828945396;61.752611333390234
M0234 Eleutherios;105.09258709941986;78.40472275352543
M0235 Ennosigaios;85.3603540905627;61.89998387077629
M0236 Enodia;107.28283456826105;71.77167328776466
M0237 Enodios;105.19619382608076;68.30688968418033
M0238 Enoplios;80.03493154367462;107.0679703532958
M0239 Enorches;84.37367827916084;70.10128276022215
M0240 Enualios;94.60022737621948;82.9098269529249
M0241 Eos;104.23565231158537;78.23965535810336
M0242 Epaine;104.86682047782627;50.562081832176595
M0243 Epidotes;101.8094281358735;92.46948630798497
M0244 Epikourios;96.25161555405708;87.13675385831758
M0245 Epipontia;105.91196588544321;78.74774198438405
M0246 Epitragidia;111.21351164514166;72.8303948777045
M0247 Epitumbidia;79.56727819159013;81.41763538354742
M0248 Erato;98.43125608539859;79.29230008629669
M0249 Ergane;92.21521130676811;65.88496382547267
M0250 Eribromios;114.79800516953905;88.62876630797341
M0251 Erigdoupos;100.78461703700103;83.44326703464307
M0252 Erinus;118.05272719446823;75.2053993679408
M0253 Eriobea;114.90699896510594;85.044640606519
M0254 Eriounios;60.43479005416454;80.55250654700862
M0255 Eriphos;110.1161886577023;77.19536187535785
M0256 Eris;124.15068571889945;61.2173817372489
M0257 Eros;116.83321420982926;66.55187631403275
M0258 Euanthes;95.71257127956467;90.74235555602907
M0259 Euaster;96.53330013910555;82.70520710329284
M0260 Eubouleus;115.89697526720313;63.68748502764139
M0261 Euboulos;120.29584344650894;68.82923707951701
M0262 Euios;101.51519868829273;91.61118867130692
M0263 Eukhaitos;95.63776583880458;60.65688731865677
M0264 Eukleia;99.86100490060197;55.97901218670023
M0265 Eukles;89.75614621019353;74.28240393264507
M0266 Eumache;111.15283777625235;95.01770051099392
M0267 Eunemos;119.4735317999219;87.36892773680646
M0268 Euplois;91.29767434065569;83.63484138713447
M0269 Euros;101.863633994541;105.35504329603799
M0270 Eurybe;97.83681782047508;84.7965552923674
M0271 Euryleia;102.82074592706778;72.61858788149166
M0272 Euterpe;96.25354457672348;67.91601139308868
M0273 Fates;103.0271128805771;76.69107188984266
M0274 Fortuna;112.19008090112276;69.32926825401121
M0275 Gaia;121.49673321650491;94.3871981529
M0276 Gaieokhos;130.76267550311215;81.15769313189227
M0277 Galea;102.14602628580377;76.67202914649094
M0278 Gamelia;87.72057586630164;71.3620945168779
M0279 Gamelios;82.5160006365044;86.78224436982451
M0280 Gamostolos;87.17954155208795;70.8137072454851
M0281 Genetor;73.74535992804446;63.215466572088545
M0282 Genetullis;126.45440532881736;55.960333837534805
M0283 Geryon;98.6856672181786;91.80449906733402
M0284 Gethosynos;84.20364386811715;78.35568446711328
M0285 giants;82.9649100178934;86.23585100545066
M0286 Gigantophonos;87.46102283312142;91.83703607708328
M0287 Glaukopis;117.84025692846004;75.27575396812485
M0288 Gorgons;119.64332917782012;85.5995811465458
M0289 Gorgopis;107.68310832672131;71.14326000331062
M0290 Graiae;95.4270321750264;67.19380834694994
M0291 griffin;112.19069764610788;71.00076336882552
M0292 Gynaikothoinas;108.21140909022405;64.16111559276712
M0293 Gynnis;102.73057054262287;74.14388814907836
M0294 Hagisilaos;90.03814985563194;68.93308882477898
M0295 Hagnos;107.29516605995427;82.66916802587122
M0296 Haides;107.63231585667552;64.53006835921364
M0297 Harmothoe;92.56528596931261;60.724749093524395
M0298 harpy;93.21849122847394;75.7086645677501
M0299 Hegemone;110.38142401417181;69.90896761055227
M0300 Hegemonios;123.71890014862385;58.90199879865101
M0301 Hekate;108.53971832816585;81.30053787657374
M0302 Hekatos;81.37656929004474;95.90436698871424
M0303 Helios;106.33708844178868;68.26898132065746
M0304 Hellotis;119.64657295769037;107.82858810766915
M0305 Hephaistia;88.27113631316189;118.02379402887453
M0306 Hephaistos;97.97979750535303;70.64774412206022
M0307 Hera;118.28523922565776;88.45993353753721
M0308 Heraios;107.87961219852077;83.4432117538581
M0309 Herakles;109.82543344575906;80.93623262724954
M0310 Herkeios;106.45639313787822;54.810975101043326
M0311 Hermes;83.93553655165391;56.88725313981331
M0312 HerosTheos;86.39460754280756;94.71159095461917
M0313 Hersos;97.35255757677918;68.94087142662677
M0314 Hestia;96.8298073474143;100.24169755616514
M0315 Heteira;95.83769008391673;53.17865882967648
M0316 Hiksios;127.72175165326462;94.47494861089733
M0317 Hipp;92.19366519262451;50.193210404778895
M0318 Hippia;101.83114793719463;101.70279238965051
M0319 Hippios;109.05280281399763;86.1992530217094
M0320 HippoiAthanatoi;95.61941772835391;82.61917415436358
M0321 Hippolyte;87.3539509124233;96.20673134833703
M0322 Hippomache;105.16174064478191;48.14766241211032
M0323 Hippothoe;85.6270507653561;79.1254952494812

12/07/2011, 10h41
Alikendarfen

Citation:

Envoyé par elentarion

J'ai du rater quelque chose d'important.

Tu veux bien nous faire partager ton code ?

Edit : sinon, place un compteur quelque part pour comparer (par exemple au niveau du calcul du temps de chaque chemin)
12/07/2011, 11h46
JeitEmgie

Citation:

Envoyé par Baruch

Bon je pense avoir trouvé quelque chose de très intéressant ^^ :

Je me ramène encore avec mon histoire d'idéalité 2 à 2. Ou plutôt, j'utilise cette propriété :

Pour tout couple de mines (M1,M2), on a une valeur p* = (c2-c1) / (c1/p1 - c2/p2) telle que :

Soit p la production juste avant l'occurrence du couple,

p >= p* <=> la mine la plus rentable du couple doit être placée avant

L'interprétation géométrique de cette formule est assez cocasse :

dans un espace 2D où X est l'axe des coûts et Y l'axe des inverses des rendements, vous calculez la tangente de l'angle que fait le segment (coordonnées de M1 - coordonnées de 2) avec l'axe des X (des coûts) et vous multipliez par le produit des rendements…

FYI: sur le problèmes des 324 mines,
l'algorithme en O(n) de tri par dominance-theta donne une première approximation de 2.196730613708496 en 0.0016 sec
et un post processing "bête et méchant" (mais un poil optimisé) donne 2.155679225921631 dans un temps total de 0.072917 sec…
(on consomme donc ≈40x plus de temps pour améliorer de moins de 2%…)

et par rapport au 2.1556776803280098 en 3.21 sec de "Algo par insertion sans remise" : ce dernier consomme encore un facteur ≈40x mais pour améliorer seulement de 0.001% … (donc par rapport à domtheta, l'algo par insertion coûte un facteur 2000x pour une amélioration de 2%…)
12/07/2011, 13h31
Baruch

Citation:

Etant donné un chemin en cours d'évaluation Ei = E(i-1) + M1,

On tente d'ajouter M2 à ce chemin.

Si T( E(i-1) + M1 + M2 ) > T( E(i-1) + M2 + M1 ), alors on laisse tomber la branche d'exploration Ei + M2.

Si tu utilises cette propriété dans ton algo, c'est alors un algo moins bien que l'algo par combinaisons (avec dominances). En effet l'algo par combinaisons traite ce cas.

Pour la propriété que j'ai énoncé plus haut, vous avez pas l'air très emballé...
Ca prouve quand même qu'à partir d'une certaine production, les mines sont triées par rentabilité décroissante et donc ça rend le problème bien plus simple (me semble-t-il).
Je suis entrain de réfléchir à un algorithme qui part de la liste triée par rentabilité décroissante pour fournir la liste idéale. Ca me fait revenir en fait à l'idéalité 2 à 2. Bref je vais faire des tests.
12/07/2011, 17h15
Alikendarfen

Citation:

Envoyé par Baruch

Si tu utilises cette propriété dans ton algo, c'est alors un algo moins bien que l'algo par combinaisons (avec dominances). En effet l'algo par combinaisons traite ce cas.

Il y a une grosse différence qui fait que dans la pratique l'algo avec dominance et optimalité 2 à 2 est beaucoup plus efficace (voir la description que j'en ai faite).

Pour le reste :

Citation:

Envoyé par Baruch

Pour la propriété que j'ai énoncé plus haut, vous avez pas l'air très emballé...
Ca prouve quand même qu'à partir d'une certaine production, les mines sont triées par rentabilité décroissante et donc ça rend le problème bien plus simple (me semble-t-il).

p* ne vaut que pour deux mines consécutives, donc ça reste un peu plus compliqué que ça...
12/07/2011, 19h18
Baruch

Citation:

Il y a une grosse différence qui fait que dans la pratique l'algo avec dominance et optimalité 2 à 2 est beaucoup plus efficace (voir la description que j'en ai faite).

Ah donc son efficacité est due au fait que la mémoire utilisée est moindre ?
Mais tu avais testé l'algo par combinaisons avec dominances absolues ?

En fait j'ai pas exactement compris ce que faisais ton algo, tu peux montrer sur un exemple simple ?

Et pourquoi dis-tu qu'il est stable en mémoire consommée ?

Citation:

p* ne vaut que pour deux mines consécutives, donc ça reste un peu plus compliqué que ça...

Oui ! Mais regarde si p > pmax, alors quels que soient les couples de mines rencontrés (quel que soit l'ordre des mines suivantes), tous leurs p* seront inférieurs à pmax, et donc le plus rentable sera toujours avant. Ce qui implique que les mines suivantes sont triées par rentabilité décroissante.

Regarde les listes idéales que tu trouves, à la fin les mines sont triées par rendement décroissant.

Bon je fais plus clair :

Soit E un ensemble de mines. Si la production initiale P0 est supérieure à Pmax, alors l'ordre idéal est le tri par rendement décroissant, et pour les mines de même rendement, par production croissante.

En effet :

Je rappelle que Pmax est le maximum des valeurs réelles de tous les p* possibles des mines de E.

Si la liste idéale comporte un couple de mines adjacentes (M1,M2), où M1 est avant M2 et M1 moins rentable que M2.
La production p juste avant l'occurrence de ce couple est supérieure ou égale à P0, qui est supérieur à Pmax, qui lui même est supérieur ou égal au p* du couple.
p >= p* implique que le plus rentable est avant.
Ce qui dans notre cas est absurde.
Donc la liste idéale est la liste où les mines sont triées par rendement décroissant.

Je rappelle que p*(M1,M2) = (c2-c1)/(c1/p1 - c2/p2)
13/07/2011, 08h38
Alikendarfen

Dans la pratique, sur le jeu d'essai de elentarion, Pmax est très supérieur à la somme des productions (pour être précis, 38 paires de mines ont un p* > pTot).
13/07/2011, 09h39
JeitEmgie

Citation:

Envoyé par Alikendarfen

Dans la pratique, sur le jeu d'essai de elentarion, Pmax est très supérieur à la somme des productions (pour être précis, 38 paires de mines ont un p* > pTot).

… voir mon post plus haut sur l'interprétation géométrique de la formule : on multiplie la tangente d'un angle par le produit des rendements…
donc dès que l'on a beaucoup de mines dont la production est supérieure au coût (r>1), il faut s'attendre à ce comportement…
de plus l'angle calculé est d'autant plus proche de pi/2 que les coûts entre les 2 mines sont différents mais les rendements proches…
13/07/2011, 10h22
Alikendarfen

Citation:

Envoyé par JeitEmgie

… voir mon post plus haut sur l'interprétation géométrique de la formule : on multiplie la tangente d'un angle par le produit des rendements…
donc dès que l'on a beaucoup de mines dont la production est supérieure au coût (r>1), il faut s'attendre à ce comportement…
de plus l'angle calculé est d'autant plus proche de pi/2 que les coûts entre les 2 mines sont différents mais les rendements proches…

Oui, je suis bien d'accord.

Je pense que l'algo naif avec dominances (absolues) et optimalité 2 à 2 (appelons-le algo NDO) reste la meilleure approche exacte jusque là.
Alors que les AG et ou l'algo par insertion ou encore le simple tri sont les plus efficaces (considérant ton post d'avant qui comparait le gain avec l'écart de temps de calcul pour l'obtenir).

Il faut peut être revenir sur l'optimalité 2 à 2 (ou dominance 2 à 2, peu importe). Je m'explique :
- L'algo NDO construit des hypothèses qui vérifient toutes l'optimalité 2 à 2
- Dans cette construction, on obtient quelques millions de chemins intermédiaires pour 100 mines et plus
- A la fin, on obtient tous les chemins complets et on garde le meilleur d'entre eux
- Or, on constate qu'on obtient 1 seul chemin complet sur le jeu de test d'elentarion (et sans doute seulement quelques uns dans le cas général, hors cas particulier).

Donc... il faut sans doute revenir à une solution de type permutations partant de la liste complète des mines...

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