Optimisation recherche des combinaisons possibles

[Stan_94]

Bonjour,
à la limite de l'informatique et des mathématiques (probablement d'analyse combinatoire), je vous expose mon problème :
J'ai une table avec n éléments dont chaque élément est une quantité. Le but de mon algorithme est de trouvé rapidement la combinaison des éléments (= somme des quantités) qui me donnera un résultat exact ou le plus proche.
Par exemple : j'ai 7 éléments : 50, 30, 20, 15, 7, 2 et 2 et je veux trouver 90.
Le mieux que je puisse faire c'est 50 + 30 + 7 + 7 + 2 = 91.

J'ai un algorithme qui marche mais prend un temps phénoménale dés que le nombre d'élément devient grand (à partir d'un trentaine ça peux durée des heures)

Quelq'un aurait-il des pistes que je pourrais suivre pour résoudre ça ?
Merci
-----

[invite88ef51f0]

Salut,
Tu n'as que l'addition ?
Personnellement, ce que je ferais, c'est commencer par trier le tableau (avec un algorithme rapide si besoin est).
Ensuite, faire une première opération un peu au pif, c'est pour l'instant mon meilleur résultat. Puis n'essayer que les combinaisons qui font mieux que le meileur résultat, en ne prenant que les nombres suffisamment petits (facile vu que mon tableau est trié).

Dans ton exemple, j'ai 50,30, 20,15, 7, 2, 2.
Premier essai, je fais 50+30+20 (je m'arrête quand je dépasse 90), j'obtiens 100 (ce qui est assez mauvais).
J'essaye ensuite 50 plus 30 mais pas 20 (car ça n'améliorerait pas) plus 15. J'obtiens 95. Je m'arrête avant d'empirer les choses.
J'essaye ensuite 50+30 mais ni 20 ni 15, plus 7 plus 2. J'obtiens 89. Rajouter encore 2 n'améliorerait pas.

Après, j'essaye 50, pas 30 (j'ai tout fait), 20, 15, 2 et 2.
...

L'idée, c'est que le nombre de possibilités croît exponentiellement avec la quantité de nombres. Donc ça devient vite infaisable. Parmi ces possibilités, il y en a qui sont clairement mauvaises et qui ne valent pas le coup d'être essayées (si 50+30+20 est trop loin, alors 50+30+20+15 sera évidemment pire). Donc en introduisant un critère permettant de rejeter les combinaisons inintéressantes, tu réduis énormément l'espace des possibilités.

[danyvio]

L'idée de Coincoin est bonne heuristiquement parlant, mais il faut bien saisir que le plus grand nombre entré dans l'addition ne convient pas forcément.
Donc, si après son premier passage d'algo la solution exacte n'est pas trouvée, il faut réitérer en ignorant ce premier grand nombre
Ex on a 50,30, 27, 20, 9 et veut trouver 66
Au premier passage, le choix de 50+etc. échouera
Mais 30+27+9 réussira.
PS Je suppose que les gens intéressés par "le compte est bon" ont dû se pencher sur ce genre de problème au demeurant très sympa

[invite79d10163]

Bonjour,
je n'ai pas d'algorithmes à donner. Mais ce problème est un problème classique de combinatoire connu sous le nom du "subset sum problem". Tu trouveras certainement quelque chose d'intéressant sur le net à partir de ces mots clés. Pour autant que je sache il y a des algorithmes efficaces pour résoudre ce problème de manière uniquement quasi-optimale ; le problème étant certainement NP-complet.

[A voir en vidéo sur Futura]

[obi76]

Sauf que pour le compte est bon, le nombre de chiffres est limité, les opérations se limitent à 4, le nombre d'opérations différentes à tester est relativement restreint (pour un ordinateur du moins, je l'ai déjà programmé).

[invite88ef51f0]

L'idée de Coincoin est bonne heuristiquement parlant, mais il faut bien saisir que le plus grand nombre entré dans l'addition ne convient pas forcément.

Oui, J'ai présenté en commençant par les plus grands nombres parce que ça faisait moins de possibilités à écrire (on dépassé vite les 90), mais on peut aussi imaginer commencer par les plus petits.
Il restera toujours plein de possibilités à tester (d'où les points de suspension dans mon message précédent), mais ça en fait déjà pas mal d'éliminées.

Sinon, Stan_94, tu codes en quel langage ?

[Stan_94]

Bonjour à tous,
et merci pour ces premières réponses !

Au final, c'est du code ABAP, sous SAP afin d'optimiser le choix de quantité pour répondre à un besoin. Ce n'est donc que des additions.

Ma première approche est celle-ci :
1. tri de la liste par valeur croissante et sommation jusqu'à ce que la somme soit >= au besoin : Ceci me donne le maximum l_max de quantité à additionner
2. tri décroissante + sommation jusqu'à ce que la somme soit >= au besoin --> l_min = nombre mini de combinaison à faire
3. avec ce tri décroissant je fais une boucle pour calculer la somme des combinaisons de N éléments, N variant de l_min à l_max.
Dans ces boucle, j'ai un appel réccurcif à une routine additionnant mes quantités et contrôlant que la somme en cour ne dépasse pas mon besoin. Si oui, je stop sinon je reprend au niveau supérieure et recommance.
Avec mon exemple ça donne :
N = 2 : 50 +30 = 80, <90 donc je stoppe N=2
(stock résultat des fois qu'il n'y ai pas mieux)
N = 3 : on repart du meilleur N = 2 trouvé
50 + 30 + 20 = 100 > 90 donc stockage + test suivant
50 + 30 + 15 = 95 > 90 donc stockage + test suivant
50 + 30 + 7 = 87 < 90 doc stop N = 3
(stock résultat des fois qu'il n'y ai pas mieux)
N = 4 : on repart du meilleur N = 3 trouvé
50 + 30 + 7 + 2 = 89 < 90 doc stop N = 4
(stock résultat des fois qu'il n'y ai pas mieux)
N = 5 : on repart du meilleur N = 4 trouvé
50 + 30 + 7 + 2 + 2 = 91 > 90 donc stockage + test suivant
ici, on a fini la recherche pour N = 5 et on était à la fin de la liste, j'arrête donc tout.
Avec cette exemple, c'est rapide mais avec une trentaine de nombre et N variant de 10 à 19, mon programme se traine lamentablement !!! D'où ma recherche d'un algo plus performant !

Je vais suivre les pistes déjà donnés !
Stan

[invite986312212]

salut,

pour moi c'est un problème de programmation quadratique: il s'agit de minimiser la fonction (a*x-b)^2 sous la contrainte linéaire x=0 ou 1 (a est le vecteur des nombre à additionner, b est la somme à atteindre).

[invite79d10163]

la difficulté étant qu'x est un vecteur de variable binaire. Néanmoins, il y a beaucoup de références sur ce problème.

[acx01b]

salut

tu as au départ i nombres dans ton tableau, b le nombre à atteindre, x(i) le ième nombre du tableau, f(i,b) la solution optimale (somme d'un sous ensemble des i nombres où l'écart à b est minimum)

si on remarque (principe de la programmation dynamique) que
abs(f(i,b)-b) = min (abs(f(i-1,b) -b) , abs(f(i-1,b-x(i)) + x(i) -b) )


f(i-1,b) : somme d'un sous ensemble des i-1 nombres (on a enlevé le premier nombre du tableau) où l'écart à b est minimum

et que b n'est pas trop grand et que tes x(i) sont des entiers alors il est intéressant de faire:

pour tout k : f(0,k) = 0
pour tout j, si k < 0 : f(j,k) = +inf

pour j = 1 à j
pour k = 1 à b
si abs(f(j-1,k)) < abs( f(j-1,k-x(j)) + x(j) )
f(j,k) = f(j-1,k)
sinon
f(j,k) = f(j-1,k-x(j)) + x(j)
fin si
fin pour
fin pour

[acx01b]

il y a une petite erreur: pour tout j, si k < 0 : f(j,k) = k (et non pas +inf)

voici un code en C qui répond 89 pour ton problème :

#include <stdio.h>
#include <stdlib.h>


int main()
{
int x[7] = {50,30,20,15,7,7,2};
int i = 7;
int b = 90;

int nbVal;

nbVal = 2*b-1;

int *f = malloc(sizeof *f * (nbVal+1));
int *f2 = malloc(sizeof *f * (nbVal+1));

int j,k;

for (k = 0; k <= nbVal; k++) f2[k] = 0;

for (j = 0; j < i; j++)
{
for (k = 0; k <= nbVal; k++)
{
if (k >= x[j] && abs(f2[k]-k) > abs(f2[k-x[j]]+x[j]-k))
{
f[k] = f2[k-x[j]] + x[j];
}
else if (abs(f2[k]-k) >= abs(x[j]-k))
{
f[k] = x[j];
}
else
{
f[k] = f2[k];
}
}
for (k = 0; k <= nbVal; k++)
{
f2[k] = f[k];
}
}

printf("%d\n", f[b]);

return 0;
}

[Stan_94]

J'ai regarder les infos concernant le problème de sommation sur un sous-ensemble (NP-complet) et c'est exactement ça. D'ailleur l'algorithme que j'ai pondu correspond à peu près à l'algorithme exacte qui est temps exponentiel ! Dans l'utilisation pratique que j'en fais, il est impossible que la recherche dure plus que quelque minutes ! Je vais regarder l'algorithme pseudo polynomiale est voir ce que ça donne...
En tout cas merci pour les réponses déjà données et pour le code C !

[acx01b]

on est d'accord que l'algo de programmation dynamique que j'ai donné est en temps quadratique O((2*b-1).i)
b nombre à atteindre, i nombre de variables

cet algo marche aussi avec des nombres flottants : il faut alors utiliser un tableau à 2 lignes dans le code que j'ai donné et faire des recherches dichotomiques, finalement ça doit être en O(k.i.log k ) avec k à déterminer (plus petit que !i)

[Stan_94]

Bonjour,
au final, j'ai coupé la poire en 2 dira-t-on, en adoptant un algorithme exacte (programmation dynamique) pour N < 20, ce qui laisse le temps d'exécution raisonable et sinon un algorithme plus rapide basé sur l'algo donné par acx01b.

Encore merci à tout ceux qui ont porté attention à mon problème.