Aide sur algorithme

Version imprimable

08/05/2011, 10h42
4Ur3L

Aide sur algorithme
Bonjour à tous !

J'aurais besoin de votre aide sur un algorithme ... Ca fait 2 jours que je suis dessus, mais toujours aucune piste valable. :cry:

Voilà, j'ai un vecteur de nombre :

Code:

v <- c(118080, 130195, 199047, 84722, 97613, 214886)

Mon objectif est de combiner ces nombres dans 3 vecteurs, dont le total de chaque vecteur sera quasiment équivalent.
En plus clair, par exemple, à partir du vecteur v, je vais former
Code:

1 2 3 v1 <- c(118080, 84722, 97613) # somme = 300415 v2 <- c(130195, 199047) # somme = 329242 v3 <- c(214886) # somme = 214886
Ici, on voit que cette combinaison n'est pas idéale car les sommes varient fortement entre les vecteurs. Bon but est de minimiser cet écart entre les sommes de chaque vecteur.

Une combinaison meilleure serait (mais ce n'est peut-être pas la meilleure) :
Code:

1 2 3 v1 <- c(118080, 130195) # somme = 248275 v2 <- c(199047, 97613) # somme = 296660 v3 <- c(84722, 214886) # somme = 299608
Car la variation entre les sommes est plus faible.

Voilà voilà ..
Est-ce que quelqu'un aurait une idée sur comment trouver la combinaison idéale permettant de diminuer au maximum la variation entre les sommes de chaque vecteur ?

PS : les 3 vecteurs finaux doivent contenir au moins 1 nombre.

Grand merci à tout ceux qui tenteront de répondre ... parce que moi j'suis perdu !
J'espère avoir correctement expliqué mon problème, mais si vous avez des questions, n'hésitez pas ! ;)

Bonjour,

Dans l'énoncé de ton problème, rien n'indique qu'on puisse faire appel à une méthode d'optimisation qui dispense de tester toutes les combinaisons possibles (ou bien si ça existe, ce n'est pas dans mes cordes).

La méthode de brute consiste à

identifier toutes les combinaisons de 1, 2 et 3 ayant la même longueur que ton vecteur v.
choisir et calculer un critère de répartition de tes sommes.
identifier la combinaison qui minimise ce critère.

Voici un exemple avec au choix trois critères (intuitivement, j'aurais tendance à dire que les deux premiers doivent être équivalents... mais dans le cas présent, les trois donnent le même résultat) :

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
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
v <- c(118080, 130195, 199047, 84722, 97613, 214886)
 
##################################################
## Identification des différentes
## combinaisons possibles :
 
## Toutes les combinaisons d'indices (d'affectation à un des trois vecteurs) :
combinaisons <- combn(rep(1:3, each=length(v)), length(v))
 
dim(combinaisons)
 
## On ne conserve que les combinaisons contenant les trois indices :
combinaisons <- combinaisons[ , apply(combinaisons,
                                      2,
                                      function(x)
                                  {
                                      length(unique(x)) >= 3
                                  })]
 
combinaisons <- unique(combinaisons, MARGIN=2) # Et on supprime les doublons.
 
dim(combinaisons)
 
##################################################
## Différents critères à minimiser...
 
## (1) Carré des écarts à la moyenne (mu) :
mu <- sum(v)/3                          # Moyenne de la somme par vecteur.
 
comb.critere <- apply(combinaisons,
                     2,
                     function(IND, v, mu)
                 {
                     sum(tapply(v, IND, # Somme...
                                function(x, mu)
                            {
                                (sum(x) - mu)^2 # ...du carré des écarts à la moyenne
                            }, mu=mu))
                 }, v=v,  mu=mu)
 
 
## (2) Calcul de la somme((distances entre sommes) au carré) pour chaque combinaison :
comb.critere <- apply(combinaisons,
                     2,
                     function(IND, v)
                 {
                     sum(dist(tapply(v, IND, sum))^2)
                 }, v=v)
## => visiblement équivalent à (1) (à vérifier de façon formelle) mais plus compact !
 
## (3) écart entre min et max :
comb.critere <- apply(combinaisons,
                     2,
                     function(IND, v)
                 {
                     diff(range(tapply(v, IND, sum)))
                 }, v=v)
 
##################################################
## Identification de la combinaison optimale :
 
## Indice de la (première) combinaison qui minimise le critère :
comb.optim <- which.min(comb.critere)
 
## Combinaison correspondante :
combinaisons[ , comb.optim]
 
## Et les sommes correspondantes.
tapply(v, combinaisons[ , comb.optim], sum)

09/05/2011, 11h57
pitipoisson

Erreur !

L'identification des différentes combinaisons possibles paraît faux.
Je vais y jeter un œil un peu plus tard.

Où avais-je la tête ?!

Voilà qui devrait être mieux pour la première partie :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
##################################################
## Identification des différentes
## combinaisons possibles :
library(gtools)
 
## Toutes les combinaisons d'indices (d'affectation à un des trois vecteurs) ; l'ordre d'apparition compte => permutations :
combinaisons <- t(permutations(3, length(v), 1:3, repeats=TRUE))
 
dim(combinaisons)
 
## On ne conserve que les combinaisons contenant les trois indices :
combinaisons <- combinaisons[ , apply(combinaisons,
                                      2,
                                      function(x)
                                  {
                                      length(unique(x)) >= 3
                                  })]
 
dim(combinaisons)

11/05/2011, 19h33
4Ur3L

Waoow, merci bien ! :ccool:

Je regarde ça dès que j'ai un peu de temps.