Problème de la couverture exacte - Définition
La liste des auteurs de cet article est disponible ici.
Rechercher des solutions
L'algorithme X de Knuth est un algorithme recursif, 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.
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.
