Algorithme X de Knuth

Carte Commune · n° 479996

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.

Lire sur Wikipédia