Discussion :

[jmmomg]

Bonjour à tous,

Je cherche à faire un algorithme mais je sèche complètement.
Je vous explique le truc :

- Le but c'est de former la meilleure combinaison possible de 5 joueurs (c'est pour le jeu de l'entraineur pour ceux qui connaissent) pour former la meilleure équipe. Chaque joueur a un prix et un niveau.

Les contraintes :

- Le prix total doit pas dépasser X
- Il faut choisir 1 gardien, 2 milieux, 2 attaquants
- Un autre critère est de prendre 3 joueurs max de la même équipe mais je pourrais m'en passer.

J'ai donc une table gardien de 10 choix, 1 table milieux de 25 choix, 1 table attaquants de 25 choix.

Et là je sèche, mon idée était de faire toutes les combinaisons possibles en ne stockant que celle dont le prix était <= X et de les trier par valeur, déjà je sais pas trop comment faire mais surtout, je ne sais pas si la solution est optimale, si vous avez des idées !

Merci

[anapurna]

salut

de façon brutale tu as 5 boucle a faire
1 sur la table des gardien
2 sur la table des milieux
2 sur la table des attaquants

vu le nombre d’éléments le temps n'est pas determinant

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
  Pour chaque occurrence Igardien de la table Gardien Faire 
     Pour chaque occurrence Imil1 de la table Milieux Faire 
        Pour chaque occurrence Imil2 de la table Milieux Faire 
           Pour chaque occurrence IAtaq1 de la table Attaquants Faire 
             Pour chaque occurrence IAtaq2 de la table Attaquants Faire 
                  si Attaquants[IAtaq1] <>  Attaquants[IAtaq2] alors
                    si Milieux[Imil1] <>  Milieux[Imil2] alors
                       PrixTot := Gardien[Igardien].prix+Milieux[Imil1].Prix+Milieux[Imil2].prix + Attaquants[IAtaq1].prix+Attaquants[IAtaq2].prix;
                       si PrixTot <= PrixMax alors
                          Ok  =  TestMaxNbSameEquipe(Gardien[Igardien],Milieux[Imil1],Milieux[Imil2].prix,Attaquants[IAtaq1],Attaquants[IAtaq2])
                          si  Ok alors 
                             AddEquipe(Gardien[Igardien],Milieux[Imil1],Milieux[Imil2].prix,Attaquants[IAtaq1],Attaquants[IAtaq2])     
                       FinSi                             
                    Fin si  
                  Fin Si
             Fin Pour
           Fin Pour
        Fin Pour
     Fin Pour
  Fin Pour

voici un algo basique, il est loin d’être optimisé mais il a le mérite de jeter les bases sur lesquels tu doit plancher

[jmmomg]

Hello,

Merci de ton retour, c'est à peu près ce que j'ai fait au mot près mais j'imaginais qu'il y avait une manière plus propre que 5 boucles imbriquées. Bon je laisse comme ça pour le moment, si y'en a qui on des suggestions entre temps, n'hésitez pas !

[phryte]

Bonjour,

Je ferais comme cela :
- Trois tableaux pour - Gardiens - Milieux - Attaquants
- On tire au hasard : 1 gardien, 2 Milieux, 2 Attaquants
- On prend comme critère : moins de x Euros ET meilleure note de l'équipe tirée au hasard
- On fait N tirages (1000 par exemple)
- On garde en mémoire la meilleure équipe.

Un exemple avec Matlab (pour 10 joueurs) :

Code matlab :

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
% Tableaux :  Numéro   Prix   Note
%Gardiens
G=[1 150 12;
   2 250 9;
   3 600 18;
   4 320 13;
   5 141 17
   6 100 12;
   7 40 4;
   8 80 19;
   9 90 9;
   10 125 11];
% Milieu de terrain
M=[1 15 12;
   2 95 19;
   3 160 18;
   4 32 13;
   5 241 17;
   6 120 10;
   7 50 6;
   8 200 18;
   9 140 15;
   10 50 8];
% Attaquants
A=[1 100 12;
    2 125 9;
    3 60 18;
    4 32 13;
    5 541 17
    6 100 16;
    7 400 19;
    8 100 11;
    9 250 15
    10 100 18];
 
Prix_max=800;
Equipe=[];
SNR=0;
NbG=10;
NbM=10;
NbA=10;
SER=0;
SERP=0;
Nb_Tirages=2000;
for n=1:Nb_Tirages
    g= G(fix(1 + NbG* rand(1)),1);
    m1=M(fix(1 + NbM* rand(1)),1);
    m2=M(fix(1 + NbM* rand(1)),1);
    a1=A(fix(1 + NbA* rand(1)),1);
    a2=A(fix(1 + NbA* rand(1)),1);
    PE=[G(g,2) M(m1,2) M(m2,2) A(a1,2) A(a2,2)];
    NE=[G(g,3) M(m1,3) M(m2,3) A(a1,3) A(a1,3)];
    SE=sum(PE);% Prix de l'équipe
    SN=sum(NE);% Note de l'équipe
        if SN > SNR & SE <= Prix_max % Critère de choix
             SNR=SN;% Note retenue
                SER=SE;% Prix retenu
                SERP=SER;
            Equipe=[G(g,1) M(m1,1) M(m2,1) A(a1,1) A(a2,1)];
    end
end
if SER==0
    disp('Pas de solution')
else
disp(['Equipe : ' num2str(Equipe)])
disp(['Total Notes : ' num2str(SNR)])
disp(['Total Points : ' num2str(SER)])
disp(' ')
end

Résultat :

Equipe : 8 2 2 7 10
Total Notes : 95
Total Points : 770

[tbc92]

Anapurna a clairement dit que son ode était archi-basique. Bien entendu qu'il y a matière à amélioration.

Amélioration évidente :
En permutant juste quelques lignes de son code, en remplaçant un test 'différent' par supérieur strict', on arrive à ça ... et à la louche, on divise le temps de traitement par 4 ou 5 :

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
 
 Pour chaque occurrence Igardien de la table Gardien Faire 
     Pour chaque occurrence Imil1 de la table Milieux Faire 
        Pour chaque occurrence Imil2 de la table Milieux Faire 
           si Milieux[Imil1] > Milieux[Imil2] alors
 
              Pour chaque occurrence IAtaq1 de la table Attaquants Faire 
                 Pour chaque occurrence IAtaq2 de la table Attaquants Faire 
                     si Attaquants[IAtaq1] >  Attaquants[IAtaq2] alors
                       PrixTot := Gardien[Igardien].prix+Milieux[Imil1].Prix+Milieux[Imil2].prix + Attaquants[IAtaq1].prix+Attaquants[IAtaq2].prix;
                       si PrixTot <= PrixMax alors
                          Ok  =  TestMaxNbSameEquipe(Gardien[Igardien],Milieux[Imil1],Milieux[Imil2].prix,Attaquants[IAtaq1],Attaquants[IAtaq2])
                          si  Ok alors 
                             AddEquipe(Gardien[Igardien],Milieux[Imil1],Milieux[Imil2].prix,Attaquants[IAtaq1],Attaquants[IAtaq2])     
                       FinSi                             
                    Fin Pour
                  Fin Pour
             Fin Si
           Fin Pour
        Fin Pour
     Fin Pour

Après, on peut avoir quelques traitements préliminaires qui peuvent encore accélérer le traitement.
Si par exemple on a 2 gardiens A et B, A vaut plus cher que B, mais il a une performance moindre que B... alors on élimine purement et simplement A de la liste des gardiens. Inutile d'analyser toutes les combinaisons qui contiennent A.

Si le cas se produit ne serait-ce qu'une fois, on économise 10% du temps de traitement.

Idem, si avec les 3 ou 4 premiers joueurs, on a déjà dépassé le budget, inutile d'explorer les 25 choix possibles pour le 5ème joueur...

[anapurna]

salut

parmi les amélioration notable tu as effectivement la deuxième boucle de la table attaquant et milieux pour laquelle tu peut commencer a l'indice supérieur de la premier boucle

exemple

Code :

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

1
2
    Pour chaque occurrence Imil1 -1 de la table Milieux Faire 
        Pour  Imil2 = Imil1+1 jusqu’à max(table Milieux)  Faire

de cette manière tu compare

Code :

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

1
2
3
4
5
6
7
8
   1 et 2
   1 et 3
   1 et 4 ...
  ensuite 
   2 et 3 
   2 et 4 .. 
  et pour finir 
   Max-1 et Max