Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Une idée, comme ça :
Si on trace une courbe où X = date et Y = la production totale, quelle serait la forme de notre chemin idéal ?
Par exemple, une parabole ? Ou en tout cas une courbe dont la dérivée est le plus fortement croissante ? Ou peut-être la courbe la plus continue possible ?
Si on vise une certaine courbe, ou du moins le respect de propriétés liées à cette courbe, peut être aura-t-on la possibilité de séquencer les mines pour respecter sa forme générale ?
Hmm bonne question...
En tout cas ce qui se passe globalement dans une liste idéale, c'est que les productions sont décroissantes et les coûts croissants.
Mais attention : on pourrait en effet peut-être trouver des méthodes qui permettent de trier "globalement" la liste, mais :
- ceci ne fournit pas la liste idéale
- on n'a pas algorithme qui est plus rapide lorsque la liste est "à peu près" triée
Enfin bon, dans le style on peut reprendre l'idée de JeitEmgie avec des probabilités.
Comme j'ai pas posté depuis longtemps, voilà ce que j'ai fait entre temps :
- J'ai revu ma démo de la dominance :
Je l'ai renommée "dominance absolue", car elle ne nécessite la connaissance que des 2 mines, pas du contexte dans lequel on les place (les autres mines, et p0).
J'ai grandement simplifié la démo, j'ai honte d'avoir publié une version aussi moche ^^. Voici la démo simplifiée (et donc bien plus compréhensible).
J'ai réfléchi à l'idée de "dominance" : les conditions de dominance absolue (p1>p2 et c1<c2) peuvent être affinées car dans le problème on connaît les autres mines et la production initiale p0. On peut ainsi donner des conditions un peu moins fortes.
J'ai commencé à faire la démo de la dominance simple, mais j'en suis à la moitié et le plus dur reste à faire.
Ce qui est très intéressant dans cette dominance, c'est qu'on peut recalculer les relations de dominance à chaque fois qu'on change la liste ou le p0, on peut donc l'appliquer à chaque sous-liste étudiée, ce qui me paraît très intéressant.
- L'implémentation en Caml :
Je n'arrive pas à trouver une bonne implémentation pour l'algo naïf avec dominance absolue (et d'ailleurs celle que j'ai fait ne marche pas)
Il faut que je remanie l'algo par combinaisons pour pouvoir par la suite ajouter les dominances (car si on veut un algo efficace, ce n'est pas avec l'algo naïf qu'il faut travailler).
Attention à votre dominance absolue : il est facile de concevoir des jeux de données dans lesquels aucune mine ne domine une autre selon votre définition, et dans ceux-là il faut une autre approche.
Une définition plus souple serait déjà celle dans laquelle vous substituez le rendement à la production.
M1(60;13) et M2(109;21) n'a pas de relation de dominance selon votre définition alors qu'avec le rendement au lieu de la production M1 domine M2.
(0.2167 > 0.1927 et 60 < 109 …)
Par contre si vous avez un graphe suffisamment dense en relations de dominance, les mines qui n'ont pas de relation orientées seraient probablement les seules qu'il faut faire bouger dans l'exploration combinatoire, ce qui peut réduire très fortement l'arbre.
Exemple si on a un graphe (1->2),(1->3),(1->4),(2->4), les 2 seules combinaisons à comparer seraient 1,2,3,4 et 1,3,2,4.
Maintenant reste à trouver une méthode efficace pour les îlots de mines sans dominance entre elles…
(avec le cas extrême évoqué au début : quand l'îlot est tout le problème initial…)
Quant à votre démo : j'ai un doute sur votre
"La permutation de Mi et Mj dans L ne modifie pas le temps d’attente pour les mines M1,...,Mi−1 ni pour les mines Mj+1, ... , Mn, puisque la production générée par la liste L′ = (Mi, ... , Mj ) ne varie pas. Aussi, il convient de n’étudier que la liste L′."
qu'on atteigne le même niveau de production est une chose, qu'on l'atteigne dans le même délai en est une autre…
Tout à fait d'accord. Les dominances sont assez fréquentes sur des listes aléatoires, mais effectivement il y a des cas où il n'y en a pas.Attention à votre dominance absolue : il est facile de concevoir des jeux de données dans lesquels aucune mine ne domine une autre selon votre définition, et dans ceux-là il faut une autre approche.
Oui mais à quoi servirait cette définition de la dominance ? Comparer les coûts et le rendement est une condition plus faible que la dominance absolue : comparer les coûts et les productions entre eux. En effet il peut y avoir une relation de dominance au sens que vous définissez, mais pas de dominance absolue.Une définition plus souple serait déjà celle dans laquelle vous substituez le rendement à la production.
Or, j'ai démontré qu'une mine est toujours avant une autre, quelles que soient les autres mines, leur ordre, et la production initiale, si et seulement si il y a une dominance absolue entre ces 2 mines (au sens de la comparaison entre les coûts et entre les productions).
On peut donc avoir une dominance au sens que vous définissez, mais trouver des cas où l'ordre relatif des 2 mines est différent, ce qui n'apporte pas grand chose je pense (à moins de parler de probabilités peut-être...)
Oui, bien entendu ce problème reste inchangé (le meilleur algorithme qu'on ait trouvé est en 2^n).Maintenant reste à trouver une méthode efficace pour les îlots de mines sans dominance entre elles…
(avec le cas extrême évoqué au début : quand l'îlot est tout le problème initial…)
Oui ce n'est pas très clair :Quant à votre démo : j'ai un doute sur votre
"La permutation de Mi et Mj dans L ne modifie pas le temps d’attente pour les mines M1,...,Mi−1 ni pour les mines Mj+1, ... , Mn, puisque la production générée par la liste L′ = (Mi, ... , Mj ) ne varie pas. Aussi, il convient de n’étudier que la liste L′."
qu'on atteigne le même niveau de production est une chose, qu'on l'atteigne dans le même délai en est une autre…
On veut comparer le temps de construction des listes :
Lij = (M1,...,Mi−1,Mi,Mi+1,...,Mj-1,Mj,Mj+1,...,Mn)p0 et Lji = (M1,...,Mi−1,Mj,Mi+1,...,Mj-1,Mi,Mj+1,...,Mn)p0
Le temps de construction d'une concaténation de sous-listes est la somme des temps de construction des sous-listes (initialisées avec la bonne valeur de p0).
Le temps de construction d'une liste donnée ne dépend que de ses mines, de leur ordre, et de la production initiale.
Ainsi dans les listes Lij et Lji, le temps de construction de la sous-liste (M1,...,Mi−1) ne varie pas.
De plus, le temps de construction de la sous-liste (Mj+1,...,Mn) dépend de la production résultante juste avant l'occurrence de cette sous-liste. Or cette production étant la somme de p0 et de la production de chaque mine déjà construite, la permutation des mines Mi et Mj ne modifie pas cette somme. Aussi, que ce soit pour les listes Lij ou Lji, le temps de construction de la sous-liste (Mj+1,...,Mn) est invariant.
La variation du temps de construction total entre les listes Lij et Lji n'est donc dû qu'à la variation du temps de construction de la sous-liste du milieu :
(Mi,Mi+1,...,Mj-1,Mj) ou (Mj,Mi+1,...,Mj-1,Mi).
Il suffit donc dans ce problème d'étudier la différence entre les temps de construction de ces 2 sous-listes.
Tout simplement à avoir plus souvent des relations orientées dans le graphe donc réduire encore plus l'arbre des combinaisons à explorer.Envoyé par Baruch
Pour ajouter les dominances dans l'algo par combinaisons :Il faut que je remanie l'algo par combinaisons pour pouvoir par la suite ajouter les dominances (car si on veut un algo efficace, ce n'est pas avec l'algo naïf qu'il faut travailler).
- dans la version actuelle de l'algo, chaque chemin exploré est complété des mines non encore traitée par paires de mines : c'est une petite optim qu'il faut abandonner si on veut traiter les dominances (trop compliqué)
- ensuite il faut pour chaque mine la liste des mines qu'elle domine : c'est une table T1 stable tout au long du déroulement de l'algo
- puis pour chaque chemin en cours d'exploration une table T2 des mines dominées associées chacune à un compteur des dominantes restant à traiter pour cette dominée dans le cadre de ce chemin :
Quand on ajoute une mine lors de l'exploration, on regarde si elle est dans T.
Puis pour chaque mine dominée en vis à vis d'elle dans T, on décrémente son compteur dans T2 : si le compteur tombe à 0, la mine dominée est libérée car toutes ses dominantes sont déjà placées et elle peut rejoindre la liste des mines non traitées du chemin.
La mine ainsi libérée rentre alors 'naturellement' dans le cadre de l'algo.
La table T1 est de la forme : Dictionary<Mine, List<Mine>>
La classe chemin devient :
C'est ce qui me semble le plus efficace (?)
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8
9
10
11
12
13class Chemin { public List<Mine> MinesNonTraitees = new List<Mine>(); public List<MineDatee> MinesDatees = new List<MineDatee>(); public double Production; public double DateFin; public BitVector Positions; public Dictionary<Mine, int> Dominees; ... }
Pour info, un 'Dictionary' est une table de hashage (accès en lecture écriture à un élément en o(1)).
L'algo que j'avais posté est essentiellement itératif (et pas forcément le plus naturel pour un langage fonctionnel).
J'essaye de vous donner une version (C#) asap (mais pas sûr que j'ai le temps à court terme).
Bon, regardez, ce que j'ai montré dans ma démonstration, c'est :Tout simplement à avoir plus souvent des relations orientées dans le graphe donc réduire encore plus l'arbre des combinaisons à explorer.
Soit une liste aléatoire de mines, initialisée avec une valeur de p0 aléatoire. Si dans cette liste on a Mj avant Mi, mais avec Mi qui domine absolument Mj, alors il existe une meilleure liste : la liste de départ dans laquelle on permute Mi et Mj.
Dans ces conditions, la seule relation de dominance qui marche est de comparer les productions entre elles et les coûts entre eux.
Pour votre dominance (comparer les coûts et comparer les rendements) :
M1 : p1 = 3 , c1 = 1
M2 : p2 = 4 , c2 = 2
on a c1 < c2 et p1/c1 > p2/c2
Soit M : p , c
Pour la liste M1,M,M2 , T = 1/p0 + c/(p0+3) + 2/(p0+3+p)
Pour la liste M2,M,M1 , T = 2/p0 + c/(p0+4) + 1/(p0+4+p)
Or si c tend vers l'infini, la liste M2,M,M1 est meilleure. Votre dominance ne permet pas de garantir que placer M1 avant M2 est toujours mieux.
MAIS, et sur ce point peut-être avez-vous raison (après démonstration bien entendu) :
Peut-être que dans la liste idéale, M1 est nécessairement avant M2.
Dans le cadre de ma dominance absolue, on est certain que dans la liste idéale les dominances sont respectées.
Dans la vôtre, c'est peut-être le cas (peut-être, à démontrer ou à réfuter).
En effet ici la liste M2,M,M1 n'est pas idéale je pense si c devient très grand (il est plus probable que la liste idéale soit M1,M2,M, à moins que p soit très grand également, peut-être).
Comme après tout seul l'ordre des mines dans la liste idéale est intéressant, il est vrai que la dominance absolue que je définis n'est peut-être pas la seule à garantir la propriété de bon ordre dans la liste idéale. Néanmoins je n'accepterai pas d'autres relations sans démonstration ^^
@ Alikendarfen
ok je regarde ça
Autre (pseudo) relation de dominance locale ?
Partant de p, soit deux mines M1, M2 :
Si c1 < c2, on ne sait décider de l'ordre de ces mines dans le cas où p1 < p2.
Dans ce cas, il y a un intervalle de temps (partant de p) entre les achats potentiel de ces mines : dt = c2/p - c1/p.
Proposition :
Si pendant dt, avec donc une production de base p+p1, il est possible d'acquérir une ou plusieurs autres mines (éventuellement incluant M2) telles que à t = c2/p la production soit supérieure ou égale à p+p2 [et le cout total d'achat soit >= à c2], alors nécessairement M1 avant M2.
Sinon, M2 avant M1.
Je ne sais si la partie entre crochet [] est nécessaire (sans doute ?).
... dans la pratique ça apporte quoi ? Une approche récursive d'exploration !
Car sur dt, avec toutes les autres mines (hors M1) on recommence, mais l'intérêt est qu'on ne travaille que sur les dt successifs.
A l'issue d'une exploration :
- Soit M1 > M2
- Soit M2 < M1
- Soit pas de décision
Mais si on décide (par ex M1 > M2), il n'est plus utile d'effectuer la même opération avec M2 versus les autres Mi.
-------------------
Autre remarque complémentaire de tous les algos (mais qui est dans la même idée, en fait) :
Dans le cadre de l'exploration des solutions, on peut appliquer la relation de dominance aux chemins en cours eux-mêmes.
Par exemple (ça n'est qu'un exemple : il faudrait trouver si possible des conditions plus faibles), soit deux chemins E1, E2 : si temps(E1) < temps(E2) et production(E1) > production(E2) et cout(E1) > cout(E2) alors E1 domine E2.
Je disais :
Mais en fait ça devrait être
car ça amène toujours à une décision, non ?A l'issue d'une exploration :
- Soit M1 > M2
- Soit M2 < M1
Il est plus que temps de remettre clairement les règles du jeu noir sur blanc…
car ici il me semble que l'on mélange un raisonnement discret avec un vocabulaire continu.
En continu cela implique que l'on travaille sur une limite pour dt -> 0
(au passage vous voyez bien qu'il y a toujours un delta t… je n'avais pas répondu car c'est trivial à partir du moment où l'on parle de production comme quantité par unité de temps… )
mais dans ce cas à l'instant t il n'y a jamais plusieurs mines à acheter en même temps (mais on peut avoir un choix trivial entre plusieurs mines de même coût…)
tandis qu'en approche discrète alors oui il peut avoir plusieurs mines à acheter à un temps t car il y aura un montant résiduel potentiel après un achat qui permettra ou non d'acheter une mine supplémentaire, montant résiduel qui est reporté (ajouté à P courant au tour suivant si on n'a pas pu le dépenser…).
Par ailleurs, n'y-t-il pas contradiction avec la règle énoncée quelque part plus avant qui voudrait qu'on achète obligatoirement une mine dès que possible et le fait que l'on puisse attendre pour acheter une mine plus chère mais qui donnerait un meilleur résultat : il faut réécrire les règles clairement pour lever cette ambiguïté.
Bon, soyons clair (c'est moi qui fixe les règles, c'est mon post ! :p)
Il n'y a pas de tours : on n'étudie pas la question d'acheter ou pas une mine chaque jour (par exemple). On étudie cette question continûment. Ceci n'implique bien évidemment pas qu'on achète n'importe qu'elle mine dès qu'on peut la payer. En revanche, cela implique qu'après chaque achat de mine, on n'a plus d'argent.
On a un nombre fini de mines.
Est-ce clair ?
Bonjour tout le monde,
j'aimerais revenir vous donner un coup de main, maintenant que mes exams sont passés, j'aurais plus de temps à vous accorder. Je pense que le problème est très intéressant, il est possible que le problème du Built Order ne soit pas encore traité dans la littérature.
Pourriez-vous me faire un résumé du problème tel qu'il est maintenant connu ? J'ai parfaitement compris les règles initiales (notamment concernant la continuité en temps mais la discrétion en solutions). En revanche, qu'en est-il des outils mis en place :
- Quelle est la dominance partielle la plus fine qui ait été mise en œuvre pour l'instant ?
- Une solution par insertion serait-elle valide (Insérer les mines une à une − dans un ordre prédéfini selon une règle générale − à la meilleur place ; cela donne-t-il une liste idéale) ?
- Ce problème se rapproche-t-il d'un problème connu ?
- Si une liste (L,p0) contient une sous liste L'=[A...], (L',p0') est-elle idéale pour p0' vallant la production totale de L avant la construction de A ?
- Si oui, la réciproque est-elle vraie ?
N'hésitez pas à me donner des informations supplémentaires.
Cordialement,
-- Yankel Scialom
Eh ! Ne vous fachez pas les gars !
On est en temps continu. Mais une mine s'achète d'un seul coup.
Pour le dt dont je parlais, il ne faut pas qu'il y a ait de confusion : c'est l'écart entre la date possible d'achat d'une mine plus chère par rapport à la date possible d'achat d'une mine moins chère partant d'une production p (aucune notion faisant tendre dt vers 0 ou autre dans ce cadre).
Maintenant si néanmoins p2 > p1, l'algo que je proposais peut permettre de discriminer le meilleur choix parmi acheter M1 tout de suite ou acheter M2 tout de suite.dt = c2/p - c1/p
Ce 'sous calcul' comporte également une combinatoire.
Cependant, cette combinatoire est réduite car elle est bornée dans le temps par dt.
D'où le gain potentiel sur la complexité globale.
Maintenant, il va falloir approfondir l'algo pour concrétiser tout ça.
Du renfort !
Bon retour prgasp. Et j'espère que tes exams se sont bien passés.
Alors, quelques réponses (et je pense Baruch corrigera/complètera) :
Dominance globale : p1 > p2 et c1 < c2Quelle est la dominance partielle la plus fine qui ait été mise en œuvre pour l'instant ?
Locale : meilleur choix M1M2 ou M2M1 (selon p et indépendamment de la suite)
Et par ailleurs, l'idéalité 2 à 2 n'implique pas une idéalité globale.
Une solution par insertion a été trouvée, mais elle ne donne pas toujours le meilleur résultat. Je n'ai plus les chiffres en tête, mais en ordre de grandeur : elle est correcte dans 95% des cas et quand elle n'est pas optimale elle est proche de la meilleure solution à < 10% près. Mais évidemment les limites de ce comparatif sont liées au fait de pouvoir calculer les solutions avec un algo exact.Une solution par insertion serait-elle valide (Insérer les mines une à une − dans un ordre prédéfini selon une règle générale − à la meilleur place ; cela donne-t-il une liste idéale) ?
Pas à ma connaissance.Ce problème se rapproche-t-il d'un problème connu ?
Edit : oui si L est idéale. Et pour la réciproque non (l'idéalité 2 à 2 n'implique pas un chemin global idéal).Si une liste (L,p0) contient une sous liste L'=[A...], (L',p0') est-elle idéale pour p0' vallant la production totale de L avant la construction de A ?
Si oui, la réciproque est-elle vraie ?
Je ne suis pas totalement sûr mais je pense que non. A moins que L' termine L.
Pourquoi ? Parce que le problème est quasi symétrique : on peut aussi le prendre en partant de la fin.
Etes vous d'accord sur ce point ?
Petit complément sur la dernière question :
en fait, c'est grâce à cela qu'on a pu produire un algo "par combinaisons" :Edit : oui si L est idéale. Et pour la réciproque non (l'idéalité 2 à 2 n'implique pas un chemin global idéal).Si une liste (L,p0) contient une sous liste L'=[A...], (L',p0') est-elle idéale pour p0' vallant la production totale de L avant la construction de A ?
Si oui, la réciproque est-elle vraie ?
Partant du principe d'une exploration globale, on réduit à chaque étape les cas possibles en ne gardant qu'un meilleur chemin E parmi les chemins comprenant exactement les mêmes mines que E.
ok,
donc si on met en parallèle votre notion de dominance absolue on peut se poser la question : existent-ils des cas où des mines prises séparément n'ont pas de relation de dominance absolue avec une mine tierce mais mises ensemble, elles en auraient une, auquel cas selon votre critère absolu il faudrait les mettre ensemble…
pour que M1 et M2 puissent être mises ensemble et dominer M3 alors qu'elles ne la dominent pas séparément il faut que la dominance ne soit pas respectée uniquement à cause du test sur P (C1+C2< C3 ne peut pas être vrai si déjà C1 ou C2 > C3…)
donc
not(p1 ≥ p3) and not(p2 ≥ p3) and (p1+p2 ≥ p3)
doit être vérifié.
M1=(10;4) M2=(5;4) M3=(15.1;7.9)
ni M1, ni M2 prises séparément ne dominent M3 puisque p1 et p2 < p3 mais ensemble oui : 10+5 < 15.1 et 4+4 > 7.9
donc si on a une situation M1(c1; p1) M2(c2;p2) M3(c1+c2+d1;p1+p2-d2) (d1, d2 > 0) dans laquelle ni M1 ni M2 ne domine M3 séparément,
quelles sont les conditions sur d1 et d2 pour que M3 puisse se glisser entre M1 et M2 (ou M2 et M1) dans la meilleure solution ?
si les conditions sur d1 et d2 conduisent à une contradiction avec les hypothèses alors vous aurez renforcé votre notion de dominance absolue car elle s'étendra aux groupements (ils font un bloc soudé face à un indéterminé qu'ils dominent ensemble) dans le cas contraire vous aurez de nouvelles conditions pour déterminer quand la fusion conduit à une relation absolue.
C'est exactement l'esprit du dernier algo que j'ai proposé !!
A la variante près que ce calcul de dominance multiple est défini dynamiquement et contextuellement.
J'ai fait un petit test avec l'algo par combinaison et l'exploitation des dominances (c1 < c2 et p1 > p2).
C'est plutôt pas mal en termes de perf :
52 mines (quelconques)
44 dominantes (pouvant chacune éventuellement être dominée par une autre)
46 dominées (dominées 1 ou plusieurs fois)
Temps de calcul : 62s
Nombre de chemins calculés : 4 147 377 (ce qui est plutôt pas mal comparé aux 2^52 chemins possibles de l'algo par combinaisons).
Je vous transmets l'algo dans les prochains posts.
Comme l'autre fois, en deux parties (car c'est un peu long) :
- Les données de base
- L'algo lui même
Pour résumé, il y a eu, au final, très peu de modif par rapport à l'algo par combinaisons.
Encore une fois, ça sera du C# : si vous avez des questions n'hésitez pas.
PS : j'ai comparé avec l'algo naïf pour valider les résultats. Tout semble ok (ce qui n'exclut cependant pas un bug...)
Données de base :
Les classes Mine et MineDatee n'ont pas changé :
Mine :
MineDatee :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8
9class Mine { public string Nom { get; set; } public double Cout { get; set; } public double Production { get; set; } public BitVector.Position Position { get; set; } }
La classe Chemin est complétée de la gestion des dominances :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6class MineDatee { public Mine Mine { get; set; } public double Date { get; set; } }
A suivre, l'algo lui-même
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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
101class Chemin { // Les mines non encore traitées pour ce chemin public List<Mine> MinesNonTraitees = new List<Mine>(); // Les mines déjà traitées et donc datées public List<MineDatee> MinesDatees = new List<MineDatee>(); // La production courante (incluant les mines traitées) public double Production; // La date courante public double DateFin; // Donnée technique pour identifier les chemins ayant exactement les mêmes mines public BitVector Positions; // Les dominantes : tous les chemins partagent cette donnée globale // qui est précalculée et invariante au cours du déroulement de l'algo public Dictionary<Mine, List<Mine>> Dominantes = new Dictionary<Mine,List<Mine>>(); // Les dominées avec le nombre de dominantes qui les 'bloquent' encore public Dictionary<Mine, int> Dominees; static int _nombreTotal = 0; public Chemin() { _nombreTotal++; } // Créer un nouveau chemin par copie public Chemin CreateCopy() { Chemin copy = new Chemin(); copy.MinesNonTraitees.AddRange( MinesNonTraitees ); copy.MinesDatees.AddRange( MinesDatees ); copy.Production = Production; copy.DateFin = DateFin; if ( Positions != null ) copy.Positions = new BitVector( Positions ); copy.Dominantes = Dominantes; if ( Dominees != null ) copy.Dominees = new Dictionary<Mine, int>( Dominees ); return copy; } // Ajout d'une mine public MineDatee AjouterMine( Mine mine ) { // On la retire des mines non traitées MinesNonTraitees.Remove( mine ); // Calcul de la date et de la production avec cette nouvelle mine DateFin += mine.Cout / Production; Production += mine.Production; // Mise à jour de la donnée technique (cf ci-avant) if ( Positions != null ) Positions[mine.Position] = true; // Si on a des dominées if ( Dominees != null ) { // Cette nouvelle mine est-elle dominante ? List<Mine> dominees; if ( Dominantes.TryGetValue( mine, out dominees ) ) { // Si oui, pour chaque dominée foreach ( Mine dominee in dominees ) { // Récupération du nombre de mines non placées qui la domine encore int n; if ( Dominees.TryGetValue( dominee, out n ) ) { // Diminution de 1 du fait de cette nouvelle mine qu'on place actuellement n--; if ( n == 0 ) { // Si c'était la dernière dominante, la mine n'est plus dominée Dominees.Remove( dominee ); // elle est donc traitable à son tour MinesNonTraitees.Add( dominee ); } else // Si ça n'était pas la dernière dominante, il reste une dominante de moins Dominees[dominee] = n; } } } } // Création de la mine datée MineDatee mineDatee = new MineDatee() { Mine = mine, Date = DateFin }; // et ajout MinesDatees.Add( mineDatee ); return mineDatee; } }
pour comparer il faudrait mettre en commun le fichier de data, par exemple :
n TAB p0
c1 TAB p1
…
cn TAB pn
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager