Algorithme X de Knuth

L'algorithme X de Donald Knuth est un algorithme récursif non-déterministe (en), de parcours en profondeur et à retour sur trace. Il permet de trouver des[évasif] solutions au problème de la couverture exacte, représenté sous la forme d'une matrice contenant des 0 et des 1. L'objectif est de déterminer un sous-ensemble de lignes tel que le chiffre 1 n'apparaisse dans chaque colonne qu'une et une seule fois. Une implémentation efficace appelée DLX utilise la structure de données des liens dansants[1].

Problème de couverture exacte modifier

Le problème de couverture exacte consiste à calculer une couverture d'un univers. Plus précisément, on se donne un univers   et une collection   de sous-ensembles. Il s'agit de sélectionner, si possible, des sous-ensembles de   de façon que chaque élément de l'univers soit couvert par un et un seul de ces sous-ensembles. Par exemple, considérons l'univers  , avec la collection d'ensembles   telle que :

  •  ;
  •  ;
  •  ;
  •  ;
  •   et
  •  .

Une solution consister à sélectionner les sous-ensembles  . L'algorithme X de Knuth utilise la représentation matricielle suivante. Les colonnes sont les éléments de l'univers. Les lignes sont les sous-ensembles. On place un 1 dans une cellule lorsque l'élément appartient au sous-ensembles. La matrice de l'exemple présenté plus haut est :

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

Principe modifier

L'algorithme X utilise la représentation matricielle du problème de la couverture exacte. On suppose que ladite matrice a été préalablement déterminée. A partir de cette matrice, l'algorithme fonctionne ainsi :

1  Tant que la matrice   n'est pas vide
2  |  Choisir la première colonne   contenant un minimum de 1 (déterministe)
3  |  Choisir une ligne   telle que   (non-déterministe)
4  |  Ajouter la ligne   à la solution partielle
5  |  Pour chaque colonne   telle que  
6  |  |  Pour chaque ligne   telle que  
7  |  |  |   Supprimer la ligne   de la matrice  
9  |  |  Supprimer la colonne   de la matrice  
12 succès

Le non-déterminisme de l'algorithme vient de la ligne 3. En effet, on ne sait pas déterminer si une ligne   précise conduit à une solution du problème. On crée alors un ensemble de sous-algorithmes qui partent tous de la matrice   mais la réduisent par rapport à des lignes   différentes. Cela revient à former un arbre de recherche, avec le problème original à la racine et chaque branche correspondant à un sous-algorithme avec une ligne différente.
En pratique, on calcule la première branche et ses sous-branches si elles existent (principe de parcours en profondeur). En cas d'échec de l'algorithme sur une branche, on remonte d'un niveau et on calcule la branche suivante, c'est-à-dire qu'on prend la ligne   suivante dans la liste des possibilités, et on s'arrête dès la réussite d'une branche, c'est le principe du retour sur trace. Il est aussi possible de continuer les calculs sur toutes les branches pour obtenir l'ensemble des solutions du problème.

Pour le choix de la colonne  , n'importe quelle règle appliquée de manière systématique fonctionnera, mais certaines sont plus performantes que d'autres. Afin de réduire le nombre d'itérations, Knuth suggère de prendre une colonne avec un minimum de 1, comme présenté dans le fonctionnement de l'algorithme, ci-dessus. De plus, toujours pour réduire les calculs, il est clair que si la colonne   est composée uniquement de 0, on ne peut créer aucune sous-branche dans l'algorithme alors que la matrice   n'est pas vide, et on a donc l'échec de l'algorithme sur la branche en cours.

Exemple modifier

 
Arbre de recherche exploré par l'algorithme X. On considère l'élément 1 que l'on essaie de couvrir avec A = {1, 4, 7}. Mais on est bloqué car on ne peut couvrir 2. On le couvre donc avec B = {1, 4}. Il y a alors une unique possibilité pour couvrir 5 : avec D = {3, 5, 6}. Puis unique possibilité pour couvrir 2 : avec F = {2, 7}.

Exécutons l'algorithme sur la matrice suivante.

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

Nous sommes actuellement à la racine de l'arbre de recherche de la solution. On commence la résolution.

Niveau 0
Étape 1 — La matrice n'est pas vide, on n'est donc pas arrivé à une solution.
Étape 2 — La première colonne avec un minimum de 1 est la colonne 1, qui est donc sélectionnée.

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

Étape 3 — Les lignes A et B ont des 1 dans la colonne 1, on lance un sous-algorithme pour chacune de ces deux lignes.

Niveau 1 : ligne A
Étape 4 — On ajoute la ligne A à la solution partielle.
Étape 5 — La ligne A possède des 1 dans les colonnes 1, 4, 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
Étape 6 — La colonne 1 contient des 1 aux lignes A et B ; la colonne 4, aux lignes A, B, C ; la colonne 7, aux lignes A, C, E et F.
On élimine donc les lignes et colonnes susmentionnées.
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
Il reste la matrice réduite suivante, où seule la ligne D et les colonnes 2, 3, 5, 6 restent :
2 3 5 6
D 0 1 1 1
L'algorithme reprend depuis l'étape 1 sur cette nouvelle matrice :
Étape 1 — La matrice n'est pas vide, on n'est donc pas arrivé à une solution.
Étape 2 — La première colonne avec un minimum de 1 est la colonne 2, qui n'en contient aucun. Mais comme il n'y a pas de 1, on ne peut plus réduire la matrice, et cette branche de l'algorithme échoue.
On passe à la ligne suivante du niveau 1 : la ligne B.
Niveau 1 : ligne B
Étape 4 — On ajoute la ligne B à la solution partielle.
Étape 5 — La ligne B possède des 1 dans les colonnes 1 et 4 :
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
Étape 6 — La colonne 1 contient des 1 aux lignes A et B ; la colonne 4, aux lignes A, B et C.
On élimine les lignes et colonnes susmentionnées.
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
Il reste la matrice réduite où seules lignes D, E, F, et les colonnes 2, 3, 5, 6, 7 restent :
2 3 5 6 7
D 0 1 1 1 0
E 1 1 0 1 1
F 1 0 0 0 1
L'algorithme reprend depuis l'étape 1 sur cette nouvelle matrice :
Étape 1 — La matrice n'est pas vide, on n'est donc pas arrivé à une solution.
Étape 2 — La première colonne avec un minimum de 1 est la colonne 5, qui n'en a qu'un. On la sélectionne.
2 3 5 6 7
D 0 1 1 1 0
E 1 1 0 1 1
F 1 0 0 0 1
Étape 3 — La ligne D a un 1 dans la colonne 5, on lance un sous-algorithme sur cette ligne.
Niveau 2 : ligne D
Étape 4 — On ajoute la ligne D à la solution partielle.
Étape 5 — La ligne D possède des 1 dans les colonnes 3, 5 et 6 :
2 3 5 6 7
D 0 1 1 1 0
E 1 1 0 1 1
F 1 0 0 0 1
Étape 6 — La colonne 3 contient des 1 aux lignes D et E ; la colonne 5, à la ligne D ; la colonne 6, aux lignes D et E.
On élimine les lignes et colonnes susmentionnées.
2 3 5 6 7
D 0 1 1 1 0
E 1 1 0 1 1
F 1 0 0 0 1
Il reste la matrice réduite où seule la ligne F et les colonnes 2, 7 restent :
2 7
F 1 1
L'algorithme reprend depuis l'étape 1 sur cette nouvelle matrice :
Étape 1 — La matrice n'est pas vide, on n'est donc pas arrivé à une solution.
Étape 2 — La première colonne avec un minimum de 1 est la colonne 2, qui n'en a qu'un. On la sélectionne.
2 7
F 1 1
Étape 3 — La ligne F a un 1 dans la colonne 5, on lance un sous-algorithme sur cette ligne.
Niveau 3 : ligne F
Étape 4 — On ajoute la ligne F à la solution partielle.
Étape 5 — La ligne F possède des 1 dans les colonnes 2 et 7 :
2 7
F 1 1
Étape 6 — La colonne 2 contient un 1 à la ligne F ; la colonne 7, à la ligne F aussi.
On élimine la ligne et les colonnes susmentionnées.
2 7
F 1 1
La matrice obtenue est vide. Les lignes sélectionnées ont été B, D, F. L'algorithme s'arrête avec la solution  

Implémentations modifier

 
Liens dansants[2].

Les Liens dansants (en) (en anglais Dancing links), plus connus sous le nom DLX, sont une technique suggérée par Knuth pour implémenter de façon efficace l'algorithme X à l'aide d'un ordinateur. Ils utilisent des listes doublement chaînées. Il y a une liste de 1 pour chaque colonne et une liste pour chaque ligne. Chaque 1 de la matrice se retrouve lié à ceux situés au-dessus, en dessous, à gauche et à droite.

Références modifier

  • (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Knuth's Algorithm X » (voir la liste des auteurs).
  • (en) Donald E. Knuth, « Dancing links », dans Jim Davies ; Bill Roscoe et Jim Woodcock, Millennial Perspectives in Computer Science : Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Sir Tony Hoare, Palgrave, coll. « Cornerstones of Computing », , 432 p. (ISBN 978-0-333-92230-9, lire en ligne), p. 187-214.

Voir aussi modifier

Articles connexes modifier

Liens externes modifier