Version imprimable
Je reviens sur ce sujet :
On a donc cC - cA borné par :Citation:
Envoyé par Alikendarfen
- borne inf : cB / (1 + qA)
- borne sup : cB
Mais c'est normal !! Car cA + cB + cC = constante (dans ce cadre pour 3 mines) !!
donc rien d'étrange... mais toujours pas de démo ! :)
Edit : à la relecture, cette remarque est sans doute un peu conne... mais bon, ce qui est écrit est écrit !!
Oui... à ceci près qu'un chemin issu de C1 n'est pas nécessairement idéal (c'est pourquoi je parlais de meilleur chemin)... mais peu importe.Citation:
Envoyé par Baruch
Pour être plus précis, trouver une solution optimale sur E et p0 ne nécessite que la (2).Citation:
Envoyé par Baruch
Mais l'algo exploite bien la (1) : lorsqu'un chemin en élimine d'autres, on ne cherche pas à savoir s'il y a par ailleurs un chemin meilleur (au sens "aboutissant au final à la solution optimale"). Donc tout se passe comme si C1 et C2 étaient seuls.
Bon j'ai lu en vitesse ce qui s'est dit, c'est pas aujourd'hui ni ce week-end que je vais pouvoir travailler dessus.
Pour ce que je voulais démontrer, Baruch l'a très bien expliqué :
C'est aussi une intuition, au même titre que celle d'Alikendarfen sur ses deux chemins en temps et prod équivalente qui font qu'il choisit le plus cher.Citation:
Soient u et v 2 chemins, de même temps (à p0), et de même production.
u et v ont des mines qui appartiennent à un ensemble E.
Montrer qu'il existe un chemin w, à éléments dans E, tel que son temps (à p0) soit inférieur à celui de u et v, et tel que sa production soit supérieure à celle de u et v.
Ce que j'ai énoncé, si c'est vrai (et j'ai des doutes, j'y reviens juste après), permettrai, en cas d'égalité entre deux chemins (même temps, même production), permettrait non pas de choisir l'un des deux chemins, mais de trouver un troisième chemin, mieux que les deux autres, et donc d'améliorer les résultats. Après, ce que je ne sais pas, c'est la qualité de votre algo, je sais qu'il n'est pas exact, mais niveau précision, ça donne quoi ?
Vous obtenez quand même les mêmes résultats qu'un algo exact, ou vous avez des résultats acceptables (à X% près) ? Si c'est le premier cas, ma preuve ne sert à rien. Si c'est le second, ma preuve est utile.
Ensuite concernant la preuve elle même, j'avais commencé par les hypothèses que tu avais annoncé Alikendarfen, (1) et/ou(2), sinon pour tout (i,j), (3) OU (4), mais j'en étais arrivé à la conclusion que ce n'était pas possible et que c'était nécessairement (1) et/ou (2), sinon (3), sinon (4).
Mais j'ai pas noté pourquoi quand je griffonnais dans tous les sens, et maintenant je ne trouve plus la raison.
Si vous me dites que votre algo non-exact est en fait "exact", je laisse tomber ma preuve. Si vous me dites que le résultat peut être amélioré, je vais la retravailler.
Enfin une question, qu'est-ce que vous essayez de faire exactement ? Il me semble que vous avez déjà trouvé un algorithme très performant, donc je ne saisis plus trop pourquoi vous continuez à travailler sur ce sujet. Pour la beauté du geste ? Vous cherchez LE meilleur algo ? Vu que c'est NP-hard ça me paraît mal engagé =)
Si vous essayez d'améliorer le résultat, pour un temps de calcul sensiblement équivalent, tester d'autres algo me semble en effet une bonne idée.
Mais si vous essayez d'améliorer le temps de calcul, il me semble que vous avez déjà balayé la majorité des contraintes qui peuvent permettre d'obtenir un résultat rapidement, et que la seule piste possible serait de faire des approximations :
- Par exemple, considérer que si deux mines ont une production et un coût égal à X% près, alors l'algo les traite comme si elles était égales.
Il faudrait voir la propagation de l'erreur que ça entraînerait (et ça me semble pas évident du tout) pour voir quelle erreur vous auriez sur le temps de construction total (à mon avis ça va pas du tout être le même X%), mais ça peut être une autre piste à explorer.
Vu qu'il n'y a pas d'application concrète derrière, on n'a pas de marge d'erreur acceptable qu'on peut se fixer, mais à mon avis on gagnerait beaucoup de temps en s'autorisant une marge de 3-4% par rapport à l'optimum.
Voila c'était mon pavé, à lundi !
L'algo donne des résultats strictement équivalent à un algo exact qui sert de comparaison (ou en tout cas, nous n'avons pas de contre exemple).Citation:
Envoyé par Myrne
Je ne sais pas !! Le sujet vient de Baruch et je ne sais dans quel cadre il a voulu l'aborder...Citation:
Envoyé par Myrne
Sinon, depuis les quelques semaines (mois ?) ou l'on a commencé, nous avons pas mal progressé (les premiers algo exacts plafonnaient à moins de 20 mines, voire une douzaine pour les tous premiers, pour un temps raisonnable, aujourd'hui c'est plus de 100 mines)... et l'un des sujets sous-jacents est effectivement de savoir jusqu'où un meilleur algo pourra être trouvé.
Concernant, les algo non exacts, nous en avons également. Ils sont plus ou moins performants mais également plus ou moins précis... normal. Par exemple : algo génétique, permutation, insertion.
Mais je crois que Baruch prépare un récap de tout cela.
Une approche pourrait être effectivement de déterminer des cadres (classes) d'application d'identifier des propriétés particulières pour les mines dans ces classes et de trouver des optimisations...Citation:
Envoyé par Myrne
A lundi Myrne !
Je reviens sur cette histoire de P*Max.
Voici quelques calculs :
- Sur la base des 100 premières mines du jeu d'essai d'elentarion (p = 5)
- On calcule les p* de tous les couples MiMj (par convention c(Mi) < c(Mj), sinon on inverse le couple)
On obtient :
- 4950 couples de mines (100 mines)
- 2444 d'entre eux sont en situation de dominance absolue (normal : environ la moitié statistiquement)
- et donc 2506 ne le sont pas
Parmi ces 2506 :
- 1589 ont un p* inférieur à p0
- 4 ont un p* supérieur à pTot = p0 + somme des pi
- 913 sont entre les deux
- Mais ces 913 impliquent 97 mines
Bien que j'y ai réfléchi de nouveau, je ne vois toujours pas comment exploiter cette approche...
@Baruch : j'ai raté un truc ?
L'idée est de recalculer P*max à chaque itération, et de le comparer au p0 actuel.
Du coup quand on avance en profondeur, P*max décroît, p0 croît, et donc il arrive un moment où p0 devient plus grand que P*max (je parle du p0 relatif aux mines déjà placées).
Si on est dans le cas où p0 est plus grand que P*max, il suffit de trier les mines par rendement décroissant.
Avant le lancement des itérations, on calcule comme tu l'as dit une matrice avec tous les p* de tous les couples de mines.
Savoir si p0 > P*max revient à n² tests, donc c'est long, mais on peut utiliser quelques astuces je pense :
- Retenir quel couple de mine donne le p* maximal. Ainsi on ne recalcule le P*max que lorsqu'une des 2 mines du couples a été placée.
- Ne calculer les P*max qu'à partir d'une certaine profondeur.
Edit :
p*(A,B) = p*(B,A)Citation:
(par convention c(Mi) < c(Mj), sinon on inverse le couple)
Pourquoi tu veux inverser le couple ?
Faut faire attention aux couples de mines qui ont un même rendement (ça fait + ou - l'infini).
OK pour tout !Citation:
Envoyé par Baruch
Mais as-tu vu les chiffres que je donnais précédemment ?
4 cas ont un p* > à tout p0 possible dans le contexte étudié. Donc p0 ne peut pas dépasser P*max...
et si j'ai bien compris, on ne peut alors rien en tirer pour aucune autre mine, non ?
Eh si !
Pour les couples de mines qui ont un p* supérieur à toute production possible :
Il y aura un moment où ces couples de mines ne seront plus étudiés, puisqu'on place des mines au fur et à mesure (c'est le P*max décroissant).
OK ! Bien vu ;) !
Mais du coup tu penses que c'est viable ? Le calcul de P*max n'est-il pas trop lourd ? T'as une idée de comment optimiser son calcul ?
Pas encore : il faut trouver une organisation des données qui soit adaptée pour gérer ça... en tenant compte si possible du reste (par exemple les dominances).
Je n'ai pas d'idée de l'efficacité globale de cette méthode. Ce qui se passe, c'est que c'est un peu comme gravir puis redescendre une colline : la pointe de la combinatoire se trouve au sommet... et c'est seulement si cette approche réduit sa hauteur qu'elle donnera des résultats.
Si la taille de la colline chute significativement, ça va nécessairement compenser les calculs additionnels.
Il faut tester...
Es-tu d'accord avec ça :
On part de NDO.
Considérant un chemin C en cours de construction, NDO nous donne toutes les mines possibles P immédiatement après C (de par les dominances absolues) et permet de sélectionner parmi ces mines celles P' qui permettent une optimalité 2 à 2.
Si on calcule P*Max sur les mines P' :
- C'est beaucoup plus court que pour toutes les mines restantes
- Mais ça ne permet QUE de trouver LA prochaine mine (celle qui du fait de P*Max serait la première). En effet, choisir l'une de ces mines pourrait libérer une mine dominée et donc ajouterait une autre mine, etc.
- (tout ça à condition que P*Max de ces mines soit dépassé par p, bien sûr)
D'accord ?
Ou pas d'accord ?
A première vue pas d'accord, ça ne donnerait pas un algorithme exact à mon avis.
Ca serait bien que tu développes un peu...
Edit : je précise de mon côté
Ces mines étant dominantes :
- 1/ La prochaine est nécessairement l'une d'entre elles
- 2/ La première d'entre elles peut être calculée comme si aucune autre mine (l'une des dominées) n'existait
Bon... suite à ça, j'ai implémenté l'algo suivant en partant de NDO :
- Pour chaque chemin en cours d'évaluation
- Identifier les mines dominantes restant à placer
- Identifier parmi celles-ci les mines qui permettent l'optimalité 2 à 2 avec le chemin en cours
- Tester production courante >= P*Max sur ces mines
- Si le test est négatif : poursuivre avec NDO "normal"
- Si le test est positif : calculer le meilleur chemin pour ces mines dominantes partant de la production courante ; garder la première mine de ce chemin et l'ajouter au chemin en cours
Résultat :
- Sur trois millions de tests, pas d'écarts avec le NDO d'origine (celui dont on est sûr qu'il est un algo exact)
- Sur les 100 mines (toujours les mêmes) réduction par env. 4 du temps de calcul (soit 40 secondes vs. 191)
Je n'ai rien optimisé pour le moment : notamment, pour calculer le meilleur chemin des mines dominantes, j'appelle NDO, donc ça recalcule des dominances alors qu'on sait qu'il n'y en a pas...
Ca reste beaucoup plus lent que le Dijkstra like (3 secondes pour les 100 mines)... mais on pourrait aussi utiliser cette méthode avec (on verra plus tard : je ne vais pas miser sur deux méthodes dont on n'a pas la preuve avérée).
Concernant la preuve pour la méthode utilisée avec P*Max, justement :
- Si p >= P*Max, on sait qu'on a un ordre strict pour les mines concernées
- Mais cet ordre ne vaut que si ces mines sont immédiatement consécutives
- Ces mines dominent toutes les autres mines non prises en compte
- Est-il possible que l'inclusion des mines non prises en compte remette en cause la position de la meilleure dominante (à l'issu de son calcul indiqué ci-avant) ?
Plutôt positif tout ça !! Mais restent encore des preuves à apporter !
Suite... j'ai quand même intégré le P*max (tel qu'indiqué précédemment pour NDO) dans le Dijkstra like (pas très long à faire, au fond).
Les résultats sont toujours corrects (pas trouvé de contre exemple), mais par contre, autant cette approche améliore les perf de NDO, autant elle les dégrade pour le Dijkstra like...
... et je n'ai pas encore compris pourquoi !
Edit : en fait si, c'est parce que l'appel imbriqué pour trouver la mine suivante nécessite de résoudre le problème jusqu'au bout alors que ces problèmes seraient sinon éliminés bien avant leur résolution complète par le dijkstra like.
Petit complément d'info sur le Dijkstra like : c'est le plus rapide pour 100 mines (3s), par contre suite à ça les temps grimpent vite... faudra un jour faire quelques courbes pour comprendre les comportements de tous ces algos...
Bien j'ai commencé à écrire un petit topo sur ce sujet (en pièce jointe), toute participation étant la bienvenue. J'ajoute également la démonstration de la dominance des mines, que j'ai un peu remaniée pour être rigoureux.
Dsl d'avoir été aussi concis Alikendarfen ^^. Je réflèchis et je te donne peut-être une démonstration ^^.
Ah sinon, pour ce qui est de cette propriété :
Soit E un ensemble de mines.
Si p0 > P*max, alors le chemin idéal est le tri par rendement décroissant.
Cette propriété est exacte, et je le prouve :
Prenons un couple de mines de E. Son p* est inférieur à p0, donc comme je l'avais prouvé auparavant, si les 2 mines du couples sont adjacentes, alors il est mieux de placer la plus rentable en premier.
Comme p0 est supérieur aux p* de tous les couples de mines de E, si 2 mines sont adjacentes, alors la plus rentable est avant.
Soit L = [M1,M2,...,Mn]
si L est le chemin optimal de E à p0, alors :
M1 est plus rentable que M2
M2 est plus rentable que M3
...
M(n-1) est plus rentable que Mn
ie L est triée par rendement décroissant.
Pour ce qui est de la propriété que tu proposes, est-ce bien ça :
- Identifier les mines dominantes :
Ca veut dire les mines qui ne sont dominées par aucune autre ?
- Prendre parmi celles-ci les mines qui respectent l'optimalité 2 à 2 :
Ok, tout ça on le faisait déjà dans le NDO.
- Regarder si p > P*max, où p est la production courante, et P*max est calculé sur cet ensemble de mines
- Si le test est positif :
Trier cet ensemble de mines, prendre la première, et l'ajouter au chemin courant.
Eh ben ! Il suffit donc de prendre la mine ayant le meilleur rendement ! (cf l'autre propriété de mon post au-dessus)
Edit : Quand tu dis "respecte l'optimalité 2 à 2", c'est bien par rapport à la dernière mine qui a été placée ?
J'ai également commencé un récap. Même si je suis un peu obligé de rappeler des choses similaires à tes documents, l'objet est de traiter essentiellement le détail des algos eux-mêmes.
En pj (en .doc car en pdf il est trop gros... : (
Pareil : ça n'est pas terminé mais n'hésite pas à faire tes remarques !
Sinon tes 2 derniers posts : oui ! J'optimise les algo avec cela :ccool:
Oui. Par rapport à la dernière mine du chemin avant les dominantes dont on parle.Citation:
Envoyé par Baruch