Voir la source de Problème de partition

{{ébauche|informatique théorique}}
En [[informatique théorique]], le '''problème de partition''' est le [[problème de décision]] qui, étant donné un [[multiensemble]] ''S'' d'entiers naturels, détermine s'il existe une [[Partition d'un ensemble|partition]] de ''S'' en deux sous-ensembles ''S''<sub>1</sub> and ''S''<sub>2</sub> tels que la somme des éléments de ''S''<sub>1</sub> soit égale à la somme des éléments de ''S''<sub>2</sub>.

On ne connait pas d'algorithme en temps polynomial permettant de trouver une solution exacte rapidement dans tous les cas, c'est un problème [[NP-complet]].

== Énoncé mathématique ==
Une définition formelle du problème de décision est la suivante: Étant donné un [[multiensemble]] <math>S</math> de n nombres entiers positifs. On cherche deux sous-multiensembles <math>S_1</math> et <math>S_2</math> de telle sorte que <math>S_1 \uplus S_2 = S</math> et <math>E = 0</math>. On définit <math>E</math> comme ceci :

<math> E = \left| \sum_{x \in S_1} x -
\sum_{y \in S_2} y \right| </math>

Si <math>E</math> est nul, alors la somme des éléments de <math>S_1</math> est égale à la somme des éléments de <math>S_2</math> et une solution au problème existe pour <math>S</math>.

Par exemple, on peut partitionner le multiensemble {3,1,1,2,2,1} en {1,1,1,2} et {2,3}, puisque la somme de leurs éléments est égale (1 + 1 + 1 + 2 = 5 ainsi que 2 + 3 = 5). Pour le multiensemble {7,3,1,7}, il n'est pas possible de trouver deux sous-multiensembles qui respectent la contrainte.

== NP-complétude ==
Pour prouver que le problème de partition appartient à la classe des [[Problème NP-complet|problèmes NP-complets]], il faut montrer que ce problème est dans NP et qu'il est NP-difficile.
=== Appartenance à NP ===
Un problème est dit NP ([[NP (complexité)|'''P'''olynomial sur une machine '''N'''on-déterministe]]) s'il est possible de vérifier une solution de ce problème efficacement, c'est-à-dire en temps polynomial par rapport à la taille de l'entrée.

Dans le cas de la partition, il existe un algorithme simple qui vérifie si une entrée donnée répond correctement ou pas au problème de partition.

  '''fonction''' verifie_partition(ens1, ens2)
     tailleEns1 = taille(ens1) - 1
     tailleEns2 = taille(ens2) - 1
 
     cptEns1 = 0
     cptEns2 = 0
 
     '''pour''' i = 0 '''à''' tailleEns1
         cptEns1 = cptEns1 + ens1[i]
 
     '''pour''' j = 0 '''à''' tailleEns2
         cptEns2 = cptEns2 + ens2[j]
 
     '''si''' cptEns1 == cptEns2
         '''retourne''' vrai
     '''sinon'''
         '''retourne''' faux

Cet algorithme donne une réponse en temps linéaire par rapport à la taille des deux ensembles donnés en entrée.

=== Appartenance à NP-difficile ===
{{...}}
== Résolution approchée ==
=== Algorithme glouton ===

Pour le problème de partition, l'idée de l'[[algorithme glouton]] est de trier les nombres par ordre décroissant puis de l'ajouter un par un dans l'ensemble « le plus petit », c'est-à-dire l'ensemble dont la somme de ses éléments est minimale.

  '''fonction''' partition(liste_entiers)
     S1 = []
     S2 = []
     tailleListe = taille(liste_entiers) - 1
 
     tri_decroissant(liste_entiers)
 
     '''pour''' i = 0 '''à''' tailleListe
         '''si''' somme_elements(S1) < somme_elements(S2)
             S1.ajouter(liste_entiers[i])
         '''sinon'''
             S2.ajouter(liste_entiers[i])
 
     '''retourne''' (S1, S2)

=== Algorithme de Karmarkar-Karp ===
Un autre moyen de trouver les deux sous-ensembles a été étudié par Karmarkar et Karp en 1982. L'algorithme prend les deux plus grands nombres de l'ensemble <math>S</math> de départ et les remplace par leur différence. L'opération est répétée jusqu'à ce qu'un seul nombre reste dans l'ensemble <math>S</math>. Le remplacement de deux nombres revient à décider que les deux nombres sont mis dans deux sous-ensembles différents, sans déterminer tout de suite quel nombre est mis dans tel ou tel sous-ensemble.

Une fois cet algorithme terminé, il est possible de retrouver les deux ensembles <math>S_1</math> et <math>S_2</math> grâce au [[retour sur trace]]<ref>{{harvsp | Karmarkar | Karp | 1982 | loc=p. 6 |id=kk}}</ref>.

== Annexes ==

{{Traduction/Référence|en|Partition problem|705050077}}
{{Traduction/Référence|nl|Partitieprobleem|40866145}}
=== Références ===
{{Références|colonnes=2}}

=== Bibliographie ===
Cette bibliographie présente quelques ouvrages de référence. Ceux qui ont été utilisés pour la rédaction de l'article sont indiqués par le symbole {{Plume}}.

* {{Article |langue=en |prénom1=Narenda |nom1=Karmarkar |prénom2=Richard M |nom2=Karp |titre=The Differencing Method of Set Partitioning |périodique=Technical Report UCB/CSD 82/113 |année=1982 |lire en ligne=http://digitalassets.lib.berkeley.edu/techreports/ucb/text/CSD-83-113.pdf |consulté le=9 juillet 2016 |éditeur=Computer Science Division (EECS) |lieu=[[Université de Californie à Berkeley]] |id=kk }} {{Plume}}

{{Palette 21 problèmes NP-complets de Karp}}
{{Portail|informatique théorique}}

[[Catégorie:Problème NP-complet|Partition]]