Version imprimable
Ah c'est très bien ce que tu as fait ! J'essayerai de faire la même chose en Caml.
Euh ça veut dire que t'avais pas réalisé cela ?Citation:
Sinon tes 2 derniers posts : oui ! J'optimise les algo avec cela
Je suis entrain de travailler sur la propriété que t'as énoncé, je te tiens au courant.
Edit : Tu veux bien confirmer ce que tu appelles "mine dominante" stp ?
J'étais focalisé sur d'autres aspects du truc... :aie:Citation:
Envoyé par Baruch
Pour info,Citation:
Envoyé par Baruch
Si une preuve est possible, il me semble que cette autre propriété suivante est nécessaire :
Si un chemin C est optimal et commence par une mine M
alors
Tout chemin optimal constitué d'une partie des mines de C et incluant M commence par M
... propriété qui pourrait aussi s'avérer intéressante.
Dans l'algo, les mines dominantes sont celles qui ne sont dominées par aucune autre (tout ça par rapport à l'ensemble des mines restant à placer).Citation:
Envoyé par Baruch
C'est à dire qu'aucune autre mine a un cout inférieur et une production supérieure à celles-ci.
Ehhhh pas bête :o Si t'as le temps tu peux faire des tests steuuuplait Aliii ? :DCitation:
Pour info,
Si une preuve est possible, il me semble que cette autre propriété suivante est nécessaire :
Si un chemin C est optimal et commence par une mine M
alors
Tout chemin optimal constitué d'une partie des mines de C et incluant M commence par M
... propriété qui pourrait aussi s'avérer intéressante.
Pour commencer, il faudrait savoir démontrer cela :
si [A;B;C] est idéale à p0, alors [A;C] est idéale à p0.
En effet, si ta propriété est vraie, alors [A;B] et [A;C] sont idéales, or [A;B] l'est par optimalité 2 à 2.
Quelques infos, quand même, en utilisant la mine de meilleur rendement :
- Sur 5 millions de tirages de 5 mines : pas d'écart avec NDO
- Cette méthode ajoutée à NDO : 15 secondes pour 100 mines
- Cette méthode ajoutée à Dijkstra like : 10 secondes pour 200 mines
Ca fait combien de différence avec les algos sans cette propriété ?
Ah sinon ta dernière propriété est fausse :
L = [{cout = 3.23426778663; prod = 1.50652198719};
{cout = 3.20406553966; prod = 1.41021193206};
{cout = 0.799279349974; prod = 0.180098440855}] = [A;B;C]
L est optimale à p0 = 1.
Mais [C;A] (3.54) est meilleur que [A;C] (3.55) à p0 = 1.
Beaucoup :mrgreen:Citation:
Envoyé par Baruch
Alors il faut peut être ajouter la condition sur P*max... dans ce contre exemple p0 < p*max...Citation:
Envoyé par Baruch
... ça peut être logique : dépasser p*max apporte une certaine stabilité (bon... je ne suis pas sûr de la règle quand même...)
Tu pourrais essayer de tester l'exactitude de l'algorithme sans utiliser l'optimalité 2 à 2 stp ? (mais en gardant la dominance)
Oui... ! c'est sans doute ça le truc : on a dépassé p*max et c'est une condition suffisante.
Donc :
Soit C un chemin en cours d'évaluation.
C correspond à ce moment à un ensemble D de mines dominantes immédiatement plaçables à la suite de C.
La production courante est supérieure à p*max des mines de D.
La meilleure mine de D pour compléter C est la première mine P du chemin optimal pour les mines de D seules et partant de la production de C (ou encore celle qui a le meilleur rendement).
Preuve :
Pour que P ne soit pas la mine à choisir, il est nécessaire qu'une autre de ces mines dominantes Di libère une mine dominée Ai qui remettrait en cause la position de P.
Alors, les chemins alternatifs possibles seraient (ces chemins sont optimaux par hypothèse) :
1/ [suite de mines incluant P et Di]Ai[suite pour les autres mines]
Donc [suite de mines incluant P et Di] est optimal
Donc P est première de par p*max valable sur ces mines
2/ [suite de mines incluant Di]Ai[suite de mines incluant P]
Or
[suite de mines incluant P] commence par P (du fait de p*max)
Donc
[suite de mines incluant Di]Ai[P] serait optimal.
Or Di domine Ai donc on peut noter :
- cAi = cDi + deltac
- pAi = pDi - deltap
Donc :
p*(AiP) = (cP - cDi - deltac) / ( (cDi + deltaC) / (pDi - deltap) - cP/pP )
donc p*(AiP) < p*(DiP)
donc les mines peuvent être triées par rendement (le p courant dépasse p*(AiP))
donc c'est contradictoire
donc P ne suit pas Ai et on se retrouve dans le cas 1/
...
Qu'en penses tu ?
Les "trous" possibles dans cette preuve :
- S'il y a plusieurs Ai est-ce que ça change quelque chose ?
- Faut-il comparer le p* de Ai avec une autre mine que P ?
OuiCitation:
Envoyé par Baruch
j'ai utilisé NDO vs. NDO avec p*max (mais donc sans l'optimalité 2 à 2 ) : sur un million de tirages pas d'écarts.
Bon, si la preuve juste avant est correcte, c'est normal.
Voici quelques chiffresCitation:
Envoyé par Baruch
Pour 100 mines (toujours le jde d'elentarion) :
NDO :
- Sans p*max : 156 secondes, 12 716 474 chemins intermédiaires calculés
- Avec : 14 secondes, 1 026 738 chemins intermédiaires calculés (si ma dernière démo est correcte, cet algo est exact)
Dijkstra like :
- Sans p*max : 2,7 secondes, 102 429 chemins intermédiaires calculés (l'algo n'est pas prouvé comme étant exact, mais pas de contre exemple mis en évidence)
- Avec : 0,7 secondes, 27 443 chemins intermédiaires calculés
... pour illustrer, l'algo naïf nécessiterait 100! > 9 * 10^157 chemins intermédiaires.
Donc on a quand même beaucoup progressé (ce qui m'amène à reposer la question : jusqu'où un algo, réputé instinctivement np complet au départ, est-il améliorable ?).
Enfin ! J'ai réussi ^^. Bon ta démo comportait des trous, mais tu as vu le point essentiel (bravo). Je fais la démo complète :
Il reste un ensemble E de mines à placer, pour une production p0.
On note D = {D1,...,Dq} l'ensemble des mines dominantes, c'est-à-dire que si Di appartient à D, alors il n'existe pas de mine M dans E telle que M domine Di.
On note A = {A1,...,Ar} = E \ D.
On note P la mine de D qui a le rendement le plus grand (et en cas d'égalité le coût le plus faible).
On a comme condition que p0 >= P*max.
On veut montrer que le chemin idéal de E commence nécessairement par P.
Auparavant, on a la propriété suivante :
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]) (*)
En effet, si on a une liste de E où P n'est pas en 1ere position, il existe de meilleures listes en faisant remonter P progressivement vers la 1ere position.
On va donc montrer ici la propriété (*) :
Si M = Di :
p >= p0 >= P*max >= p*(P,Di) donc "le plus rentable est avant", donc on a Tp([P,Di]) <= Tp([Di,P])
Si M = Aj :
Il existe Di dans D tel que Di domine Aj.
Montrons que p*(P,Aj) <= p*(P,Di) :
p*(P,Aj) = (cp - cj) / (cj/pj - cp/pp)
cj/pj - cp/pp >= 0 car P est plus rentable que Di, qui est plus rentable que Aj, car Di domine Aj.
Di domine Aj donc ci <= cj donc p*(P,Aj) <= (cp - ci) / (cj/pj - cp/pp)
Di domine Aj donc Di est plus rentable que Aj donc cj/pj - cp/pp >= ci/pi - cp/pp >= 0
donc p*(P,Aj) <= (cp - ci) / (ci/pi - cp/pp) = p*(P,Di)
p*(P,Aj) <= p*(P,Di) <= P*max <= p0 <= p donc "le plus rentable est avant", donc on a Tp([P,Aj]) <= Tp([Aj,P]), car P plus rentable que Aj.
Voilà, tous les cas sont démontrés.
T'as vraiment eu la bonne idée pour la comparaison des p* dans une situation de dominance.
Par contre, la démo n'est pas finie (eh oui ^^) :
Ici je n'ai pas considéré la contrainte d'idéalité 2 à 2 avec la mine précédente. Ce que ça change :
Soit D l'ensemble des mines dominantes, et D' l'ensemble des mines dominantes qui respectent l'idéalité 2 à 2 avec la mine précédente.
- La mine la plus rentable de D n'est pas forcément la mine la plus rentable de D'.
Bravo Baruch ! :ccool:
Concernant :
Donc il faut simplement modifier l'algo pour :Citation:
Envoyé par Baruch
- Tester p*max sur D
- Identifier la meilleure mine de D
- Identifier la meilleure mine de D'
- Et vérifier que ces deux meilleures sont les mêmes
Sinon,
- On déroule l'algo 'normalement' sans cette optimisation
tu es d'accord ? (l'alternative étant de prouver que ça ne change rien pour x raisons).
Ca va dégrader un peu les perf, mais bon...
Ben tu avais codé l'algorithme sur D' non ? Et il n'y avait pas de contre exemple ?
Il doit y avoir une raison à ça... Je me pencherai sur le problème plus tard.
Mais oui l'algo que tu proposes est démontré exact.
Edit :
Si t'as le temps, tu peux tester si la mine la plus rentable de D est la mine la plus rentable de D' stp ?
J'y crois pas trop mais on peut rêver ^^.
Il faut quand même se méfier du fait de ne pas trouver de contre exemple (il y a eu un cas, je ne sais plus lequel, où un contre exemple existait sans que je le trouve par tirage aléatoire : donc il faut peut être bien plus que quelques millions de cas ou plus de mines ou revoir la répartition statistique).Citation:
Envoyé par Baruch
Donc pour le moment, j'ai modifié l'algo (en attendant qu'on ait une preuve). Par contre : conséquence immédiate les perfs sont moins bonnes (ça élague beaucoup moins l'arbre de recherche : ça c'est confirmé !).
Je te confirme qu'il y a de nombreux cas où la plus rentable de D n'est pas dans D' (d'où la perte de l'élagage de l'arbre dont je parlais juste avant).Citation:
Envoyé par Baruch
Edit : je précise quand même
cas 1/ On ne s'intéresse qu'aux mines qui sont optimales deux à deux avec la fin du chemin.
P*max est calculé sur D'
cas 2/ On vérifie si D et D' ont la même meilleure mine
P*max est calculé sur D
Bonsoir à tous les deux,
J'ai pas eu le temps de tout lire aujourd'hui, légèrement débordé, mais je me suis arrêté sur la preuve de la dominance de Baruch, il y a quelque chose que je ne comprends pas.
Lorsque tu élimines les ci, tu dis (dans le cas où ci non-nul) :
Soit i dans [1,n], on divise par ci et on fait tendre vers +inf, ça donne l'inégalité "machin".
Si j'ai bien saisi, tu fais ça pour chacun des ci, ce qui reviens à dire que tu divises par le produit c1.c2....cn, et tu fais tendre chacun de ces termes vers l'infini.
En faisant ça, tu te retrouves avec une somme d'éléments nuls et tu ne devrais rien pouvoir conclure. Est-ce qu'il y aurait quelque chose que je n'aurais pas compris ?
Pour le reste, je lirais ce soir chez moi =)
Flatté que tu lises ma démo ^^
Non, j'ai dit "soit i dans [1,n]", c'est-à-dire que je prends un seul i quelconque.
Je divise tout par Ci, ne reste donc après la limite que le coefficient de Ci.
De là, on obtient Pa >= Pb.
Si j'avais pris un autre i dans [1,n], le raisonnement et le résultat auraient été les mêmes (le résultat ne dépend pas de i).
Effectivement, si j'avais divisé par le produit de tous les Ci, j'aurais eu 0 <= 0, ce qui n'est pas forcément utile ^^.
Une mise à jour du doc de récap sur les algos (il reste encore à faire la partie concernant p*max et les algos non exacts).
Dans l'idéal, il faudra également qq courbes montrant la progression de la complexité de chacun (reste à faire également).
Merci de vos remarques.
Bonne soirée
Wow c'est vraiment un bon document, merci Ali ^^.
Je te fais confiance sur les codes en eux-mêmes, par contre tu expliques vraiment bien comment les algorithmes fonctionnent. Sur la notion de dominance, tu peux indiquer que c'est bien une propriété démontrée. Pour ce qui est de l'optimalité 2 à 2, on ne peut pas comprendre le concept si on ignore ce que c'est ^^, mais c'est pas grave je l'ai décrite rigoureusement dans le rapport d'avancement. Et pour le p*, il n'y pas de démo, mais c'est pas grave non plus, je vais le mettre dans mon rapport.
Enfin sinon c'est un très bon document de référence pour les codeurs, bravo :)