Problème de partition

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 S₁ and S₂ tels que la somme des éléments de S₁ soit égale à la somme des éléments de S₂.

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 ${\displaystyle S}$ de n nombres entiers positifs. On cherche deux sous-multiensembles ${\displaystyle S_{1}}$ et ${\displaystyle S_{2}}$ de telle sorte que ${\displaystyle S_{1}\uplus S_{2}=S}$ et ${\displaystyle E=0}$. On définit ${\displaystyle E}$ comme ceci :

${\displaystyle E=\left|\sum _{x\in S_{1}}x-\sum _{y\in S_{2}}y\right|}$

Si ${\displaystyle E}$ est nul, alors la somme des éléments de ${\displaystyle S_{1}}$ est égale à la somme des éléments de ${\displaystyle S_{2}}$ et une solution au problème existe pour ${\displaystyle S}$.

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

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 ${\displaystyle S}$ 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 ${\displaystyle S}$. 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 ${\displaystyle S_{1}}$ et ${\displaystyle S_{2}}$ 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

1. 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),‎ 1982 (lire en ligne, consulté le 9 juillet 2016)