Ordre de construction de mines

Citation:

---

Envoyé par Baruch

Mauvaise nouvelle !
...

---

Je reviens sur quelques remarques liées à ton message ci-dessus.

Tel que l'algo se déroule (algo sans dominance globale ou optimalité 2 à 2), les optimalités sont "naturellement" testées.

En effet,

Si [AB] et [BA] restent en compétition et que [AB] est le plus court, alors [BA] sera éliminé (temps plus court pour [AB] et par ailleurs, mêmes cout et production). Donc cela couvre l'optimalité 2 à 2.

Mais c'est vrai aussi pour n mines : si deux suites S1 et S2 des mêmes mines sont en compétition et que S1 est la plus courte, alors S2 sera éliminée. On a donc une optimalité n à n (pour mémoire, c'est ce que faisait l'algo par combinaisons).

Ce qu'on peut donc dire, c'est que les trois conditions incluent l'optimalité et par voie de conséquence, la dominance (ce qui ne signifie pas qu'on ne doive pas les utiliser en plus pour des raisons d'optimisation), MAIS à condition de construire progressivement les chemins de cette manière : donc prendre deux chemins in extenso et leur appliquer les conditions ne fonctionne pas (c'est à mon sens ce que montre ton contre exemple).


Concernant des chemins comprenant de mines différentes... Ca se complique (et c'est d'ailleurs tout le sujet) !
On peut d'une part remarquer qu'à un moment, les différents chemins vont converger pour avoir les mêmes mines.

Et donc ce qu'il s'agirait de vérifier c'est qu'on n'élimine pas de manière intermédiaire des débuts de chemins idéaux à cause de chemins localement/temporairement meilleurs (selon les 3 critères)... et cela pourrait expliquer une grande rareté des contre exemples dans des situations de tirages aléatoires.

Me revoilà !

Désolé de pas avoir répondu à tes posts, mais j'apporte de bonnes nouvelles !

La raison pour laquelle je n'ai finalement pas étudié la structure de ton algorithme, c'est que cette propriété semble être toujours vérifiée (j'ai fait beaucoup de tests) :

Soient c1 et c2 deux chemins.

Si :

- p(c1) >= p(c2)
- t(c1,p0) <= t(c2,p0)

Alors :

Le chemin idéal ne peut pas commencer par c2.

Autrement dit :

Soit un chemin c2. S'il existe un chemin c1 qui produit plus en moins de temps, alors c2 ne peut pas être bon.

J'ai enlevé la condition du coût total, qui semble inutile.

Tu peux donc améliorer ton algorithme en enlevant cette condition (et tu as le droit de faire des tests aussi ^^).

De plus, on retrouve la dominance entre mines, donc celle-ci n'est plus utile à coder (elle n'apportera rien de plus).


Je n'ai pas réussi à le démontrer pour l'instant.

Bonjour, bonjour

J'étais en congés, d'où l'absence de réponse depuis 3 semaines !

Pour revenir à notre sujet :

Citation:

---

Envoyé par Baruch

J'ai enlevé la condition du coût total, qui semble inutile.

---

... peut être, mais en faisant des tests en enlevant la condition sur le coût, il y a des cas où on ne trouve aucune solution !!

Pourquoi ? parce qu'il arrive qu'un chemin sélectionné sur la date de fin et la production seules ne puisse pas être complété en respectant l'optimalité 2 à 2.

Et comme un tel chemin est susceptible d'éliminer les bonnes solutions, au final on arrive à une impasse.

Donc il est peut être possible de se passer de la condition sur le coût mais il faudrait changer d'algo... mais je ne vois pas comment...

Citation:

---

Envoyé par Baruch

De plus, on retrouve la dominance entre mines, donc celle-ci n'est plus utile à coder (elle n'apportera rien de plus).

---

Là pas d'accord car la dominance absolue permet toujours de réduire l'arbre d'exploration...

Il est vivant ! :D :D Oh tu m'as fait peur...

Oui bon d'accord j'ai dit des bêtises dans le post d'avant.

Où j'en suis :

- J'essaye de garder en vue le fait que je veux par la suite résoudre des problèmes multi-ressources.

Aussi, la relation de dominance ne me semble pas très adaptée :

Avec une seule ressource, pour une mine donnée, il y a 1 chance sur 4 pour qu'une autre mine la domine.
Avec 2 ressources, 1 chance sur 16,
Avec n ressources, 1 chance sur 4^n

Donc ça devient vite inutile. (euh je dis tout ça mais j'ai pas démontré la dominance en multi-ressources moi x] )

- Je viens de me rappeler qu'on pouvait utiliser dijkstra :

Il faut que je code le NDO avec un dijkstra par dessus. C'est-à-dire qu'on a une liste de chemins potentiels, triés par temps croissant. A chaque itération on enlève le 1er chemin de la liste (de temps minimal), on crée tous les chemins fils possibles de celui-ci avec une mine de plus, et on les insère dans la liste des chemins potentiels. On fait ça jusqu'à ce que le 1er de la liste soit de taille n. Tout ça en rajoutant la dominance entre mines, et l'idéalité 2 à 2.

Tu peux me dire si ça vaut le coup ?

J'ai codé l'algo naïf avec dijkstra, mais j'ai l'impression qu'avec le dijkstra c'est un peu plus lent. En même temps je n'ai pu tester que sur de petits ensembles de mines, donc il faudra sur le NDO ce que ça donne. Et puis l'algorithme avec le dijkstra est plus lourd.

- J'ai envie d'essayer d'aller plus loin :

- Passer en multi-ressources :

Ne pas oublier que selon la production initiale, il peut ne pas exister de solution pour construire toutes les mines en un temps fini.

- Ajouter les temps de construction des mines (pendant lequel on peut, ou on ne peut pas construire d'autres mines)

- Ne plus travailler sur un ensemble de mines fini, au sens :

La construction de certaines mines en "débloque" d'autres. Pour ce problème en "ensemble infini", le but n'est bien entendu pas de construire toutes les mines, mais d'atteindre un montant de ressources donné le plus vite possible. Et le fait d'avoir un certain montant de ressources peut être modélisé par le fait de construire une mine de coût ce même montant.

C'est d'ailleurs pour ça que j'aurais tendance à écarter la dominance entre chemins (pour laquelle je n'ai toujours pas trouvé de démonstration). Il me semble qu'elle n'est valable que pour un ensemble fini de mines (après c'est juste une intuition).


En gros si on veut passer en multi-ressources, il ne reste que l'idéalité 2 à 2 (et l'algorithme par combinaisons, qu'on avait écarté, mais peut-être ne faut-il pas l'oublier).

Le problème c'est que la relation T([AB]) < T([BA]) en multi-ressources ne peut pas être simplifiée, comme on l'a fait en mono-ressource (les termes en p0² se simplifiaient). On est obligés de la garder telle quelle, puisqu'on ne connaît pas la ressource limitante (à moins que ?).

Donc il faut voir ce que donne l'ago naïf avec optimalité 2 à 2 en multi-ressources (et avec dijkstra). J'ai envie de réessayer l'optimalité 3 à 3.


Voilà ! :D :D

Ah sinon j'essaye de mobiliser des gens motivés dans mon école, ça sera peut-être plus facile qu'à 2. D'ailleurs il faudrait que je fasse un résumé de ce topic en annexe, pour que les gens n'aient pas à fouiller dans les 15 pages de discussion.

Je vais réfléchir à tout ça...

En multi ressources, au sens où une mine nécessite n quantités de n ressources pour être construite et produit elle-même p productions de p ressources, il faut aussi bien définir ce que devient la production initiale (car en fonction, il n'y aura pas toujours une solution au problème).

On pourrait également considérer que la production d'une mine s'épuise (quantité limitée)... ?

Citation:

---

- Je viens de me rappeler qu'on pouvait utiliser dijkstra :

Il faut que je code le NDO avec un dijkstra par dessus. C'est-à-dire qu'on a une liste de chemins potentiels, triés par temps croissant. A chaque itération on enlève le 1er chemin de la liste (de temps minimal), on crée tous les chemins fils possibles de celui-ci avec une mine de plus, et on les insère dans la liste des chemins potentiels. On fait ça jusqu'à ce que le 1er de la liste soit de taille n. Tout ça en rajoutant la dominance entre mines, et l'idéalité 2 à 2.

Tu peux me dire si ça vaut le coup ?

---

Ben... c'est exactement ce que fait le dernier algo à la différence près qu'il élimine en plus les chemins de la listes selon les 3 conditions (t1 < t2, c1 >= c2, p1 >= p2).
On peut évidemment garder tous les chemins sans les éliminer mais la liste va vite grimper en mémoire consommée.

Concernant l'algo par combinaison, je suis d'accord qu'il ne faut pas l'oublier. Mais "t1 < t2, c1 >= c2, p1 >= p2" traite les situations de combinaisons puisqu'on tombe alors dans le cas "t1 < t2, c1 = c2, p1 = p2"... donc si ces 3 conditions sont vraies (non démontré) c'est plus efficace.

Citation:

---

Ah sinon j'essaye de mobiliser des gens motivés dans mon école, ça sera peut-être plus facile qu'à 2. D'ailleurs il faudrait que je fasse un résumé de ce topic en annexe, pour que les gens n'aient pas à fouiller dans les 15 pages de discussion.

---

OK bien entendu pour avoir du renfort !! ;)

Citation:

---

En multi ressources, au sens où une mine nécessite n quantités de n ressources pour être construite et produit elle-même p productions de p ressources, il faut aussi bien définir ce que devient la production initiale (car en fonction, il n'y aura pas toujours une solution au problème).

---

Tout à fait d'accord.

Citation:

---

On pourrait également considérer que la production d'une mine s'épuise (quantité limitée)... ?

---

Pourquoi pas ^^

Citation:

---

Ben... c'est exactement ce que fait le dernier algo à la différence près qu'il élimine en plus les chemins de la listes selon les 3 conditions (t1 < t2, c1 >= c2, p1 >= p2).
On peut évidemment garder tous les chemins sans les éliminer mais la liste va vite grimper en mémoire consommée.

---

Ouép en effet. Mais si on fait un dijkstra avec optimalité 2 à 2, la mémoire consommée sera toujours inférieure à l'algo naïf avec optimalité 2 à 2 non ?

Citation:

---

Concernant l'algo par combinaison, je suis d'accord qu'il ne faut pas l'oublier. Mais "t1 < t2, c1 >= c2, p1 >= p2" traite les situations de combinaisons puisqu'on tombe alors dans le cas "t1 < t2, c1 = c2, p1 = p2"... donc si ces 3 conditions sont vraies (non démontré) c'est plus efficace.

---

Oui oui, je disais ça au cas où on écarte cette relation de dominance.

Citation:

---

Envoyé par Baruch

Ouép en effet. Mais si on fait un dijkstra avec optimalité 2 à 2, la mémoire consommée sera toujours inférieure à l'algo naïf avec optimalité 2 à 2 non ?

---

Pour l'algo naïf, ça dépend de la façon de l'implémenter !

Au plus "court", l'algo naïf nécessite :
- De parcourir toute les combinaisons : la taille mémoire correspondante est relative au nombre de mines (donc en n), car on est sur un parcourt en "profondeur d'abord"
- Parmi les chemins complets, d'en garder à chaque fois un seul : le plus court

Dijkstra nécessite de garder en attente en mémoire tous les chemins encore en compétition. Donc pour donner une idée, c'est de l'ordre de C(N, N/2)... ce qui peut devenir vite assez énorme et dans les implémentations qu'on a faites, ce nombre est (fortement) réduit par 3 optimisations :
- La dominance absolue
- L'optimalité 2 à 2
- L'élimination de chemins intermédiaires par les 3 règles (temps >, cout <, production <)

Citation:

---

Au plus "court", l'algo naïf nécessite :
- De parcourir toute les combinaisons : la taille mémoire correspondante est relative au nombre de mines (donc en n), car on est sur un parcourt en "profondeur d'abord"
- Parmi les chemins complets, d'en garder à chaque fois un seul : le plus court

---

Ouép, d'ailleurs je viens de me rendre compte que la façon dont je l'ai implémenté n'est pas du tout optimisée ^^.

Citation:

---

Dijkstra nécessite de garder en attente en mémoire tous les chemins encore en compétition. Donc pour donner une idée, c'est de l'ordre de C(N, N/2)... ce qui peut devenir vite assez énorme et dans les implémentations qu'on a faites, ce nombre est (fortement) réduit par 3 optimisations :
- La dominance absolue
- L'optimalité 2 à 2
- L'élimination de chemins intermédiaires par les 3 règles (temps >, cout <, production <)

---

C(N, N/2) ça fait du O(n^1/2 * 2^n) il me semble.

Ok je suis d'accord.

J'ai bien envie de voir le NDO avec dijkstra (et sans la dominance entre chemins), histoire de voir ce que donne vraiment cette dominance.

Pour la dominance entre chemins, j'ai pas bien compris ton explication sur le fait qu'on ne pouvait pas trop enlever l'inégalité des coûts totaux...

Rah si on arrivait à démontrer cette relation, on en saurait un peu plus sur son fonctionnement -__-.

Moi j'en suis au point mort, j'ai même pas réussi à démontrer que pour un ensemble de mines {A;B;C}, si [A;B] domine [C], alors le chemin idéal n'est pas fils de [C].

Citation:

---

Envoyé par Baruch

Pour la dominance entre chemins, j'ai pas bien compris ton explication sur le fait qu'on ne pouvait pas trop enlever l'inégalité des coûts totaux...

---

Si on ne considère pas les couts, il y a des situations pour lesquelles le meilleur chemin C sélectionné (plus court et plus productif) ne peut pas être complété en respectant l'optimalité 2 à 2.
Pourtant, la sélection de ce chemin C induit l'élimination de tous les chemins plus longs ou moins productifs parmi lesquels les solutions optimales 2 à 2.
... on se retrouve donc le bec dans l'eau car on a éliminé des solutions parmi lesquelles figurait la solution optimale.

Pour le dire autrement, il est intuitif qu'entre deux chemins intermédiaires de même temps et de même production, le meilleur d'entre eux est celui qui a couté plus cher (car ce qui reste à acheter est moins cher).

Bonjour,

Je suis la discussion depuis un certain temps, et je m'interroge sur quelques remarques faites récemment :

Citation:

---

Envoyé par Alikendarfen

Pour le dire autrement, il est intuitif qu'entre deux chemins intermédiaires de même temps et de même production, le meilleur d'entre eux est celui qui a couté plus cher (car ce qui reste à acheter est moins cher).

---

Je ne trouve pas ça particulièrement intuitif. Tu dis "le meilleur d'entre eux est le plus cher, car ce qui reste à acheter est moins cher". Mais on pourrait tout aussi bien dire le contraire : "le meilleur d'entre eux les le moins cher, car il nous reste plus d'argent pour acheter le reste", et je ne vois pas d'argument qui pencherait vers l'un ou l'autre de ces choix.
J'ai essayé de prouver ton intuition, mais je ne suis arrivé à rien de concluant. Je continue d'y travailler.

Citation:

---

Envoyé par Baruch

j'ai même pas réussi à démontrer que pour un ensemble de mines {A;B;C}, si [A;B] domine [C], alors le chemin idéal n'est pas fils de [C].

---

Je n'ai pas lu l'ensemble des pages donc j'ai peut-être raté quelque chose, mais qu'entends tu par "si [A;B] domine [C] ?
que Ca + Cb < Cc et Pa + Pb > Pc ? (respectivement coûts et productions).
Et considères tu que tu achètes A et B en même temps, ou A puis B ?
Sur un cas à 3 mines, il me semble qu'il serait possible de détailler tous les cas pour apporter cette preuve, avec ces quelques détails je me mettrais à y travailler =)

Merci pour ces remarques Myrne, cependant je ne suis pas d'accord avec ton contre argument :

Citation:

---

Envoyé par Myrne

Je ne trouve pas ça particulièrement intuitif. Tu dis "le meilleur d'entre eux est le plus cher, car ce qui reste à acheter est moins cher". Mais on pourrait tout aussi bien dire le contraire : "le meilleur d'entre eux les le moins cher, car il nous reste plus d'argent pour acheter le reste", et je ne vois pas d'argument qui pencherait vers l'un ou l'autre de ces choix.
J'ai essayé de prouver ton intuition, mais je ne suis arrivé à rien de concluant. Je continue d'y travailler.

---

En fait, à l'issue de l'achat d'une mine donnée, il ne reste plus d'argent, car on achète au plus tôt dès qu'on possède le montant requis pour la prochaine mine.
L'argent qu'on peut posséder n'est lié qu'à la production totale courante (c'est à dire la production initiale plus la somme des productions des mines déjà acquises).

Du coup, quand tu dis "le meilleur d'entre eux les le moins cher, car il nous reste plus d'argent pour acheter le reste" ça ne correspond pas (à mon sens) à l'énoncé car il ne nous reste pas d'argent à l'issue d'un achat...

Le cout total des mines (ensemble fini) peut se décomposer en C = A + R, où A est la somme des couts des mines déjà achetées et R la sommes des couts des mines restant à acquérir : la règle "intuitive" dont je parlais vient simplement du fait que plus A est grand, plus R est petit puisque C est constant. Ceci étant complété par la seconde règle sur les productions qui indique que le chemin sélectionné doit également avoir la meilleure production.

Donc pour reformuler cette règle concernant la dominance de chemins (règle non démontrée) : un chemin C1 est nécessairement meilleur qu'un chemin C2 si à la fois C1 termine avant C2, produit plus que C2 et a un coût total supérieur à celui de C2 (donc a un reste à acquérir inférieur à celui de C2).


... mais n'hésite pas à nous faire d'autres remarques (car sauf à repartir sur le problème étendu à n ressources, comme l'indiquait Baruch, on est plutôt à court d'idées depuis pas mal de temps) !!

Merci pour ces précisions. Du coup je m'interroge sur autre chose:

Si j'ai bien saisi, on a deux chemins, C1 et C2, de temps de production t1=t2, de productions équivalents p1=p2, et enfin de coûts différents, disons c1 < c2.

En voyant ça, j'ai l'intuition qu'il doit être possible de sortir de l'ensemble des mines incluses dans C1 et l'ensemble des mines incluses dans C2 un troisième chemin C3 qui serait meilleur que C1 et C2: soit un t3< t1&t2 pour une production équivalente, soit un p3> p1&p2 pour un temps équivalent.

J'ai du mal à concevoir correctement la chose, mais je me dis que deux chemins offrant les mêmes temps et production pour des coûts différents doivent forcément permettre d'obtenir un chemin C3, à partir de C1 et C2, qui serait mieux que C1 et C2.

Une question qui pourrait peut-être changer cela : lorsque vous comparez deux chemins dans vos algorithmes, ceux-ci ont-ils nécessairement le même nombre de mines, ou peut-on comparer un chemin C1 contenant 3 mines à un chemin C2 contenant 12 mines ?

Je vais aussi réfléchir à ça, mais pour le moment, il faut vraiment que je me remette au boulot ;)

On est plus tout seuls ! ^^

Citation:

---

Je ne trouve pas ça particulièrement intuitif. Tu dis "le meilleur d'entre eux est le plus cher, car ce qui reste à acheter est moins cher". Mais on pourrait tout aussi bien dire le contraire : "le meilleur d'entre eux les le moins cher, car il nous reste plus d'argent pour acheter le reste", et je ne vois pas d'argument qui pencherait vers l'un ou l'autre de ces choix.
J'ai essayé de prouver ton intuition, mais je ne suis arrivé à rien de concluant. Je continue d'y travailler.

---

Sur cette remarque, la réponse d'Alikendarfen me semble tout à fait juste.
Néanmoins, la question de l'intuition est intéressante. Je m'explique :

Un jour Alikendarfen nous a sorti de nulle part cette relation de dominance entre chemins :

c1 domine c1 <=> ( p(c1) > p(c2) et c(c1) < c(c2) et t(c1,p0) < t(c2,p0) )

Avec la propriété : Soit c un chemin. S'il existe un chemin c' tel que c' domine c, alors le chemin optimal ne peut pas être fils de (issu de) c.

Je dis "de nulle part", parce-que bon déjà il n'y a pas de démonstration, mais surtout parce-que je n'arrive pas à voir le côté intuitif de cette propriété.
Donc ça serait intéressant qu'Alikendarfen s'explique là-dessus ^^.

Citation:

---

Je n'ai pas lu l'ensemble des pages donc j'ai peut-être raté quelque chose, mais qu'entends tu par "si [A;B] domine [C] ?
que Ca + Cb < Cc et Pa + Pb > Pc ? (respectivement coûts et productions).
Et considères tu que tu achètes A et B en même temps, ou A puis B ?
Sur un cas à 3 mines, il me semble qu'il serait possible de détailler tous les cas pour apporter cette preuve, avec ces quelques détails je me mettrais à y travailler =)

---

D'après ce que j'ai écrit plus haut, "[A;B] domine [C]" équivaut à :

cA + cB <= cC
pA + pB >= pC
cA/p0 + cB/(p0+pA) <= cC/p0

Si on a ces 3 conditions réunies, il faut montrer que [C;A;B] et [C;B;A] ne sont nécessairement pas les chemins idéaux, c'est-à-dire qu'il existe toujours un meilleur chemin que ces deux là.

Citation:

---

Une question qui pourrait peut-être changer cela : lorsque vous comparez deux chemins dans vos algorithmes, ceux-ci ont-ils nécessairement le même nombre de mines, ou peut-on comparer un chemin C1 contenant 3 mines à un chemin C2 contenant 12 mines ?

---

Non, la nombre de mines dans un chemin n'est pas important.


Bon tu as l'air de t'intéresser à la démonstration. Il se trouve que j'ai déjà passé pas mal d'heures à retourner dans tous les sens ce problème. Je te ferai part des quelques constats que j'ai faits (ultérieurement, pas le temps ^^).

Mais avant tout, sur tous les tests que j'ai effectués, la condition de coût m'a semblé inutile. Mais Alikendarfen dit que non, donc je sais pas. En tout cas sur le cas "[A;B] domine [C]", cette condition de coût ne change rien.

Citation:

---

Envoyé par Myrne

Une question qui pourrait peut-être changer cela : lorsque vous comparez deux chemins dans vos algorithmes, ceux-ci ont-ils nécessairement le même nombre de mines, ou peut-on comparer un chemin C1 contenant 3 mines à un chemin C2 contenant 12 mines ?

---

Non, ils n'ont pas nécessairement le même nombre de mines.

Et je reprécise que nous n'avons pas la preuve que cet algo soit un algo exact (nous pouvons simplement dire que sur plusieurs millions de tirages aléatoires, cet algo a toujours donné la même solution qu'un algo exact pris comme référence).

Je redonne les grandes lignes du fonctionnement de cet algo.
Dans l'esprit, il ressemble à l'algo de Dijkstra qui consiste à trouver le plus court chemin entre deux noeuds d'un graphe (voir ce lien pour plus d'info http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra).

Dans notre contexte voici les différences ou correspondances par rapport à l'algo d'origine :
- Les noeuds sont des mines
- Il est possible de circuler d'une mine vers n'importe quelle autre
- Le cout de circulation d'une mine vers une autre est dépendant du cout de cette autre mine et de la production totale du chemin en cours d'évaluation
- Dijkstra poursuit sa recherche sur la base du plus court chemin parmi les chemins en cours d'éval
- Notre algo également
- Dijkstra élimine un chemin lorsqu'un chemin précédent (donc plus court) est déjà passé par un noeud : donc le chemin éliminé aboutit au même noeud en plus de temps
- Notre algo élimine un chemin selon les 3 critères (temps plus long, cout inférieur, production inférieure) : donc le chemin éliminé, en plus d'être plus long, laisse à acquérir un ensemble de mines plus cher partant d'une production moindre


Pour les remarques concernant C1 et C2 permettant d'aboutir à C3... je ne vois pas mais pourquoi pas... dis nous !

Et enfin concernant "mais pour le moment, il faut vraiment que je me remette au boulot"... je suis d'accord mais comme c'est "gratuit et intéressant" c'est quand même plus fun... merci Baruch !! ;)

Citation:

---

Envoyé par Baruch

On est plus tout seuls ! ^^

---

Effectivement et c'est tant mieux !! :)

Citation:

---

Envoyé par Baruch

Un jour Alikendarfen nous a sorti de nulle part cette relation de dominance entre chemins :

c1 domine c1 <=> ( p(c1) > p(c2) et c(c1) < c(c2) et t(c1,p0) < t(c2,p0) )

---

Attention, attention !! C'est :
c1 domine c2 <=> ( p(c1) > p(c2) et c(c1) > c(c2) et t(c1,p0) < t(c2,p0) )

Citation:

---

Envoyé par Baruch

Donc ça serait intéressant qu'Alikendarfen s'explique là-dessus ^^.

---

... histoire de s'amuser un peu, je dirais qu'il y a deux niveaux de réponse :

Celle où il n'y a pas d'explication car personne ne sait pourquoi nos pensées, paroles et parfois actes nous viennent à la place d'autres pensées, paroles ou actes (le libre arbitre existe-t-il vraiment ??).

Celle où simplement je cherchais à assimiler un chemin à une mine (on peut formaliser un chemin comme une mine... bien que je n'ai pas trouvé d'usage concret de cela). Et dans ce cadre, pour les mines, on a dit M1 domine M2 si c1 < c2 et p1 > p2.
J'ai simplement cherché à étendre/adapter ces critères aux chemins... et dire que si on arrive plus rapidement à avoir acheté plus en produisant plus est mieux que le reste semble assez logique/intuitif (mais ok, les intuitions ne sont pas raison...).

Citation:

---

Envoyé par Baruch

Mais Alikendarfen dit que non, donc je sais pas. En tout cas sur le cas "[A;B] domine [C]", cette condition de coût ne change rien.

---

Là, j'ai juste lancé une série de tests aléatoires pour identifier des impasses lorsqu'on supprime la condition sur le cout.
Mais effectivement, ça "se voit" assez rapidement sur au moins 4 mines (sur deux mines, c'est impossible ; sur 3 mines, je n'ai pas trouvé de contre exemple)

Bon, j'ai gribouillé un paquet de pages, sans arriver à aucune conclusion. Ce que je peux dire jusque là:

la construction de A puis B, que je noterai [A;B] est équivalente à la construction d'une seule mine AB de production pA+pB et de coût (cA/p0 + cB/(p0+pA) ).(pA+pB).

Dire que AB > C implique donc :
pA + pB >= pC
(cA/p0 + cB/(p0+pA) ) x (pA+pB) <= cC

Citation:

---

Envoyé par Baruch

D'après ce que j'ai écrit plus haut, "[A;B] domine [C]" équivaut à :

cA + cB <= cC
pA + pB >= pC
cA/p0 + cB/(p0+pA) <= cC/p0

---

Cette équivalence n'est pas la même que celle de AB domine C et je ne pense pas que l'on puisse prouver que l'on a l'une qui implique l'autre, puisque le coût de AB dépend de p0 quand celui de A et B ne dépend de rien. Je vais lancer quelques simulations ce soir pour voir un peu si j'arrive à obtenir des contre-exemples.

Après une pause, je me suis rendu compte que j'avais tourné en rond pendant trois heures, donc ça suffira pour ce soir, je m'y remets demain =)

Attention encore une fois :

sauf à ce que vous parliez d'autre chose, la règle utilisée est:

Etant donnés deux chemins C1, C2,

Si
- Le cout de C1 est supérieur ou égale à celui de C2
- La production de C1 est supérieure ou égale à celle de C2
- La date de fin de C1 est inférieure ou égale à celle de C2

Alors
C1 domine C2 (et "domine" signifie "le meilleur chemin complet issu de C2 termine toujours après le meilleur chemin complet issu de C1").

Dans les premières pages, quand ça parlait de dominance entre deux mines, la notion était "un temps d'obtention plus faible pour une production meilleure", ce qui me semble intuitivement logique. Étendue à un chemin, la notion de coût ne devrait pas apparaître. Mais vu que je n'ai fait tourner aucun algo, je vais te croire sur ce point =)

En tout cas, j'ai fait tourner un milliard de jeux de 4 mines (ça m'a pris 3 bonnes heures) dont 3 d'entre elles respectaient les conditions "[A;B] domine C" énoncées par Baruch, et je n'ai trouvé aucun contre-exemple, aucun des chemins où C était avant A et B n'était idéal.

Sinon je vais revenir à mon idée initiale et essayer d'y travailler aujourd'hui:

Citation:

---

deux chemins offrant les mêmes temps et production pour des coûts différents doivent forcément permettre d'obtenir un chemin C3, à partir de C1 et C2, qui serait mieux que C1 et C2.

---

Et par "mieux que C1 et C2", histoire qu'on se mette d'accord, j'entends "prix indifférent mais production supérieure ou égale et temps de construction total inférieur ou égal" =)

Un détail qui peut éventuellement aider à simplifier les démonstrations :

Il s'agit de définir des productions normalisées par rapport à p0, en écrivant pour toute mine Mi "qi = pi/p0" (p0 est strictement positif).

Les trois conditions sont alors (cas des trois mines A B C) :
(1) cA + cB >= cC
(2) qA + qB >= qC
(3) cA + cB / (1 + qA) <= cC

Il s'en suit que depuis (3) cB / (1 + qA) <= cC - cA donc que cC >= cA
Mais aussi que depuis (1) cC - cA <= cB
... c'est effectivement étrange ! pourquoi cC ne pourrait-il pas être aussi grand qu'on veut ??

Que se passe-t-il dans l'algo lorsqu'il ne trouve pas de solution lorsqu'on ne prend pas en compte la condition sur le cout :
- On considère le plus court chemin C parmi la liste L des chemins encore en compétition
- On élimine de L tous les chemins dont la production est moindre
- On tente de compléter C avec chacune de ses mines Mi restantes pour obtenir de nouveaux chemins C'i = C + Mi mais tels Mi soit optimale 2 à 2 avec la mine précédente... et on n'en trouve pas (ou pas toujours) !!
- Du coup, aucun chemin C'i n'est généré et on finit par avoir une liste L vide : d'où l'échec

... pour le moment, je n'ai pas plus d'explication :(

en choisissant d'avoir un cout de production pour A et B supérieur à celui de C, tu majores forcément le coût de C. Pour être précis, tu obtiens même un encadrement de C selon (1) et (3) :
cA+cB >= cC >= cA+cB/(1+qA)

Et ceci doit quand même fortement limiter le nombre de fois où tu peux te ramener à cette inégalité pour décider du chemin à prendre. Je pense que le problème vien aussi du fait que cA+cB, ce n'est pas le coût de construction de A puis B, c'est une condition beaucoup plus restrictive que cela.

Le coût de construction de A puis B est en réalité (cA+cB/(1+qA))(qA+qB). Si tu veux que ce coôt soit supérieur à celui de C, en notant cAB la valeur (cA+cB/(1+qA)), ton inégalité passe alors de

cA+cB >= cC >= cAB
à
cAB(qA+qB) >= cC >= cAB


Edit: remarque "plus restrictive", j'en sais rien, ça dépent des pA, pB et p0. En tout cas, ces inégalités n'ont aucun rapport entre elles =)