Problème de la couverture irredondante
Le problème de la couverture irredondante est apparu vers 1950 en électronique numérique. C'est l'origine d'une technique de calcul booléen, facilement adaptable à d'autres optimisations combinatoires s'exprimant en termes de graphes bi-partis ou d'hypergraphes.
Énoncé modifier
Soit un ensemble d'éléments à réaliser (par exemple, des fournitures à se procurer), et une couverture de ces éléments (ou collection de moyens suffisante pour les réaliser : par exemple, une liste suffisante des fournisseurs possibles). On appellera couverture irredondante une (sous-)collection de ces moyens réalisant tous les éléments, et telle qu'aucun moyen retenu n'est superflu, i.e. ne réalise que des éléments déjà réalisés par ailleurs.
Cette couverture existe (c'est au pire la collection donnée), mais n'est pas nécessairement unique. Des considérations de coût permettent alors de passer des couvertures irredondantes aux couvertures minimales : il suffit que toute couverture minimale soit nécessairement irredondante, ce qui est vrai dès que le coût de chaque ensemble de la couverture est strictement positif.
Exemple modifier
Soit U = {1, 2, 3, 4, 5, 6, 7, 8} un jeu de 8 éléments
et soit S = {A, B, C, D, E, F} une collection de 6 ensembles de ces éléments (), avec :
- A = {1, 2, 3} ; B = {4, 5, 6} ; C = {1, 3, 4, 6} ; D = {6, 7} ; E = {7, 8} ; et F = {1, 8}.
Approche algébrique modifier
Posons que 1 = (A+D) exprime la nécessité de garder A ou D pour que 1 soit réalisé.
- À chaque élément est associé une clause booléenne similaire.
- La réalisation de tous les éléments s'exprime par la valeur de la fonction booléenne R =1.2.3.4.5.6.7.8 ;
- Les couvertures irredondantes sont données par la base première de R.
Ici, 1 = A+C+F ; 2 =A ; 3 = A+C ; 4= B+C ; 5 = B ; 6 = B+C+D ; 7 = D+E ; 8 = E+F ; 1.2.3 = (A+C+F).A.(A+C) = A ; 4.5.6 = (B+C).B.(B+C+D)= B ; 7.8 = (D+E).(E+F)= E+DF ; R = 1.2.3.4.5.6.7.8 = AB(E+DF) ; soit finalement R = ABE+ABDF.
Les collections ABE et ABDF, couvertures de U, sont irredondantes, i.e. nécessaires et suffisantes.
- C, qui pouvait sembler le plus utile, n'est finalement jamais nécessaire.
La question d'une solution minimale suppose d'autres informations pour départager ABE et ABDF, ABE étant a priori la plus simple.
Approche tabulaire modifier
Si on doit confronter un ensemble fini de n éléments à réaliser, et une collection couvrante de m ensembles les réalisant tous, alors le problème de la couverture irredondante 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 moyen et la j-ème colonne de la matrice représente le j-ème élément.
L'entrée de la matrice dans la i-ème ligne et la j-ème colonne est 1 si le i-ème ensemble contient le j-ème élément, 0 sinon.
Étant donné une telle matrice, une couverture irredondante est une sélection de lignes telles que chaque colonne possède un 1 dans au moins une des lignes sélectionnées, sans qu'on puisse retirer une ligne de cette sélection.
Pour l'exemple ci-dessus, nous représentons les 6 ensembles dans S = {A, B, C, D, E, F} sous forme de lignes et les 8 éléments de U = {1, 2… 8} sous forme de colonnes, et notre problème de couverture est représenté par une table 6×8.
Ajoutons la ligne "T=", qui indique pour chaque élément le nombre de moyens qui le réalise. Alors :
- chaque élément réalisé par un seul moyen rend ce moyen obligatoire (i.e. commun à toutes les solutions );
- on réduit le problème en ôtant :
- les (colonnes des) éléments réalisés par les moyens obligatoires ;
- les (lignes des) moyens obligatoires ;
- en recalculant T ;
- on peut ensuite choisir pour un élément restant l'un des moyens qui le réalise, supprimer ce moyen et les éléments qu'il réalise etc.
1 2 3 4 5 6 7 8 A 1 1 1 0 0 0 0 0 B 0 0 0 1 1 1 0 0 C 1 0 1 1 0 1 0 0 D 0 0 0 0 0 1 1 0 E 0 0 0 0 0 0 1 1 F 1 0 0 0 0 0 0 1 T= 3 1 2 2 1 3 2 2
Dans le cas présent, 2 est réalisé par le seul moyen de A, qui réalise aussi 1 et 3. 5 est réalisé par le seul moyen de B, qui réalise aussi 4 et 6.
A et B sont obligatoires, réalisent 1, 2, 3, 4, 5, 6, et rendent C inutile.
D'où un problème résiduel : confronter (7, 8) aux ensembles D, E, F.
| 7 | 8 | |
|---|---|---|
| D | 1 | 0 |
| E | 1 | 1 |
| F | 0 | 1 |
| T= | 2 | 2 |
Ce qui laisse le choix entre E et D+F.
On retrouve bien R = AB(D+EF).
Intérêt modifier
De façon générale, cette méthode est utile dans de nombreux problèmes de confrontation moyens/fins, dès lors que les fins (ou éléments) à réaliser sont disjointes.
En termes d'hypergraphes, les éléments correspondent aux points, sommets ou nœuds, et les ensembles aux hyperarêtes.
De même, en termes de graphes bipartis, les éléments correspondent à une partie des sommets, et les ensembles à l'autre partie.
Fonctions logiques modifier
En matière de réduction des fonctions logiques, cette méthode est utilisée comme épilogue des méthodes associant à une fonction logique sa base première, comme la méthode de Quine-Mc Cluskey, la méthode des consensus, ou la méthode de double dualisation.
Elle permet de passer de la base première à des sous-bases irredondantes, sommes les plus simples suffisant à décrire la fonction, en particulier pour des réalisations au moindre coût.
Dans le cas de fonctions f sous-déterminées, on confronte la base première de sup(f), collection des points non nuls de f, aux éléments de inf(f)= (sup(f'))', collection des points p pour lesquels f vaut 1.
Organisation de tournées modifier
Supposons, dans le cas étudié, que U désigne les clients à desservir, et S l'ensemble des tournées envisageables.
Les tournées A et B sont obligatoires (sinon 1 et 5 ne sont pas desservis), donc 1, 2, 3, 4, 5, 6 sont desservis, donc C est inutile. Reste à desservir 7 et 8, soit par une tournée D soit par les tournées E et F. La question de la solution optimale ne se pose qu'à ce stade.
Articles connexes modifier
Référence modifier
- Kuntzmann J., 1968, Algèbre de Boole, Dunod.
