Discussion :

[elentarion]

Ok donc en supposant un temps continu j'ai ce type de résultat:

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
 
Shortest combination complete in 2 days, 12 hours, 24 minutes, 36 seconds
[0D:9H:36M:0S] Building mine Apollo B0, new income: 9
[0D:17H:35M:59S] Building mine Geb Z2, new income: 85
[0D:19H:51M:30S] Building mine Dagda J2, new income: 163
[0D:20H:44M:30S] Building mine Enlil B1, new income: 181
[0D:21H:16M:19S] Building mine Belenus E2, new income: 202
[0D:22H:20M:28S] Building mine Bragi Q1, new income: 251
[0D:22H:43M:24S] Building mine Frigg T1, new income: 269
[0D:23H:10M:9S] Building mine Hecate M0, new income: 270
[0D:23H:47M:29S] Building mine Morrigan Q2, new income: 359
[0D:23H:51M:29S] Building mine Bran F2, new income: 368
[1D:0H:11M:2S] Building mine Thor B2, new income: 400
[1D:0H:36M:14S] Building mine Selene S0, new income: 408
[1D:2H:7M:59S] Building mine Odin Z1, new income: 416
[1D:2H:39M:8S] Building mine Kishar G1, new income: 427
[1D:3H:6M:6S] Building mine Enuda C1, new income: 429
[1D:3H:26M:14S] Building mine Ares C0, new income: 433
[1D:4H:16M:7S] Building mine Tyr C2, new income: 437
[1D:7H:0M:52S] Building mine Cronus F0, new income: 637
[1D:7H:7M:38S] Building mine Anubis U2, new income: 641
[1D:7H:16M:37S] Building mine Zeus U0, new income: 653
[1D:7H:51M:53S] Building mine Mummu I1, new income: 667
[1D:8H:4M:50S] Building mine Ea A1, new income: 680
[1D:8H:19M:39S] Building mine Athena E0, new income: 690
[1D:8H:25M:54S] Building mine Aegir O1, new income: 693
[1D:8H:59M:8S] Building mine Idun W1, new income: 702
[1D:12H:55M:1S] Building mine Marduk H1, new income: 827
[1D:14H:13M:22S] Building mine Atum W2, new income: 848
[1D:14H:23M:33S] Building mine Uranus T0, new income: 853
[1D:14H:31M:59S] Building mine Hades K0, new income: 868
[1D:14H:35M:18S] Building mine Shamash L1, new income: 870
[1D:14H:41M:55S] Building mine Sif A2, new income: 876
[1D:14H:48M:29S] Building mine Hebe L0, new income: 884
[1D:15H:3M:8S] Building mine Ishtar E1, new income: 902
[1D:15H:6M:19S] Building mine Nuadha S2, new income: 903
[1D:15H:22M:15S] Building mine Hadad D1, new income: 910
[1D:15H:41M:14S] Building mine Tiamat N1, new income: 921
[1D:15H:49M:3S] Building mine Gaia J0, new income: 922
[1D:16H:23M:24S] Building mine Loki X1, new income: 925
[1D:17H:19M:26S] Building mine Brigit G2, new income: 970
[1D:17H:20M:55S] Building mine Ashur Y0, new income: 971
[1D:17H:53M:32S] Building mine Damkina Z0, new income: 975
[1D:19H:35M:26S] Building mine Lug N2, new income: 1011
[1D:19H:42M:33S] Building mine Helios N0, new income: 1026
[1D:20H:20M:26S] Building mine Anshar V0, new income: 1048
[1D:21H:51M:7S] Building mine Aten V2, new income: 1059
[2D:0H:1M:39S] Building mine Cernuros I2, new income: 1062
[2D:1H:31M:8S] Building mine Bet Y2, new income: 1150
[2D:1H:49M:54S] Building mine Hermes Q0, new income: 1160
[2D:2H:1M:4S] Building mine Bast X2, new income: 1163
[2D:2H:4M:46S] Building mine Anu W0, new income: 1177
[2D:2H:31M:40S] Building mine Vali D2, new income: 1189
[2D:2H:53M:27S] Building mine Nabu J1, new income: 1255
[2D:2H:54M:35S] Building mine Artemis D0, new income: 1256
[2D:3H:8M:20S] Building mine Ceridwen H2, new income: 1262
[2D:3H:11M:45S] Building mine Dyonisus H0, new income: 1272
[2D:3H:16M:16S] Building mine Eos I0, new income: 1280
[2D:3H:32M:1S] Building mine Hodur V1, new income: 1287
[2D:3H:43M:12S] Building mine Freyr R1, new income: 1309
[2D:4H:7M:24S] Building mine Hestia R0, new income: 1325
[2D:4H:12M:50S] Building mine Aphrodite A0, new income: 1328
[2D:4H:22M:35S] Building mine Freya S1, new income: 1350
[2D:4H:38M:35S] Building mine Nemain R2, new income: 1354
[2D:4H:44M:57S] Building mine Apsu X0, new income: 1363
[2D:5H:8M:11S] Building mine Nintu K1, new income: 1387
[2D:5H:11M:17S] Building mine Demeter G0, new income: 1393
[2D:5H:32M:59S] Building mine Lyr O2, new income: 1395
[2D:6H:19M:26S] Building mine Danu K2, new income: 1404
[2D:6H:22M:30S] Building mine Kingu F1, new income: 1407
[2D:7H:41M:18S] Building mine Epona L2, new income: 1452
[2D:8H:25M:55S] Building mine Heimdall U1, new income: 1496
[2D:10H:1M:12S] Building mine Ogma T2, new income: 1561
[2D:10H:34M:24S] Building mine Manannan mac Lir P2, new income: 1568
[2D:11H:3M:47S] Building mine Gwydion M2, new income: 1574
[2D:11H:16M:35S] Building mine Hera P0, new income: 1589
[2D:11H:23M:49S] Building mine Baldur P1, new income: 1638
[2D:12H:2M:29S] Building mine Sin M1, new income: 1690
[2D:12H:22M:55S] Building mine Niord Y1, new income: 1696
[2D:12H:24M:36S] Building mine Hephaestus O0, new income: 1711

Sachant que sur plusieurs exécutions, je reste autour de 2 jours et 12 heures mais que par contre le nombre de minutes varie beaucoup.

[Alikendarfen]

Bonjour,

Pour info, le résultat avec un algo exact (algo par combinaisons avec dominances, décrit avant).

Temps pour le meilleur chemin (ou plutôt, un des meilleurs chemins) : 1.8075422775614463 (en jours)

Et la solution elle-même :

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

Le tableau se lit : [<date d'achat arrondie>:<nom>/<cout>/<production>]

[elentarion]

Alikendarfen > Combien de temps pour obtenir le résultat ?

Il semblerais que je doive optimiser un peu ... J'aimerai bien descendre en dessous des deux jours.

[Alikendarfen]

Je n'ai pas noté le temps de calcul (quelques minutes, mais ma machine est actuellement chargée de plein d'autres trucs : l'algo par combinaison est consommateur en mémoire).

Sinon, j'avais aussi exploré la piste algo génétiques (voir post #79 page 4).

Et du coup, je l'ai relancé sur ton jeu d'essai :

Meilleur temps : 1.8075422775614463 (donc le même, mais ça ne marche pas toujours !)

Résultat :

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

Ma population fait 400 individus.
J'ai généré 50 000 générations, mais le meilleur individu n'est pas amélioré à partir de la 19 483ième génération. En tout, il y a eu 360 améliorations du meilleur individu.

Dans cette implémentation basique, il n'y a pas de tentative de préserver la diversité dans la population et tout est fait à base de mutations (pas de croisements).

Je n'ai pas noté le temps de calcul non plus (mais c'est beaucoup plus court que l'autre algo).

[Alikendarfen]

Pour info : 109 secondes pour les 50000 générations x 400 individus (mais je n'ai en rien chercher à optimiser : notamment, je fais un simple 'sort' à chaque génération sur l'ensemble de la population).

Puisque je l'ai relancé : même résultat et cette fois-ci trouvé à la 19693 ième génération (ce qui est relativement stable !).

[elentarion]

J'ai l'impression que ce problème se prête très bien aux algos génétiques en fait.

Pour ma part, j'essaye de rester sous la barre des 5 secondes et d'améliorer la solution.

Je pense que mon problème vient de la fonction de reproduction. Pourrais-tu me donner un aperçu de la tienne ou une explication du fonctionnement ?

[Alikendarfen]

J'ai l'impression que ce problème se prête très bien aux algos génétiques en fait.

Oui !

Je pense que mon problème vient de la fonction de reproduction. Pourrais-tu me donner un aperçu de la tienne ou une explication du fonctionnement ?

Comme je disais avant tout est post #79 page 4.

Pour la reproduction c'est ça, une simple mutation (pas de croisement, car en l'occurrence je ne vois pas le sens que ça aurait) :

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
 
            public Gene Muter()
            {
                Gene gene = new Gene() { ProductionInitiale = ProductionInitiale, Mines = new List<Mine>( Mines ) };
 
                int limit = 1 + AlgoRandom.Next( 6 );
                for ( int i = 0 ; i < limit ; i++ )
                {
                    int p1 = AlgoRandom.Next( gene.Mines.Count );
                    int p2 = AlgoRandom.Next( gene.Mines.Count );
 
                    Mine m1 = gene.Mines[p1];
                    Mine m2 = gene.Mines[p2];
 
                    gene.Mines[p1] = m2;
                    gene.Mines[p2] = m1;
                }
 
                return gene;
            }

Donc j'intervertis, entre 1 et 6 fois, deux mines prises au hasard.

[elentarion]

Effectivement, avec cette fonction j’obtiens de meilleurs résultats (entre 1.85 et 2.05 jours) par contre le temps de calcul a explosé: 35s. Probablement, la faute de la fonction rand.

Ce qui pourrais être intéressant serais de corser un peu le problème en ajoutant des paramètres:

- un nombre indéterminé de ressources (chaque mine nécessite X de telle ressource, Y de telle ressource, Z de telle ressource et produit W d'une autre ressource).

- la possibilité de solliciter des prêts (nécessité de réflexion sur le long terme) : A l'instant X il faut savoir s'il est plus intéressant de prendre un prêt de Y ressources à taux Z plutôt que d'acheter une mine moins chère.

- l'ajout de plusieurs agents acheteurs, le pool de mine changerais donc au cours du temps. Nécessité d'adapter l'algorithme.

[Alikendarfen]

Effectivement, avec cette fonction j’obtiens de meilleurs résultats (entre 1.85 et 2.05 jours) par contre le temps de calcul a explosé: 35s. Probablement, la faute de la fonction rand.

Ce qui pourrais être intéressant serais de corser un peu le problème en ajoutant des paramètres:

- un nombre indéterminé de ressources (chaque mine nécessite X de telle ressource, Y de telle ressource, Z de telle ressource et produit W d'une autre ressource).

- la possibilité de solliciter des prêts (nécessité de réflexion sur le long terme) : A l'instant X il faut savoir s'il est plus intéressant de prendre un prêt de Y ressources à taux Z plutôt que d'acheter une mine moins chère.

- l'ajout de plusieurs agents acheteurs, le pool de mine changerais donc au cours du temps. Nécessité d'adapter l'algorithme.

je crois que tout ça était l'idée de base de Baruch !


Sinon, concernant les AG, une optimisation simple est la suivante :
- Partir d'une solution non nécessairement optimale mais bonne
- Puis appliquer les AG

Dans la pratique, l'algo par insertions donne de très bon résultats et est en o(n²). L'algo et différents comparatifs sont donnés dans les posts précédents.

Je viens de le tester et la meilleure solution est trouvée dès la première génération !!
Maintenant, avec les AG, un des ennuis est de savoir quand s'arrêter de calculer...

[Alikendarfen]

Effectivement, avec cette fonction j’obtiens de meilleurs résultats (entre 1.85 et 2.05 jours) par contre le temps de calcul a explosé: 35s. Probablement, la faute de la fonction rand.

Ce qui m'interpelle c'est que tu ne trouves pas le résultat (alors qu'il semble que je l'ai systématiquement).

J'utilise 400 individus et (sans l'optim décrite juste avant) la solution est trouvée vers la 20 000ième génération.

Et pour toi ?

[Baruch]

Ce qui pourrais être intéressant serais de corser un peu le problème en ajoutant des paramètres:

- un nombre indéterminé de ressources (chaque mine nécessite X de telle ressource, Y de telle ressource, Z de telle ressource et produit W d'une autre ressource).

- la possibilité de solliciter des prêts (nécessité de réflexion sur le long terme) : A l'instant X il faut savoir s'il est plus intéressant de prendre un prêt de Y ressources à taux Z plutôt que d'acheter une mine moins chère.

- l'ajout de plusieurs agents acheteurs, le pool de mine changerais donc au cours du temps. Nécessité d'adapter l'algorithme.

Oula oula ^^. Je pense qu'il vaut mieux y aller progressivement, le cas basique ayant déjà fait couler beaucoup d'encre (virtuelle, je sais).
Néanmoins je pense que le problème suivant à étudier est en effet l'existence de plusieurs ressources.
Pour tes autres propositions, je pense qu'il vaut mieux les écarter pour l'instant, afin que les algorithmes produits ici soient les plus généraux possibles.
Ah oui, un autre problème qui m'intéresse, c'est de considérer que les mines ont un temps de construction : un temps d'attente pour réunir les ressources, on lance la construction, on attends le temps de construction, puis la production de la mine est lancée.
Bref à part ça je pense qu'on a pas totalement fini d'explorer le cas "basique" ^^.

Sinon, concernant les AG, une optimisation simple est la suivante :
- Partir d'une solution non nécessairement optimale mais bonne
- Puis appliquer les AG

Ca me fait repenser à l'histoire de l'idéalité 2 à 2 :

On a une liste L de mines. Avant de lui appliquer l'algo génétique, on l'améliore un peu en permutant des couples de mines adjacentes. L'intérêt je crois est la rapidité du test (mais je ne suis pas sûr, à vous de me dire).

Par exemple, on peut parcourir la liste en entier une seule fois, et permuter les couples qui sont mal ordonnés.

Soit L une liste de mines.
Soit (M1,M2) un couple de mines adjacentes dans L, tel que M1 est plus rentable que M2, ie p1/c1 >= p2/c2
Soit p la production résultante juste avant l'occurrence du couple (M1,M2).
Soit p* = (c2-c1)/(c1/p1-c2/p2)

p <= p* <=> M2 est avant M1

(comprendre : permuter M1 et M2 de manière à placer M2 en premier donne une liste avec un temps de construction inférieur)


Une autre idée pour partir d'une "meilleure" liste avant d'appliquer l'algo génétique, est de trier par production ou par coût les mines. Ca peut paraître barbare dans certains cas, mais en général la liste idéale est globalement triée par productions décroissantes et par coûts croissants.

[Alikendarfen]

Un nouvel algo exact !

Il est juste basé sur la notion de dominance 2 à 2 qu'on n'a pas exploitée comme ça jusque là.

Il exploite également les dominances 'absolues', de la même façon que l'algo par combinaisons donné précédemment.

De plus, j'ai utilisé une approche récursive et non plus itérative.

Sur le jeu d'essai redonné par elentarion (78 mines), il donne les résultats suivants :
- Résultat exact
- Temps de calcul : env. 60s
- Chemins intermédiaires générés : 7 460 572

Mais surtout, l'approche récursive permet de le rendre stable en mémoire ram consommée (ce qui était loin d'être le cas pour l'algo par combinaisons).

Les résultats sont interceptés par l'intermédiaire d'une continuation (fonction passée en paramètre qui peut être appelée au coeur de l'algo, ce qui évite de 'sortir de la récursion' pour obtenir un résultat).

Le principe est simple et s'appuie sur une exploration exhaustive (mais tenant compte des dominances absolues) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
- Calculer les dominances absolues (même chose que précédemment)
- Partir d'un chemin vide comme chemin initial
- Appeler le traitement avec ce chemin et la fonction de continuation
  (voir ci-après)
- Et dans ce traitement :
     > Prendre chaque mine X non encore traitée
     > Vérifier que X ne domine pas 2 à 2 la dernière mine du 
       chemin en cours
     > Et si effectivement X ne la domine pas 2 à 2, alors ajouter X 
       au chemin et rappeler le traitement avec ce nouveau chemin

En termes de complexité, on est dans les mêmes ordres de grandeur que l'algo par combinaison.
Par contre, comme on gagne énormément en ram, ça va plus vite et on peut calculer pour encore plus de mines (même si les temps de calcul risquent d'exploser).

Si elentarion voulait bien nous trouver 26 noms de planètes de plus, je suis preneur pour faire le test !

[Alikendarfen]

Voici le code de l'algo décrit juste avant :

Partie principale :

Code C# :

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
 
        public Chemin Traiter( List<Mine> mines, double p, Action<Chemin> trace = null )
        {
            //Algo5b algo5b = new Algo5b();
            //Chemin cheminReference = algo5b.Traiter( mines, p );
 
            // Création du chemin initial vide mais comprenant la liste des mines d'origine
            Chemin cheminInitial = new Chemin( p );
 
            // Calcul des dominances
            Dictionary<Mine, List<Mine>> dominantes = Dominance.CalculerDominantes( mines );
            // Table des dominees
            Dictionary<Mine, int> dominees = Dominance.CalculerDominees( dominantes );
 
            cheminInitial.Dominantes = dominantes;
            cheminInitial.Dominees = dominees;
 
            // Affectation initiale avec les mines n ayant aucune dominante
            cheminInitial.MinesNonTraitees.AddRange( Dominance.CalculerNonDominees( mines, dominees ) );
 
            Stopwatch sw = new Stopwatch();
            sw.Start();
 
            // Un meilleur chemin
            Chemin meilleur = null;
 
            // Le premier appel récursif, 
            // avec la continuation en paramètre qui capte le meilleur résultat au fur et à mesure
            Traiter( cheminInitial, c =>
            {
                if ( meilleur == null || c.DateFin < meilleur.DateFin )
                    meilleur = c;
            } );
 
            sw.Stop();
            long elapsed = sw.ElapsedMilliseconds;
 
            //double delta = cheminReference.DateFin - meilleur.DateFin;
 
            return meilleur;
        }

La fonction 'principale' du traitement

Code C# :

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
 
        void Traiter( Chemin chemin, Action<Chemin> action )
        {
            // Plus de mines à ajouter : produire un résultat
            if ( chemin.MinesNonTraitees.Count == 0 && action != null )
                action( chemin );
            else
            {
                // Pour chaque mine parmi les mines non traitées
                foreach ( Mine nonTraitee in chemin.MinesNonTraitees )
                {
                    // Vérifier l'optimalité 2 à 2 pour la mine à ajouter
                    if ( VerifierOptimales2a2( chemin, nonTraitee ) )
                    {
                        // Si c'est le cas, créer un nouveau chemin identique au chemin actuel
                        Chemin nouveauChemin = chemin.CreateCopy();
 
                        // Lui ajouter la mine
                        nouveauChemin.AjouterMine( nonTraitee );
 
                        // Et récursion
                        Traiter( nouveauChemin, action );
                    }
                }
            }
        }

La vérification de la dominance 2 à 2 :

Code C# :

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
 
        bool VerifierOptimales2a2( Chemin chemin, Mine mine )
        {
            // Si le chemin est actuellement vide, c'est forcément bon
            if ( chemin.MinesDatees.Count == 0 )
                return true;
 
            else
            {
                // Calculer le temps qui résulterait de l'ajout de la mine au chemin
                double t1 = chemin.DateFin + mine.Cout / chemin.Production;
 
                // Récupérer la mine précédente
                Mine precedente = chemin.MinesDatees[chemin.MinesDatees.Count - 1].Mine;
 
                // Calculer la production du chemin avant la mine précédente
                double productionAvantPrecedente = chemin.Production - precedente.Production;
                // Le temps avant la dernière mine
                double t2 = chemin.DateFin - precedente.Cout / productionAvantPrecedente;
                // Le temps avec le nouvelle mine à la place de la dernière mine
                t2 += mine.Cout / productionAvantPrecedente;
                // Le temps avec la dernière mine replacée après la mine étudiée
                t2 += precedente.Cout / (productionAvantPrecedente + mine.Production);
 
                // C'est optimal si t1 (ajout de la mine étudiée en dernier) inférieur ou EGAL à t2
                // (le 'égal' est important, sinon, on perd des chemins !)
                return t1 <= t2;
            }
        }

Note :
Les fonctions et classes de base ont été données dans les posts précédents, donc je ne les répète pas ici.
Notamment, la dominance 'absolue' est traitée au sein de la fonction d'ajout d'une mine à un chemin.

[Baruch]

Cet algo c'est donc l'algo naïf avec les dominances si j'ai bien compris.

J'avais essayé de coder cet algo, mais j'arrivais pas ^^ (caml m'a énervé).

Ca m'étonne qu'il soit aussi rapide, enfin bon c'est une bonne nouvelle

Edit :

Oula attends j'avais pas regardé ta fonction pour la dominance.

C'est quoi que tu appelles "dominance 2 à 2" ?

Désolé mais je crois que cet algo est faux...

[Alikendarfen]

Désolé mais je crois que cet algo est faux...

Pas de problème, j'ai pu me tromper, mais alors justifie ce que tu dis !

Edit :
ah si... je vois : il est juste mais j'aurais du l'appeler 'optimalité 2 à 2' ! ... d'ailleurs, c'est le nom de la fonction...

Cet algo c'est donc l'algo naïf avec les dominances si j'ai bien compris.

Plus exactement, c'est donc l'algo naïf avec dominances (au sens c1 < c2, p1 > p2) et l'optimalité 2 à 2.

[JeitEmgie]

FYI

l'algorithme O(n) qui trie sur la dominance et le theta donne
1.8793135 en 0.3 msec (3/10000 sec)
améliorer "bêtement" - mais inexploitable sur de plus grands jeux de données - à partir de ce premier résultat donne 1.8075421 en 0.034046 sec…
(donc 10% du temps pour arriver à 96% de l'optimum, 90% du temps pour gagner les 4%…)

On a donc beaucoup de marge dans l'optimisation du processus d'amélioration à partir d'un résultat relativement bon : on est à 4% de l'optimum en 5 ordres de grandeur plus vite que des solutions visant uniquement l'optimum…

Toutefois l'approche par segmentation topologique n'est pas encore applicable ici : le jeu ne données est encore trop petit : elle aurait renvoyé au grand maximum 3 sous-jeux (dont les 4 premières mines de la solution, une grande partie du reste sauf les 2-3 dernières…) et donc les zones de flou auraient couvert totalement les extrémités, donc optimiser cette partie du problème reste encore un objectif en soi.

[Alikendarfen]

Pourrais tu développer un peu plus :

améliorer "bêtement" - mais inexploitable sur de plus grands jeux de données - à partir de ce premier résultat donne 1.8075421 en 0.034046 sec…

Qu'entends-tu par 'améliorer' ici ?

Toutefois l'approche par segmentation topologique n'est pas encore applicable ici : le jeu ne données est encore trop petit : elle aurait renvoyé au grand maximum 3 sous-jeux (dont les 4 premières mines de la solution, une grande partie du reste sauf les 2-3 dernières…) et donc les zones de flou auraient couvert totalement les extrémités, donc optimiser cette partie du problème reste encore un objectif en soi.

Quelle est cette segmentation ? J'ai raté un post ?

Merci

[Baruch]

Pas de problème, j'ai pu me tromper, mais alors justifie ce que tu dis !

Oui oui roooo je vais le faire ^^

l'optimalité 2 à 2

Tu peux expliquer ce que c'est stp ?

[Alikendarfen]

Tu peux expliquer ce que c'est stp ?

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.

[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.

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.

Je vais essayer aussi d'optimiser un peu plus au niveau logiciel en multithreadant tout ça.

J'ai aussi généré un nouveau jeu de test avec plus de mines (323). Sachant que le cost et l'income sont des doubles aléatoires entre 0 et 100. Le nom est pioché là : http://frontiernet.net/~quickbasicguru/gods.txt

Je pense que je vais essayer de coder un générateur un peu plus évolué (notamment avec une répartition non linéaire). Si le ratio income / cost forme une gaussienne, il y a probablement moyen d'optimiser un peu plus tout ça.

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
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;26.129976783909427;51.14172097054934
M0001 Amen;94.61080777265035;25.963496805578757
M0002 Amon;81.92645141949463;29.14651499085581
M0003 Amun;63.41047732311084;29.60293925798496
M0004 Anat;71.43136107234935;63.446681958822516
M0005 Anqet;88.3857339082908;58.45523648420059
M0006 Antaios;70.86318171850475;40.11863543198564
M0007 Anubis;87.9069234483871;62.52031638103416
M0008 Anuket;70.6748690827364;30.698986235991022
M0009 Apep;43.29752981126713;71.88491584672494
M0010 Apis;38.5551685332902;59.46761041501774
M0011 Astarte;26.94214055099321;73.17545014289523
M0012 Aten;85.09881843663598;83.23613462096026
M0013 Aton;57.381182959398494;5.805460157107523
M0014 Atum;81.9777280054215;86.33048373417552
M0015 Bastet;46.507825466478224;10.442531749967898
M0016 Bat;45.04300212318974;16.209930449546594
M0017 Buto;43.14251995446939;23.936036615560386
M0018 Duamutef;35.51024187429505;11.044139898007977
M0019 Duamutef;44.54588659875309;29.888438094381353
M0020 Hapi;51.22824158572406;99.57344041081372
M0021 Har-pa-khered;42.84074172487787;42.11929775851233
M0022 Hathor;77.00390294920915;85.70661651175504
M0023 Hauhet;96.84926588260247;19.462528711034476
M0024 Heket;38.053739265038935;65.56430864422157
M0025 Horus;71.51144146223619;84.65387834634423
M0026 Huh;53.875111621654256;63.055070490865305
M0027 Imset;66.83605357326222;47.50698398706559
M0028 Isis;21.177911135306292;11.575034644625637
M0029 Kauket;66.245719238289;13.142760476888615
M0030 Kebechsenef;63.99011547810199;54.051017034607455
M0031 Khensu;70.21251819133087;89.72834499654705
M0032 Khepri;76.6482579515143;81.30083036504196
M0033 Khnemu;45.24103146290125;96.9981205450959
M0034 Khnum;51.106541070519285;79.56346513159326
M0035 Khonsu;10.540671343580144;16.77085014062015
M0036 Kuk;23.845957979561117;12.055694631363545
M0037 Maahes;5.13938838442296;19.74331078481746
M0038 Ma'at;99.6374449226211;16.54058864272121
M0039 Mehen;26.726006884268383;49.03220139871751
M0040 Meretseger;9.510770475315244;61.14732547435025
M0041 Min;10.16853257777649;40.25257783723725
M0042 Mnewer;38.50347992996572;64.06054406737174
M0043 Mut;18.44102594188334;10.362388898701147
M0044 Naunet;15.111891705552294;49.20149880732273
M0045 Nefertem;51.60171534686382;53.06915245545063
M0046 Neith;88.83883328917055;79.65204796133077
M0047 Nekhbet;40.500185040743816;37.28620288627306
M0048 Nephthys;34.83037140353693;83.32652734936025
M0049 Nun;81.05171665262652;16.9423284359413
M0050 Nut;15.316553721035909;61.275385461975596
M0051 Osiris;82.20187213686422;25.39004764538332
M0052 Ptah;96.41875007861157;48.00843641807154
M0053 Ra;46.11470537678829;45.724168611745306
M0054 Re;65.85888016442954;75.3544144604259
M0055 Renenet;72.65305748326638;19.513682724702363
M0056 Sakhmet;22.2034900548314;76.62748464784147
M0057 Satet;81.87957435674178;80.76644631229817
M0058 Seb;9.498205351938338;56.250240601484144
M0059 Seker;78.09224426070995;79.3875276285661
M0060 Sekhmet;52.495879284458994;41.486631239894166
M0061 Serapis;36.81839990073193;88.95846534016079
M0062 Serket;7.154297620010974;27.567153728100223
M0063 Set;82.22631149978778;77.35614862193795
M0064 Seth;78.67699049711284;25.24260089687501
M0065 Shai;36.57359837897859;55.54636463444575
M0066 Shu;75.09342107012058;20.681474874152673
M0067 Shu;65.59691967889923;9.82854369122893
M0068 Sia;58.22234418300272;61.6301756154405
M0069 Sobek;14.157472068199773;65.87455141619772
M0070 Sokar;25.8349468862904;90.88392304873264
M0071 Tefnut;24.992076739453616;29.095873367784186
M0072 Tem;8.931890008542476;58.37028923869412
M0073 Thoth;60.079702689075646;95.18986973060773
M0074 Acidalia;96.27111604207965;56.52613377938766
M0075 Aello;98.91848647404372;27.15723184919335
M0076 Aesculapius;4.630943986902592;40.15262323235713
M0077 Agathe;70.9184617173144;50.649142965908744
M0078 Agdistis;97.76554694743021;11.561955793846746
M0079 Ageleia;90.1503239675988;28.194105380175017
M0080 Aglauros;19.607687806154416;74.58326394029288
M0081 Agne;99.85076370814363;34.670711419935195
M0082 Agoraia;47.996132622252105;86.87414216146458
M0083 Agreia;1.3700458911539037;71.33415330638604
M0084 Agreie;94.0528743430906;68.98808029519644
M0085 Agreiphontes;37.657634112282565;23.77058337762623
M0086 Agreus;69.30796192534204;60.77706748931282
M0087 Agrios;24.91686766225827;90.3448909626226
M0088 Agrotera;17.767346510432102;50.96244706011953
M0089 Aguieus;77.71980052466344;82.02384237713943
M0090 Aidoneus;63.34185056592582;44.08610910083992
M0091 Aigiokhos;52.65853538822669;21.89795674742141
M0092 Aigletes;54.40300675998376;70.55792116763608
M0093 Aigobolos;43.51945574715745;53.291901560706314
M0094 Ainia;96.70415144414787;90.14427983360206
M0095 Ainippe;97.00200746992178;99.04454329058592
M0096 Aithuia;53.502865996132144;86.99651038842191
M0097 Akesios;82.16376062838027;1.3562842957411836
M0098 Akraia;57.443444203902104;5.196785401715287
M0099 Aktaios;39.05868346802546;11.542641538033527
M0100 Alalkomene;22.605781655099676;27.803148601576222
M0101 Alasiotas;52.44570435223225;92.09948545448997
M0102 Alcibie;67.09972362543688;59.50408427377681
M0103 Alcinoe;44.97979138419734;39.67671714856571
M0104 Alcippe;56.68151593952322;33.2470280743291
M0105 Alcis;60.95793425889352;36.873615634530374
M0106 Alea;58.09174858094748;24.58411928661517
M0107 Alexikakos;16.477577664601117;93.21044791038918
M0108 Aligena;47.16175004080273;23.98236353538602
M0109 Aliterios;24.775200437077814;41.197381963351745
M0110 Alkaia;51.20811828146669;86.97431161160415
M0111 Amaltheia;66.54790288255755;12.113124435655
M0112 Ambidexter;17.83266373210468;54.779271977165756
M0113 Ambologera;64.22101152504545;27.92209063299088
M0114 Amynomene;92.9677621251828;13.90395574651999
M0115 Anaduomene;36.40987474181856;10.700385309153049
M0116 Anaea;59.85471839964005;42.23535861740224
M0117 Anax;54.234164095514934;29.007234493706914
M0118 Anaxilea;37.615421051366496;71.26764563775367
M0119 Androdameia;94.67816978599463;71.82986287239653
M0120 Andromache;63.175247679695076;79.35862068473492
M0121 Andromeda;87.85073833668335;65.04636798900661
M0122 Androphonos;83.51776871207484;19.290347509058
M0123 Anosia;84.78361659604342;22.792381761969736
M0124 Antandre;66.59952431641507;74.91234961078325
M0125 Antania;30.317194837346705;56.68381562466812
M0126 Antheus;98.72579432423953;36.27474875658331
M0127 Anthroporraistes;11.65771197791946;49.539369084818375
M0128 Antianara;73.78586642962615;80.41258890409179
M0129 Antianeira;67.35021659733654;37.06288719681007
M0130 Antibrote;95.46907390762365;45.82150519190405
M0131 Antimache;83.69668390048588;30.887037138027097
M0132 Antimachos;7.430454042869561;92.66882009280246
M0133 Antiope;76.05887966225778;59.44621973240205
M0134 Antiopeia;38.347539105267444;47.91301673784806
M0135 Aoide;51.020694454692105;99.33801320198286
M0136 Apatouria;98.9074868612165;44.75849138091152
M0137 Aphneius;72.04482407089255;19.14885007686373
M0138 Aphrodite;95.98639189859063;79.25135758412104
M0139 Apollo;6.0438703548660655;60.16103617405544
M0140 Apotropaios;35.630253566200444;23.325995094800234
M0141 Areia;11.196021180241612;33.924662669064546
M0142 Areia;70.91977664894618;53.24096334039008
M0143 Areion;37.37071625516405;25.369299949320144
M0144 Areopagite;13.398800986905336;75.09674060239317
M0145 Ares;49.6897606277947;51.946836554939004
M0146 Areto;67.46883319087736;55.006748132476126
M0147 Areximacha;53.03458722615575;44.238157937827594
M0148 Argus;65.99979204099796;90.49693995750441
M0149 Aridnus;90.72049993465882;81.52289967218455
M0150 Aristaios;82.37976252543999;91.8382161813585
M0151 Aristomache;14.09382707359368;37.00270231477846
M0152 Arkhegetes;69.32417896492424;77.26973879562232
M0153 Arktos;71.46820075419384;61.68504351452133
M0154 Arretos;27.987528093784164;24.450249006280046
M0155 Arsenothelys;44.60118700452568;63.375934628281925
M0156 Artemis;42.268336606411964;61.978285146776976
M0157 Asclepius;68.82274932124318;17.796287581529292
M0158 Asklepios;22.670815983718505;29.45115439833935
M0159 Aspheleios;8.962164850412346;82.528115121804
M0160 Asteria;91.68426069181609;82.28642755132789
M0161 Astraeos;27.380114163872804;71.3131534280645
M0162 Athene;8.363877794509333;68.40861285731745
M0163 Auxites;72.69790244920792;86.16790383291392
M0164 Avaris;73.64446019522998;57.90757479461317
M0165 Axios;38.225866199854785;97.8454548556056
M0166 AxiosTauros;79.89088472804421;63.90416202736359
M0167 Bakcheios;87.62821359578302;11.365945645485908
M0168 Bakchos;68.28717777916269;53.11244366402658
M0169 Basileus;22.021662870802505;52.653821591222794
M0170 Basilis;35.88842035690244;7.966822786790795
M0171 Bassareus;67.49044051235069;64.76151608225526
M0172 Bauros;90.50756221829964;68.68623374998622
M0173 Boophis;94.91034155276127;7.725605464829588
M0174 Boreas;86.08172648135908;53.27650529243191
M0175 Botryophoros;45.00969709217082;14.792822645414748
M0176 Boukeros;83.76039175841787;26.225908755703397
M0177 Boulaia;20.755252953425874;69.56978270511951
M0178 Boulaios;74.68033474127131;62.52780533932915
M0179 Bremusa;26.436170791162606;33.59165374301496
M0180 Bromios;69.24002671121124;32.668180706686215
M0181 Byblis;78.22941938508585;71.87144846572586
M0182 Bythios;4.658717021325054;16.344839021962677
M0183 Caliope;84.56508388900927;95.18292008996427
M0184 Cedreatis;47.70315670948474;37.93883703680901
M0185 Celaneo;96.27020599294083;62.14659841333508
M0186 Cerberus;72.68755676821067;5.137726802849462
M0187 Charidotes;56.25495097665591;61.629776896101674
M0188 Charybdis;76.20000676736953;23.614034509030713
M0189 Chimera;36.415069711318836;26.537742080285575
M0190 Chloe;49.48128841430842;55.29133846687273
M0191 Chloris;35.45973711707524;13.764920158912386
M0192 Choreutes;66.97961450867584;85.48417387056084
M0193 Choroplekes;25.534047950408045;21.891025677047626
M0194 Chthonios;65.32752416278782;65.07695551571506
M0195 Clete;77.7905796132338;8.148689494004657
M0196 Clio;80.83480918042288;97.91097994561446
M0197 Clyemne;67.47460319504096;9.255478357515246
M0198 cockatrice;85.56398478132157;50.67744981476848
M0199 Crataeis;57.62266367403066;66.89459838806602
M0200 Custos;12.152507049836714;72.8684494943287
M0201 Cybebe;87.13443410913513;7.944993322338679
M0202 Cybele;85.7685633450724;27.716614930326976
M0203 Cyclops;43.76287691417991;32.00293697340445
M0204 Daphnaia;87.93494709633296;51.55822374069861
M0205 Daphnephoros;85.47790285494254;14.303682340144308
M0206 Deianeira;61.42815422237319;78.68327355635053
M0207 Deinomache;84.69390822967291;40.843031700947805
M0208 Delia;28.057519594736256;91.49007993560157
M0209 Delios;9.011685495421073;54.31522475762517
M0210 Delphic;31.851866558003906;81.6407833125032
M0211 Delphinios;19.41036755601806;4.424831597722756
M0212 Demeter;39.02877201317605;36.918110033639074
M0213 Dendrites;62.23527209208044;64.19683691236231
M0214 Derimacheia;23.09424635184666;0.6125695281608112
M0215 Derinoe;54.86257193432604;95.10042411213834
M0216 Despoina;38.518247057085084;85.5232652036455
M0217 Dikerotes;16.581962854693288;18.118477803953347
M0218 Dimeter;39.65412862299703;63.03430803914859
M0219 Dimorphos;76.02362878167698;75.3360928636246
M0220 Dindymene;32.9177648498882;89.23283201641887
M0221 Dioktoros;94.36592958575312;47.18793556376002
M0222 Dionysos;59.71475791321599;74.66338437673032
M0223 Discordia;79.59543720392138;24.195574689189858
M0224 Dissotokos;95.20178247512395;52.06752722516185
M0225 Dithyrambos;31.251059556585503;18.84240238321273
M0226 Doris;13.690787443929587;47.33625014043517
M0227 Dryope;47.36921962089964;43.175115637459925
M0228 Echephyle;15.352436165064443;12.906785177826151
M0229 Echidna;45.75710262922015;70.78716381453214
M0230 Eiraphiotes;30.847788475138227;39.96430814965005
M0231 Ekstatophoros;0.25623806984493847;48.03095573561483
M0232 Eleemon;20.614931398072265;26.062882308539905
M0233 Eleuthereus;69.31882460482754;18.62203916106995
M0234 Eleutherios;63.759897316778094;38.158946420505735
M0235 Ennosigaios;99.00427541945766;78.23987272716677
M0236 Enodia;87.84885117203106;77.55454054759412
M0237 Enodios;15.413761373575285;81.29619067549072
M0238 Enoplios;25.371221855141734;22.876351817926466
M0239 Enorches;82.61555150663526;80.73341535105257
M0240 Enualios;95.24106038207576;99.9706086486262
M0241 Eos;91.27419563537941;93.53192412689353
M0242 Epaine;98.4266253591457;3.4727122535004096
M0243 Epidotes;60.48168795595858;49.54642879283669
M0244 Epikourios;85.64578774582982;73.81444613614153
M0245 Epipontia;80.6989842940187;99.35810665073369
M0246 Epitragidia;2.0375399764326008;15.560458395608368
M0247 Epitumbidia;99.25130452212552;28.020524485181454
M0248 Erato;38.817552028504686;28.219670711829757
M0249 Ergane;51.480878410654526;45.89383561851478
M0250 Eribromios;25.148379255321483;9.0561455668292
M0251 Erigdoupos;70.44594639710986;5.203093163090222
M0252 Erinus;74.80251326601075;78.92784241381074
M0253 Eriobea;65.96492880149589;21.5229673047754
M0254 Eriounios;61.66925500171641;76.81062306976943
M0255 Eriphos;49.839905205668614;63.082520056602974
M0256 Eris;35.753907542796185;66.4187550530217
M0257 Eros;98.25363779210326;7.60015175432801
M0258 Euanthes;7.04054172995483;99.21208193058042
M0259 Euaster;84.61958172196933;56.30018249999824
M0260 Eubouleus;18.437184020524178;82.08392237698351
M0261 Euboulos;86.57444648778075;37.82897294151971
M0262 Euios;0.9949724100219992;5.152657358575052
M0263 Eukhaitos;69.338023811477;30.979898525935823
M0264 Eukleia;54.69045136529888;95.3339227796353
M0265 Eukles;74.32521434726007;84.45284732999451
M0266 Eumache;26.282857198886823;74.74915381440738
M0267 Eunemos;96.68024367244583;14.315417899465132
M0268 Euplois;62.105881326814625;19.53019224264928
M0269 Euros;18.313303515925384;15.399274709320776
M0270 Eurybe;98.1260708604244;34.20856376982084
M0271 Euryleia;74.0549635273749;31.55661447457855
M0272 Euterpe;12.19767885231322;79.63190772023128
M0273 Fates;67.7038718066605;91.5181011224859
M0274 Fortuna;4.166417698016167;18.228983069157355
M0275 Gaia;22.02839458383149;32.03495568201582
M0276 Gaieokhos;88.32225531285276;69.44858418043188
M0277 Galea;42.19304713427018;98.05438999579606
M0278 Gamelia;79.67401299876995;0.3265440567426281
M0279 Gamelios;95.6156812786652;30.86892665744999
M0280 Gamostolos;30.61621795006313;11.3890148489862
M0281 Genetor;62.92156121452502;29.49654116861522
M0282 Genetullis;27.781292048625428;16.479007378301358
M0283 Geryon;94.44564170204893;97.99001387602543
M0284 Gethosynos;90.21781286594988;56.59716669283649
M0285 giants;14.644486276517377;71.94026958070113
M0286 Gigantophonos;19.50828348211312;32.476623934762685
M0287 Glaukopis;52.8144220592667;51.1298445910499
M0288 Gorgons;40.037429448514864;88.36566590476214
M0289 Gorgopis;42.67271890954495;52.10910045090722
M0290 Graiae;33.3447692019029;30.370907151551584
M0291 griffin;25.643687871045806;34.40916070355905
M0292 Gynaikothoinas;14.342814731626518;16.717501072490393
M0293 Gynnis;13.101791463274658;47.17195917739564
M0294 Hagisilaos;19.154944535110708;14.41191139550735
M0295 Hagnos;11.358985416572509;89.16921069456846
M0296 Haides;74.42460781708225;77.04655867714469
M0297 Harmothoe;89.84368715989972;74.49851651842096
M0298 harpy;96.17022991876362;61.86468724990516
M0299 Hegemone;77.70389984527883;48.68620024877032
M0300 Hegemonios;22.607804859334703;70.70761636922983
M0301 Hekate;6.97723263152027;5.492911242254772
M0302 Hekatos;19.835821704359923;69.09548191257375
M0303 Helios;81.50561142404334;13.409421709335035
M0304 Hellotis;11.874831050991908;10.446448155088095
M0305 Hephaistia;39.93274925686671;72.64644151491166
M0306 Hephaistos;77.27664753002736;68.31836362322403
M0307 Hera;98.40751583397075;88.36369628705214
M0308 Heraios;23.365766779627638;58.560603612090446
M0309 Herakles;4.0265303050735834;63.94990905406536
M0310 Herkeios;96.14831459527434;15.392867442245583
M0311 Hermes;3.5844883767091607;89.35674543818061
M0312 HerosTheos;9.02143196116053;70.68156220415446
M0313 Hersos;33.860812594636336;23.80617677043524
M0314 Hestia;76.63870660108267;74.06327795715109
M0315 Heteira;69.45646172976019;49.632115648488075
M0316 Hiksios;21.63489583690581;83.06883301149212
M0317 Hipp;22.104841712754986;4.583615729393509
M0318 Hippia;81.38582886620712;47.030205098512454
M0319 Hippios;71.4158993459152;83.60829017418455
M0320 HippoiAthanatoi;79.57707228113249;6.306639106359979
M0321 Hippolyte;21.172685347094223;37.95104164215002
M0322 Hippomache;43.07755067690812;29.245047034884642
M0323 Hippothoe;17.584816999937193;89.3446008013591