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].

Le problème de couverture exacte consiste à calculer une couverture d'un univers. Plus précisément, on se donne un univers ${\displaystyle {\mathcal {U}}}$ et une collection ${\displaystyle {\mathcal {S}}}$ de sous-ensembles. Il s'agit de sélectionner, si possible, des sous-ensembles de ${\displaystyle {\mathcal {S}}}$ 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 ${\displaystyle {\mathcal {U}}=\{1,2,3,4,5,6,7\}}$, avec la collection d'ensembles ${\displaystyle {\mathcal {S}}=\{A,B,C,D,E,F\}}$ telle que :

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

Une solution consister à sélectionner les sous-ensembles ${\displaystyle B,D,F}$. 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

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 ${\displaystyle M}$ n'est pas vide
2  |  Choisir la première colonne ${\displaystyle c}$ contenant un minimum de 1 (déterministe)
3  |  Choisir une ligne ${\displaystyle \ell }$ telle que ${\displaystyle M_{\ell ,c}=1}$ (non-déterministe)
4  |  Ajouter la ligne ${\displaystyle \ell }$ à la solution partielle
5  |  Pour chaque colonne ${\displaystyle j}$ telle que ${\displaystyle M_{\ell ,j}=1}$
6  |  |  Pour chaque ligne ${\displaystyle i}$ telle que ${\displaystyle M_{i,j}=1}$
7  |  |  |   Supprimer la ligne ${\displaystyle i}$ de la matrice ${\displaystyle M}$
9  |  |  Supprimer la colonne ${\displaystyle j}$ de la matrice ${\displaystyle M}$
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 ${\displaystyle \ell }$ précise conduit à une solution du problème. On crée alors un ensemble de sous-algorithmes qui partent tous de la matrice ${\displaystyle M}$ mais la réduisent par rapport à des lignes ${\displaystyle \ell }$ 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 ${\displaystyle \ell }$ 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 ${\displaystyle c}$, 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 ${\displaystyle c}$ est composée uniquement de 0, on ne peut créer aucune sous-branche dans l'algorithme alors que la matrice ${\displaystyle M}$ n'est pas vide, et on a donc l'échec de l'algorithme sur la branche en cours.

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 ${\displaystyle {\mathcal {S^{*}}}=\{B,D,F\}}$

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.

• (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 », 30 novembre 2000, 432 p. (ISBN 978-0-333-92230-9, lire en ligne), p. 187-214.

• Problème de la couverture exacte

• (en) « Implémentation en C# d'un solveur du problème de couverture exacte »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)} - utilise l'algorithme X et les liens dansants.
• (en) Polycube solver Programme (et code source Lua) pour remplir des boîtes avec des polycubes, utilisant l'algorithme X.
• (en) Article de Donald Knuth sur les Dancing Links.

v · m Donald Knuth
Publications	The Art of Computer Programming The Complexity of Songs (en) Computers and Typesetting Concrete Mathematics Things a Computer Scientist Rarely Talks About (en) Selected papers series (en)
Logiciels	TeX MIXAL MIX MMIX GNU MDK
Polices de caractères	AMS Euler (en) Computer Modern Metafont
Programmation lettrée	WEB CWEB (en)
Algorithmes	Algorithme X de Knuth Algorithme de Knuth-Bendix Algorithme de Knuth-Morris-Pratt Mélange de Knuth Correspondance de Robinson-Schensted-Knuth Trabb Pardo–Knuth algorithm (en)
Autres	Dancing Links (en) Knuth reward check (en) Prix Donald E. Knuth Man or boy test (en) Système quater-imaginaire Nombre surréel -yllion (en) Potrzebie system of weights and measures (en)

• Portail de l'informatique théorique