Problème de la couverture exacte

Problème de la couverture exacte

Le problème de la couverture exacte est un problème d'optimisation combinatoire NP-complet qui fait partie des 21 problèmes NP-complets de Karp.

Sommaire

Énoncé

Étant donné un univers U d'éléments et une collection \mathcal{S} d'ensembles, une couverture exacte est une collection de sous-ensembles \mathcal{S}^* de \mathcal{S} telle que tout élément dans U est aussi un élément dans exactement un des ensembles de \mathcal{S}^*.

En d'autres termes, une couverture exacte est une sous-collection \mathcal{S}^* de \mathcal{S} qui est une partition de U : les ensembles dans \mathcal{S}^* sont disjoints et leur union est U.

Étant donné un univers U d'éléments et une collection \mathcal{S} d'ensembles, le problème de la couverture exacte consiste en trouver une couverture exacte \mathcal{S}^* ou bien de déterminer qu'il n'en existe pas.

Le problème de la couverture exacte est un exemple d'un problème de satisfaction de contraintes.

Exemple 1

Soit U = {0, 1, 2, 3, 4, ...} l'univers des entiers naturels et soit \mathcal{S} = {E, I, P} une collection de trois ensembles d'entiers naturels :

Alors, la sous-collection \mathcal{S}^* = {E, I} est une couverture exacte, puisque chaque nombre naturel est soit pair ou impair, mais pas les deux.

Par contre, {E, P} n'est pas une couverture exacte, puisque certains nombres naturels ne sont contenus dans aucun ensemble : par exemple, 1 est ni pair ni premier. De plus, certains nombres naturels sont contenus dans plusieurs ensembles : par exemple, 2 est et pair et premier.

Exemple 2

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

  • 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 \mathcal{S}^* = {B, D, F} est une couverture exacte, 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 ensemble 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 ensemble 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ésentation matricielle

Si \mathcal{S} = {S1, S2, ..., Sm} est une collection finie de m ensembles et U = {x1, x2, ..., xn} est un univers fini de n éléments, alors le problème de la couverture exacte peut être représenté comme une matrice m×n contenant seulement des 0 et des 1. 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.

Exemple 3

Si dans l'exemple 2 ci-dessus, nous représentons les 6 ensembles dans \mathcal{S} = {A, B, C, D, E, F} 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 :

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

Comme dans l'exemple 2, la sélection \mathcal{S}^* = {B, D, F} de lignes est une solution de ce problème de couverture exacte :

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

Généralisations

Bien que le problème standard de la couverture exacte implique une collection \mathcal{S} d'ensembles contenant des éléments dans un univers U, la structure du problème ne dépend pas de la présence d'ensembles contenant des éléments. La même structure existe s'il y a deux ensembles avec une certaine relation binaire entre eux.

É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*. Ici R-1 est l'inverse de R.

En général, R-1 restreinte à Y×X* est une fonction, c.a.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.a.d., si chaque élément de X est R-relié à au moins un élément de Y, alors R-1 restreinte à Y×X* est une fonction 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 \mathcal{S} est non-vide. Évidemment, 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 \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.a.d. si aucun ensemble n'est vide, alors R-1 restreinte à Y×X* est une fonction surjective, c.a.d. chaque élément dans la couverture contient au moins un élément.

Exemple 4

La matrice dans l'exemple 3 ci-dessus peut être réinterprété pour représenter la relation binaire « est contenu dans » entre 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}

La même représentation matricielle comme dans l'exemple 3 s'applique ici, mais elle est étiquetée différemment :

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

Comme dans l'exemple 3, une solution consiste à sélectionner les 2e, 4e et 6e 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 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. Vraiment, les problèmes de la couverture exacte et les problèmes d'ensemble intersectant exact sont duaux l'un de l'autre, c.a.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 liens dansants (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 efficiente 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 plus approfondis

Beaucoup de problèmes peuvent être réduits à des problèmes de la couverture exacte, qui 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 est un exemple de problème de la couverture exacte.

Par exemple, voir le site en anglais Solving Pentomino Puzzles with Backtracking.

Le problème des huit reines

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

Sudoku

Le problème dans les Sudokus est d'assigner une certaine quantité de nombres (ou chiffres, valeurs, symboles) aux cellules (ou carrés) dans une grille tout en satisfaisant certaines contraintes.

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

Ligne-Colonne : Chaque intersection d'une ligne et d'une colonne, i.e, chaque cellule, 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 est un problème de la couverture exacte.

Plus précisément, résoudre un Sudoku est un problème d'ensemble intersectant, ce qui est équivalent à un problème de la couverture exacte (comme dans l'exemple 4 ci-dessus), lorsqu'il est vu comme un problème de sélection de possibilités tel que chaque ensemble de contraintes contient (i.e., est atteint par) exactement une possibilité sélectionnée. Dans la notation ci-dessus pour le problème de la couverture exacte (généralisé), X est l'ensemble des possibilités, Y est un ensemble d'ensembles de contraintes, et R est la relation binaire "est contenu dans".

Chaque assignation possible d'un nombre particulier à une cellule particulière est une possibilité (ou un candidat). Lorsque le Sudoku est joué avec un crayon et un papier, les possibilités sont souvent appelées des marques de crayon.

Dans les variantes standard d'un Sudoku 9×9, dans lequel chacune des cellules 9×9 est assignée un des 9 nombres, il y a 9×9×9 = 729 possibilités. En utilisant une notation évidente pour les lignes, colonnes et nombres, les possibilités peuvent être étiquetées comme ceci : R1C1#1, R1C1#2, …, R9C9#9.

Le fait que chaque sorte de contrainte implique exactement une chose est ce qui fait que le Sudoku est un problème d'ensemble intersectant exact. Les contraintes peuvent être représentées par les ensembles de contraintes. Le problème est de sélectionner les possibilités telles que chaque ensemble de contraintes contient (c.a.d., est atteint par) exactement une possibilité sélectionnée.

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 : Un ensemble de contraintes ligne-colonne contient toutes les possibilités pour l'intersection d'une ligne et d'une colonne particulière, i.e., pour une cellule. Par exemple, l'ensemble de contraintes pour la ligne 1 et la colonne 1, qui peut être étiquetée R1C1, contient les 9 possibilités 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 }.
Ligne-Nombre : Un ensemble de contraintes ligne-nombre contient toutes les possibilités pour une ligne particulière et un 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 possibilités 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 }.
Colonne-Nombre : Un ensemble de contraintes colonne-nombre contient toutes les possibilités pour une colonne particulière et un 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 possibilités 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 }.
Boite-Nombre : Un ensemble de contraintes boite-nombre contient toutes les possibilités pour une boîte particulière et un 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 possibilités 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 }.

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, les variantes standard d'un Sudoku 9×9 est un problème d'ensemble intersectant exact avec 729 possibilités 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 :

Contraintes Ligne-Colonne
R1
C1
R1
C2
R1C1#1 1 0
R1C1#2 1 0
R1C1#3 1 0
R1C1#4 1 0
R1C1#5 1 0
R1C1#6 1 0
R1C1#7 1 0
R1C1#8 1 0
R1C1#9 1 0
R1C2#1 0 1
R1C2#2 0 1
R1C2#3 0 1
R1C2#4 0 1
R1C2#5 0 1
R1C2#6 0 1
R1C2#7 0 1
R1C2#8 0 1
R1C2#9 0 1
Contraintes Ligne-Nombre
R1
#1
R1
#2
R1C1#1 1 0
R1C1#2 0 1
R1C2#1 1 0
R1C2#2 0 1
R1C3#1 1 0
R1C3#2 0 1
R1C4#1 1 0
R1C4#2 0 1
R1C5#1 1 0
R1C5#2 0 1
R1C6#1 1 0
R1C6#2 0 1
R1C7#1 1 0
R1C7#2 0 1
R1C8#1 1 0
R1C8#2 0 1
R1C9#1 1 0
R1C9#2 0 1
Contraintes Colonne-Nombre
C1
#1
C1
#2
R1C1#1 1 0
R1C1#2 0 1
R2C1#1 1 0
R2C1#2 0 1
R3C1#1 1 0
R3C1#2 0 1
R4C1#1 1 0
R4C1#2 0 1
R5C1#1 1 0
R5C1#2 0 1
R6C1#1 1 0
R6C1#2 0 1
R7C1#1 1 0
R7C1#2 0 1
R8C1#1 1 0
R8C1#2 0 1
R9C1#1 1 0
R9C1#2 0 1
Contraintes Boîte-Nombre
B1
#1
B1
#2
R1C1#1 1 0
R1C1#2 0 1
R1C2#1 1 0
R1C2#2 0 1
R1C3#1 1 0
R1C3#2 0 1
R2C1#1 1 0
R2C1#2 0 1
R2C2#1 1 0
R2C2#2 0 1
R2C3#1 1 0
R2C3#2 0 1
R3C1#1 1 0
R3C1#2 0 1
R3C2#1 1 0
R3C2#2 0 1
R3C3#1 1 0
R3C3#2 0 1

La matrice 729×324 complète est disponible sur le site de Bob Hanson (en anglais).

Notez que l'ensemble des possibilités 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 possibilités. Chaque boîte Bw est un « tube » 9x3×3 de possibilités. 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 possibilités. Chaque ensemble de contraintes boîte-nombre Bw#z est un « carré » 3x3×1 de possibilités. Et chaque possibilité RxCy#z est un « mini-cube » 1x1×1 consistant en une unique possibilité.

De plus, chaque ensemble de contraintes ou possibilité est l'intersection des ensembles de composants. Par exemple, R1C2#3 = R1 · C2 · #3, où "·" désigne l'ensemble d'intersection.

Bien que d'autres variations de Sudoku ont des nombres différents de lignes, colonnes, nombres et/ou différentes sortes de contraintes, ils impliquent tous des possibilités et des ensembles de contraintes, et ainsi peuvent être vus comme des problèmes d'ensembles intersectants exacts.

Preuve de la NP-complétude

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

Voir aussi

Liens externes

  • (en) Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, New York, W.H. Freeman, 1979, 25e éd., poche (ISBN 978-0-7167-1045-5) (LCCN 78012361)  A3.1: SP2: EXACT COVER BY 3-SETS (X3C), p. 221.
  • Karl Dahlke, « NP Complete, Exact Cover », Math Reference Project. Consulté le 27 juin 2006

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Problème de la couverture exacte de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Probleme de la couverture exacte — Problème de la couverture exacte Le problème de la couverture exacte est un problème d optimisation combinatoire NP complet qui fait partie des 21 problèmes NP complets de Karp. Sommaire 1 Énoncé 1.1 Exemple 1 1.2 Exemple 2 …   Wikipédia en Français

  • Couverture exacte — Problème de la couverture exacte Le problème de la couverture exacte est un problème d optimisation combinatoire NP complet qui fait partie des 21 problèmes NP complets de Karp. Sommaire 1 Énoncé 1.1 Exemple 1 1.2 Exemple 2 …   Wikipédia en Français

  • Probleme du sac a dos — Problème du sac à dos Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? Le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un …   Wikipédia en Français

  • Problème du sac à dos — Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? En algorithmique, le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • 21 problemes NP-complets de Karp — 21 problèmes NP complets de Karp Les 21 problèmes NP complets de Karp ont marqué une étape importante de l histoire de la théorie de la complexité des algorithmes. Ce sont 21 problèmes réputés difficiles de combinatoire et de théorie des graphes… …   Wikipédia en Français

  • 21 problèmes NP-complets de Karp — Les 21 problèmes NP complets de Karp ont marqué une étape importante de l histoire de la théorie de la complexité des algorithmes. Ce sont 21 problèmes réputés difficiles de combinatoire et de théorie des graphes qui sont réductibles entre eux. C …   Wikipédia en Français

  • 21 problèmes NP complets de Karp — Les 21 problèmes NP complets de Karp ont marqué une étape importante de l histoire de la théorie de la complexité des algorithmes. Ce sont 21 problèmes réputés difficiles de combinatoire et de théorie des graphes qui sont réductibles entre eux. C …   Wikipédia en Français

  • Liste de problèmes NP-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problème de décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive. La …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”