Discussion :

[Baruch]

Désolé je parle beaucoup xD

Soit (M1,M2) un couple de mines connexes.
Son p* est égal à (c2-c1)/(c1/p1-c2/p2)

J'ai dit que :
si p<p* , alors le moins rentable est avant
si p>p* , alors le plus rentable est avant

Mais je n'ai pas tenu compte d'une chose : p est toujours > 0.
Donc si p* <= 0 alors la mine la plus rentable sera toujours avant, quel que soit p.

Or p* < 0 équivaut à :

c1 < c2 et p1/c1 > p2/c2
ou
c2 < c1 et p2/c2 > p1/c1

Donc l'ordre de 2 mines connexes est invariant selon p si et seulement si une des mines est moins chère ET est plus rentable que l'autre. Dans le cas contraire, p* > 0, et donc l'ordre des 2 mines dépend de la production initiale p. Dans ce cas, si p < p*, on prend la moins rentable avant (mais elle est moins chère). Et si p > p*, on prend la plus rentable, même si elle est plus chère.

Voilà je pense que j'ai tout expliqué sur ce qui se passait pour ordonner 2 mines connexes.

Quelques remarques :

Si M1 domine M2 <=> c1 < c2 et p1 > p2
ça implique
c1 < c2 et p1/c1 > p2/c2
et donc p* < 0
d'où si M1 et M2 sont connexes, M1 est toujours avant M2.

On a ici qu'une implication, donc si on veut penser à une relation d'ordre partiel, peut-être que la relation (c1 < c2 et p1/c1 > p2/c2) est mieux... A voir !

[Alikendarfen]

Bonjour à tous,

Intéressant problème !

J'ai fait quelques tests... pas super concluant !

En premier lieu avec un algo en n!, pour permettre de valider les autres résultats. En jouant un peu avec les mines de mon jeu d'essai, on peut déjà dire que les résultats sont étonnants... un petit changement de paramètre et hop ! la (ou plutôt les) meilleure(s) solution(s) varient du tout au tout !!

En ajoutant la notion de dominance, on peut gagner pas mal... mais sur un nombre de mines plutôt réduit : 14 mines, ça commence à faire beaucoup (ça a consommé mes 4Go, même si mon algo n'est sûrement pas très bien codé).

Donc une idée : pourquoi ne pas utiliser un algo de type dijkstra ?

Sur le principe :

1/ Depuis un résultat courant [Ri;M] où :
- Ri = un état du problème avec i mines placées et n-i mines restantes
- M = le meilleur résultat jusque là, c'est à dire celui dont la date est le plus tôt

2/ Evaluer les n-i résultats de Ri+1 et ne poursuivre sur ceux-là que s'ils sont meilleurs de M.

3/ Sinon poursuivre sur M, trouver un nouveau M, etc

...

Cela dit, même si ça marche, il n'y aura pas de miracle (on a quand même une combinatoire).

En plus, il faut définir ce qu'est la meilleure solution courante. Par exemple :
a- Celle dont la date est la plus petite
b- Et en cas d'égalité celle dont le gain journalier est le meilleur
c- Et en cas d'égalité encore, celle dont le compte en banque courant est le plus élevé

(ou l'inverse entre b et c, parce qu'au final, à date égale, la meilleure solution est celle qui nous laisse avec le plus d'argent...)

... quant à généraliser (x mines produisant y minerais et nécessitant z ressources pour être construites, comme l'évoquait Baruch) ... on n'y est pas !!


Étonnant qu'il n'y ait pas un peu de littérature sur le sujet ? ... je vais poursuivre en cherchant un peu plus sur internet !

[Baruch]

Salut !

Euh le dijkstra ça fait n! de toute façon non ?

Bon je résume où en est le problème.

- Ya l'idée de trouver une relation d'ordre partielle, c'est-à-dire avoir certaines mines, qui si elles vérifient qq conditions intrinsèques, sont toujours de la même façon ordonnées l'une par rapport à l'autre, ie indépendamment des autres mines, et de p.

- Il y a aussi l'idée de l'idéalité 2 à 2, qui permet d'obtenir au moins une solution meilleure.


Pour la relation d'ordre partielle, j'ai passé plein de temps ce we dessus. J'ai essayé de trouver les conditions équivalentes à l'existence de ce type de relation. J'ai pas encore fini, c'est assez compliqué. Mais néanmoins, je trouve que si M1 domine M2 (càd est toujours avant M2, qq soient les conditions), alors nécessairement p1>p2 et c1<c2. Mais je n'ai encore pu prouver l'équivalence, peut-être qu'il y a d'autres conditions à prendre en compte.

Mais la question est : imaginons qu'on ait une relation d'ordre partielle, vérifiée pour certains couples de mines. Comment faire en sorte d'utiliser cette information afin de simplifier l'algorithme de base ?

Pour l'idéalité 2 à 2, il faudrait réfléchir à quel algorithme utiliser pour minimiser le nombre de permutations (par exemple faire en premier les permutations les plus rentables ?)

[Alikendarfen]

Bonjour,

Dijkstra, selon wikipedia :

Si le graphe possède m arcs et n nœuds, en supposant que les comparaisons des poids d'arcs soient à temps constant, et que le tas soit binomial, alors la complexité de l'algorithme est en [(m+n) * ln(n)]

Dans notre cas, le nombre d'arcs est m = n * (n - 1). Donc on serait en n²ln(n)... ?

Mais attention : il faudrait adapter l'algo, car on ne peut pas l'appliquer tel quel (repasser sur une même mine par deux chemins ne permet pas toujours de conclure).
L'idée est la suivante : sur la base d'un parcourt exhaustif (en n!) ne faire avancer l'exploration que sur les chemins les meilleurs (règle à définir).

De la mine A, j'explore la construction de B et de C. Si AB est meilleur que AC, alors j'explore AB tant que AB[X] est meilleur que AC.


Dans ce cadre, également, toute relation intrinsèque peut être exploitée : si A est intrinsèquement devant B, alors l'exploration vers B n'entre en jeu que si A est déjà exploré sur ce chemin.

Il y a peut être d'autres règles. Par exemple, si on a deux chemins :
- Ch1 = A[X]B
- Ch2 = A[Y]B
A quelles conditions peut on affirmer que l'un est définitivement meilleur que l'autre ?
Ch1 meilleur que Ch2 si
- longueur(Ch1) > longueur(Ch2)
- et production(Ch1) > production(Ch2)
- et date(Ch1) > date(Ch2)
?


Donc, ça me semble compatible avec ta démarche (si j'ai bien compris ??), même si au final ça n'est pas la bonne solution.


Une remarque sinon : le problème semble être à temps discret (c'est chaque jour qu'on engrange les productions).
Donc les calculs de type c/p ne sont pas exacts (d'où les calculs de modulo dans le code de Vakhyw).
A l'issue de l'achat d'une mine on a donc une production accrue mais aussi un compte en banque éventuellement non vide !

[Alikendarfen]

Je viens de penser à un truc (et après ça, promis, je me remets au taf ) :

Si (à chaque étape), on prend les mines deux par deux (= n * (n-1) calculs si n mines restantes à ce stade).

Mais par contre on doit pouvoir (toujours ?) soit éliminer [AB] ou [BA], soit considérer qu'ils sont équivalents ?

et ça diviserait de 2^(n-1) l'exploration ?

[Baruch]

Mais par contre on doit pouvoir (toujours ?) soit éliminer [AB] ou [BA], soit considérer qu'ils sont équivalents ?

Euh je comprends pas trop ce dont tu parles, mais je rappelle ceci :

- On n'a pas de relation d'ordre totale sur une liste de mines, càd que à la connaissance seule des caractéristiques de M1 et de M2, on ne peut pas a priori déterminer laquelle sera toujours avant, quelles que soient les conditions.

- On a une relation d'ordre entre certaines mines si celles-ci vérifient certaines conditions (démo pas encore finie)

- Pour les mines connexes :

si on prend la liste (M1,...,Mn1,Ma,Mb,M'1,...,M'n2)
alors l'ordre entre Ma et Mb ne dépend que de la production juste avant, ie somme de Pi pour i allant de 1 à n1
Ce qui veut dire que dans certaines conditions Ma est avant Mb, et dans d'autres c'est le contraire

- Néanmoins, sous certaines conditions, 2 mines connexes peuvent être toujours ordonnées de la même façon

Voilà ce sont les propriétés qu'on a.



Pour le dijkstra, j'ai compris le principe, mais je comprends pas trop l'algo que tu proposes.

Pour la "valeur" des chemins :

C'est pas facile, puisque la seule chose qu'on puisse évaluer et comparer, c'est le temps résultant pour le chemin final, càd composé de toutes les mines.

Car le problème, c'est que si L=L1@L2
et que L1 et L2 sont idéales (ordonnées de la meilleure façon),
alors L n'est pas nécessairement idéale

Euh non non ce n'est pas à temps discret attention, je sais plus qui avait cru ça au départ

[Alikendarfen]

Je crois qu'on ne se comprend pas.. ?

- Pour l'histoire de [AB] et [BA] :

On est dans un état E du problème.
Cet état E est une hypothèse constituée de k mines (ordonnées) sur les n possibles.

Depuis E, on évalue l'hypothèse de poursuivre en achetant soit les mines A puis B, soit les mines B puis A.

On a donc deux nouvelles hypothèses :
E1 = E + [AB]
E2 = E + [BA]

A l'issue, E1 et E2 ont la même production totale. Par contre, les dates auxquelles on arrive ne sont pas nécessairement les mêmes.

Si date(E1) < date(E2) alors nécessairement (du moins je le pense) E1 est meilleur que E2 et il n'est plus utile de poursuivre sur l'hypothèse E2.
Si date(E1) = date(E2) les deux hypothèses sont quantitativement équivalentes.

On a donc réduit l'espace à explorer dans les deux cas.


- Concernant l'algo Dijkstra-like :

Il faut considérer que c'est une heuristique sur la base d'un algo qui explore toutes les solutions possibles. Dans ce cadre, on cherche simplement à ne pas faire du travail pour rien.

Dans cet algo, on a un ensemble d'hypothèses Ei en cours de construction.
Parmi ces Ei, si Ej est actuellement plus mauvais (par exemple date >) qu'un autre élément de Ei, alors on n'explore pas les hypothèses découlant de Ej pour le moment.

Prenons l'exemple que tu citais au tout début :

On prend M_1 avec c_1=1 ; p_1=1
et M_2 avec c_2=10 ; p_2=infini
p = 1

alors
E1 = [M_1] => date1 = 1
E2 = [M_2] => date2 = 10

date1 < date2, donc on poursuit :
E1 = [M_1 M_2] => date1 = 6
E2 = [M_2] => date2 = 10

donc pas la peine d'aller calculer E2 = [M_2 M_1] qui est nécessairement plus mauvais que E1.

PS : pour l'histoire du temps discret... c'est au choix selon l'énoncé, ok. Par contre, ça complique car on n'a plus de lien entre les dates auxquelles on gagne de la production... mais bon, mettons que cela soit un détail pour le moment.

PS2 : j'ai aussi un doute sur un truc du coup. Le p initial, on le gagne toujours par la suite, même si on a acquis des mines ?

[Baruch]

Euh je sais pas si on se comprend, mais essayons quand même xD

- Pour l'histoire de [AB] et [BA] :

Depuis E, on évalue l'hypothèse de poursuivre en achetant soit les mines A puis B, soit les mines B puis A.

Pourquoi ne considérer que ces 2 hypothèses ?
A et B sont pris dans les n-k mines restantes, donc on a (n-k)(n-k-1) hypothèses

A l'issue, E1 et E2 ont la même production totale. Par contre, les dates auxquelles on arrive ne sont pas nécessairement les mêmes.

Ouép je suis d'accord

Si date(E1) < date(E2) alors nécessairement (du moins je le pense) E1 est meilleur que E2 et il n'est plus utile de poursuivre sur l'hypothèse E2.

Ouép je suis aussi d'accord, puisqu'au final, E+[A,B]+F est meilleur que E+[B,A]+F, et ce quels que soient E et F.



Bon si on bien d'accord, tu essayes avec cet algorithme de réduire le nombre de possibilités à étudier.

Mais tu peux faire mieux à mon avis (en fait je crois que ton algo est faux, cf + bas)

- Pour tout couple (A,B) de mines connexes, on sait en fonction de p (la production juste avant l'occurrence de ce couple), l'ordre idéal du couple.

Donc par exemple pour savoir si E+[AB] est mieux que E+[BA], il suffit de connaître la production résultante à l'issue de E. Ca c'est juste un détail qui permet de simplifier les calculs.

- Si E est idéale (càd l'ordre des mines permet un temps minimal), alors E est idéale 2 à 2. Ca veut dire que si on extrait une liste de 2 mines connexes à partir de E, cette liste est nécessairement bien ordonnée. Donc, toujours dans l'idée de réduire le nombre de possibilités à étudier, on peut ne construire que des listes idéales 2 à 2, puis comparer leur temps.

Ton algorithme rajoute les mines 2 par 2, ce qui me paraît étrange (ou alors je n'ai pas compris). Il étudie des listes qui ne sont pas idéales 2 à 2, et je crois même qu'il oublie d'étudier certaines listes idéales 2 à 2.

Un algorithme qui se restreint à moins de possibilités serait donc celui-ci :

On a E une liste idéale 2 à 2, avec E=E'+[A]
Soit n le nombre de mines restantes.
On connaît la production résultante à la fin de E', on connaît les caractéristiques de A et des n mines restantes, donc on peut connaître l'ensemble des mines qui peuvent être juste après A.
Si cet ensemble est vide et n<>0, E est une hypothèse fausse.
Sinon, il faut itérer pour toutes les hypothèses E+[M], où M est une mine qui convient.
(et si n=0, on retient E)


Cet algorithme permet (si je me trompe pas), de construire toutes les listes idéales 2 à 2. Ensuite il suffit de prendre le candidat dont le temps est minimal.




- Concernant l'algo Dijkstra-like :

La technique de réduction des possibilités étudiées que tu exposes est celle de l'idéalité 2 à 2 juste au-dessus, n'est-ce pas ?



Enfin j'espère que tu m'as compris.

L'algo qui permet d'obtenir toutes les listes idéales 2 à 2 permet d'enlever pas mal de possibilité à mon avis.

Regardons un peu les résultats de cet algo :

On a 3 mines notées 1,2,3 , qu'on souhaite ordonner.
On a une production initiale p.

- 1ère itération :

On a 3 hypothèses : 1 ; 2 ;3

- 2e itération :

On connaît p, donc on a 3 relations d'ordre entre 1,2,3.
Donc on a 3 hypothèses, comme par exemple : 12 ; 13 ; 23

- 3e itération :

Les hypothèses possibles sont : 123 ; 132 ; 231
Mais on ne peut pas considérer en même temps 123 et 132, puisque pour la production p+p1, on connaît l'ordre de (2,3). Pour 231, cette hypothèse peut ne pas exister, ça dépend de l'ordre de (1,3) pour la production p+p2
Donc à la fin il reste au maximum 2 candidats.


Il suffit donc ensuite de comparer les temps des candidats pour savoir quelle est la liste idéale.

On a donc quand même pas mal réduit le nombre de possibilités, puisqu'à l'issue de l'algorithme, on a sélectionné 2 candidats potentiels, alors qu'il y en avait 3!=6 au départ.

J'ai fait ce même raisonnement pour 4 mines, on trouve 5 candidats au maximum à la fin.


Pour tes PS :

- Oui oui, si on prend un temps discret, ça complique, donc évitons.
- Oui on garde le p initial, les productions des mines viennent s'ajouter à celle-ci

[Alikendarfen]

en fait, je crois qu'on se comprend... presque !

Là où je n'ai pas été clair c'est que le Dijkstra-like et le [AB][BA] sont deux trucs indépendants.

Pour le Dijkstra, juste deux mots : il n'élimine aucune hypothèse (donc on ne perd pas de solutions optimales), simplement il réduit l'arbre de recherche dans la pratique (cf. l'exemple de mon post d'avant).
Je l'ai testé : en moyenne (sur un exemple qui vaut ce qu'il vaut) on étudie 3 à 4 fois moins de possibilités.
Mais c'est clair qu'un "vrai Dijkstra" pour lequel chaque ville est reliée à toutes les autres et pour lequel tous les arcs ont la même valeur sera complètement inefficace...

=> pour conclure, le Dijkstra-like peut éventuellement être un complément mais c'est pas lui qui fera gagner la course !! Donc je suis d'accord avec toi



Pour l'histoire du [AB][BA], c'est beaucoup plus proche de ta recherche d'idéalité tel que je le vois. Mais je crois que j'avais un coup de retard dans la compréhension du truc.

Je vais tenter de reformuler ce que tu indiques pour qu'on soit en phase...

- Si E1(P0) est idéale et E2(P0) est idéale alors E1(P0) + E2(p(E1)) n'est pas nécessairement idéale

- Si E(P0) = E1(P0) + E2(p(E1)) est idéale E1(P0) et E2(p(E1)) sont idéales

- Quel que soit E(P0) non nécessairement idéale et deux mines A et B, si E + [A B] est meilleur que E + [B A], alors E + [B A] ne peut pas être idéale.


Au-delà, pour l'algo que tu indiques, je ne suis pas sûr de comprendre : quand tu élimines soit 123 soit 132, c'est juste que tu as testé les deux pour les comparer... donc on ne gagne rien et on reste en fait sur 3 possibilités... ? non ?

... mais 3 sur 3 possibles, ça trouble un peu

* Prenons quatre mines A B C D

On prend tous les couples (AB), (AC), (AD), (BC), (BD), (CD)

Pour chaque couple, on considère les chemins possible. Par exemple pour (AB), [AB] et [BA]. Et on déduit lequel est le meilleur. Par exemple [AB].

Donc de ces 6 couples (et 12 chemins de longueur 2 possibles), on garde 6 chemins. Par exemple [AB], [AC], [AD], [BC], [BD], [CD].

De là, on peut compléter chacun : [AB] par C ou D => [ABC] ou [ABD].

Donc au total, on retrouve 12 chemins de longueur 3.

Mais ces 12 chemins correspondent à 4 groupes :
- le groupe "ABC", constitué de [ABC], [ACB], [BCA]
- le groupe "ABD", constitué de [ABD], [ADB], [BDA]
- etc

En évaluant chaque chemin de chaque groupe, on est donc à même de garder un seul chemin par groupe.

On se retrouve donc avec 4 possibilités et non plus 12.

* Avec cinq mines

On a 10 couples, donc 10 chemins candidats de longueur 2

De là on obtient 30 chemins de longueur 3, répartis en 10 groupes.

Donc, il reste 10 possibilités pour les chemins de longueur 3

En longueur 4, 20 chemins, 5 groupes, restent donc 5 candidats...

Si je ne me trompe pas, on a (quand même) 75 évaluations à faire comparées aux 120 d'origine.

[Alikendarfen]

... par contre, si je ne me trompe pas non plus, ça fait 186 évaluations pour 6 mines (vs. 720 combinaisons totales).

... ça semble pas mal finalement : demain, j'essaye de trouver du temps pour tester un algo et généraliser la formule...

[Baruch]

Bon là j'ai pris la peine de regarder ce qu'est le Dijkstra la page wiki ^^

Pour le Dijkstra, juste deux mots : il n'élimine aucune hypothèse (donc on ne perd pas de solutions optimales), simplement il réduit l'arbre de recherche dans la pratique (cf. l'exemple de mon post d'avant).

Ouép je suis d'accord avec ça. Aussi avec le fait que c'est indépendant de ce qu'il y a en-dessous.

- Si E1(P0) est idéale et E2(P0) est idéale alors E1(P0) + E2(p(E1)) n'est pas nécessairement idéale

- Si E(P0) = E1(P0) + E2(p(E1)) est idéale E1(P0) et E2(p(E1)) sont idéales

- Quel que soit E(P0) non nécessairement idéale et deux mines A et B, si E + [A B] est meilleur que E + [B A], alors E + [B A] ne peut pas être idéale.

Ouép je suis d'accord


Bon j'ai compris où on en est, en fait on part sur 2 algos un peu différents.


Ton algo est bien, je résume pour voir si on est ok :

n=1 -> A ; B ;C ; D
n=2 -> AB ; AC ; AD ; BC ; BD ; CD
n=3 -> ABC ; ABD ; ACD ; BCD
n=4 -> ABCD

Cet algorithme permet de trouver la solution idéale.

A chaque itération : on crée toutes les possibilités, et pour les listes contenant le même ensemble de mines, on ne garde que le minimum.

J'ai un peu de mal là à trouver le nombre d'évaluations de chemins à effectuer pour n mines.

Néanmoins, je ne vois pas trop comment implémenter cet algorithme, puisqu'il faut pouvoir regrouper entre elles les listes contenant le même ensemble de mines. Enfin peut-être que ça se fait.

Edit : je viens de me rendre compte que si 2 listes ont le même ensemble de mines, alors la somme des productions est égale. Mais la réciproque n'est pas toujours vraie...


Mon algorithme est un peu différent :

n=1 -> A ; B ; C ; D
n=2 -> AB ; AC ; AD ; BC ; BD ; CD
n=3 -> ABC ; ABD ; ACD ; BCA ; BCD ; BDA ; CDA ; CDB
n=4 -> ABCD ; ACDB ; BCAD ; BDAC ; CDAB

Cet algorithme ne donne pas la solution idéale, mais donne toutes les solutions idéales 2 à 2.
La comparaison de tous ces candidats permet donc de trouver la solution idéale.

A chaque itération : on ajoute toutes les mines possibles à la fin de chaque chemin, de manière à ce que les 2 dernières mines soient bien ordonnées.

Par exemple,

AB donne ABC et ABD
AC donne ACB (à écarter puisque ABC est valide) et ACD
AD donne ADB (à écarter puisque ABD est valide) et ADC (à écarter puisque ACD est valide)

Puis on passe du groupe "A" au groupe "B", donc toutes les relations d'ordre peuvent changer

BC donne BCA et BCD
BD donne BDA et BDC (invalide)

CD donne CDA et CDB

L'avantage de cet algorithme, à mon avis, est qu'il me paraît facilement implémentable (ton algorithme l'est peut-être, mais là je ne vois pas trop).

Si on veut estimer la complexité, il faudrait prendre en compte le nombre de comparaisons faites à chaque fois (pour savoir quelles mines on peut rajouter au bout), mais aussi le nombre de candidats obtenus à la fin. Je ne pense pas que ce soit trop mauvais, en tout cas c'est toujours mieux que rien ^^.

De plus, cet algorithme peut être encore amélioré :

J'ai considéré ici que quand on change de groupe, càd les mines avant la dernière de la liste, alors les relations d'ordre sont totalement bouleversées.

Or, ce n'est pas vraiment le cas : j'ai montré que l'ordre entre 2 mines connexes est déterminé par une comparaison entre p, la production considérée avant l'occurrence des 2 mines, et p*, une valeur intrinsèque à l'ensemble des 2 mines considérées.

si p<p*, alors la moins rentable est avant
si p>p* alors la plus rentable est avant

Donc calculons le p* de tous les ensembles de 2 mines possibles (il y en a environ n²/2), et ordonnons ces p* de manière croissante. Si on regarde l'ordre des doubletons de mines impliqué par une production p, puis par une production p', alors les seuls doubletons dont l'ordre a changé sont les doubletons dont le p* est compris entre p et p'. Je pense qu'on peut utiliser ça.

Il y a aussi le fait que certains doubletons ont leur p* négatif, ce qui fait que leur ordre ne varie jamais, il n'y a donc pas de calcul à faire.

[Baruch]

Du coup un algorithme qui marche ça serait :

E et L sont des listes de couples de réels \\ E est le chemin que l'on est entrain de suivre, L est la liste des mines restantes
explore(E,L) est une liste de listes de couples de réels \\ c'est l'ensemble des chemins valides à partir de E

explore(E,L) :=
si taille(L)=0, alors [E];
F:=[]; \\ F sera le résultat de l'exploration
si E=[] alors
pour chaque mine Mi de L
F:=explore([Mi],L/Mi);
fin
sinon
M est le dernier élément de E;
p est la production résultante avant M;
pour chaque mine Mi de L
si (p<p*i)=(Mi plus rentable que M), alors F:=F@explore(E@[Mi],L/Mi);
fin;
fin;
F;
trouve_min(explore([],L)); \\ L étant la liste de toutes les mines, et trouve_min donne la liste qui prend le moins de temps


Voilà je pense que cet algorithme fonctionne, après on peut faire quelques optimisations mineures mais je crois que l'essentiel y est.

Après je crois qu'on peut rajouter un Dijkstra par dessus non ?

[Alikendarfen]

Pour info, l'algo que je propose est en 2^n car il est proportionnel à la somme des combinaison(n;i).

Concernant le tien, je n'ai pas encore tout compris...

explore(E,L) :=
si taille(L)=0, alors [E];

OK : si on a tout exploré, c'est E

F:=[]; \\ F sera le résultat de l'exploration
si E=[] alors
pour chaque mine Mi de L
F:=explore([Mi],L/Mi);
fin

OK : on initialise la première fois

sinon
M est le dernier élément de E;
p est la production résultante avant M;

OK : c'est les paramètres avant itération

pour chaque mine Mi de L
si (p<p*i)=(Mi plus rentable que M), alors F:=F@explore(E@[Mi],L/Mi);
fin;
fin;
F;

Là, par contre, je ne vois pas entièrement :

si (p<p*i) : Mi est plus rentable que M par rapport à p d'accord

Mais alors il faut F := F @ explore( (E/M)@Mi@M, L/Mi ) ??
Et sinon, F := F @ explore( E @ Mi, L/Mi )

Ce qui revient à dire, partant de E = E' @ M, regarder ce qui est meilleur entre E' @ Mi @ M et E' @ M @ Mi.

Si c'est bien ça, on est (je crois) sur une complexité en (n! / 2^n), puisqu'on élimine une possibilité sur 2 lors de chaque itération ??

[Alikendarfen]

Bon... tout ça tourne un peu en rond parce qu'on affronte toujours une combinatoire (plus ou moins importante, mais qui ne permet pas d'espérer de traiter plus de 15 mines en un temps raisonnable).

Donc testons une autre piste. L'idée est la suivante : plus on gagne tôt une production élevée, plus on termine vite !!

Alors mettons qu'on calcule une accélération procurée par chaque mine :

Partant de P
Avec n mines Mi restantes

Pour chaque mine Mi :

- Ti = Ci / P,
la date à laquelle on peut acheter la mine

- P' = P + Pi,
la nouvelle production à l'issue de l'achat

- C|i,
la somme des couts de toutes les autres mines, donc hors Mi (C| = C barre)

- T|i = Ti + C|i / P'
la date à laquelle on peut acheter toutes les autres mines avec P'

- Ai = C(toutes les mines) / T|i
l'accélération "globale" apportée par l'achat de Mi

A l'issue de l'évaluation de toutes ces mines, on garde celle qui "accélère" le plus comme étant la première à cette étape et on recommence avec les mines restantes.

Là, au moins, l'algo est en n² !

Maintenant, est-ce une simple heuristique qui marche plus ou moins, ou bien peut on prouver une loi générale ??

... j'essaye de m'y remettre en fin de journée
a+

[Baruch]

Pour ton algo, il est en 2^n si le fait de comparer entre eux les chemins du même groupe est rapide. Et ça me semble pas si évident. Car en fait il faut construire une fonction qui indique si 2 listes contiennent les mêmes éléments, et c'est assez lourd je pense.



Euh oui dsl pour mon algo, j'avais effectivement fait une faute (il était tard aussi xD). Ouép on est d'accord sur ce que fait cet algo :

si p<p*i et Mi plus rentable, alors on explore E@[M,Mi]
ou si p>p*i et Mi moins rentable que M, on explore E@[Mi,M]

C'est que tu as compris je crois.

Pour la complexité, ça doit être un truc dans ce style (n!/2^n) je pense.



Pour ton idée :

J'ai un peu de mal à cerner pourquoi tu fais ça. En tout cas quand tu dis :

plus on gagne tôt une production élevée, plus on termine vite !!

Pour moi c'est juste un calcul d'accélération de mine, où Ai = Pi/Ti = Pi/(Ci*p) = p*Pi/Ci
Et donc il faut juste comparer les différents Pi/Ci. Mais on a un contre exemple avec

On prend M_1 avec c_1=1 ; p_1=1
et M_2 avec c_2=10 ; p_2=infini
p = 1

Mais apparemment, c'est pas ce que tu fais comme calcul, toi tu raisonnes sur toute la liste.

- Ai = C(toutes les mines) / T|i
l'accélération "globale" apportée par l'achat de Mi

Ben ça c'est pas une accélération... Enfin pour moi une accélération c'est une production sur un temps non ?

Enfin bon je comprends pas trop, et puis j'avoue que quand tu me parles d'accélération, je suis sceptique.



Par contre, une piste que je n'ai pas évoquée avec toi (je crois), c'est la relation de dominance.

M1 domine M2 <=> quelles que soient les conditions, permuter M1 et M2 de manière à placer M1 avant donne une meilleur liste.

Peut être qu'on peut exploiter ça, si une telle relation (d'ordre partiel en fait) existe. Parce-que je pense qu'avec les utilisations qu'on pourrait faire de ce problème et les données qui sont entrées, on peut obtenir pas mal de relations d'ordre, et donc diviser la complexité. Par contre on gardera toujours des ensembles de mines qui ne se dominent pas entre elles.

J'avais commencé la démonstration pour expliciter M1 domine M2, càd les relations que vérifient M1 et M2 entre elles, pour que M1 domine M2. Je suis bloqué dans la démo, mais j'ai déjà montré que si M1 domine M2, alors nécessairement p1>p2 et c1<c2. Le début de la démo est ici.

[Alikendarfen]

Effectivement, ce que je proposais ci-dessus (l'histoire de l'accélération) n'est pas la bonne règle (et effectivement ça n'est pas une accélération en fait).

Par contre, je crois tenir une autre règle (qui me semble très complémentaire de la notion de dominance précédemment évoquée).

La voici :

On calcule pour chaque Mi

- Sa date possible d'acquisition Ti=Ci/P

- La production à l'issue de l'acquisition P'i=P+Pi


La question est alors :

Considérant 2 mines Mi et Mj, telles que Ti < Tj

Si ayant acquis Mi, il est possible à Tj d'acheter une (ou plusieurs) autre mine (éventuellement Mj) qui fasse qu'à Tj la production est supérieure à P'j,

Alors Mi doit être avant Mj (à cette étape)

Si ça n'est pas le cas, Mj doit être avant Mi


Là où c'est un peu compliqué, c'est qu'à Tj, il peut être possible et nécessaire d'acheter plusieurs mines pour dépasser Mj... (ça ressemble à du backpack...)

Je réfléchis encore et je regarde aussi la démo que tu indiques.


Pour ce qui est de l'autre algo en 2^n. Je le pense implémentable, l'idée est la suivante :
- Pour chaque chemin en cours d'évaluation on garde à la fois l'ordre d'achat des mines du chemin et une liste L des mêmes mines dans un ordre fixe (par exemple, selon leur nom unique)
- Ainsi deux chemins ayant les mêmes mines ont la même liste L
- Pour associer deux chemins qui ont la même liste L, il faut traduire L en une clé et mettre ensuite les chemins dans une table de hash en fonction de la clé
- Pour créer L efficacement, on peut utiliser un vecteur de bits de taille n

... dans tous les cas, j'aimerais bien qu'on trouve une solution pour traiter 100 mines (au moins) et jusque là, on n'y est pas !!

[Alikendarfen]

Dans la démo que tu indiques :

J'avais commencé la démonstration pour expliciter M1 domine M2, càd les relations que vérifient M1 et M2 entre elles, pour que M1 domine M2. Je suis bloqué dans la démo, mais j'ai déjà montré que si M1 domine M2, alors nécessairement p1>p2 et c1<c2. Le début de la démo est ici.

je n'ai pas compris le (3) :

Si on fixe toutes les variables sauf ci, et qu’on fait tendre ci vers +infini, alors nécessairement pour que l’inégalité soit
respectée, on a : ...

Si tu avais un peu de temps pour expliquer...

[Alikendarfen]

Bon, essayons de prendre un peu de recul (enfin... essayons).

Trouver une dominance absolue peut être efficace, mais, l'efficacité réelle va dépendre des données concrètes à traiter (si ces données ne dégagent pas de dominance absolue, pas de gain).

Trouver une dominance contextuelle (selon le p actuel) peut être au moins aussi efficace, car cela comprend aussi les dominances absolues. Par contre, cela nécessite un calcul à chaque par itération. Donc tout dépend de la simplicité (rapidité) de ce calcul.

A part ça, on a définit ensemble deux algo :
1- Celui basé sur les comparaisons E + [AB] versus E + [BA], qui divise par 2^n la combinatoire en n!.
2- Celui basé sur les comparaisons de chemins regroupant les mêmes mines qui est en 2^n plutôt que n!.

Pourquoi ne pas combiner les deux algos ?

On aurait :
- Considération des mines par couple (AB) et détermination du meilleur chemin entre [AB] et [BA] (base algo 1)
- On saurait alors que [AB] > [BA], [AC] > [CA], ... (où '>' signifie meilleur)
- Regroupement des chemins hypothèses E = E' + [AB] par l'algo 2 (c'est à dire, par exemple à l'itération 2, qu'on met ensemble et compare à l'itération 2 [CD] + [AB] et [AB] + [CD] afin de n'avoir à l'issue qu'un quadruplet candidat)

En termes de gain, ça donne quoi ?
Grosso modo, 2^(n / 2) ????

Je me trompe peut être (fin de journée)...


Si, malgré mes remarques du début de ce post, on sait combiner ça avec les notions de dominance, peut être, on avance ??

Tu en penses quoi ?

[Baruch]

Pour ton algo en 2^n :

Effectivement, ça peut s'implémenter bien.

- Pour associer deux chemins qui ont la même liste L, il faut traduire L en une clé et mettre ensuite les chemins dans une table de hash en fonction de la clé

Alors là je comprends pas grand chose.

Sinon j'ai trouvé comment implémenter ton algorithme :

n est le nombre de mines à trier
Les mines sont toutes indicées par un entier entre 1 et n
Un chemin est une liste d'indices (avec jamais 2 fois le même)
Un ensemble est une liste d'indices triée
A chaque chemin correspond un seul ensemble
L est la liste des ensembles existant qu'il reste à ordonner
C est la liste des chemins, c'est une liste de couples de chemins et d'indices, où l'indice est le n° de l'élément de L correspondant au chemin

Par exemple, si on a C = [([1],3),([2],1),([3],2)], alors L = [[1,3],[1,2],[2,3]].

A chaque itération,

Pour chaque couple (E,i) appartenant à C
On trouve le i-ième élément F de L
Pour chaque j-ième élément de F
On considère F\j privé de cet élément \\ F\j n'a pas à être ordonné puisqu'il l'est déjà
Si F\j n'appartient pas déjà à L'
On le rajoute à la fin de L', à l'emplacement k
On rajoute un élément à C, cet élément étant le couple (E+[F.(j)],k)
Sinon si F\j appartient déjà à L', et qu'il est à l'emplacement k
On compare le temps du chemin de C' correspondant au k-ième élément de L', avec le temps du chemin E+[F.(j)]
On ne garde que le minimum, donc le chemin de C' considéré n'est pas modifié, ou alors il est remplacé par le chemin E+[F.(j)]
Fin Si
Fin pour chaque
Fin pour chaque

Je pense que cet algorithme marche. A la fin de chaque itération, on a bien C' et L' de même taille.
On peut écourter le calcul des temps de chemins en ayant des 3-uplets dans C, en se trimbalant le temps résultant du chemin.

Je prends un exemple pour te convaincre et me convaincre aussi ^^ :

On prend n=5
On initialise à C=[([1],1),([2],2),([3],3),([4],4),([5],5)] et L=[[2,3,4,5],[1,3,4,5],...]

On commence une itération, donc on a C'=L'=[]

On prend d'abord E=[1] et i=1
On a alors F=L.(i)=[2,3,4,5]

On commence par j=1
On a alors F\j = [3,4,5]
F\j n'appartient pas à L', donc on fait L':=L'@[[3,4,5]], d'où k=1 puisque L' était vide
On fait ensuite C':=C'@[([1,2],1)]

On prend ensuite j=2
F\j = [2,4,5]
Donc même chose pour j=1,2,3,4

On a donc après j=4 :
L' = [[3,4,5],[2,4,5],[2,3,5],[2,3,4]]
C' = [([1,2],1),([1,3],2),([1,4],3),([1,5],4)]

On passe ensuite à l'élément suivant de C, donc E=[2] et i=2
On a alors F=[1,3,4,5]

On commence par j=1
On a alors F\j = [3,4,5]
F\j appartient déjà à L', il est à l'emplacement 1 de L', donc l'élément correspondant dans C' est ([1,2],1)
On compare donc [1,2] avec E@[F.(j)] = [2,1]
Si [1,2] est mieux, on ne change rien et on passe au j suivant
Si [2,1] est mieux, on change l'élément de C', ([1,2],1), en ([2,1],1), et c'est tout, on passe au j suivant

Et on fait de même pour tous les j, pour tous les i.

Puis on fait C:=C' et L:=L' et puis on réitère. On compte les itérations et on s'arrête à la bonne (environ la n_ième ^^)


Voilà j'espère que j'ai pas fait de faute, dis-moi si tu comprends pas.


Euh j'ai pas beaucoup de temps là pour étudier ton idée de relation de dominance, mais j'avoue que j'y crois pas trop (mais laisse moi le temps de chercher un contre-exemple ^^)

Si tu avais un peu de temps pour expliquer...

Oui donc en fait t'as ton inégalité de départ. Tu prends i entre 1 et n (n'importe lequel, ça revient au même). Tu fixes toutes tes variables, et tu considères que seul Ci peut bouger. Alors de chaque côté de l'inégalité tu as une fonction affine. Donc en fait ton inégalité peut se noter a*Ci + b < a'*Ci + b'. Donc tu as 2 fonctions affines, telles que l'une est toujours supérieure à l'autre. Et donc (si tu fais un graphe tu verras), il faut nécessairement que a<a', sinon à partir d'une certaine valeur de Ci, l'inégalité est renversée. Et a<a' équivaut à (3). (C'est vrai que l'explication que je donne est plus ou moins bof bof ^^)

Donc après ça on montre la réciproque, et donc on a réussi à trouver une équivalence qui ne dépend pas des Ci (ce qui est déjà pas mal). Après j'essaye de supprimer les Pi, mais là c'est beaucoup plus corsé ^^ (analyse de fonction et calcul formel à fond)

Trouver une dominance absolue peut être efficace, mais, l'efficacité réelle va dépendre des données concrètes à traiter (si ces données ne dégagent pas de dominance absolue, pas de gain).

Tout à fait d'accord, mais je pense qu'on a bien souvent des relations de ce type, donc c'est toujours utile de faire le test avant (on peut déterminer toutes les relations de ce type en un temps très correct si on est malin).

Trouver une dominance contextuelle (selon le p actuel) peut être au moins aussi efficace, car cela comprend aussi les dominances absolues.

Ouép, ça aussi ça peut toujours servir.

A part ça, on a définit ensemble deux algo :
1- Celui basé sur les comparaisons E + [AB] versus E + [BA], qui divise par 2^n la combinatoire en n!.
2- Celui basé sur les comparaisons de chemins regroupant les mêmes mines qui est en 2^n plutôt que n!.

Ouép, mais moi le 1. je lui donne le nom pompeux d'algorithme de recherche des solutions idéales 2 à 2 (ben oui, c'est moi qui l'ai créé quand même ^^)

On aurait :
- Considération des mines par couple (AB) et détermination du meilleur chemin entre [AB] et [BA] (base algo 1)
- On saurait alors que [AB] > [BA], [AC] > [CA], ... (où '>' signifie meilleur)
- Regroupement des chemins hypothèses E = E' + [AB] par l'algo 2 (c'est à dire, par exemple à l'itération 2, qu'on met ensemble et compare à l'itération 2 [CD] + [AB] et [AB] + [CD] afin de n'avoir à l'issue qu'un quadruplet candidat)

Hmmm alors là ça se corse... J'arrive pas à trop à raisonner, c'est pas très clair. Au cas où le code que j'ai proposé pour ton algo est bon selon toi, tu peux dire quelles parties tu modifies ?


Ouép en fait je pense qu'il faut partir de ton algorithme, et voir en quoi on peut l'améliorer (idéalité 2à2, dominance, dominance dépendant de p, drikjstra (et zut comment ça s'écrit ? xD),...).

[Alikendarfen]

Pour "mon algo", je propose qu'on l'appelle "algo par combinaisons" si ça te va ?

Je vais relire attentivement tout ton post (pour le moment, j'ai fait une lecture rapide).

Mais pour l'algo par combinaison, il existe des outils simples et performants pour mettre ensemble des chemins qui ont les mêmes mines (ça peut nous simplifier la vie).

Voilà le principe :

- Effectivement, on attribut à chacune des n mines un indice de 1 à n (ou zéro à n-1, peu importe). On obtient l'indice de Mi par indice(Mi).

- Un chemin E de longueur k est à un moment donné représenté par :

- C ses k mines dans l'ordre (ce que tu appelles aussi C)
- V un vecteur de bits de taille n (même rôle que ce que tu appelles L)

(un vecteur de bit, c'est simplement un vecteur de valeurs 0/1)

- Au départ, V est composé de 0. On parcourt les Mi de C et on affecte V[indice(Mi)] = 1

- V représente donc une valeur N (équivalent à un entier < 2^n)

- On utilise ensuite une table de hashage H : c'est un outil qui permet de stocker et récupérer des éléments en vis à vis d'une clé en o(1)

- De là, à une étape x du calcul, on dispose de m chemins Ei, donc de m Vi, donc de m Ni

- On boucle donc sur les Ei et on affecte chaque Ei dans une liste dans H en vis à vis de son Ni
- A l'issue on a donc dans H k clés avec en vis à vis de chacune les Ei partageant les mêmes éléments.

> ça peut paraitre compliqué (?), mais ce sont des outils courants et très efficaces.

Dans la pratique, partant d'un Ei de taille k, on va générer x nouveaux E'i de taille k+1.
Ca nécessite de faire une copie E'i de Ei et ajouter une mine M. Voici les opérations après la copie :
- L( E'i ) = L( E'i ) + M
- V( E'i )[indice(M)] = 1
Donc le traitement du vecteur coute peu (la copie de n/8 octets pour n mines, essentiellement).

Pour ce qui est de la table de hash, à titre d'info, les machines actuelles (sans être des bêtes de course) peuvent y stocker environ 1 million d'éléments par seconde.


Bon sinon, je relis attentivement tout ton post dans la journée...