Aaaannnh !
Eh beh, je croyais vraiment qu'on avait loupé l'évidence... (hier soir je croyais avoir trouvé la démo, mais en fait elle était fausse)
Version imprimable
Aaaannnh !
Eh beh, je croyais vraiment qu'on avait loupé l'évidence... (hier soir je croyais avoir trouvé la démo, mais en fait elle était fausse)
Au fait Alikendarfen, tu avais une idée pour la démo du P*max sur D' ?
Je n'y avais pas trop repensé, mais je ce que je disais est faux (dans le sens ou la preuve est un peu plus complexe).Citation:
Envoyé par Baruch
Je propose qu'on note (M1 < M2)(p) si M1M2 est optimal à p.
Si on reprend les règles utilisées par la première démo sur ABC seuls, écrire :
(a) t(MB) < t(BM) à p'
(b) t(MC) > t(CM) à p'
Partant de (a) et (b), on finit par déduire que t(BC) > t(CB) à p'
Revient à :
(M < B)(p') et (C < M)(p') => (C < B)(p')
Ou encore :
(C < M < B)(p') => (C < B)(p')
... bon ça c'est juste parce que c'est plus simple à écrire et lire.
On en était resté à deux cas non démontrés :
1/ C1 = Chemin+[Bi;Bj;...;Bz;Cj;A] optimal incohérent
2/ C2 = Chemin+[B;Ci;Cj;...;Cy;Cz;A] optimal incohérent
(ce qui signifie pas qu'on ait après ça traité tous les cas, mais ça peut toujours apporter des idées...)
1/ C1 = Chemin+[Bi;Bj;...;Bz;Cj;A] optimal incohérent ?
Soit pz la production avant Bz
(A < Bz)(p) car A et Bz dans D', p*max(D') <= p et A première de D'
donc
(A < Bz)(pz) car pz > p
et
(Bz < Cj)(pz) car C1 optimal
donc
(A < Cj)(pz)
Soit pj la production avant Cj
(Cj < A)(pj) car C1 optimal
Donc pz < p*(ACj) < pj
Mais
à p'
(M < A)(p') car A dans D'
et
(Cj < M)(p') car Cj n'est pas dans D'
donc (Cj < A)(p') contradictoire (même principe que ta version de la démo)
2/ C2 = Chemin+[B;Ci;Cj;...;Cy;Cz;A] optimal incohérent ?
A p'
(M < A)(p') car A dans D'
et
(Cz < M)(p') car Cz n'est pas dans D'
=>
(Cz < A)(p')
Et par ailleurs on a toujours (Cz < A)(pz) (pz étant la prod avant Cz)
Donc :p*max(ACz)p*(ACz) et p ne se croisent pas entre p' et pz
Soit py la prod avant Cy
On a (Cy < Cz)(py) et (Cz < A)(py)
Mais aussi (Cy < A)(p')
Donc :p*max(ACy)p*(ACy) et p ne se croisent pas entre p' et py
etc.
Donc au final, on devrait avoir Chemin+[B;Ci;A] optimal et on sait que c'est impossible
... donc déjà qu'en pensez-vous ?
Ensuite, a-t-on d'autres situations ?
Effectivement, l'erreur de mon raisonnement vient de ce que la courbe de p est un escalier, donc non continue. Ainsi, p peut traverser plusieurs p* d'un coup. C'est le cas dans le contre exemple d'Alikendarfen : en choisissant M1 en premier, on a p = 19 -> 103 qui traverse instantanément p*(M0,M1)=19.51 et p*(M0,M2)=53.94
je pense cependant que l'algo reste vrai lorsque p ne peut traverser plusieurs p*, pour les raisons que j'ai mentionnées. Pour ces même raisons, si le potentiel de Mi < au potentiel de Mj, et si p*(Mi,Mj) < p, on a Mi avant Mj dans la résolution finale.
on peut donc corriger l'algorithme de la façon suivante :
soit {Mi,Mi+1...Mn} une suite de mine dans l'ordre des potentiels croissants, p la production,
si p*(Mi,Mi+1)<p, alors on choisit Mi et on passe à la mine suivante.
si p<p*(Mi,Mi+1)<p+pi, alors il faut déterminer les p* que l'on peut croiser et trouver une façon simple de trouver la meilleure mine
si p*(Mi,Mi+1)>p+pi, je pense qu'on peut prendre Mi, mais il faudrait que j'y réfléchisse plu sérieusement ^^ sinon, il faut faire comme pour le cas précédent : déterminer les p* rencontrés.
La remarque de Sharcoux est intéressante, mais là je réponds aux démos d'Alikendarfen :
Tu remarqueras qu'avec les potentiels ça vient tout seul.Citation:
Si on reprend les règles utilisées par la première démo sur ABC seuls, écrire :
(a) t(MB) < t(BM) à p'
(b) t(MC) > t(CM) à p'
Partant de (a) et (b), on finit par déduire que t(BC) > t(CB) à p'
Revient à :
(M < B)(p') et (C < M)(p') => (C < B)(p')
Ou encore :
(C < M < B)(p') => (C < B)(p')
Je suis tout à fait d'accord avec ta démo.Citation:
1/ C1 = Chemin+[Bi;Bj;...;Bz;Cj;A] optimal incohérent ?
Citation:
2/ C2 = Chemin+[B;Ci;Cj;...;Cy;Cz;A] optimal incohérent ?
Autrement dit, on a :Citation:
(Cz < A)(p')
Et par ailleurs on a toujours (Cz < A)(pz) (pz étant la prod avant Cz)
Donc : p*(ACz) et p ne se croisent pas entre p' et pz
p*(ACz) < p'
ou alors
p*(ACz) > pz
On ne peut pas conclure dans quel cas on se trouve, puisqu'on ignore si A est plus rentable que Cz ou non.
Après tu fais ça avec tous les Ci, mais comment tu conclus que :
Je vois pas du tout comment tu fais.Citation:
Donc au final, on devrait avoir Chemin+[B;Ci;A] optimal et on sait que c'est impossible
Un truc (je sais pas si c'est intéressant) :
(B<Ci)(p) et (Ci<B)(p'), donc Ci est moins rentable que B, donc moins rentable que A.
et p' < p*(B,Ci) < p
Ici, c'est juste pour la notation qui est plus lisible (enfin, pour moi en tout cas ;)).Citation:
Envoyé par Baruch
Exact soit p*(ACz) < p' soit p*(ACz) > pz.Citation:
Envoyé par Baruch
Mais que ce soit à p' ou à pz, Cz est devant A.
Donc Cz est devant A pour toutes les valeurs de p entre p' et pz.
Ce qui permet de conclure que Cz est devant A à py (et c'est tout ce qui nous intéresse ici).
Parce que Cz peut être éliminé !Citation:
Envoyé par Baruch
Et puisqu'on a prouvé que (Cy < A)(py), Chemin+[....;Cy;A] est optimal (sans le Cz).
Donc on recommence le raisonnement => on élimine Cy... puis Cx... etc.
... pour finir par tomber sur Chemin+[B;Ci;A]
?... je vais y réfléchirCitation:
Envoyé par Baruch
J'ai trouvé ! Bon encore une fois t'as fait le plus gros du travail èé
Bon je recommence du début :
Soit D' = {A,B,B1,B2,...} l'ensemble des mines X telles que (M<X)p', avec A la plus rentable des mines de D'.
Les autres mines sont C1,C2,...
On a p > P*max(D'). Montrons que la liste idéale de E ne peut pas commencer par B.
Soit L un chemin commençant par B.
Si dans L, on a un Bi qui est juste avant A, alors L n'est pas idéale puisque (A<Bi) pour toute production supérieure à p.
Sinon, L est de la forme :
L = L'' @ L', avec L' de la forme L' = [B,C1,...,Cn,A]
(pour plus de clarté, j'ai renommé la mine de D' en B, et j'ai changé les indices des C, mais cela n'a pas d'importance)
Soit px la production de L''. Soit Pk = somme des productions des mines C1 à Ck.
Montrons que L' ne peut pas être idéale à p+px.
(M<A)p' et (Cn<A)p' impliquent (Cn<A) à p+px+P(n-2)
or (Cn-1 < Cn) à p+px+P(n-2)
donc (Cn-1 < A) à p+px+P(n-2)
Donc L'' @ [B,C1,...,Cn-1,A] est idéale à p.
Par récurrence décroissante sur n, on obtient finalement :
L'' @ [B,C1,A] est idéale à p.
Et puis j'imagine que la démo qui a été faite pour BCA marche toujours.
Edit : Bon en fait cette démo est fausse xD. Je m'explique :
Si [ABCD] idéale à p, et [BD] idéale à p+pA, alors [ABD] n'est pas nécessairement idéale à p.
MAIS, on s'en fiche, puisque dans la récurrence, ce n'est pas l'idéalité du chemin qui nous est utile, seulement l'idéalité 2 à 2.
Bon du coup, il faut réécrire cette démo, en étant bien rigoureux sur la récurrence.
Edit 2 : La démo entière n'est pas finie :
1) On a démontré la propriété sur D (avant)
2) On vient de démontrer la propriété sur l'ensemble des mines qui respectent l'optimalité avec M
Il reste donc à montrer la propriété sur D', ce qui n'est pas évident à première vue.
Edit 3 :
C'est bon j'ai réussi à faire le lien. Je fais la démo en latex.
Bon en fait j'arrive pas à finir la démo ^^ :
La démo du P*max sur D, que j'avais faite, est fausse. J'avais fait en fait la même erreur que Sharcoux :
Du coup j'arrive pas à faire la démo entière... :/Citation:
Le chemin idéal de E commence par P, si :
Quel que soit M dans E\{P}, quel que soit p dans [p0,+inf[, Tp([P,M]) <= Tp([M,P]) (*)
Donc il faudrait trouver comment on démontre la propriété sur D.
Je ne comprends pas... on était sur la bonne voie (je pensais).Citation:
Envoyé par Baruch
Peux-tu (précisément) expliquer là où ça ne va pas ?
... et par la même occasion indiquer ce qui n'irait pas non plus dans celle que j'ai proposée (après relecture, il manque une étape d'explication, mais cette étape est 'simple') ?
Je reprends la partie qui semble être celle sur laquelle on bute.
A p'Citation:
Envoyé par Alikendarfen
(M < A)(p') car A dans D'
et
(Cz < M)(p') car Cz n'est pas dans D'
=>
(Cz < A)(p')
Et par ailleurs on a toujours (Cz < A)(pz) (pz étant la prod avant Cz)
Donc : p*(ACz) et p ne se croisent pas entre p' et pz
Donc : (Cz < A)(py) avec py la prod avant Cy
On a (Cy < Cz)(py) et (Cz < A)(py)
Mais aussi (Cy < A)(p')
Donc : p*(ACy) et p ne se croisent pas entre p' et py
Donc : (Cy < A)(px) avec px la prod avant Cx
... etc. pour arriver à :
Donc : (Ci < A)(pi) avec pi la prod avant Ci
On a fini pour la 'descente'.
On prend maintenant le chemin inverse :
Par hypothèse : [BCi] optimal (car [BCi...CzA] optimal)
Soit A est avant B (mais auquel cas, c'est bon : A est première), soit A est après Ci (d'après la descente).
Donc [BCiA] optimale.
Puis [BCiCj] est optimal et A après Cj, d'après la descente.
Donc [BCiCjA] optimale.
Puis [BCiCjCk] est optimal et A après Ck, d'après la descente.
Donc [BCiCjCkA] optimale.
... etc. jusqu'à : donc [BCiCj...CzA] optimale.
Cependant, ce qui nous intéresse c'est seulement [BCiA] optimale qu'on sait être faux. Donc A avant B.
Ca n'est pas suffisant ??
En fait, si une mine A vérifie p*(AMi) < p pour toute Mi et que A est devant toutes les Mi, ça doit être la première à placer à la suite du chemin (ce qui est une condition moins forte que Vij p*max(MiMj) < p).Citation:
Envoyé par Sharcoux
Edit : dans la pratique, il peut y avoir plusieurs mines A. Auquel cas, il y a autant de solutions possibles à explorer.
... enfin... ça reste à démontrer tout ça !
Non, on n'a pas (Cy < A)(p'). Car pour ça il faut avoir (Cy < M)(p'), or Cy respecte peut-être l'optimalité 2 à 2 avec M. En effet, les Ci, ce sont des mines qui sont dominées, ou qui ne respectent pas l'optimalité 2 à 2 avec M. Donc Cy peut respecter l'optimalité 2 à 2 avec M, mais elle est donc dominée.Citation:
A p'
(M < A)(p') car A dans D'
et
(Cz < M)(p') car Cz n'est pas dans D'
=>
(Cz < A)(p')
Et par ailleurs on a toujours (Cz < A)(pz) (pz étant la prod avant Cz)
Donc : p*(ACz) et p ne se croisent pas entre p' et pz
Donc : (Cz < A)(py) avec py la prod avant Cy
On a (Cy < Cz)(py) et (Cz < A)(py)
Mais aussi (Cy < A)(p')
Si Cy respecte l'optimalité 2 à 2 avec M, alors on sait faire. Sinon :
Il existe une mine Bi qui domine Cy. Bi peut être supposée dans D, par transitivité de la relation de dominance.
Si Bi est dans D', ça marche, puisque [Cy,A] n'est donc pas optimal à py (on regarde le p* etc), et donc c'est absurde.
Si Bi est dans D, mais pas dans D' : c'est là que je coince.
Donc suite à ça :
Ce qui ne marche pas : identifier les mines A qui sont à la fois avant toutes les autres et telles que p <= p*(AMi) <= p+pA
Ce qui marche (mais j'ai peur que les contre-exemples soient juste rares) : identifier les mines A qui sont à la fois avant toutes les autres et telles que p <= p*(AMi) <= p+pA et en plus que p <= p*(AMi <= p+pMi
Pour info, quelques comparatifs sur 100 mines (jde elentarion)
NDO : 157s / 12 716 474 de chemins testés
NDO pmax : 14s / 1 026 738 c
NDO pmax V2 (cet algo) : 7ms / 101 c
Dijkstra : 3s / 102 429 c
Dijkstra pmax : 810ms / 27 443 c
Dijkstra pmax V2 (cet algo) : 10ms / 101 c
Non non : Cy n'est pas dominée. Les Ci sont uniquement des dominantes (après M) qui ne respectent pas (M < Ci)p'Citation:
Envoyé par Baruch
Et on a démontré avant qu'une mine dominée ne peut pas prendre la place de A.
Encore non, désolé. Bi est dans D', par définition (ce sont les Ci qui sont dans D et pas dans D').Citation:
Envoyé par Baruch
Donc au final, on a bien (Cy < M)(p') car (M < Cy)p' est faux.
Par contre, ça a été mal formulé (par moi). J'aurais du dire :
- D = l'ensemble des mines dominantes après M
- D' = les mines de D telles que (M < Bi)p'
- et j'aurais du nommer D'' = les mines de D telles que (M < Ci)p' est faux
(alors que j'ai utilisé D à la place de D'' dans les démos)
Mais à cette erreur de formulation près, ça me semble ok..., non ?
Je pense que non :Citation:
Envoyé par Alikendarfen
oui, quand on classe les mines par ordre de potentiels, ont peut avoir deux mines au même potentiel (disons A1 et A2). Dans ce cas, ça veut dire que
p = p*(A1,A2). Mais p est croissante ! Je suis donc persuadé que la mine à choisir est celle qui aura le plus faible potentiel à p' > p.
Désolé d'avancer beaucoup d'hypothèses sans les prouver. Mais je me dis qu'on aura qu'à faire les preuves quand on aura trouvé un algo qui marche sur les tests ^^
Au fait, on peut avoir ton dernier algo Alikendarfen, parce que j'avoue que je suis pas sûr d'avoir compris ce que tu fais au final
et si tu veux des contre-exemples au passage, regarde ces ensembles de mines Mi = (c[i],p[i]) avec p0 = 1. Je les ai dimensionné pour générer plus ou moins des cas critiques.
c=[3/4,1,2];
p=[9/10,1,6];
c=[1/2,1,2];
p=[3/8,1,6];
A voir... pour le moment, je reste sur des données plus basiques, à savoir : a-t-on à p t(M1M2) < t(M2M1) ou non (c'est équivalent au potentiel mais c'est juste plus "directement parlant" et l'éventuelle différence de temps de calcul importe peu).Citation:
Envoyé par Sharcoux
Si plusieurs mines sont sélectionnées et ont le même potentiel, je ne choisis pas l'une ou l'autre (on pourra ajouter cette optimisation plus tard).
De là, je vais chercher parmi les mines Mi restant à placer à p celles Mj qui vérifient :
Pour tout i :
- p*(MiMj) <= p ou p*(MiMj) >= p + max(pMi, pMj)
- t(MjMi) <= t(MiMj)
Il se trouve que si on teste seulement :
- p*(MiMj) <= p ou p*(MiMj) >= p + pMj
- t(MjMi) <= t(MiMj)
ça ne marche pas (contre-exemples trouvés).
Voici le code de l'algo.Citation:
Envoyé par Sharcoux
Fonction principale (point d'entrée) :
Code:
2
3
4
5
6
7
8
9
10
11
12
13
14// Initialisation d'un chemin vide traitant les dominances absolues Chemin cheminInitial = Chemin.CreerAvecDominances( mines, p ); // Le meilleur chemin initial 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; } );
La fonction portant l'algo proprement dit :
Code:
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
31void Traiter( Chemin chemin, Action<Chemin> action ) { // Plus de mines à ajouter : produire un résultat if ( chemin.MinesNonTraitees.Count == 0 && action != null ) action( chemin ); else { // Identification des mines optimales 2 à 2 à la suite immédiate du chemin List<Mine> nonTraiteesOptimales = Proprietes.Optimales2a2Apres( chemin, chemin.MinesNonTraitees ); // Sélection de celles qui sont avant toutes les autres List<Mine> meilleures = Proprietes.MeilleuresMinesAp( nonTraiteesOptimales, chemin.Production ); // Les mines candidates sont les meilleures (s'il y en a) ou sinon les non traitées opt2à2 List<Mine> candidates = meilleures.Count == 0 ? nonTraiteesOptimales : meilleures; // Pour chaque mine parmi les mines candidates foreach ( Mine candidate in candidates ) { // Créer un nouveau chemin identique au chemin actuel Chemin nouveauChemin = chemin.CreateCopy(); // Lui ajouter la mine nouveauChemin.AjouterMine( candidate ); // Et récursion Traiter( nouveauChemin, action ); } } }
Et la fonction qui trouve les meilleures mines à p avec les règles dont on parle :
Code:
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
28public static List<Mine> MeilleuresMinesAp( List<Mine> mines, double p ) { List<Mine> resultat = new List<Mine>(); foreach ( Mine m1 in mines ) { bool toujoursMeilleure = true; foreach ( Mine m2 in mines ) { // Calcul du p* de ces mines double pEtoile = PEtoile( m1, m2 ); // Si p* est dans la 'mauvaise plage' ou si t(M2M1) < t(M1M2), ça n'est pas la bonne mine if ( (pEtoile > p && (pEtoile < p + Math.Max( m1.Production, m2.Production))) || Optimales2a2( m1, m2, p ) == false ) { toujoursMeilleure = false; break; } } if ( toujoursMeilleure ) resultat.Add( m1 ); } return resultat; }
Oui, j'avais fini par remarquer que ne tester que sur p + pA ne marchait pas... Même si, intuitivement, j'ai un petit peu de mal à comprendre...
Du coup, je pense que j'ai à peu près le même algo que toi.
edit: par contre, j'ai beaucoup de mal à comprendre tes réticences à utiliser le potentiel. En l'utilisant, tu peux avoir en n calcul les résultats qu'il te faudrait n(n-1)/2 opérations pour avoir avec les comparaisons 2 à 2... Et même : tu ne trouves pas qu'il est plus facile de gérer une suite d'inégalités du type µ(A)<µ(B)<µ(C)... plutôt que µ(A)<µ(B) & µ(A)<µ(C) & µ(B)<µ(C) ?
... mais tester sur p+pA et p+pB n'est pas très satisfaisant non plus ! Il n'y a rien de 'physique' qui le justifie... puisque ça n'est pas B qu'on place. Donc ?? L'algo est probablement faux ??Citation:
Envoyé par Sharcoux
Edit : dans la pratique, c'est p+max(pB) qui compte (dans l'algo). Ca a 'davantage de sens'.
... il y a deux raisons.Citation:
Envoyé par Sharcoux
Une raison générale : j'ai maintenant une bonne dizaine d'algo avec pour chacun plusieurs variantes et je préfère pour le moment garder les mêmes bases pour tous (une fois les résultats complètement avérés, je ferai les optimisations).
Et concernant cet algo : l'idée était bien pour moi, au départ, de regarder les choses par couple de mines. Certes j'aurais pu faire comme suit :
- trouver la (ou les) premières selon le potentiel
- et ensuite comparer les choses deux à deux seulement pour celle(s)-ci
...
Mais bon : la vraie question est 'quelle est la bonne règle' ?
Une petite remarque/réflexion concernant le potentiel :
On peut écrire : c1(1 + p/p1) < c2(1 + p/p2)
Mais on peut aussi écrire :
p1/c1(p+p1) > p2/c2(p+p2)
Avec ri = pi/ci, le rendement de la mine, on a :
r1/(p+p1) > r2/(p+p2)
Je pense que ri/(p+pi) serait une meilleure définition du potentiel, puisque ça fait apparaitre plusieurs choses :
- Ce potentiel est plus fort en début de chemin (ce qui est approprié car plus p est grand, plus l'apport d'une mine est faible)
- Cela correspond à une atténuation du rendement du fait de p et de la mine elle-même
- Cela '''montre''' (avec plein de guillemets) une projection à p+p1 d'un côté et p+p2 de l'autre, ce qui éclairerait la règle (non démontrée) qui voudrait que l'inégalité doit encore être vraie à p=p+max(p1,p2)
... évidemment, tout ça ne change rien à l'algo !
Un petit bug s'était malencontreusement glissé... donc pour le moment, toujours pas de contre exemple
:?
bon... ce matin, le hasard nous sort des contre-exemples !! (pourquoi ce matin et pas avant... c'est une autre histoire...)
Sur 3 millions de tirages de 5 mines, 6 cas.
Les voici ci-dessous. Ca vaut le coup que vous les vérifiiez (mon implémentation peut être fausse quelque part) !
Ci-dessous,
- NDO = naïf avec dominance et opt 2 à 2 (l'algo de référence)
- NDO Pmax 2 = l'algo basé sur les potentiels (le dernier publié).
- M0;5;2 = la mine M0 de cout 5 et production 2
p=15
M0;5;2
M1;10;8
M2;25;100
M3;30;74
M4;45;55
NDO : 2,22645634637794[1,67:M2/25/100][1,93:M3/30/74][2,17:M4/45/55][2,21:M1/10/8][2,23:M0/5/2]
NDO PMax 2 : 2,24579329321054[0,67:M1/10/8][1,75:M2/25/100][2,00:M3/30/74][2,23:M4/45/55][2,25:M0/5/2]
p=51
M0;28;85
M1;38;77
M2;62;76
M3;4;5
M4;69;53
NDO : 1,36630826254782[0,55:M0/28/85][0,83:M1/38/77][0,85:M3/4/5][1,13:M2/62/76][1,37:M4/69/53]
NDO PMax 2 : 1,3670324659241[0,08:M3/4/5][0,58:M0/28/85][0,85:M1/38/77][1,13:M2/62/76][1,37:M4/69/53]
p=40
M0;63;70
M1;94;54
M2;11;5
M3;69;50
M4;86;22
NDO : 3,23341376089664[1,58:M0/63/70][2,20:M3/69/50][2,27:M2/11/5][2,84:M1/94/54][3,23:M4/86/22]
NDO PMax 2 : 3,23739103362391[0,28:M2/11/5][1,68:M0/63/70][2,28:M3/69/50][2,84:M1/94/54][3,24:M4/86/22]
p=10
M0;14;15
M1;22;57
M2;37;4
M3;44;90
M4;21;90
NDO : 2,79815631305919[2,10:M4/21/90][2,32:M1/22/57][2,60:M3/44/90][2,66:M0/14/15][2,80:M2/37/4]
NDO PMax 2 : 2,82833967536026[1,40:M0/14/15][2,24:M4/21/90][2,43:M1/22/57][2,69:M3/44/90][2,83:M2/37/4]
p=10
M0;26;65
M1;61;33
M2;41;8
M3;5;2
M4;62;47
NDO : 4,22007122799808[2,60:M0/26/65][3,43:M4/62/47][3,93:M1/61/33][3,96:M3/5/2][4,22:M2/41/8]
NDO PMax 2 : 4,22494345254773[0,50:M3/5/2][2,67:M0/26/65][3,47:M4/62/47][3,96:M1/61/33][4,22:M2/41/8]
p=91
M0;70;98
M1;18;14
M2;91;46
M3;74;95
M4;40;16
NDO : 1,64579363973952[0,77:M0/70/98][1,16:M3/74/95][1,22:M1/18/14][1,53:M2/91/46][1,65:M4/40/16]
NDO PMax 2 : 1,65064908145752[0,20:M1/18/14][0,86:M0/70/98][1,23:M3/74/95][1,53:M2/91/46][1,65:M4/40/16]