Discussion :

[muse54]

Bonjour,

voila maintenant quelques jours que je bloque sur mon probleme.

J'ai un nombre A, et un tableau de nombre.

Je cherche a atteindre le nombre A en additionnant tout ou une partie des nombres du tableau. Le probleme est que je peux avoir des nombres négatifs, du coup l'algo glouton ne va pas.

Pour exemple , je cherche a atteidre 20, mon tableau contient [4,5,-9,200,-14,12,8, 20, 5 ]

ON peut donc atteindre 20 en faisant : 4 + 5 -14 + 12 + 8 +5 , ou on allant directement a 20 , ou en faisant 12 + 8 ...

La premiere solution trouvé sera la bonne.

Une idée d'algo ?

merci

[foetus]

Une idée d'algo "brute force - naïf" mi en C mi en C++ mi algo:

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
39
40
41
42
struct elt {
    int sum;
    List number_list;
} Elt;
 
 
vector<Elt> tab; // Tableau dynamique ou liste chaînée ou ...
vector<Elt>::Iterator* it = tab.iterator();
 
Elt* new_elt = NULL;
 
int ori_tab[] = {4, 5, -9, 200, -14, 12, 8, 20, 5};
int size = 9 /* or (sizeof(ori_tab) / sizeof(ori_tab[0]) */;
 
int max = 20, tmp_sum = 0, tmp_number = 0, pos = 0;
 
 
for(; pos < size; pos++, it->first()) {
   tmp_number = ori_tab[pos];
 
   if (tmp_number > max) { continue; /* Skip */ }
 
 
   while(it->next()) {
      tmp_sum = it->sum + tmp_number;
 
      if (tmp_sum > max) { continue; /* Skip */ }
 
      if (tmp_sum == max) { /* Found */ }
 
      new_elt = new Elt(it); // Copy
      new_elt->sum += tmp_number;
      new_elt->number_list.add(tmp_number);
 
      tab.add(new_elt);
   }
 
   new_elt = new Elt();
   new_elt->sum = tmp_number;
   new_elt->number_list.add(tmp_number);
   tab.add(new_elt);
}

En gros:
ori_tab -> [4, 5, 200, -9, -14, 12, 8, 20, 5]
tab -> vide

1ière itération: 4
tab vide on ne peut rien faire
On ajoute {4, [4]} dans tab

tab -> [{4, [4]}]


2ième itération: 5
tab contient {4, [4]}
Donc la somme {9, [4, 5]}
On ne retire pas la somme puisque 9 < 20
On ajoute {5, [5]} dans tab

tab -> [{4, [4]}, {9, [4, 5]}, {5, [5]}]


3ième itération: 200
On ne fait rien 200 > 20


4ième itération: -9
tab contient {4, [4]}, {9, [4, 5]}, {5, [5]}
Donc les sommes {-5, [4 -9]}, {0, [4, 5 -9]}, {-4, [5 -9]}
On ne retire pas les sommes puisque -5, 0 et -4 < 20
On ajoute {-9, [-9]} dans tab

tab -> [{4, [4]}, {9, [4, 5]}, {5, [5]}, {-5, [4 -9]}, {0, [4, 5 -9]}, {-4, [5 -9]}, {-9, [-9]}]

Et ainsi de suite....

[foetus]

Je viens de réfléchir et mon algo a (à vue de nez )

• Une complexité de O(2^n - (n + 1))
• Une complexité de O(2^n - 1) en "place mémoire"

Avec n le numéro de l'itération qui commence à 1

C'est monstrueux : pour 10 chiffres on aura déjà au plus 1023 "débuts" de solution

Je me demande s'il ne faut pas passer par un algo génétique

Le dossier qui va bien

[muse54]

Hello,

effectivement la complexité risque de vite exploser. Mais je vois mal comment faire un algo genetique la dessus... d'autant plus que je suis limité par le language qui diot etre VB Access ...

[foetus]

Je pense que VB n'est pas un problème si tu as les tableaux, les structures (ou les simuler je ne connais pas le VB) et les entiers

Je pense à un algo génétique parce que pendant mes études j'ai eu un projet "Découverte Algo Génétique": tu as X chansons de Y minutes et tu dois graver un C.D. de Z minutes au maximum.
La différence: toi c'est "exactement", en supposant que tu es au moins 1 solution dans ta liste de nombre... parce que pour vérifier

Un algo génétique ressemble à cela, mais tu peux trouver des variantes

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
 
struct elt {
    int sum;
    List number_list;
} Elt;
 
 
Procédure algo_génétique
    gen -> un tableau dynamique
    c, childs -> un tableau de 2 individus de type Elt
    nb -> entier, 0
 
    gen = generate_first_generation(N);
 
    do
        while (nb < M) {
            c <- select(g);
 
            childs <- crossover(c, PERCENTAGE_CROSSOVER)
            mutation(childs, PERCENTAGE_MUTATION)
 
            add(gen, childs)
 
            nb <- nb +1;
        }
 
        fitness(gen)
 
        select(gen, N);
    while(XXX)

C'est simple, mais tu vois qu'il y a plein de choses à évaluer, tester réfléchir


La génération de la première génération generate_first_generation:
Il faut choisir N, le nombre d'individus.
Une solution est représentée par une liste d'opérateurs et leur somme (c'est la structure Elt)
Il faut tirer aléatoirement un certain nombre d'opérateurs pour créer un individu.

Mais il y a deux subtilités:

• Pas de redondance des opérateurs (quoique, si dans ta liste il y a 2 fois le même opérateur, il ne faut pas tirer 2 fois la même "case")
• Gérer le fait qu'il y aura des individus en moins parce qu'il ne faut pas dépasser MAX. Peut-être un nombre d'individus minimal.

La sélection select:
On va choisir 2 individus
Regarde sur Internet, il y en a plusieurs sélections:

• Aléatoire
• Par roulette: l'évaluation [ici c'est plus la somme *] d'un individu correspond à un pourcentage, pourcentage utilisé pour le tirage
• Par tournoi: Pour 1 individu, on choisit aléatoirement 2 individus et on choisit le meilleur en fonction de leurs évaluations
• ...

* -> Individu 1 {19, [...]}, Individu 2 {15, [...]}, Individu 3 {3, [...]} -> Somme totale = 19 + 15 + 3 = 37
Pourcentage de tirer l'Individu 1: 19/ 37, l'Individu 2: 15/ 37, l'Individu 3: 3/ 37

Le croisement crossover:
On va croiser 2 individus pour avoir 2 enfants.
En regardant sur Internet, c'est ainsi [peut-être que tu peux faire autre chose]: on a 2 individus, on va échanger une partie du premier avec une partie du deuxième.
Là c'est assez subtil [notamment avec la redondance des opérateurs qu'il faut éviter], et la gestion "si un individu dépasse le max" se fera après pendant la fonction d'évaluation

Exemple: Individu 1 {19, [12, 5, 2]}, Individu 2 {11, [10, 1]}. Enfant 1 {17, [10, 5, 2}}, Enfant 2 {13, [12, 1}}

On peut introduire un pourcentage PERCENTAGE_CROSSOVER [de 0 à 100], à tester: on tire aléatoire un nombre A entre 0 et 100.
Si A < PERCENTAGE_CROSSOVER alors on fait le croisement sinon les enfants sont des copies des parents.

Les mutations mutation:
2 mutations, mais peut-être il y en a d'autres.

La mutation qui échange dans la liste des opérateurs d'un individu 1 ou plusieurs opérateurs avec un autre ou d'autres opérateurs de la liste initiale.
La mutation qui ajoute dans la liste des opérateurs d'un individu 1 ou plusieurs opérateurs pris dans la liste initiale.

Avec la mutation il faut un pourcentage PERCENTAGE_MUTATION, parce que les mutations ne doivent pas se faire souvent.
on tire aléatoire un nombre A entre 0 et 100. Si A < PERCENTAGE_MUTATION, alors on fait la mutation sur les enfants sinon rien.


La question: on fait cela combien de fois? [ou que vaut M]
Soit on croise tous les individus de la génération entre-eux soit seulement la moitié (N/ 2)
À tester


La fonction d'évaluation fitness:
Le truc simple: une règle de trois. Si la somme d'un individu vaut SUM alors fitness = (SUM / MAX)
Il faut gérer les individus qui dépassent le maximum MAX: fitness = 0 // ou un truc de ce style
Peut-être introduire une évaluation plus subtile


La sélection select:
En fait en regardant sur Internet, dans tous les algos que j'ai vu ils maintiennent une population de N individus.
C'est pour cela que croiser que la moitié des individus va faire seulement doubler notre population.

Mais, il y a une subtilité: on ne peut pas maintenir exactement N individus puisque certains peuvent dépasser le maximum MAX.
Sûrement, comme pour la génération de la première génération, maintenir un minimum et au besoin créer de nouveaux individus


La question: on fait cela combien de fois? [ou que vaut XXX]
Soit on arrête si on a atteint le maximum MAX: un individu à une évaluation de 1
Soit X fois, X à choisir
Soit autre chose

[muse54]

Hello, merci pour ta réponse ! J'ai trouvé une astuce qui m'a permis de m'en sortir

[zaza576]

Bonjour,

si ton problème est résolu n'hésite pas à le signaler dans le titre de ce message.
Merci