Algorithme des Liens Dansants (Dancing Links)

Présentation

Ce fameux algorithme a été décrit par Donald E. Knuth dans cet article scientifique :  Dancing Links.

Cet algorithme permet de résoudre des problèmes de couverture exacte. Un problème de couverture exacte c’est comme la résolution d’un puzzle, on a un ensemble de pièces qui peuvent aller à plusieurs endroits et on cherche un ensemble de positions qui permettent de recouvrir entièrement le puzzle.

ensemble

Voici un ensemble A = {1,2,3,4,5,6,7}

Résoudre un problème de couverture exacte sur cet ensemble revient à chercher un ensemble de sets qui permet de couvrir tous les éléments une seule et unique fois.

L’unique solution ici est l’union du set rouge et du set bleu.

Principe de l’algorithme

L’algorithme des liens dansants est un algorithme récursif de parcours en profondeur avec backtracking.

Récursif c’est à dire qu’à chaque étape de l’algorithme on réduit le problème en un sous problème qui peut lui aussi être résolus de la même façon.

Backtracking veut dire que l’algorithme attends une réponse de la résolution du sous problème et que si la résolution du sous problème à échouée, il annule les modifications qu’il a fait et sort en erreur.

Le backtracking est souvent utilisé dans une structure en arbre. Ici c’est un arbre de décision sur l’ensemble que l’on rajoute à la solution. Chaque étape de l’algorithme corresponds à un choix d’un ensemble.

arbre_choix

L’algorithme des liens dansants est représenté par des doubles listes chaînées circulaires. Chaque colonne représente un élément de l’ensemble ici de 1 à 7.

Chaque ligne est un set, les couleurs permettent de faire le lien avec le schéma.

probleme01

Une solution du problème de couverture exacte doit être un ensemble de lignes qui, si on les fusionnent, permettent d’avoir qu’un seul carré par colonne. Par exemple, le set rouge et le set vert sont incompatibles car ils ont tous les deux un carré dans la colonne 7.

Vu qu’il existe des sets incompatibles, lorsque l’on choisi de prendre un set, on doit retirer les sets incompatibles avant de relancer une sous instance du problème.

probleme02

Le premier set que nous avons choisi est le rouge. Le seul set incompatible avec le rouge est le vert donc nous devons le retirer. Nous nous retrouvons avec une sous-instance du problème constituée du set cyan et du bleu.

Ces deux sets sont incompatible, il faut choisir entre l’un ou l’autre :

Choix du cyan :

Si l’on choisi le cyan, il faut enlever le bleu et le sous problème correspondant est constitué des colonnes 4 et 6 qui n’ont toujours pas été couverte. Seulement nous n’avons plus de set capable de les couvrir donc c’est une impasse ! Nous sommes arrivés au fond du parcours en profondeur après de multiples choix. Cette suite de choix n’est pas bon donc il faut faire demi-tour. La sous-instance renvoie une erreur à l’instance dessus qui va essayer de faire un autre choix pour tester si il peut mener à une solution.

probleme03

Choix du bleu :

Si l’on choisi le bleu, il faut enlever le cyan qui est incompatible. Le sous problème est vide ! C’est à dire qu’il n’y a plus de colonne à couvrir car elles ont toutes été couvertes ! La sous-instance vient de trouver une solution et elle va renvoyer la nouvelle à l’instance du dessus qui va faire pareils jusqu’en haut afin d’enregistrer la liste des choix qui ont menés à la réponse.

probleme04

Nous comprenons facilement que cet algorithme va parcourir entièrement l’arbre des décisions jusqu’à trouver une solution. Comme cet arbre peut être très grand, il est important de trouver une façon de converger le plus rapidement possible vers une solution afin de ne pas avoir à explorer tout l’arbre. De plus il est important de faire les bons choix le plus rapidement possible car c’est les bons choix les plus en haut de l’arbre qui supprime le plus de possibilités à explorer.

L’algorithme des liens dansants permet de faire ces choix ! En effet, il est plus avantageux de commencer à explorer des solutions qui sont forcement ou qui ont beaucoup de chance d’être dans la solution finale. Continuons avec notre exemple:

Il existe des éléments de l’ensemble qui sont très contraints c’est à dire qu’il existe peu de sets les contenants. C’est le cas ici des nœuds 3 et 5. Ces nœuds ne font partis que du set rouge ! Si il existe une solution au problème de couverture exacte, le set rouge fait forcement parti de la solution. Il est bête de choisir le set vert en premier choix vu qu’il est incompatible avec le rouge qui est forcement une solution …

A chaque instance du problème, on choisit de travailler sur la colonne avec le plus de contraintes donc le minimum de carrés. Ce choix permet de converger le plus rapidement possible vers la solution en faisant les choix qui ont le plus de chance d’être bon 🙂

Il reste une question … Comment faire du backtracking simplement ? Chaque instance doit garder en mémoire le choix qu’elle a fait et les sets incompatibles qu’elle a supprimée … Afin de faire celà simplement la structure des doubles listes chaînées circulaire est parfaite !

couvrir

Le double chaînage permet de garder en mémoire les relations car l’élément du maillon n’est pas supprimé comme d’habitude … Il n’est plus visible par la colonne mais encore par la ligne. De plus je ne l’ai pas dis mais chaque maillon garde en mémoire un pointeur vers sa colonne.

Utilisation de l’algorithme

Les problèmes de couverture exacte sont nombreux et beaucoup de problèmes peuvent être ramenés à ces problèmes.

Par exemple un puzzle avec des pentominos comme tetris, il y a une colonne pour chaque pièce ainsi qu’une colonne par case. Une ligne doit prendre une pièce et l’ensemble des cases couvertes par la pièce. On met autant de lignes que de possibilités de placer la pièce dans le puzzle. On fait ça pour toutes les pièces. L’algorithme des liens dansants va trouver un ensemble de lignes qui permet d’avoir toutes les pièces utilisées pour couvrir toutes les cases en ne chevauchant pas les pièces c’est à dire une solution du puzzle !