Problème de partition
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/44px-Max-cut.svg.png)
Cet article est une ébauche concernant l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
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 de S en deux sous-ensembles S1 and S2 tels que la somme des éléments de S1 soit égale à la somme des éléments de S2.
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 de n nombres entiers positifs. On cherche deux sous-multiensembles et de telle sorte que et . On définit comme ceci :
Si est nul, alors la somme des éléments de est égale à la somme des éléments de et une solution au problème existe pour .
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è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 (Polynomial sur une machine Non-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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/87/Fairytale_warning.png/17px-Fairytale_warning.png)
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 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 . 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 et grâce au retour sur trace[1].
Annexes
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Partition problem » (voir la liste des auteurs).
- (nl) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en néerlandais intitulé « Partitieprobleem » (voir la liste des auteurs).
Références
- ↑ Karmarkar et Karp 1982, p. 6
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 .
- (en) Narenda Karmarkar et Richard M Karp, « The Differencing Method of Set Partitioning », Technical Report UCB/CSD 82/113, Université de Californie à Berkeley, Computer Science Division (EECS), (lire en ligne, consulté le )
v · m | |
---|---|
|
Portail de l'informatique théorique