Algorithme X de Knuth

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, et, à partir de cette matrice, l'algorithme fonctionne ainsi :

1  Tant que la matrice A n'est pas vide faire
2  | Choisir la première colonne C contenant un minimum de 1 (déterministe);
3  | Choisir une ligne L telle que ALC = 1;
4  | On ajoute la ligne L à la solution partielle;
5  | Pour chaque colonne J telle que ALJ = 1 faire
6  | | Pour chaque ligne I telle que AIJ = 1 faire
7  | | | Supprimer la ligne I de la matrice A;
8  | | Fin
9  | | Supprimer la colonne J de la matrice A;
10 | Fin
11 Fin

Le non-déterminisme de l'algorithme vient de la ligne 3. En effet, on ne sait pas déterminer si une ligne L précise conduit à une solution du problème. On crée alors un ensemble de sous-algorithmes qui partent tous de la matrice A mais la réduisent par rapport à des lignes L 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 L 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 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 C est composée uniquement de 0, on ne peut créer aucune sous-branche dans l'algorithme alors que la matrice A n'est pas vide, et on a donc l'échec de l'algorithme sur la branche en cours.

Considérons un problème de couverture exacte sur 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\}}$.

Soit, sous forme matricielle :

	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 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 :

	2	3	5	6
D	0	1	1	1

L'algorithme reprend depuis l'étape 1 sur cette nouvelle matrice A_A :

É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 :

	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 A_B :

É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 :

	2	7
F	1	1

L'algorithme reprend depuis l'étape 1 sur cette nouvelle matrice A_BD :

É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

Il ne reste qu'une matrice vide:

L'algorithme reprend depuis l'étape 1 sur cette nouvelle matrice A_BD :

Étape 1 — La matrice est vide, on a trouvé une solution : ${\displaystyle \{B,D,F\}}$.

Il n'y a plus de ligne sélectionnée au niveau 3, on remonte au niveau 2.

Il n'y a plus de ligne sélectionnée au niveau 2, on remonte au niveau 1.

Il n'y a plus de ligne sélectionnée au niveau 1, on remonte au niveau 0.

Il n'y a plus qu'une branche à ce niveau, l'algorithme se termine.

Finalement, on a trouvé une solution au problème de couverture exacte défini au début de l'article : ${\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.