- Probleme de la somme de sous-ensembles
-
Problème de la somme de sous-ensembles
Le problème de la somme de sous-ensembles aussi noté SSP (de l'anglais Subset Sum Problem) est un problème important en complexité algorithmique et en cryptologie. Le problème est le suivant : étant donnés n entiers numérotés de 1 à n, ayant chacun une valeur, existe-t-il un sous-ensemble de ces éléments dont la somme des valeurs est nulle ?
C'est un problème NP-complet et l'un des plus simples à décrire. Le problème de la somme des sous-ensembles peut être vu comme un cas particulier du problème du sac à dos. Un cas particulier du problème de la somme des sous-ensembles est le problème de partition.
Sommaire
Exemple
On considère l'ensemble suivant : { −7, −3, −2, 5, 8}. Le problème admet une solution avec le sous-ensemble {-3, -2, 5} dont la somme est nulle.
On considère maintenant un autre ensemble : { -1, -2, -3}. Il est clair que le problème n'admet pas de solution (la somme est obligatoirement négative). Plus généralement, si tous les nombres sont strictement positifs ou tous les nombres sont strictement négatifs, alors le problème n'admet pas de solution (pour autant que la somme visée doit être nulle).
Généralisation
Le problème de la somme de sous-ensembles peut être généralisé pour toute somme cible s, avec s un entier :
Étant donnés n entiers numérotés de 1 à n, ayant chacun une valeur, existe-t-il un sous-ensemble de ces éléments dont la somme des valeurs est s ?
Algorithmes de solution
Algorithme exponentiel
Algorithme pseudo-polynomial
Algorithme d'approximation
Un algorithme d'approximation peut résoudre la version suivante du problème. Étant donné un ensemble de N nombres x1, x2, ..., xN et un nombre s, retourner
- oui, s'il y a un sous-ensemble dont la somme est s ;
- non, s'il n'y a pas de sous-ensemble dont la somme est entre (1-c)s et s pour un petit c>0 ;
- n'importe quoi, s'il y a un sous-ensemble dont la somme est entre (1-c)s et s, mais aucun dont la somme est s.
Si tous les nombres sont non négatifs, la version approximative du problème de la somme de sous-ensembles se résout en temps polynomial en fonction de N et 1/c.
Références
- T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. MIT Press, 2001. Chapter 35.5, The subset-sum problem.
- Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, ISBN 0-7167-1045-5.
- Portail de la cryptologie
Catégories : Problème NP-complet | Logique mathématique
Wikimedia Foundation. 2010.