Problème De La Couverture Exacte

Ce problème est général et permet, par exemple, de calculer une couverture (ou pavage) d'un ensemble de cellules par des pentominos : chaque cellule doit être couverte par un et un seul pentominos. Il permet aussi de résoudre un Sudoku ou le problème des huit reines. C'est un problème d'optimisation combinatoire NP-complet qui fait partie des 21 problèmes NP-complets de Karp.

Cet article ne cite pas suffisamment ses sources (novembre 2022).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

L'algorithme X de Donald Knuth trouve toutes les solutions au problème de couverture exacte. Cet algorithme est nommé DLX quand il est implémenté en utilisant la structure de données des dancing links.

Étant donné un ensemble U et une collection ${\displaystyle {\mathcal {S}}}$  de sous-ensembles de U, une couverture exacte de U est une sous-collection ${\displaystyle {\mathcal {S}}^{*}}$  de ${\displaystyle {\mathcal {S}}}$  tel que tout élément de U est élément d'exactement un des ensembles de ${\displaystyle {\mathcal {S}}^{*}}$ . En d'autres termes, une couverture exacte de U est une sous-collection ${\displaystyle {\mathcal {S}}^{*}}$  de ${\displaystyle {\mathcal {S}}}$  qui est une partition de U : les ensembles éléments de ${\displaystyle {\mathcal {S}}^{*}}$  sont disjoints deux à deux, et leur union est U.

Le problème de la couverture exacte est le problème de décider s'il existe ou non une couverture exacte pour un ensemble U et une collection ${\displaystyle {\mathcal {S}}}$  de sous-ensembles de U. Ce problème est NP-complet ; et ce même si chaque sous-ensemble dans ${\displaystyle {\mathcal {S}}}$  contient exactement 3 éléments ; cette restriction du problème est connu sous le nom de couverture exacte par 3-ensembles, et est souvent abrégé en X3C. Le problème de la couverture exacte est un exemple de problème de satisfaction de contraintes.

Exemple 1

Soit U = {0, 1, 2, 3, 4} et soit ${\displaystyle {\mathcal {S}}}$  = {E, I, P} la collection de trois ensembles suivants :

• E = {0, 2, 4} ;
• I = {1, 3} ;
• P = {2, 3}.

Alors, la sous-collection ${\displaystyle {\mathcal {S}}^{*}}$  = {E, I} est une couverture exacte. En revanche, {E, P} n'est pas une couverture exacte : une raison suffisante est que 1 n'est contenu ni dans E ni dans P, une autre raison suffisante est que 2 est contenu à la fois dans E et P.

Exemple 2

 

Soit U = {1, 2, 3, 4, 5, 6, 7} un ensemble de 7 éléments et soit ${\displaystyle {\mathcal {S}}}$  = {A, B, C, D, E, F} une collection de 6 sous-ensembles de U :

• A = {1, 4, 7} ;
• B = {1, 4} ;
• C = {4, 5, 7} ;
• D = {3, 5, 6} ;
• E = {2, 3, 6, 7} ; et
• F = {2, 7}.

Alors, la sous-collection ${\displaystyle {\mathcal {S}}^{*}}$  = {B, D, F} est une couverture exacte de U, puisque chaque élément est contenu dans exactement un des ensembles B = {1, 4}, D = {3, 5, 6}, ou F = {2, 7}.

De plus, {B, D, F} est la seule couverture exacte, comme le démontre l'argument suivant : Une couverture exacte doit couvrir 1 et A et B sont les seuls ensembles contenant 1, ainsi une couverture exacte doit contenir A ou B, mais non les deux. Si une couverture exacte contient A, alors elle ne contient ni B, C, E, ou F, comme chacun de ces ensembles ont au moins un élément en commun avec A. Alors D est le seul ensemble restant qui soit une partie de la couverture exacte, mais la collection {A, D} ne couvre pas l'élément 2. En conclusion, il n'existe pas de couverture exacte contenant A. D'un autre côté, si une couverture exacte contient B, alors elle n'inclut ni A ni C, comme chacun de ces ensembles ont au moins un élément en commun avec B. Alors D est le seul ensemble restant qui contient 5, donc D doit être une partie de la couverture exacte. Si une couverture exacte contient D, alors elle ne contient pas E, comme D et E ont les éléments 3 et 6 en commun. Alors F est le seul ensemble restant qui soit une partie de la couverture exacte, et la collection {B, D, F} est vraiment une couverture exacte. Voir l'algorithme X de Knuth pour une version de cet argument basée sur une matrice.

Dans le problème de couverture exacte, il y a deux deux types d'objets. Des éléments d'une part, par exemple 1, 2, 3, 4, 5, 6, 7. Et une collection de sous-ensembles de U d'autre part. En fait, la nature des objets (élément, ou sous-ensemble) n'est pas importante. On donne ici des représentations alternatives qui montrent que la nature des objets n'est pas importante.

Représentation matricielle

Soit U = {x₁, x₂, ..., x_n} est un univers fini de n éléments et ${\displaystyle {\mathcal {S}}}$  = {S₁, S₂, ..., S_m} est une collection finie de m ensembles. Le problème de la couverture exacte peut être représenté comme une matrice m×n contenant seulement des 0 et des 1 de la façon suivante. La i-ème ligne de la matrice représente le i-ème ensemble S_i et la j-ème colonne de la matrice représente le j-ème élément x_j. L'entrée de la matrice dans la i-ème ligne et la j-ème colonne est 1 si l'ensemble S_i contient l'élément x_j; l'entrée est 0 sinon.

Étant donné une telle matrice, une couverture exacte est une sélection de lignes telles que chaque colonne possède un 1 dans exactement une des lignes sélectionnées. En d'autres termes, une couverture exacte est une sélection de lignes dont la somme est une ligne qui ne contient que des 1.

Retour sur l'exemple 2

Si dans l'exemple 2 ci-dessus, nous représentons les 6 ensembles A, B, C, D, E et F de ${\displaystyle {\mathcal {S}}}$  sous forme de lignes et les 7 éléments dans U = {1, 2, 3, 4, 5, 6, 7} sous forme de colonnes, alors le problème de la couverture exacte est représenté par la matrice 6×7 :

Elements Sous-ensembles	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
B	1	0	0	1	0	0	0
C	0	0	0	1	1	0	1
D	0	0	1	0	1	1	0
E	0	1	1	0	0	1	1
F	0	1	0	0	0	0	1

On met un 1 dans une case quand l'élément appartient au sous-ensemble, et 0 sinon. Par exemple, 4 appartient à C d'où le 1 dans la cellule à la ligne C et colonne 4. Par contre, 3 n'est pas dans C d'où le 0 dans la cellule à la ligne C colonne 3. La sélection ${\displaystyle {\mathcal {S}}^{*}}$  = {B, D, F} de lignes est une solution de ce problème de couverture exacte :

Elements Sous-ensembles	1	2	3	4	5	6	7
B	1	0	0	1	0	0	0
D	0	0	1	0	1	1	0
F	0	1	0	0	0	0	1

Si on somme les trois lignes B, D, F on obtient :

Graphe biparti

 

On peut construire un graphe biparti de la façon suivante. Les sommets du paquet de gauche sont les sous-ensembles A, B, C, D, E, F. Les sommets du paquet de droite sont les éléments 1, 2, 3, 4, 5, 6, 7. On trace une arête entre un sous-ensemble e et un élément x si x appartient à e. Par exemple, B = {1, 4}, et donc on a une arête entre B et 1, et entre B et 4.

L'objectif est de sélectionner un sous-ensemble d'arêtes de façon que chaque élément soit touché une et une seule fois. Dans l'exemple, 1 est touché une et une seule fois car l'arête B-1 est sélectionnée.

Relation abstraite

Bien que le problème standard de la couverture exacte implique une collection ${\displaystyle {\mathcal {S}}}$  de sous-ensembles d'un univers U, la structure du problème ne dépend pas de la présence de sous-ensembles contenant des éléments. On peut définir un problème de couverture exacte abstrait avec deux ensembles : un ensemble Y représente l'univers U, et l'ensemble X est un ensemble abstrait qui représente la collection ${\displaystyle {\mathcal {S}}}$ . De plus, on se donne une certaine relation binaire R entre X et Y. La relation R s'interprète intuitivement comme suit : (x, y) dans R se lit "x contient y". La relation inverse R^-1 s'interprète intuitivement comme suit : (y, x) dans R^-1 se lit "y appartient à x".

Étant donné un ensemble X, un ensemble Y, et une relation binaire R entre X et Y, une couverture exacte (généralisée) est un sous-ensemble X* de X tel que chaque élément de Y est R^-1-relié à exactement un élément de X*.

En général, R^-1 restreinte à Y×X* est une fonction, c.-à-d., chaque élément Y est R^-1-relié à exactement un élément de X* : l'unique élément de X* qui « couvre » l'élément particulier de Y.

De plus, si R est totalement gauche, c.-à-d., si chaque élément de X est R-relié à au moins un élément de Y, alors R^-1 restreinte à Y×X* est surjective. (La condition dans le problème généralisé que R est totalement gauche correspond à la condition dans le problème standard que chaque ensemble dans ${\displaystyle {\mathcal {S}}}$  est non vide. Cela ne fait pas de différence si un ensemble vide est une partie d'une couverture ou non.)

Dans la représentation matricielle du problème généralisé, la relation R est représentée par une matrice, les éléments de X sont représentés par les lignes de la matrice, et les éléments de Y sont représentés par les colonnes de la matrice. Alors, comme dans le problème standard, une couverture exacte (généralisée) est une sélection de lignes telles que chaque colonne possède 1 dans exactement une des lignes sélectionnées.

Le problème standard est un cas particulier du problème généralisé dans lequel l'ensemble X est une collection ${\displaystyle {\mathcal {S}}}$  d'ensembles, l'ensemble Y est un univers U d'éléments, et la relation binaire R est la relation « contenue » entre les ensembles et les éléments. Alors R^-1 restreinte à Y×X* est une fonction des éléments vers les ensembles précisant l'unique ensemble dans la couverture qui contient l'élément précisé. De plus, si R est totalement gauche, c.-à-d. si aucun ensemble n'est vide, alors R^-1 restreinte à Y×X* est une fonction surjective, c.-à-d. chaque élément dans la couverture contient au moins un élément.

Problème de l'ensemble intersectant

On rappelle la matrice de l'exemple 2.

La version matricielle montre que la nature des objets n'est pas importante. Quitte à renommer 1, 2, 3, 4, 5, 6, 7 en A, B, C, D, E, F, G, et renommer A, B, C, D, E, F en 1, 2, 3, 4, 5, 6 on obtient :

On peut alors considérer l'ensemble X = {1, 2, 3, 4, 5, 6} de 6 éléments et la collection Y = {A, B, C, D, E, F, G} de 7 ensembles :

• A = {1, 2}
• B = {5, 6}
• C = {4, 5}
• D = {1, 2, 3}
• E = {3, 4}
• F = {4, 5}
• G = {1, 3, 5, 6}

Comme dans l'exemple 2, une solution consiste à sélectionner les 2^e, 4^e et 6^e lignes de la matrice :

	A	B	C	D	E	F	G
2	1	0	0	1	0	0	0
4	0	0	1	0	1	1	0
6	0	1	0	0	0	0	1

Mais à la différence de l'exemple 3, l'interprétation ici montre que la solution est l'ensemble des éléments X* = {2, 4, 6} tel que chaque ensemble A, B, C, D, E, F, G dans Y contient exactement un élément de X* :

• A = {1, 2}
• B = {5, 6}
• C = {4, 5}
• D = {1, 2, 3}
• E = {3, 4}
• F = {4, 5}
• G = {1, 3, 5, 6}

En d'autre termes, la solution est un ensemble intersectant exact. Les problèmes de la couverture exacte et les problèmes d'ensemble intersectant exact sont duaux l'un de l'autre, c.-à-d. essentiellement les mêmes.

L'algorithme X de Knuth est un algorithme récursif, non déterministe, de parcours en profondeur, en force brute qui trouve toutes les solutions du problème de la couverture exacte.

Les liens dansants (en) (en anglais Dancing Links), communément connus sous le nom DLX, est la technique suggérée par Knuth pour implémenter de manière efficace son algorithme X sur un ordinateur. Les liens dansants utilisent la représentation matricielle du problème. Ils implémentent la matrice comme une série de listes doublement liées de 1 de la matrice : chaque élément 1 possède un lien vers le 1 au-dessus, en dessous, à gauche et à droite de lui-même.

Le problème de la couverture exacte est connu comme étant NP-complet.

Beaucoup de problèmes algorithmiques peuvent être réduits au problème de la couverture exacte. Ainsi, ils peuvent alors être résolus avec des techniques comme les liens dansants. Par exemple, le problème de pavage d'une surface donnée avec des pentominos, le problème des huit reines, et la résolution des Sudokus peuvent tous être vus comme des problèmes de la couverture exacte et être résolus avec les liens dansants.

Pavage de pentominos

Le problème de pavage d'une surface donnée avec des pentominos peut être vu comme un problème de la couverture exacte. Il s'agit aussi de l'exemple donné par Donald Knuth quand il expose les dancing links. On considère un échiquier 8x8 dans lequel on enlève le carré 2x2 central. On obtient l'ensemble de cellules suivants :

Si l'on peut utiliser plusieurs fois le même pentomino, on peut utiliser la formalisation suivante. On prend l'ensemble U est l'ensemble de ces cellules. Puis la collection ${\displaystyle {\mathcal {S}}}$  contient les sous-ensembles de cellules qui ont la forme d'un pentomino. Autrement dit, un sous-ensemble de ${\displaystyle {\mathcal {S}}}$  correspond à un placement possible d'un pentomino dans U. La figure ci-dessus montre un pavage de U avec des sous-ensembles de ${\displaystyle {\mathcal {S}}}$ . Un tel pavage est une sous-collection ${\displaystyle {\mathcal {S}}^{*}}$ .

Si l'on demande à ce que chaque pentomino soit utilisé, une et une seule fois, on utilise cette formalisation. On note les pentaminos par F I L P N T U V W X Y Z. L'ensemble U est alors l'ensemble des cellules et l'ensemble des pentaminos : U = {11, 12, 13, ... 87, 88, F, I, L, P, N, T, U, V, W, X, Y, Z}.

Les sous-ensembles ${\displaystyle {\mathcal {S}}}$  correspondent à des positions prises par un certain pentomino ainsi que le pentamino lui-même :

• {F, 12, 13, 21, 22, 32}
• {F, 13, 14, 22, 23, 33}
• …
• {I, 11, 12, 13, 14, 15}
• {I, 12, 13, 14, 15, 16}
• …
• {L, 11, 21, 31, 41, 42}
• {L, 12, 22, 32, 42, 43}
• …

Voici une des solutions obtenus en prenant ces sous-ensembles là qui couvrent chaque élément de U une seule fois :

• {I, 11, 12, 13, 14, 15}
• {N, 16, 26, 27, 37, 47}
• {L, 17, 18, 28, 38, 48}
• {U, 21, 22, 31, 41, 42}
• {X, 23, 32, 33, 34, 43}
• {W, 24, 25, 35, 36, 46}
• {P, 51, 52, 53, 62, 63}
• {F, 56, 64, 65, 66, 75}
• {Z, 57, 58, 67, 76, 77}
• {T, 61, 71, 72, 73, 81}
• {V, 68, 78, 86, 87, 88}
• {Y, 74, 82, 83, 84, 85}

Cette solution correspond au pavage suivant :

 

Le problème des huit reines

Le problème des huit reines est un exemple de problème de la couverture exacte.

Sudoku

 

On considère ici la variante standard du Sudoku 9×9. On considère une grille de taille 9×9. Le but est d'écrire un nombre entre 1 et 9 dans chaque cellule tout en satisfaisant ces quatre sortes de contraintes suivantes :

Ligne-Colonne : Chaque cellule (qui est l'intersection d'une ligne et d'une colonne) doit contenir exactement un nombre.
Ligne-Nombre : Chaque ligne doit contenir chacun des 9 nombres exactement une seule fois.
Colonne-Nombre : Chaque colonne doit contenir chacun des 9 nombres exactement une seule fois.
Boîte-Nombre : Chaque boîte doit contenir chacun des 9 nombres exactement une seule fois.

Bien que la première contrainte semble triviale, il est cependant nécessaire de s'assurer qu'il n'y aura qu'un seul nombre par cellule.

La résolution d'un Sudoku peut se voir un problème d'ensemble intersectant qui est équivalent à un problème de couverture exacte (voir section problème d'ensemble intersectant). D'une part on se donne les éléments suivants : R1C1#1, R1C1#2, …, R9C9#9. L'élément RiCj#k signifie qu'il y a écrit le nombre k dans la cellule à la ligne i et la colonne j. Par exemple, R2C3#6 signifie qu'il y a écrit un 6 dans la case à la ligne 2 et la colonne 3. Comme il y a 9 lignes, 9 colonnes et 9 nombres différents, il y a 9×9×9 = 729 éléments.

Les contraintes vont elles être représentés par des sous-ensembles d'éléments.

Dans les variantes standard d'un Sudoku 9×9, il existe quatre sortes d'ensembles de contraintes correspondant aux quatre sortes de contraintes :

Ligne-Colonne : Par exemple, l'ensemble de contraintes pour la ligne 1 et la colonne 1, qui peut être étiquetée R1C1, contient les 9 éléments pour la ligne 1 et la colonne 1 mais avec des nombres différents :
R1C1 = { R1C1#1, R1C1#2, R1C1#3, R1C1#4, R1C1#5, R1C1#6, R1C1#7, R1C1#8, R1C1#9 }. Vu comme un problème d'ensemble intersectant, une solution contient exactement un élément de R1C1. Cet élément indique quel nombre est inscrit dans la case (1, 1).

Ligne-Nombre : Par exemple, l'ensemble de contraintes pour la ligne 1 et le nombre 1, qui peut être étiquetée R1#1, contient les 9 éléments pour la ligne 1 et le nombre 1 mais de différentes colonnes :
R1#1 = { R1C1#1, R1C2#1, R1C3#1, R1C4#1, R1C5#1, R1C6#1, R1C7#1, R1C8#1, R1C9#1 }.
Une solution contient exactement un élément de R1#1. Cet élément indique où se trouve le 1 dans la ligne 1.
Colonne-Nombre : Par exemple, l'ensemble de contraintes pour la colonne 1 et le nombre 1, qui peut être étiquetée C1#1, contient les 9 éléments pour la colonne 1 et le nombre 1 mais de différentes lignes :
C1#1 = { R1C1#1, R2C1#1, R3C1#1, R4C1#1, R5C1#1, R6C1#1, R7C1#1, R8C1#1, R9C1#1 }. De la même façon, une solution contient exactement un élément de C1#1 qui indique où se trouve le 1 dans la colonne 1.

Boîte-Nombre : Par exemple, l'ensemble de contraintes pour la boîte 1 (dans le coin supérieur gauche) et le nombre 1, qui peut être étiquetée B1#1, contient les 9 éléments pour les cellules dans la boîte 1 et le nombre 1 :
B1#1 = { R1C1#1, R1C2#1, R1C3#1, R2C1#1, R2C2#1, R2C3#1, R3C1#1, R3C2#1, R3C3#1 }. L'unique élément de B1#1 dans la solution indique où se trouve le 1 dans la boîte en haut à gauche.

Puisqu'il existe 9 lignes, 9 colonnes, 9 boîtes et 9 nombres, il existe 9×9=81 ensembles de contraintes ligne-colonne, 9×9=81 ensembles de contraintes ligne-nombre, 9×9=81 ensembles de contraintes colonne-nombre et 9×9=81 ensembles de contraintes boîte-nombre : 81+81+81+81=324 ensembles de contraintes en tout. En bref, on obtient un problème d'ensemble intersectant exact avec 729 éléments et 324 ensembles de contraintes. Le problème peut donc être représenté par une matrice 729×324. Bien qu'il soit difficile de présenter la matrice 729×324 entière, la nature générale de la matrice peut être vue à partir de plusieurs captures :

Notons que l'ensemble des éléments RxCy#z peut être arrangé comme un cube 9×9×9 dans un espace à 3 dimensions de coordonnes x, y et z. Ainsi, chaque ligne Rx, colonne Cy, ou nombre #z est une « tranche » 9×9×1 de éléments. Chaque boîte Bw est un « tube » 9x3×3 de éléments. Chaque ensemble de contraintes ligne-colonne RxCy, ensemble de contraintes ligne-nombre Rx#z, ou ensemble de contraintes colonne-nombre Cy#z est une « bande » 9x1×1 de éléments. Chaque ensemble de contraintes boîte-nombre Bw#z est un « carré » 3x3×1 de éléments. Et chaque élément RxCy#z est un « mini-cube » 1x1×1 consistant en une unique élément. De plus, chaque ensemble de contraintes ou éléments est l'intersection des ensembles de composants. Par exemple, R1C2#3 = R1 · C2 · #3, où "·" désigne l'ensemble d'intersection.

D'autres variations de Sudoku ont des nombres différents de lignes, colonnes, nombres et/ou différentes sortes de contraintes. Ils peuvent ils peuvent être vus comme des problèmes d'ensembles intersectants exacts, avec d'autres éléments et sous-ensembles.

Le problème de la couverture exacte a été prouvé NP-complet par une réduction à partir de celui de la coloration de graphe.