Ordre de construction de mines

En fait, dans l'esprit de cette règle, ça n'est pas tant le cout de A et B qui m'intéresse, mais c'est le fait que le cout de A et B étant fort, le cout des mines restantes est plus faible : il nous reste moins à acheter (et par ailleurs on a déjà acheté plus vite des mines nous apportant une production plus forte).


Par ailleurs (et ça compte), tous les chemins comparés sont optimaux 2 à 2 : Baruch avait mis en avant un exemple montrant que ces 3 règles ne fonctionnent pas si les chemins ne sont pas optimaux 2 à 2.
... Ce qui revient à dire que des règles additionnelles sur le cout sont déjà appliquées en plus des 3 critères.

Une idée pour une approche un peu différente de ce qu'on a fait précédemment.

Ca s'inspire de la discussion fusion-listes-ordonnancees sur ce même forum.

Voilà l'idée :
- On constitue un ensemble de chemins correspondant aux listes ordonnancées à fusionner
- Chaque chemin est lui-même créé dans le bon ordre car on utilise les conditions de dominance absolue pour le créer
- Ensuite, on fusionne les chemins, en respectant les règles d'optimalité 2 à 2

Les chemins de base pourraient être créés de la manière suivante (il y a d'autres méthodes) :
- Imaginons les mines réparties sur un repère à deux dimensions cout et production
- On part de la mine M1 la plus à gauche (la moins chère) et en cas d'égalité la plus en haut (la plus productive)
- M1 domine toutes les mines plus chères et moins productives (celles du cadran en bas à droite par rapport à M1)
- On prend la mine M2 la plus à gauche et la plus en haut de ce cadran : on constitue un chemin M1M2
- Puis on continue avec le cadran de M2, ainsi de suite jusqu'à ce que le cadran de la dernière mine de ce chemin soit vide
- Une fois ce premier chemin constitué, il nous reste des mines : on recommence en constituant un second chemin de la même manière avec les mines restantes
- Ainsi de suite jusqu'à ce qu'il n'y ait plus de mines

On a donc créé x "chemins de dominance".

De là il s'agit de les fusionner (voir la discussion citée plus haut) en respectant des règles. Typiquement :
- la propagation d'une dominance (transitivité)
- l'optimalité 2 à 2

Avant de passer éventuellement à une implémentation : qu'en pensez vous ?

Oula mais vous ne travaillez donc jamais ? ^^

Bon quelques réponses à tous les posts de ce matin :

Citation:

---

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

---

Oui c'est pour ça que l'algo NDO+ (faut lui trouver un nom) est plutôt un dijkstra-like, puisque pour moi dans un graphe les arêtes ont un poids fixe (je crois).

A propos, j'ai codé le NDO avec dijkstra, mais sans la dominance entre chemins, et c'est notablement plus lent que le NDO simple (est-ce surprenant ?).

Citation:

---

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...).

---

Oui assimiler un chemin à une mine est une bonne idée... mais qui ne mène à rien (sauf pour l'intuition). En effet on ne peut pas réduire le temps d'un chemin sous la forme C' / p0.

logique/intuitif... bof ^^. J'avais montré cela (je sais pas si tu as vu Myrne, #277) :

Dans un système de 4 mines {A.B;C;D},

Supposons qu'on ait [A;B] qui domine [C;D]. (les 3 conditions)

On peut avoir le cas suivant :

Le chemin optimal issu de [C;D] peut être meilleur que le chemin optimal issu de [A;B].
Néanmoins, le chemin optimal issu de [C;D] n'est pas le chemin optimal du système.

A méditer...

Citation:

---

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 ??

---

C'est pour cela que la condition de coût me paraît bancale.

Citation:

---

En fait, dans l'esprit de cette règle, ça n'est pas tant le cout de A et B qui m'intéresse, mais c'est le fait que le cout de A et B étant fort, le cout des mines restantes est plus faible : il nous reste moins à acheter (et par ailleurs on a déjà acheté plus vite des mines nous apportant une production plus forte).

---

C'est pour cela que j'ai l'impression que cette dominance ne marche qu'en "système fini" (pas de mines qui se débloquent etc.). Et c'est aussi à coup sûr un point clé de la démonstration.



Pour ta proposition d'algo par fusion, je vais y réflèchir ^^.


Ah sinon là j'essaye de rajouter au NDO une propriété que je sais plus qui avait directement mis à la poubelle :

Soit E un ensemble de mines.
La production initiale est p0.

On note P*max le maximum des p* de tous les couples de mines de E.

Si P*max < p0 , alors le chemin optimal de E correspond au tri par rendement. (propriété démontrée)

Pour Myrne (je ne sais pas si tu avais vu) :

Soient 2 mines A et B. On note p*(A,B) = p*(B,A) = (cA - cB) / (cB/pB - cA/pA)

On a la propriété (démontrée) :

Supposons que pA/cA > pB/cB,

p0 < p*(A,B) <=> [BA]p0 est meilleur que [AB]p0



Je pense que cette propriété, bien qu'assez lourde à coder, peut simplifier le problème pour des grands ensembles de mines.

Bon j'ai trouvé la preuve de ce que j'avançais sur l'histoire de l'existence d'un chemin C3 mieux que deux chemins C1 et C2 de temps et prod équivalentes. Ceci à condition que j'aie bien compris la phrase suivante :

Citation:

---

Envoyé par Alikendarfen

Par ailleurs (et ça compte), tous les chemins comparés sont optimaux 2 à 2

---

Je l'ai traduite par : pour toutes mines i,j incluses dans un chemin optimal deux à deux, i<j implique Ci<=Cj et Pi>=Pj.

J'ai bon ? Si c'est bon je poste ma démo ce soir, là je retourne bosser.

Citation:

---

Bon j'ai trouvé la preuve de ce que j'avançais sur l'histoire de l'existence d'un chemin C3 mieux que deux chemins C1 et C2 de temps et prod équivalentes. Ceci à condition que j'aie bien compris la phrase suivante :

Citation:
Envoyé par Alikendarfen
Par ailleurs (et ça compte), tous les chemins comparés sont optimaux 2 à 2

Je l'ai traduite par : pour toutes mines i,j incluses dans un chemin optimal deux à deux, i<j implique Ci<=Cj et Pi>=Pj.

---

Euh attention, je crois que tu fais une grosse erreur (ou alors j'ai pas compris ta démarche) :

2 mines peuvent ne pas se dominer l'une l'autre : Ci < Cj et Pi < Pj par exemple.

Et il existe des chemins idéaux 2 à 2 dans lesquels toutes les mines ne se dominent pas.

Idéal 2 à 2 signifie :

Pour chaque couple de mines consécutives, permuter ce couple donnerait un chemin de temps plus long.

Oula attention j'avais pas vu :

Citation:

---

Par ailleurs (et ça compte), tous les chemins comparés sont optimaux 2 à 2 : Baruch avait mis en avant un exemple montrant que ces 3 règles ne fonctionnent pas si les chemins ne sont pas optimaux 2 à 2.
... Ce qui revient à dire que des règles additionnelles sur le cout sont déjà appliquées en plus des 3 critères.

---

Non ! xD

J'ai jamais dit ça... Ou alors il était très tard.
Par ailleurs les tests effectués sur 3 mines que j'ai réalisés ne prenaient pas en compte l'idéalité 2 à 2.
De plus Alikendarfen a fait des tests plus généraux en très grand nombre, sans l'optimalité 2 à 2, qui se sont avérés corrects.

Ok donc j'm'a planté chef.

Cela dit, à la relecture de ma preuve, ça ne change rien, je n'ai pas utilisé cette propriété, et ma preuve est valable même si les chemins ne sont pas optimaux 2 à 2. La seule condition est que leurs temps de construction et production finale soient les mêmes. Vu qu'on nous a coupé l'accès au réseau Airbus, je ne peux plus bosser et je suis obligé de poster ma preuve :

Définition du problème:

Citation:

---

Soient:
U : [1,m] -> [1,N] injective et
V : [1,n] -> [1,N] injective et
U([1,m]) différent de V([i,n]) (si l'on étudie les mêmes mines dans un ordre différent mais menant au même résultat, cette preuve est fausse, mais dans ce cas là ça n'a probablement pas beaucoup d'importance.)

Telles que:
t(U) = temps de construction total selon l'ordre U([1,m])
= Somme(C(u(i))/(P0+Somme_de_1_à_i-1(P(u(j)))))

(je sais, c'est pas lisible).

P(U) = production totale de l'ensemble des mines de U([1,m])
=Somme(P(u(i)))

Et
t(V)=t(U)
P(V)=P(U).

---

Montrons que:

Citation:

---

il existe
W : [1,p] -> U([1,m]) U V([1,n]) injective

telle que:
- t(W) <= T(U)
- P(W) >) P(U)
- W différente de U et W différente de V

---

Enumération des cas possibles :

Citation:

---

(1) : Il existe (i,j) dans [1,m]x[1,n] tel que:
C(u(i))<=C(v(j))
P(u(i))>=P(v(j))
u(i) n'est pas inclus dans V([1,n])

(2) : il existe (i,j) dans [1,m]x[1,n] tel que:
C(u(i))>=C(v(j)) et P(u(i))<=P(v(j))
v(j) n'est pas inclus dans U([1,m])

(3) : (1) et (2) ne sont pas vérifiées et:
pour tout (i,j) dans [1,m]x[1,n]
C(u(i)) >= C(v(j))
P(u(i)) >= P(v(j))

(4) : (1) et (2) ne sont pas vérifiées et:
pour tout (i,j) dans [1,m]x[1,n]
C(u(i)) <= C(v(j))
P(u(i)) <= P(v(j))

---

Ces 4 hypothèses regroupe l'ensemble des inégalités possibles entre les coûts des mines U et V et les production des mines U et V.
Montrons que chacun de ces cas permet de trouver un W satisfaisant les hypothèses énoncées plus haut.

Cas (1)

Citation:

---

La liste W : [1,n]\i U j -> U([1,n]\i) U v(j) définie par:
W([1,i-1]) = V([1,i-1])
W(i)=u(i)
W([i+1,n]) = V([i+1,n])
est injective,
t(W) <= t(V),
P(W) >= P(V)

---

cas (2):

Citation:

---

Même démonstration avec U<->V et i<->j.

---

cas(3):

Citation:

---

Comme U est différente de V, il peut exister un couple (i,j) tel que:
P(u(i))>P(v(j))
Dans ce cas P(U)<P(V), ce qui est en contradiction avec les hypothèses initiales, ce cas ne peut donc pas se produire.

S'il n'existe pas de tel couple, c'est que toutes les production sont égales, alors puisque U différente de V, il existe forcément un couple (i,j) tel que:
C(u(i))>C(v(j))
Dans ce cas t(U)>t(V), ce qui est en contradiction avec les hypothèses initiales, ce cas ne peut donc pas se produire.

---

cas (4):

Citation:

---

même démonstration que (3) avec U<->V et i<->j

---

On a donc montré que les cas (1) et (2) sont les seuls cas possibles pour deux chemins différents ayant même temps de construction et même production finale, et que ces deux cas mènent à la construction d'un troisième chemin meilleur que les deux premiers. CQFD.


Si vous voyez des failles/erreurs, ou si c'est pas clair demandez moi. En tout cas si c'est juste, ça permet de s'affranchir de la question du coût que je trouvais particulièrement non-intuitive, niark niark niark.

Edit: après relecture, ce n'est pas tout à fait ça, les hypothèses ne regroupent pas tous les cas. Lorsque U et V ont une partie de leurs mines en commun, on peut n'avoir ni (1) ni (2) mais ne pas avoir les cas (3) ou (4) quand même. J'y retravaillerai ce soir.

Cas (1) et (2) -> ok.

Après, ce qui reste quand on n'est pas dans les cas (1) et (2) c'est :

qqsoit (i,j) dans [1,n]x[1,m]

c(Ui) >= c(Vj)
et p(Ui) >= p(Vj)

ou

c(Ui) <= c(Vj)
et p(Ui) <= p(Vj)


Ce qui n'est pas ce que tu as écrit. Peut-être as-tu une explication ?

Edit : Sinon les cas (3) et (4) que tu donnes sont effectivement bien démontrés.

Citation:

---

Envoyé par Baruch

Oula mais vous ne travaillez donc jamais ? ^^

---

Ben si... entre les posts : ))

Citation:

---

Envoyé par Baruch

Oui c'est pour ça que l'algo NDO+ (faut lui trouver un nom) est plutôt un dijkstra-like, puisque pour moi dans un graphe les arêtes ont un poids fixe (je crois).

---

Oui, je l'avais appelé dijkstra like aussi au début...

Citation:

---

Envoyé par Baruch

A propos, j'ai codé le NDO avec dijkstra, mais sans la dominance entre chemins, et c'est notablement plus lent que le NDO simple (est-ce surprenant ?).

---

??? comment fais tu sans la dominance ? Seulement avec la date de fin ?? Si c'est le cas, c'est pas étonnant à mon sens (l'obligation de préserver tous les chemins + cout des comparaisons sur la date de fin).

Citation:

---

Envoyé par Baruch

C'est pour cela que la condition de coût me paraît bancale.

---

Oui... mais pas trouvé d'exemple où ça ne marche pas...

Citation:

---

Envoyé par Baruch

C'est pour cela que j'ai l'impression que cette dominance ne marche qu'en "système fini" (pas de mines qui se débloquent etc.). Et c'est aussi à coup sûr un point clé de la démonstration.

---

Oui, je suis d'accord... mais reste à bien définir la notion de meilleur chemin pour un système non fini !!

Citation:

---

Envoyé par Baruch

Ah sinon là j'essaye de rajouter au NDO une propriété que je sais plus qui avait directement mis à la poubelle : etc.

---

C'est moi ! :)
Mais en fait je ne l'ai pas mise à la poubelle. De mémoire, j'avais simplement indiqué que les calculs du pMax me semblait difficilement exploitables car complexes en termes d'algo en complément du reste.
Mais l'idée rejoint ce que j'avais longtemps défendu : trouver une condition de dominance dépendante de p0 (ou en tout cas p actuel) et la somme des pi.

Concernant les remarques de Baruch suite au post de Myrne sur l'idéalité 2 à 2, je confirme évidemment le post de Baruch.

Citation:

---

Envoyé par Baruch

Oula attention j'avais pas vu :

Non ! xD

J'ai jamais dit ça... Ou alors il était très tard.
Par ailleurs les tests effectués sur 3 mines que j'ai réalisés ne prenaient pas en compte l'idéalité 2 à 2.
De plus Alikendarfen a fait des tests plus généraux en très grand nombre, sans l'optimalité 2 à 2, qui se sont avérés corrects.

---

Ce qui s'était passé :
- tu as trouvé un contre exemple mais ce contre exemple ne respectait pas l'idéalité 2 à 2
- malgré les tests que j'ai pu faire (je ne suis pas sûr qu'ils aient été si nombreux que ça), l'idéalité 2 à 2 semble bien nécessaire

Edit : mais effectivement je n'ai pas dit que tu avais formulé cette conclusion, j'ai seulement dit que tu avais trouvé un contre exemple non idéal 2 à 2

@ Myrne :

Pourquoi tu veux montrer cette propriété au fait ? ^^

@ Alikendarfen :

Citation:

---

Citation:
Envoyé par Baruch
A propos, j'ai codé le NDO avec dijkstra, mais sans la dominance entre chemins, et c'est notablement plus lent que le NDO simple (est-ce surprenant ?).

??? comment fais tu sans la dominance ? Seulement avec la date de fin ?? Si c'est le cas, c'est pas étonnant à mon sens (l'obligation de préserver tous les chemins + cout des comparaisons sur la date de fin).

---

Ben je fais un dijkstra (je crois... ^^) :

Je gère une banque de chemins potentiels, ordonnée par temps croissant.

A chaque itération :

- Je prends le 1er chemin de la banque (celui de temps minimal), je le retire de la banque. Je crée tous les chemins fils qui résultent de la concaténation de ce chemin-là, et d'une mine absente de ce chemin.
- J'insère tous les chemins créés dans la banque, de telle sorte que la banque reste toujours triée par temps croissant.

Je fais ça à chaque itération, jusqu'à ce que le 1er chemin de la banque, c'est-à-dire le plus court, soit de taille n (la taille de l'ensemble des mines).

A cet algorithme j'ajoute lors de la création des chemins fils la condition de dominance des mines, et la condition d'idéalité 2 à 2.

C'est bien un dijkstra non ? J'explore toujours le chemin le plus court jusqu'à arriver à l'objectif final.

Citation:

---

C'est moi !
Mais en fait je ne l'ai pas mise à la poubelle. De mémoire, j'avais simplement indiqué que les calculs du pMax me semblait difficilement exploitables car complexes en termes d'algo en complément du reste.
Mais l'idée rejoint ce que j'avais longtemps défendu : trouver une condition de dominance dépendante de p0 (ou en tout cas p actuel) et la somme des pi.

---

Ben je vais le coder, comme ça on sera fixés ^^

Edit :

Citation:

---

Ce qui s'était passé :
- tu as trouvé un contre exemple mais ce contre exemple ne respectait pas l'idéalité 2 à 2
- malgré les tests que j'ai pu faire (je ne suis pas sûr qu'ils aient été si nombreux que ça), l'idéalité 2 à 2 semble bien nécessaire

Edit : mais effectivement je n'ai pas dit que tu avais formulé cette conclusion, j'ai seulement dit que tu avais trouvé un contre exemple non idéal 2 à 2

---

Il faut faire attention de quoi on parle :

Au début j'ai voulu montrer la propriété (1) :

Si c1 domine c2, alors le chemin idéal issu de c1 est meilleur que le chemin idéal issu de c2.

J'ai trouvé un contre-exemple. J'ai donc énoncé la propriété (2), qui est plus faible :

Si c1 domine c2, alors le chemin idéal du système n'est pas issu de c2.


Peut-être que (1) est vrai si l'on considère que les chemins sont idéaux 2 à 2.

Mais, dans tous les tests que j'ai effectués, c'est la propriété (2) que j'ai étudiée, et qui semble toujours vérifiée. Et ce, sans aucune considération d'idéalité 2 à 2.

Citation:

---

Envoyé par Baruch

@ Alikendarfen :



Ben je fais un dijkstra (je crois... ^^) : etc.

---

... donc c'est bien ce que j'avais supposé et je confirme que ça me semble normal que ce soit plus long que NDO simple !

Ah d'accord. Mais je croyais que DIJKSTRA c'était un mot magique moi D:

:mouarf: magique si cela réduit l'exploration significativement... mais juste en prenant le plus court c'est bof :(

ça serait comme prendre le vrai dijkstra (celui du calcul du plus court chemin entre deux villes) et ne pas élaguer les hypothèses passant par une ville déjà visitée....

PS : d'où la nécessité du test sur les 3 critères...

Ah d'accord.

Bon quelques questions :

Suite à une de tes remarques, j'ai refait l'algorithme naïf en "profondeur d'abord", ce qui m'évite un "Out of memory" ^^.

Du coup je me suis dit que j'allais faire le NDO de la même façon, c'est-à-dire en créant une fonction NDO récursive.
Mais le problème c'est qu'à cause de l'idéalité 2 à 2, la fonction NDO appliquée à certains ensembles ne donne pas de résultat, puisqu'il n'y a pas possibilité d'avoir une liste idéale 2 à 2, à cause de la mine qui a été placée juste avant.
Donc je me demande, est-ce qu'on peut opérer de la même façon que l'algo naïf ?
Parce-que quand on ne trouve pas de solution, il faudrait pouvoir rembobiner...

Pour le PS : d'où la nécessité d'une démonstration :p

Citation:

---

Envoyé par Baruch

Il faut faire attention de quoi on parle : etc

---

Ben je fais attention, autant que possible ! 8-)

On peut donc dire : si le dijkstra like (incluant l'optimalité 2 à 2 et utilisant les trois critères) est un algo exact, l'optimalité 2 à 2 est une condition nécessaire de son bon fonctionnement.

Ca te va ?


Sinon @Myrne, pour ta démo, moi j'aurais besoin d'une définition en bon vieux français de ce que tu cherches à montrer... tu peux en donner une stp ?

Citation:

---

On peut donc dire : si le dijkstra like (incluant l'optimalité 2 à 2 et utilisant les trois critères) est un algo exact, l'optimalité 2 à 2 est une condition nécessaire de son bon fonctionnement.

---

Ben non ^^. Rien ne prouve qu'on ait besoin de l'optimalité 2 à 2 pour que l'algorithme fonctionne (et en plus ce serait un peu bizarre je trouve).

Citation:

---

Sinon @Myrne, pour ta démo, moi j'aurais besoin d'une définition en bon vieux français de ce que tu cherches à montrer... tu peux en donner une stp ?

---

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.

Citation:

---

Envoyé par Baruch

Du coup je me suis dit que j'allais faire le NDO de la même façon, c'est-à-dire en créant une fonction NDO récursive.
Mais le problème c'est qu'à cause de l'idéalité 2 à 2, la fonction NDO appliquée à certains ensembles ne donne pas de résultat, puisqu'il n'y a pas possibilité d'avoir une liste idéale 2 à 2, à cause de la mine qui a été placée juste avant.
Donc je me demande, est-ce qu'on peut opérer de la même façon que l'algo naïf ?
Parce-que quand on ne trouve pas de solution, il faudrait pouvoir rembobiner...

---

A priori ça rembobine tout seul... !! :D
Comment as tu codé la chose ?

Si je reprends l'algo NDO ça donne ça (où "action" est une fonction qui prend en compte les chemins complets).
Si à la suite d'une mine aucune des mines à placer ne permet l'optimalité 2 à 2, on ne rentre simplement pas dans la récursion (ligne 21) à cause du test (ligne 12) et donc on passe simplement à la suite...

Code:

---

1 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

void Traiter( Chemin chemin, Action<Chemin> action ) { // Plus de mines à ajouter : produire un résultat if ( chemin.MinesNonTraitees.Count == 0 && action != null ) action( chemin ); else { // Pour chaque mine parmi les mines non traitées foreach ( Mine nonTraitee in chemin.MinesNonTraitees ) { // Vérifier l'optimalité 2 à 2 pour la mine à ajouter if ( VerifierOptimales2a2( chemin, nonTraitee ) ) { // Si c'est le cas, créer un nouveau chemin identique au chemin actuel Chemin nouveauChemin = chemin.CreateCopy();   // Lui ajouter la mine nouveauChemin.AjouterMine( nonTraitee );   // Et récursion Traiter( nouveauChemin, action ); } } } }

---

Pour le PS sur le PS : je suis bien d'accord !

Oula... que de posts aujourd'hui !!

Citation:

---

Envoyé par Baruch

Ben non ^^. Rien ne prouve qu'on ait besoin de l'optimalité 2 à 2 pour que l'algorithme fonctionne (et en plus ce serait un peu bizarre je trouve).

---

A mon sens si. Je reformule :
SI l'algo est exact
alors il a besoin de l'optimalité 2 à 2

Preuve : tu as trouvé un contre exemple non optimal 2 à 2.

Par contre, je parle bien de l'algo. Si on devait parler d'une propriété à prouver et qui soit à l'image de l'algo, ça serait quelque chose comme ça :

Etant donné un ensemble E de mines et deux chemins optimaux 2 à 2 C1 et C2.
Si t(C1) <= t(C2) et c(C1) >= c(C2) et p(C1) >= p(C2)
Alors le meilleur chemin issu de C1 est termine avant le meilleur chemin issu de C2.

Citation:

---

Envoyé par Baruch

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.

---

... on parlait d'intuition... Myrne doit en avoir l'intuition car de mon côté je ne vois aucune raison pour que w existe (sauf à dire que w puisse éventuellement être égal à u ou v).
... bref, je ne vois pas du tout en quoi ça serait vrai et après ça ce qu'on pourrait en faire
... mais je rate surement un truc !! :?

Citation:

---

... on parlait d'intuition... Myrne doit en avoir l'intuition car de mon côté je ne vois aucune raison pour que w existe (sauf à dire que w puisse éventuellement être égal à u ou v).
... bref, je ne vois pas du tout en quoi ça serait vrai et après ça ce qu'on pourrait en faire
... mais je rate surement un truc !!

---

Idem... Myrne a l'air de dire que ça nous débarrasserait de la condition de coût, mais je vois pas vraiment...
Surtout qu'au niveau de la démonstration, le gros du boulot n'a pas été fait :/

Citation:

---

A mon sens si. Je reformule :
SI l'algo est exact
alors il a besoin de l'optimalité 2 à 2

Preuve : tu as trouvé un contre exemple non optimal 2 à 2.

Par contre, je parle bien de l'algo. Si on devait parler d'une propriété à prouver et qui soit à l'image de l'algo, ça serait quelque chose comme ça :

Etant donné un ensemble E de mines et deux chemins optimaux 2 à 2 C1 et C2.
Si t(C1) <= t(C2) et c(C1) >= c(C2) et p(C1) >= p(C2)
Alors le meilleur chemin issu de C1 est termine avant le meilleur chemin issu de C2.

---

Hmm je persiste à dire non ^^.

Citation:

---

Au début j'ai voulu montrer la propriété (1) :

Si c1 domine c2, alors le chemin idéal issu de c1 est meilleur que le chemin idéal issu de c2.

J'ai trouvé un contre-exemple. J'ai donc énoncé la propriété (2), qui est plus faible :

Si c1 domine c2, alors le chemin idéal du système n'est pas issu de c2.

---

La propriété que tu as évoqué là, c'est mon (1).

On est d'accord que (1) => (2).

La (1) est fausse si il n'y a pas d'optimalité 2 à 2;
Si il y a optimalité 2 à 2, on ne sait pas.

Mais de toute façon peu importe, ton algorithme ne nécessite que la propriété (2), qui est plus faible.

Et pour cette propriété, on n'a pas de contre-exemple, idéal 2 à 2 ou pas.