Merci merci Baruch :ccool:
Pour les démo, je ne les mets volontairement pas, considérant que c'est "plus ton terrain". Donc, autant que possible, je me limite à la partie algo...
... si tu veux on fera un merge des docs à la fin.
Version imprimable
Merci merci Baruch :ccool:
Pour les démo, je ne les mets volontairement pas, considérant que c'est "plus ton terrain". Donc, autant que possible, je me limite à la partie algo...
... si tu veux on fera un merge des docs à la fin.
Désolé d'insister Baruch, mais je ne saisis pas la démarche. Si tu ne fais la division et la limite vers +inf que sur un seul ci, alors ta propriété Pa>=Pb n'est-elle pas valable que pour ci -> +inf, et pas pour tout ci ?
Oui, la propriété Pa >= Pb qui découle de la limite que j'effectue, n'est bien entendu pas équivalente à mon inégalité de départ (1). Je n'obtiens par cette limite qu'une condition nécessaire.
De plus, j'avais montré juste avant cette limite, une autre condition nécessaire (2), en prenant tous les Ci nuls.
Et après je remarque que ces 2 conditions nécessaires prises ensembles, sont équivalentes à mon inégalité de départ (1). J'obtiens donc enfin une équivalence entre l'inégalité (1), et le système des 2 conditions Pa >= Pb et (2).
Je reviens sur D et D' des dernières démo et sur l'algo correspondant.
On a dit si la première de D n'est pas la même que la première de D', alors on applique l'algo 'normal' sans l'optimisation p*max.
Or
1/ quand on considère p >= p*max(D), l'ordre de D entier est déterminé et par voie de conséquence celui de D' aussi.
Si la première de D n'est pas la même que celle de D', alors simplement ce chemin ne peut pas être optimal !
2/ Si on considère p < p*max(D) et p >= p*max(D'), on ne peut s'appuyer que sur l'ordre de D'.
Mais alors, soit la première mine de D' est la bonne, soit elle sera (serait) remise en cause lorsque p dépasse p*max(D'). Donc on peut toujours parier sur cette mine (éventuellement, plus tard, l'hypothèse sera éliminée).
Donc finalement, on peut s'appuyer sur p >= p*max(D') et la première mine de D'. Soit ce chemin s'avère fructueux... soit il sera éliminé par la suite.
Si le 1/ est juste, on a donc une règle pour se rendre compte qu'une hypothèse n'a pas d'avenir !!
Correct ? Ou pas ?
En fonction... algo, etc. !! ;)
Hmm je pense qu'il serait plus judicieux de faire d'abord des tests complémentaires pour savoir si la propriété sur D' est exact, et donner une piste pour la démonstration. C'est d'ailleurs ce que je suis entrain de faire (par exemple regarder les p*).
J'ai la foi donc je pense que la propriété est exacte ^^. Tu te ranges du côté des pessimistes en cherchant un algorithme pour contourner le problème ^^.
Je vais donc d'abord tenter la démonstration, et si vraiment j'y arrive pas je regarde ton astuce ok ? ^^
Nan, nan, nan ! On ne s'est pas compris.Citation:
Envoyé par Baruch
Je pense que mon post précédent est une démo ! Relis-le stp et donne des contre arguments.
Ou alors ça n'est pas clair ?! Bref, j'attends vos retours...
Edit : je vais quand même expliquer un petit peu plus (parce que je ne suis pas pessimiste : j'espère te faire comprendre, et parce que ça n'est pas une astuce :mouarf:)
1/ p >= p*max(D)
donc l'ordre est imposé sur tout D
donc si la première de D n'est pas optimale 2 à 2 avec la dernière du chemin : pas possible de placer la première de D, mais aussi pas possible de changer l'ordre de D
donc si la première de D n'est pas optimale 2 à 2 avec la dernière du chemin : ça ne peut pas être la bonne solution
2/ p < p*max(D) et p >= p*max(D')
les positions relatives des mines de D' ne changeront pas lorsque p sera >= p*max(D)
donc soit la bonne prochaine mine est la première de D', soit plus tard l'optimalité 2 à 2 ne sera pas respectée (car passé p*max, l'optimalité 2 à 2 et l'optimalité globale d'un chemin se confondent)
J'espère que c'est plus clair (mais évidemment, il peut y avoir des erreurs...).
En tout cas, sans rancune (pour les histoires de pessimisme et d'astuce... :mouarf:)
Ah oui excuse moi !
Avant de commencer toute démonstration, il faut remarquer cela :
Soit K la mine qui était placée juste avant. Soit E l'ensemble des mines restantes à placer. Soit C le chemin idéal de E à p0 (production courante après K). Soit P la première mine de C.
On doit supposer pour cette démonstration que [K,P] est idéale à (p0 - pK). (*)
1) p0 > P*max (D)
Comme montré auparavant, P est donc la mine la plus rentable de D.
D'après (*), [K,P] est idéale, donc P appartient à D'.
Donc P est bien la mine la plus rentable de D'.
2) P*max (D') < p0 < P*max (D)
D'après (*), P appartient à D'.
La question est donc : pourquoi est-ce la plus rentable de D' ?
Désolé je n'arrive pas bien à comprendre ce que tu veux dire :/Citation:
2/ Si on considère p < p*max(D) et p >= p*max(D'), on ne peut s'appuyer que sur l'ordre de D'.
Mais alors, soit la première mine de D' est la bonne, soit elle sera (serait) remise en cause lorsque p dépasse p*max(D'). Donc on peut toujours parier sur cette mine (éventuellement, plus tard, l'hypothèse sera éliminée).
Donc finalement, on peut s'appuyer sur p >= p*max(D') et la première mine de D'. Soit ce chemin s'avère fructueux... soit il sera éliminé par la suite.
Si le 1/ est juste, on a donc une règle pour se rendre compte qu'une hypothèse n'a pas d'avenir !!
Edit :
Oui, mais si les mines de D' sont collées. Sinon, on n'en sait rien.Citation:
2/ p < p*max(D) et p >= p*max(D')
les positions relatives des mines de D' ne changeront pas lorsque p sera >= p*max(D)
Pas compris ton explication.Citation:
donc soit la bonne prochaine mine est la première de D', soit plus tard l'optimalité 2 à 2 ne sera pas respectée (car passé p*max, l'optimalité 2 à 2 et l'optimalité globale d'un chemin se confondent)
Non pas seulement ! L'ordre des mines de D' est entièrement défini ! Les p* définissent un ordre pour les mines 2 à 2, qu'elles soient ou non collées au final !Citation:
Envoyé par Baruch
Edit :
les p* des mines de D' ne changeront pas, donc l'ordre relatif de ces mines non plus
comme on calcule p* pour tous les couples de mines, on calcule nécessairement des ordres (classements) directs (deux mines consécutives) et indirects (les mines sont disjointes).
Si on dépasse p*max, l'ordre est total (il n'existe plus d'ordre partiel), donc un seul ordre possible, donc opt2à2 = chemin optimalCitation:
Envoyé par Baruch
Peut-être, mais encore faut-il le montrer.Citation:
Non pas seulement ! L'ordre des mines de D' est entièrement défini ! Les p* définissent un ordre pour les mines 2 à 2, qu'elles soient ou non collées au final !
Supposons qu'on ait D'={A,B} , A + rentable que B, et C une mine hors de D'. On a p0 > p*(A,B).
Les chemins possibles sont :
ABC
ACB
BCA
Pourquoi BCA peut-il être éliminé ?
Tu parles du P*max sur E ou sur D ?Citation:
Si on dépasse p*max, l'ordre est total (il n'existe plus d'ordre partiel), donc un seul ordre possible, donc opt2à2 = chemin optimal
Il n'est pas certain que P*max soit dépassé par la suite.
Pour les mines de D', le p*max est dépassé, donc l'ordre des mines de D' (l'ordre de ces seules mines entre elles, indépendamment de mines intercalées) ne change pas !
Pourquoi ? ^^Citation:
Pour les mines de D', le p*max est dépassé, donc l'ordre des mines de D' (l'ordre de ces seules mines entre elles, indépendamment de mines intercalées) ne change pas !
Parce que !Citation:
Envoyé par Baruch
p augmente, ok
et ce faisant, on peut déterminer que l'ordre d'autres mines change et devient fixe
MAIS
pour les seules mines de D', leur p* ne change pas (et leur p* est indépendant de tout, sauf de ces mines et l'ordre final n'est que dépendant du fait que p dépasse des p*)
donc leur ordre relatif est définitivement établi
Désolé d'insister, mais non ^^ :
- Oui, le p* est indépendant de tout
Ah ? Prouve-le...Citation:
l'ordre final n'est que dépendant du fait que p dépasse des p*
Il y a (n(n-1)/2) p* différents. Donc pour un ensemble E de mines, il y aurait au maximum (n(n-1)/2 +1) ordres différents pour des p0 différents.
Peut-être que c'est vrai hein, mais à première vue c'est pas évident.
Tu ne le prouves pas, et ça ne répond pas au cas BCA évoqué au-dessus.Citation:
donc leur ordre relatif est définitivement établi
tu as raison... mais cependant, on peut améliorer l'algo.Citation:
Envoyé par Baruch
Au lieu de :
- Si p >= p*max(D), alors si la meilleure de D = la meilleure de D', on utilise p*max, sinon algo 'normal'
On a :
- Si p >= p*max(D), alors si la meilleure de D = la meilleure de D', on utilise p*max, sinon pas de solution
OK, avec ça ?
Je mets à jour le rapport d'avancement en pièce jointe. Il a l'avantage de résumer pas mal de choses sur ce topic. Il exclut l'algorithme par combinaisons, et les algorithmes approchés.
J'ai lancé le sujet sur le forum les-mathématiques.net, ici.
Edit : Correction d'une erreur dans le document
Attention, il y a une petite erreur dans le rapport pour la dominance de chemins (en début de page 3) :
c'est :
C(C1) >= C(C2)
P(C1) >= P(C2)
T(C1) <= T(C2)
et non pas :
C(C1) >= C(C2)
P(C1) <= P(C2)
T(C1) <= T(C2)
et on sait aussi que ces chemins doivent être optimaux 2 à 2.
Ah oui faut que je corrige.
Euh depuis quand l'optimalité 2 à 2 est nécessaire ?
Tu avais trouvé un contre exemple non optimal 2 à 2 :Citation:
Envoyé par Baruch
Citation:
Envoyé par Baruch
Non ! Je sais qu'on en a déjà parlé, mais bon :
La propriété qui importe, c'est :
Si c1 domine c2, alors le chemin idéal ne peut pas commencer par c2.
Et c'est tout ! (Mon contre exemple portait sur une autre propriété)
BCA peut-il être optimal ?Citation:
Envoyé par Baruch
Si BCA est optimal :
1er cas / On part d'un chemin vide
Donc D=D' (pas d'élimination du fait de l'optimalité 2 à 2 avec la mine précédente) donc un tel C n'existe pas
2nd cas/ Le chemin n'est pas vide et se termine par une mine M
Soit p' la production avant M
Par hypothèse :
(a) t(MB) < t(BM) à p', car sinon B n'est pas dans D'
(b) t(MC) > t(CM) à p', car sinon C serait dans D'
Partant de (a) et (b), on finit par déduire que t(BC) > t(CB) à p'
Mais t(BC) < t(CB) à p (car BCA optimal par hypothèse)
Donc p > p*(BC) > p'
Edit : pour p*(AC), le principe est le même (mais autant le préciser)
[
t(BC) < t(CB) à p (par hypothèse BCA optimal)
t(BA) > t(AB) à p (car AB optimal à p)
donc t(CA) > t(AC) à p
également
t(MA) < t(AM) à p' (car A est dans D')
t(MC) > t(CM) à p' (car C n'est pas dans D')
donc t(AC) > t(CA) à p'
donc p > p*(AC) > p'
]
Donc on peut trier ABC par rendement croissant
Donc A est avant B et c'est contradictoire
Donc BCA ne peut pas être optimal
Ca vous semble correct ?