Problème de la couverture exacte

vignette|Pavage avec des pentominos d'un échiquier dans lequel on a retiré le carré 2x2 central.En informatique théorique, le problème de la couverture exacte (exact cover en anglais) consiste à couvrir un ensemble d'éléments, chaque élément étant couvert par exactement un sous-ensemble. 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 pentomino. 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 This book is a classic, developing the theory, then cataloguing many NP-Complete problems. qui fait partie des 21 problèmes NP-complets de Karp.

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.

Énoncé

Étant donné un ensemble U et une collection de sous-ensembles de U, une couverture exacte de U est une sous-collection de tel que tout élément de U est élément d'exactement un des ensembles de . En d'autres termes, une couverture exacte de U est une sous-collection de qui est une partition de U : les ensembles éléments de 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 de sous-ensembles de U. Ce problème est NP-complet ; et ce même si chaque sous-ensemble dans 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 = {E, I, P} la collection de trois ensembles suivants : E = {0, 2, 4} ; I = {1, 3} ; P = {2, 3}. Alors, la sous-collection = {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 vignette|L'instance de l'exemple 2. Il s'agit de choisir des lignes colorées de façon que tous les éléments 1, 2, 3, 4, 5, 6, 7 soient couverts exactement une fois. Soit U = {1, 2, 3, 4, 5, 6, 7} un ensemble de 7 éléments et soit = {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 = {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.

Représentations 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 = {x1, x2, ..., xn} est un univers fini de n éléments et = {S1, S2, ..., Sm} 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 Si et la j-ème colonne de la matrice représente le j-ème élément xj. L'entrée de la matrice dans la i-ème ligne et la j-ème colonne est 1 si l'ensemble Si contient l'élément xj; 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 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 : {| cellspacing="0" cellpadding="5" border="1" ! ! 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 = {B, D, F} de lignes est une solution de ce problème de couverture exacte : {| cellspacing="0" cellpadding="5" border="1" ! ! 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 : 1 1 1 1 1 1 1

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 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 . 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 à 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 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 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. 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 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 : A B C D E F G 1 1 0 0 1 0 0 1 2 1 0 0 1 0 0 0 3 0 0 0 1 1 0 1 4 0 0 1 0 1 1 0 5 0 1 1 0 0 1 1 6 0 1 0 0 0 0 1 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} {| cellspacing="0" cellpadding="5" border="1"

Comme dans l'exemple 2, une solution consiste à sélectionner les , et de la matrice : {| cellspacing="0" cellpadding="5" border="1" ! !! 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'autres 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.

Rechercher des solutions 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 (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.

Exemples d'applications