Problème de partition

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 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.

Une définition formelle du problème de décision est la suivante: Étant donné un multiensemble $S$ de n nombres entiers positifs. On cherche deux sous-multiensembles $S_{1}$ et $S_{2}$ de telle sorte que $S_{1}\uplus S_{2}=S$ et $E=0$ . On définit $E$ comme ceci :

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

Si $E$ est nul, alors la somme des éléments de $S_{1}$ est égale à la somme des éléments de $S_{2}$ et une solution au problème existe pour $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

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 $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 $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 $S_{1}$ et $S_{2}$ grâce au retour sur trace^[1].

Problème de partition

NP-complétude

Appartenance à NP

Appartenance à NP-difficile

Résolution approchée

Algorithme glouton

Algorithme de Karmarkar-Karp

Annexes

Références

Bibliographie

Related Articles