Discussion :

[Baruch]

Bonjour !

J'essaye de trouver un bon algorithme pour résoudre ce problème, mais je n'y arrive pas, quelqu'un pourrait-il s'y intéresser ?


Voici en quoi consiste le problème :

On souhaite optimiser l’ordre de construction de mines.

Une mine est un bâtiment qui a un coût, mais qui rapporte une certaine somme d’argent tous les jours. On a à notre disposition plusieurs mines qu’il est possible de construire, à condition bien entendu d’avoir l’argent nécessaire pour les payer. Le but du jeu est de construire toutes ces mines en un minimum de temps. En effet, on se rend compte que l’ordre de construction des mines a son importance, puisque les mines rapportent de l’argent une fois construites, et qu’elles minimisent donc le temps d’attente avant la construction des mines suivantes. Le but de l’algorithme est de trouver l’ordre de construction idéal, qui nécessite un temps total minimal.

Je n’ai pas réussi à trouver d’algorithme intelligent, autre que le test de toutes les combinaisons possibles.

On a à notre disposition n mines.
Chaque mine M_i a un coût c_i et une production p_i.
Au départ, on n’a pas d’argent, mais on gagne p argent par jour.
On considère ici que les mines n’ont pas de temps de construction, c’est-à-dire qu’une fois payées, elles sont fonctionnelles instantanément.

Soit T_i le temps d’attente avant la construction de la mine M_i.

On a T_i = c_i / (p + somme pour j allant de 1 à i-1 de p_j)

Le but est donc de minimiser la somme des T_i.


Voilà ! Si quelqu'un a une idée, merci d'avance !

[prgasp77]

Sans démonstration aucune, je pense que construire les mines dans l'ordre décroissant des valeurs est la stratégie gagnante

[Baruch]

En effet, ça paraît être la solution au premier abord, mais en réalité ce n'est pas le cas :

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

p_1/c_1 = 1
p_2/c_2 = infini

donc M2 devrait être avant.

Or avec p=1,
Pour la configuration M1,M2, on trouve T=6
Et pour M2,M1, on trouve T=10

Donc M1,M2 est meilleur

[HelixLeChat]

p_2/c_2 tend vers 0 plutôt non ?

[Baruch]

Euh non, c'est p_2 qui est infini

[prgasp77]

Exact, j'ai omis un détail de mon raisonnement, c'est que le chronomètre s'arrête une fois la dernière mine construite, on ne profite donc pas de sa production. Et personnellement, j'ai toujours eu du mal à optimiser un système non continu ... La seule chose que je peux apporter c'est une formalisation du problème :

Soient

• une suite de couples de réels représentant les mines, leur coût et leur production ;
• une bijection de dans lui-même représentant l'ordre dans lequel les minues sont construites ;
• le temps de construction de toutes les minues suivant l'ordre ;
• la production totale une fois la n-ième mine construire suivant l'ordre ;
• et le temps d'attente nécessaire entre la construction de la (n-1)-ième mine et la n-ième suivant l'ordre

Alors, les égalités suivantes sont respectées :

• 
• 
• 

Et c'est ce dernier terme qu'il faut minimiser en jouant sur . Bon courage !

[Baruch]

Ouép c'est tout à fait ça
Merci, on y voit plus clair (même si ça n'apporte pas la solution ^^)

Le problème, c'est qu'on ne peut pas établir de relation d'ordre entre les mines, puisque ça dépend de la permutation u, ainsi que de la production initiale p

[Baruch]

Bon j'ai peut-être une première piste :

Soit la liste de mines suivante :
(A1,...,Ap,B1,...,Bq)

Si on permute les mines B_i entre elles, le temps d'attente pour les mines A_i n'est pas modifié, puisque celui-ci ne dépend que de ce qui se passe avant, pas après.

De même, si on permute les mines A_i entre elles, la production résultante au début des B_i reste la même, puisque on permute les éléments d'une somme de productions. Ainsi le temps d'attente pour les mines B_i n'est pas modifié.



Avant d'aller plus loin, il faut faire attention à la notion de liste idéale :

L'ordre idéal des mines dans une liste varie en fonction de la production initiale (pas forcément évident à première vue, mais le calcul et des exemples le prouvent).
Il faut donc parler de liste idéale pour la production p.



Ceci implique (si je ne me trompe pas) :

Soit (A1,...,Ap,B1,...,Bq) une liste de mines ordonnée de façon idéale pour p.

Alors (A1,...,Ap) est une liste idéale pour p
Et (B1,...,Bq) est une liste idéale pour la somme des productions des A_i


Je crois que c'est quand même une propriété intéressante.


De ce fait, on peut par exemple en tirer cette règle :

Soit (M1,...,Mn) une liste idéale pour p.
Alors toutes les listes (M_i,M_(i+1)) sont idéales pour la production résultante à la fin de M_(i-1).

Or la condition d'idéalité pour une liste de taille 2 est la suivante :

Soit M1 avec c1 et p1
Soit M2 avec c2 et p2
Soit p la production initiale

(M1,M2) est mieux que (M2,M1)
ssi T12 < T21

or T12 = c1/p + c2/(p+p1)
et T21 = c2/p + c1/(p+p2)

donc la condition est équivalente à :

c1 * (1+p/p1) < c2 * (1+p/p2)

Au passage, ce calcul montre que l'ordre dépend de p.



Donc là on a une condition nécessaire d'idéalité : toutes les mines connexes vérifient 2 à 2 cette propriété.
Je ne sais pas si c'est une condition suffisante... (ça serait cool quand même ^^, mais faut pas trop rêver je crois)

En tout cas, on a un moyen d'améliorer une liste non idéale :
On parcourt les couples de mines connexes, et on permute si elles ne vérifient pas la condition d'idéalité.


Par contre, la recherche d'une solution vérifiant la propriété d'idéalité 2 à 2 peut être longue :

Prenons une liste de 3 mines (1,2,3)

on fait un test et on a 1<2 et 2>3
on permute donc 2 et 3, on a alors (1,3,2)
si 1>3, on a ensuite (3,1,2)
or c'est possible que 2>1 ici, puisque la production de base considérée a changé (1<2 si c'est p, 2>1 si c'est p+p3)
donc on peut encore continuer comme ça, avec au maximum le test des 6 combinaisons... pas génial

[Vakhyw]

Ca me semble NP-Hard... Donc je ne crois pas que tu puisses trouver de solutions exactes en temps polynomial

Néanmoins si tu cherches un formalisme adapté, ça devrait ressembler à :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
27
28
29
30
31
32
33
34
35
36
37
38
 
long computeTime(Mine mines_restantes[], long production, long argent, long temps){
 
   // Si plus de mines, le resultat est le temps courant
   if(isEmpty(mines_restantes)){
      return temps;
   }
 
   // Sinon, on calcule le temps minimum :
   // pour chaque mine, je regarde quel est le resultat si c'est elle que je construis, et je choisis le minimum !
 
   long temps_min[] = new long[mines_restantes.length];
 
   for(int index = 0 ; i<mines_restantes.length ; ++i){
      Mine mine = mine_restantes[i];
      if(mine.cout() <= argent){
         // Dans ce cas, la mine peut etre construite instantanement !
         temps_min[i] = computeTime(mines_restantes.remove(i), production + mine.production(), argent - mine.cout(), temps);
      }
      else{
         // Sinon, combien de temps pour la construire ?
          long difference = mine.cout() - argent;
          long modulo = difference % production;
          short offset = 0;
          if(modulo != 0){
             offset = 1;
          }
          long temps_construction = difference / prodution + offset;
          temps_min[i] = computeTime(mines_restantes.remove(i), production + mine.production(), argent + (temps_construction * production) - mine.cout(), temps + temps_construction);
      }
   }
 
   // Retourner le temps minimum
   int indexMin = getIndexMin(temps_min);
   long temps_min_glob = temps_min[indexMin];
   return temps_min_glob;
 
}

Selon ton nombre de mines, ca pourrait tenir la charge

[prgasp77]

J'ai l'impression que tu supposes que dans tous les cas, si possible, il faut construire. Il est des cas où il est plus intéressant d'attendre afin de construire une mine plus chère.

[Vakhyw]

Non, pour une mine donnée soit je peux la construire (suffisamment d'argent) et je regarde le temps résultant si je la construis, soit je ne peux pas la construire et alors je regarde combien de temps je dois attendre pour la construire en fonction de mon argent et de ma poduction.
La seule chose dont on est sûr, c'est qu'attendre alors qu'on a suffisamment d'argent pour construire la mine est contre productif