Discussion :

[Alikendarfen]

Pour info, pour trouver que ça ne marche pas, j'ai fait un tirage aléatoire, comme tu préconisais.

Voici les conditions de ce tirage :

p = un réel entre 0 et 1

Nombre de mines (fixe) = 5 (c'est limité par le temps d'exécution de l'algo par combinaisons...)

ci = un réel entre 0 et 1
pi = un réel entre 0 et 1

4000 tirages et calculs.

En moyenne l'algo par insertion est mauvais une 15zaine de fois (sur les 4000).

Avec la règle de l'idéalité 2 à 2 on peut facilement identifier les mauvaises solutions : si l'idéalité n'est pas vérifiée alors le chemin n'est pas optimal (tu es d'accord ? et que la réciproque n'est pas prouvée ?)

Auquel cas, il est peut être possible de trouver une solution alternative pour les chemins qu'on sait ne pas être optimaux ?

Mais ça serait cool de prouver la réciproque : auquel cas on pourrait engager un 'calcul long' seulement dans ces situations ?

[Alikendarfen]

Donc, dans la foulée : la réciproque est fausse.

Il y a bien des chemins non optimaux dont les mines sont idéales 2 à 2.

(même méthode et contexte pour trouver des exemples : 13 cas sur 40000 tirages, soit sur 154 chemins non optimaux)

[Baruch]

Eh bien moi j'ai une bonne nouvelle

J'ai enfin réussi à montrer que la mine 1 est toujours avant la mine 2 quelles que soient les conditions, si et seulement si p1 > p2 et c1 < c2

Je publie la démo quand j'aurai fini de la retranscrire.

Maintenant faudrait réfléchir à comment on pourrait utiliser cette propriété pour simplifier un peu le problème au départ...

[JeitEmgie]

Eh bien moi j'ai une bonne nouvelle

J'ai enfin réussi à montrer que la mine 1 est toujours avant la mine 2 quelles que soient les conditions, si et seulement si p1 > p2 et c1 < c2

Je publie la démo quand j'aurai fini de la retranscrire.

Maintenant faudrait réfléchir à comment on pourrait utiliser cette propriété pour simplifier un peu le problème au départ...

p1 > p2 et c1 < c2 => r1 > r2 …
or on sait que des situations où le tri par rendement ne donne pas toujours le meilleur résultat…

Prenez des M telles que les C et P soient des multiples tels que le R soit constant :
(10,10), (20,20), (30,30)

Si p0 < c2, il faut les construire dans l'ordre croissant de coût, donc (10,10) < (20,20) < (30,30) mais p1 < p2 < p3.
par contre si p0 ≥ c2 alors on peut construire M2 le premier jour et donc on a intérêt à le faire (et resp. même raisonnement si p0 ≥ c3…)
quoique dans ce cas simplissime, çà ne changera rien tant que p0 n'est pas tel que l'on puisse construire 2 mines le même jour (donc à J1 si p0 ≥ c3 + c1…).

… où comment on retombe sur les aspects topologiques dont je parlais plus haut…
auxquels on pourrait rajouter la notion de "densité" des coûts des mines : combien de mines sont telles que la différence de coût ≤ p0… cette "densité" augmentant la probabilité que l'on ait des journées où l'on puisse construire plus d'une mine à la fois. (et cette densité évolue en cours de route évidemment si l'on appelle p0 la production courante…)

[Baruch]

Euh attention ici on gère un temps continu, pas discret (tu parles de journées).

Ce qu'on a ici c'est une relation d'ordre partielle, donc c'est toujours bon à prendre nn ?
Et oui en effet le tri par rendement n'est pas la solution. Je parle bien de dominance (coût moindre et production plus élevée).

[JeitEmgie]

Euh attention ici on gère un temps continu, pas discret (tu parles de journées).

Ce qu'on a ici c'est une relation d'ordre partielle, donc c'est toujours bon à prendre nn ?
Et oui en effet le tri par rendement n'est pas la solution. Je parle bien de dominance (coût moindre et production plus élevée).

Premier post qui explique le problème :
"Une mine est un bâtiment qui a un coût, mais qui rapporte une certaine somme d’argent tous les jours."
Valeurs entières, jours… pas vu grand chose dans les discussions jusqu'ici qui sous-entende un mode continu, tout à l'air de parler d'un jeu "par tour".

Il n'y a pas de relation de "dominance" ou "d'ordre" qui tienne de manière absolue dans ce problème :
vous ne trouverez pas de formule qui fonctionne uniquement sur les caractéristiques de 2 mines et qui soit vraie dans toutes les situations hors du contexte du reste de mines, or c'est ce que votre formule sous-entend.

Il faut une approche probabiliste (du genre de la logique floue) qui tienne en compte les caractéristiques statistiques du problème, par contre l'idée de segmentation en sous-problèmes est intéressante à condition qu'elle se fasse en groupant les mines selon des caractéristiques multiples de proximité relative : càd si l'on groupe par rendement, il faut aussi que le coût soit similaire, et par similaire on doit entendre relativement à la répartition statistique des coûts dans le problème.
(et donc on aura une solution "probablement" proche de la meilleure possible… pas "la" meilleure…)

Ensuite on pourra trier les sous-problèmes pour déterminer l'ordre, et il faudra voir si les sous-groupes doivent être considérer comme des ensembles unitaires (tous les éléments construit l'un après l'autre) ou simplement des indications de priorité relative (les éléments du groupe 2 devant être construit après les premiers éléments du groupe 1 mais par nécessairement tous après le dernier élément du groupe 1 : il pourrait avoir un chevauchement de certains éléments : la frontière entre les groupes pourrait être elle aussi floue… si les premiers éléments du groupe 2 aurait "presque" pu être membre du groupe 1), par contre l'ordre de priorité à l'intérieur d'un groupe défini par une certaine cohérence topologique sera certainement le tri par rendement.

Une fonction qui calcule la durée de construction d'un sous-groupe à partir d'une production et un budget de départ sera nécessaire au centre de l'algorithme et au départ il faut une fonction qui calcule moyenne, écart-type, variance, … des coûts, productions et rendements du problème de départ, une mine M aura donc des coordonnées (X,Y,Z, …) qu'il faudra sans doute normaliser en [0,1] dans un espace à M dimensions où s'expriment des positions relatives à un critère statistique et il faudra les grouper par proximité : des sortes de "sphères" à M dimension. Déterminer le meilleur rayon (ou les meilleurs rayons, chaque dimension pourrait avoir le sien, et on aurait donc des ellipsoïdes à M dim.) sera un des problèmes à résoudre mais il faudra sans doute le voir comme un facteur de zoom : si l'espace est bien occupé le rayon sera plus grand pour que les groupes ne soient pas trop petits, si l'espace est au contraire occupé par zone, un rayon plus petit jouera comme un zoom permettant de distinguer les mines dans les amas...

Évidemment, tout ceci ne vaut la peine que si N est (très) grand, tant que N est "raisonnable" le calcul brut de toutes les solutions reste le plus simple à condition de l'optimiser un maximum en organisant une cache des résultats intermédiaires (ce qui peut être déjà un défi très amusant en soi, mais très faisable en organisant intelligemment l'ordre d'évaluation des permutations…).

[Baruch]

Premier post qui explique le problème :
"Une mine est un bâtiment qui a un coût, mais qui rapporte une certaine somme d’argent tous les jours."
Valeurs entières, jours… pas vu grand chose dans les discussions jusqu'ici qui sous-entende un mode continu, tout à l'air de parler d'un jeu "par tour".

Ouép mais par la suite j'ai précisé que c'était bien continu.

Il n'y a pas de relation de "dominance" ou "d'ordre" qui tienne de manière absolue dans ce problème :
vous ne trouverez pas de formule qui fonctionne uniquement sur les caractéristiques de 2 mines et qui soit vraie dans toutes les situations hors du contexte du reste de mines, or c'est ce que votre formule sous-entend.

J'ai pourtant bien démontré ce résultat. En quoi n'est-ce pas possible ?

Il faut une approche probabiliste (du genre de la logique floue) qui tienne en compte les caractéristiques statistiques du problème, par contre l'idée de segmentation en sous-problèmes est intéressante à condition qu'elle se fasse en groupant les mines selon des caractéristiques multiples de proximité relative : càd si l'on groupe par rendement, il faut aussi que le coût soit similaire, et par similaire on doit entendre relativement à la répartition statistique des coûts dans le problème.
(et donc on aura une solution "probablement" proche de la meilleure possible… pas "la" meilleure…)

Es-tu entrain de dire que des mines qui ont des caractéristiques "proches" se retrouvent côte à côte dans l'ordre idéal ?

le calcul brut de toutes les solutions reste le plus simple à condition de l'optimiser un maximum en organisant une cache des résultats intermédiaires (ce qui peut être déjà un défi très amusant en soi, mais très faisable en organisant intelligemment l'ordre d'évaluation des permutations…).

Tu peux préciser ta pensée ?

[Alikendarfen]

Ben ça Baruch:

Citation:
Il n'y a pas de relation de "dominance" ou "d'ordre" qui tienne de manière absolue dans ce problème :
vous ne trouverez pas de formule qui fonctionne uniquement sur les caractéristiques de 2 mines et qui soit vraie dans toutes les situations hors du contexte du reste de mines, or c'est ce que votre formule sous-entend.
J'ai pourtant bien démontré ce résultat. En quoi n'est-ce pas possible ?

C'est ce que je n'arrête pas de te dire (voir ma démo tenant compte de P = somme des pi des autres mines) !!

[Alikendarfen]

JeitEmgie, par contre, je ne suis pas vraiment d'accord avec ça :

Évidemment, tout ceci ne vaut la peine que si N est (très) grand, tant que N est "raisonnable" le calcul brut de toutes les solutions reste le plus simple à condition de l'optimiser un maximum en organisant une cache des résultats intermédiaires (ce qui peut être déjà un défi très amusant en soi, mais très faisable en organisant intelligemment l'ordre d'évaluation des permutations…).

Le calcul brut est en n! : permet de calculer env. 10 à 12 mines
Le calcul par combinaison en n * 2^n (cf. plus haut) : permet de calculer une quinzaine de mines

Quand je dis "permet de calculer", j'entends le fait d'avoir un résultat en moins de 10mn sur un PC de puissance raisonnable.

Les deux sont optimisables en termes de réal, mais il ne faut pas rêver : calculer pour 100 mines est hors de portée de ces algos.

Mais cela étant dit : on ne peut être que preneur des optimisations que tu pourrais trouver !!

Par contre, la petite implémentation par AG (que j'ai publiée un peu avant) permet d'aller beaucoup plus haut : la centaine de mines peut être atteinte (dans les 10mn). Mais évidemment, pas de preuve que la soluce trouvée soit optimale...

[Baruch]

C'est ce que je n'arrête pas de te dire (voir ma démo tenant compte de P = somme des pi des autres mines) !!

Quoi ? Tu peux préciser ta pensée stp ?
Je rappelle que si M1 domine M2, alors leur p* est négatif. Donc quel que soit p, p>p*. Donc le plus rentable est toujours avant, ie M1 est toujours avant M2.

[Alikendarfen]

Je précise (mais voir la démo que j'ai transmise) :

T(M1M2) > T(M2M1) dépend d'une fonction de f(p) de la forme f(p) = (p + p2)/(p + p1) - cst.

Qui est soit croissante, soit décroissante selon p1, p2.

Quand p parcourt [p0 ; P] où P = somme des pi des autres mines, f(p) peut ou non changer de signe (selon p0 et P).

... c'est ce qu'on s'est dit avant en concluant que cette règle ne semblait de toute façon pas donner un résultat exploitable pour un calcul (pas de changement significatif de la complexité).

[JeitEmgie]

Ouép mais par la suite j'ai précisé que c'était bien continu.

il doit quand même avoir un delta T…

J'ai pourtant bien démontré ce résultat.

et le problème est toujours là…

Es-tu entrain de dire que des mines qui ont des caractéristiques "proches" se retrouvent côte à côte dans l'ordre idéal ?

non, pas nécessairement côte à côte mais la probabilité qu'elles soient proches dans la solution est plus grande : entre une mine (30,10) et une mine (31,10) il y a peu de chance d'avoir une autre mine qui vienne se glisser entre les deux…
un autre façon de le dire est que des "petites" variations (dans la définition d'une mine) ne changeront pas sa position dans la solution, ce qui est quand même assez intuitif à comprendre.
Mais attention : "petites" variations relativement à la topologie du problème !
une mine (300,100) et une mine (310,90) peuvent être très proches dans un problème de 20 mines où les coûts sont dans un intervalle [10;500] et très éloignées dans un problème de 500 mines où les coûts sont dans l'intervalle [299;311] … (et resp. pour la production et le rendement).

Tu peux préciser ta pensée ?

il est clair qu'évaluer toutes les permutations conduit à réévaluer plusieurs fois certaines séquences…
donc concevoir une cache capable dévaluer rapidement le temps de construction d'une séquence connue sur base d'un paramètre de budget initial une fois que l'on connaît la durée pour le budget 0 doit permettre d'économiser pas mal de calculs - du moins en théorie.
Mais cela reste repousser le problème à plus tard, et de toute façon c'est moins amusant qu'une solution plus sophistiquée.

[Alikendarfen]

@JeitEmgie

il est clair qu'évaluer toutes les permutations conduit à réévaluer plusieurs fois certaines séquences…

C'est le but de l'algo par combinaison (voir avant) qui à chaque étape compare les chemins correspondant exactement aux mêmes mines et ne garde que le meilleur.
On passe alors de n! à somme( c(n,p) ) = 2^n.

[Baruch]

Je précise (mais voir la démo que j'ai transmise) :

T(M1M2) > T(M2M1) dépend d'une fonction de f(p) de la forme f(p) = (p + p2)/(p + p1) - cst.

Qui est soit croissante, soit décroissante selon p1, p2.

Quand p parcourt [p0 ; P] où P = somme des pi des autres mines, f(p) peut ou non changer de signe (selon p0 et P).

En effet, mais regarde :

Tu as montré que T12 < T21 <=> f(p)>0
où f(p)=(p+p2)/(p+p1) - c1p2/(c2p1)

Dans le cas où p1>p2 et c1<c2 (càd M1 domine M2) :

Comme p1>p2, f est croissante (tu l'as montré).
Donc f(p) > f(0) , puisque p est toujours positif
Or f(0) = p2/p1 - c1p2/(c2p1) = p2/p1 (1-c1/c2)
Or c1<c2 , donc f(0) est positif
Donc f(p) est toujours positif
Donc T12 < T21 , quel que soit p

Voilà, je peux pas être plus clair... Ca c'est dans le cas où les mines sont adjacentes. Moi j'ai montré dans le cas général où il y a des mines entre M1 et M2.

il doit quand même avoir un delta T…

Euh ? Pourquoi ?

et le problème est toujours là…

Bon personne me croit xD Je poste la démo dès que j'ai fini de galérer avec latex.

non, pas nécessairement côte à côte mais la probabilité qu'elles soient proches dans la solution est plus grande : entre une mine (30,10) et une mine (31,10) il y a peu de chance d'avoir une autre mine qui vienne se glisser entre les deux…
un autre façon de le dire est que des "petites" variations (dans la définition d'une mine) ne changeront pas sa position dans la solution, ce qui est quand même assez intuitif à comprendre.

Je pense que tes deux façons de le dire sont bien distinctes. En effet, je suis d'accord pour les petites variations. Mais en quoi cela prouve que 2 mines avec des caractéristiques "voisines" (relativement à la topologie du problème), sont "proches" dans la liste ?

donc concevoir une cache capable dévaluer rapidement le temps de construction d'une séquence connue sur base d'un paramètre de budget initial une fois que l'on connaît la durée pour le budget 0 doit permettre d'économiser pas mal de calculs - du moins en théorie.
Mais cela reste repousser le problème à plus tard, et de toute façon c'est moins amusant qu'une solution plus sophistiquée.

J'ai du mal à comprendre ce que tu appelles une "cache".
On est d'accord qu'on économise jamais d'argent n'est-ce pas ? Dès qu'on a l'argent nécessaire pour construire la mine visée, on la construit.
Par "sophistiquée", tu entends approchée (plus ou moins) ?

[Baruch]

Voilà la démo de la dominance : Demo

Si vous ne me croyez pas, contestez la démo ^^.

Bon maintenant il faudrait réfléchir à la réelle utilité de cette relation d'ordre partiel.

[Alikendarfen]

bon, ça marche Baruch.

Je n'ai fait qu'une lecture rapide (mais je relirai) mais c'est ok.

Et ok, j'ai bien compris ma connerie sur l'histoire de [p0 ; P].

Côté algo,

Dans la pratique, dire que celle qui rapporte plus et coute moins cher doit être achetée d'abord.... arrive 2 fois sur 4 pour 2 mines si les tirages sont aléatoires et homogènes pour ci et pi.

Pour le dire autrement, chaque mine domine en moyenne n/4 autres mines.

... ramener au déroulement d'une exploration exhaustive mais tenant compte de la dominance, ça doit valoir le cout (bien que je ne vois pas encore comment calculer le gain en complexité de l'algo).

[Baruch]

Pour ma démo :

J'ai considéré ici qu'on ne connaissait que les caractéristiques des 2 mines Ma et Mb. C'est-à-dire que si M1 domine M2, alors quel que soit l'"univers" dans lequel on les place, M1 est avant M2.
Mais en réalité, on connaît les autres mines, ainsi que le production initiale p0. Les valeurs de p et p* sont donc quantifiées, prenant un nombre fini de valeurs, et on connaît les Ci possibles. Donc on peut à mon avis trouver une condition moins forte que c1<c2 et p1>p2, en intégrant une sorte de marge de manœuvre, pour que M1 domine M2.
Si on trouve une condition un peu moins forte, on peut peut-être dans certains cas augmenter le nombre de relations d'ordre qu'on peut trouver sur notre liste.
Je vais regarder ça.

Pour le dire autrement, chaque mine domine en moyenne n/4 autres mines.

Ouép je suis d'accord

... ramener au déroulement d'une exploration exhaustive mais tenant compte de la dominance, ça doit valoir le cout (bien que je ne vois pas encore comment calculer le gain en complexité de l'algo).

Oué ça m'a l'air pas facile. Il faudrait trouver le nombre de combinaisons possibles de n mines en connaissant k relations d'ordre

Edit :

Niveau complexité, c'est complexe ^^ :
Une mine domine en moyenne n/4 mines certes, mais combien a-t-on de relations d'ordre en tout ?
Et sachant le nombre de relations d'ordre, combien reste-t-il de combinaisons possibles ? Dur, puisque pour 3 mines 1,2,3 :
1 avant 2 -> 123 ou 132 ou 312
puis
1 avant 3 -> 123 ou 132
2 avant 3 -> 123
donc ça dépend ^^

Bref peut-être faudrait-il avant ça imaginer un algo qui utilise les relations de dominance...

[Baruch]

Bon pour l'algorithme utilisant les dominances :

On peut commencer par faire un algo naïf (pas celui par combinaisons)

On commence par créer un vecteur de taille n contenant pour chaque mine la liste des mines qui peuvent être après celle-ci. Ca doit pouvoir se faire en n².
Ensuite on fait comme l'algo naïf initial, mais au lieu d'utiliser une seule liste contenant toutes les mines restantes, on utilise la liste correspondant à la mine qui vient d'être placée. A chaque itération, on enlève la mine placée de toutes les listes.

C'est ptet pas clair, mais jvais le coder. Il faut voir ensuite comment adapter l'algo par combinaisons pour utiliser les dominances

[Alikendarfen]

C'est ptet pas clair, mais jvais le coder. Il faut voir ensuite comment adapter l'algo par combinaisons pour utiliser les dominances

Si, c'est clair.

Et effectivement, l'approche en n! semble plus simple pour utiliser la dominance.

En fait, l'algo par combinaisons marcherait aussi, mais on aurait moins de regroupements (chemins ayant exactement les mêmes mines) à chaque étape car la relation d'ordre partielle décorrélerait les chemins.

PS : ça fait quelques temps que j'ai envie de me mettre au F# (quasi compatible caml). Donc si tu avances dans tes implémentations fais nous en part !!!

[Baruch]

Ok, chui entrain de coder là.