Le problème du compactage de tables consiste à trouver les recoupements maximums dans des tables aléatoires, c'est-à-dire des tables qui permettent en fonction de conditions initiales de donner une liste coefficientée de résultats possibles. Par exemple, dans un jeu qui ressemblerait aux dames avec des pions rouges et bleus et un dé à six faces, il pourrait y avoir une table qui nous dit que sur un jet de dé, si nous avons un pion bleu qui arrive sur un pion rouge, sur un 1, les deux sont éliminés, sur un 2 ou un 3, le pion rouge reste et sinon, le pion bleu prend la place ; alors que si un pion rouge arrive sur un bleu, les résultats 1 à 4 donnent le pion rouge vainqueur et 5 et 6 le pion bleu. Le compactage dans le cas précédent consisterait à dire qu'on lance un dé, qu'on garde la table comme elle est pour le premier cas, que l'on ajoute +2 dans le deuxième cas, et que sur un résultat de 7 ou 8 c'est le pion rouge qui gagne.
Nous avons montré (avec Jean-Yves Moyen que le problème est NP-complet dans le cas général, et étudié certaines des restrictions du problème.
Autour de JAC 2008
Cette publication dans JAC 2008 (Journées Automates Cellulaires, le titre a été forcé en français pour faire penser à Jacques Mazoyer) était un peu limite, car assez hors-sujet : pas de mention d'automate cellulaire, juste un automate probabiliste. Ceci dit, le problème a intéressé plusieurs personnes lors de l'exposé, et une application à la programmation d'automates a même été suggérée. J'ai fait mon propre commentaire de la conférence agrémenté de photographies.
Autour de cet article
Le sujet de cet article est tiré de constatations que j'ai faite pendant des parties de wargame. Les tables utilisées dans ces jeux donnent souvent des résultats croissants en fonction d'un jet de dé ; plus on fait, mieux c'est. À cause de la diversité des situations, il y a souvent des modificateurs (si on plus de tanks, on rajoute 2 ; si on a de l'aviation, on rajoute aussi 2 au jet de dé ; si on a les deux, on rajoute 4). Et des fois apparaissent dans les tables des résultats plus faibles dans le haut que dans le bas. Ce qui s'explique par le fait que ce qui compte du point de vue du jet de dé, ce n'est pas le résultat précis obtenu, mais la probabilité de l'obtenir. Donc notamment la différence entre la ligne ajoutée par le modificateur (ou les lignes) et les lignes qu'on ne peut plus atteindre (par exemple, si le résultat 1 signifie un échec total de l'attaque, un bonus de +1 permet de ne pas avoir d'échec total, et c'est déjà un avantage, même si le résultat maximal+1 n'est qu'un échec partiel). Nous nous sommes aperçus avec Jean-Yves qu'en construisant une telle table, le problème était assez complexe. De fait, il est NP-complet. Je remercie d'ailleurs encore une fois Pierre Borgnat pour nous avoir expliqué ce particularisme de la table d'assaut d'Europa Universalis.
Le résultat essentiel
Comme expliqué en introduction et dans les transparents de l'exposé, il s'agit en fait d'une variante du problème du supermot : étant donné une collection de mots (ici, tous de la même longueur), il s'agit de trouver le plus petit mot qui contient au moins une fois de façon contiguë chacun des mots de la collection. Par exemple, si je prends les mots aabc, abbb et abcc, le mot bbabcc est une réponse correcte au problème puisque les trois mots apparaissent.
Le problème est NP-complet (donc difficile à résoudre). Il est aussi #P-complet, ce qui signifie que si on sait compter le nombre de solutions de ce problème, on sait aussi compter le nombre de solutions de beaucoup d'autres problèmes. La réduction est faite depuis le problème du chemin hamiltonien.
Les restrictions restent NP-complètes dès que l'on garde des mots d'au moins trois lettres. Lorsque l'on a seulement deux lettres (pile ou face, en quelque sorte), il existe une méthode polynomiale pour résoudre le problème (basée sur le chemin eulérien).
Un problème ouvert intéressant est apparu lors de la rédaction de cet article. Il y a \(\ell+k-1\choose\ell\) mots possibles de \(k\) lettres de longueur \(\ell\). On pourrait donc imaginer placer ses mots les uns à la suite des autres en passant de l'un à l'autre par une seule lettre. Étonnament, ce n'est pas possible. La longueur du plus petit mot contenant une permutation de tous les mots de \(k\) lettres de longueur \(\ell\) reste donc un mystère.
Les documents
Citer cette publication
Cette publication a été faite dans les actes de la conférence JAC 2008 qui s'est déroulée cette année-là à Uzès (France). On notera que cet article a été mis sous licence CC-BY-ND et insérée automatiquement dans HAL (et normalement aussi dans arXiv).
@InProceedings{dm08,
author = {Jean-Christophe Dubacq and Jean-Yves Moyen},
title = {Study of the NP-completeness of the Compact Table problem},
booktitle = {Proceedings of the First Symposium on Cellular Automata Journ\'{e}es Automates Cellulaires},
pages = {451--464},
year = {2008},
editor = {Bruno Durand},
address = {Moscow},
month = apr,
publisher = {MCCME Publishing House},
isbn = {978-5-94057-377-7}
}