Je crois pas que ce soit terriblement fondamental, mais bon, une petite explication rapide, pas forcément claire, est de rigueur. Il s'agit de programmation par contrainte (PPC en français, on trouve plus couramment CSP, Contraint Satisfaction Problem).
Il s'agit grosso modo de modéliser un problème par un jeu de variables, pouvant prendre leurs valeurs dans un domaine, et un jeu de contraintes. Résoudre le problème revient alors à trouver des valeurs pour les variables de telle sorte que toutes les contraintes soient satisfaites. Le grand classique des CSP est le problème des reines, où il s'agit de placer 8 reines sur un échiquier de façon à ce qu'aucune ne risque de se faire prendre au coup suivant. On peut facilement identifier les X variables (8 couples, les coordonnées), les contraintes (lignes différentes, diagonales différentes, etc.). On peut alors disposer de tout l'armada algorithmique développé pour les CSP pour résoudre le problème des 8 reines.
La méthode naïve est la méthode de recherche par arbre, où on explore toutes les possiblités. C'est codé en trois minutes, mais vous vous rendrez vite compte que vos enfants, petits-enfants et l'Humanité sera probablement décédée quand vous aurez toutes vos solutions. Pour résoudre ça, on fait appel au "backtracking", c'est à dire qu'au lieu de générer et tester naïvement toutes les possibilités on va vérifier à chaque fois que l'instanciation partielle (par exemple, 4 reines sur 8 seulement) est bien consistante (elle ne viole aucune contrainte). Quand une instanciation partielle devient inconsistante, on backtracke, et on essaye l'autre combinaison. On a donc coupé une bonne partie de notre arbre, et les choses vont beaucoup mieux.
L'idée derrière le DDB (Dependency-Directed Backtracking, ce dont Stallman parlait) est que le backtracking "simple" (backtracking chronologique) explore une grande partie de l'espace de recherche du CSP en redécouvrant à chaque fois les mêmes contradictions. Il suffit pour éviter ça de garder en mémoire une trace des inférences que l'exploration a réussi à mettre en évidence (les dépendances, donc) et les contradictions rencontrées (les "nogoods" dans le papier en question). De là, on peut s'éviter beaucoup de tests inutiles, et plus facilement inférer une solution partiellement consistante lorsqu'on se retrouve bloqué dans un cas d'inconsistance.
Le DDB est une technique très utilisée en programmation par contraintes, et en particulier dans toute la branche de la démonstration automatique, et de l'analyse de preuves.
(Disclaimer: je n'assure pas la clareté ou le sens de mes propos à 2am. Désolé ;-)
[^] # Re: quelqu'un ?
Posté par Manuel Menal . En réponse à la dépêche Interview de Richard Stallman sur KernelTrap. Évalué à 10.
Il s'agit grosso modo de modéliser un problème par un jeu de variables, pouvant prendre leurs valeurs dans un domaine, et un jeu de contraintes. Résoudre le problème revient alors à trouver des valeurs pour les variables de telle sorte que toutes les contraintes soient satisfaites. Le grand classique des CSP est le problème des reines, où il s'agit de placer 8 reines sur un échiquier de façon à ce qu'aucune ne risque de se faire prendre au coup suivant. On peut facilement identifier les X variables (8 couples, les coordonnées), les contraintes (lignes différentes, diagonales différentes, etc.). On peut alors disposer de tout l'armada algorithmique développé pour les CSP pour résoudre le problème des 8 reines.
La méthode naïve est la méthode de recherche par arbre, où on explore toutes les possiblités. C'est codé en trois minutes, mais vous vous rendrez vite compte que vos enfants, petits-enfants et l'Humanité sera probablement décédée quand vous aurez toutes vos solutions. Pour résoudre ça, on fait appel au "backtracking", c'est à dire qu'au lieu de générer et tester naïvement toutes les possibilités on va vérifier à chaque fois que l'instanciation partielle (par exemple, 4 reines sur 8 seulement) est bien consistante (elle ne viole aucune contrainte). Quand une instanciation partielle devient inconsistante, on backtracke, et on essaye l'autre combinaison. On a donc coupé une bonne partie de notre arbre, et les choses vont beaucoup mieux.
L'idée derrière le DDB (Dependency-Directed Backtracking, ce dont Stallman parlait) est que le backtracking "simple" (backtracking chronologique) explore une grande partie de l'espace de recherche du CSP en redécouvrant à chaque fois les mêmes contradictions. Il suffit pour éviter ça de garder en mémoire une trace des inférences que l'exploration a réussi à mettre en évidence (les dépendances, donc) et les contradictions rencontrées (les "nogoods" dans le papier en question). De là, on peut s'éviter beaucoup de tests inutiles, et plus facilement inférer une solution partiellement consistante lorsqu'on se retrouve bloqué dans un cas d'inconsistance.
Le DDB est une technique très utilisée en programmation par contraintes, et en particulier dans toute la branche de la démonstration automatique, et de l'analyse de preuves.
(Disclaimer: je n'assure pas la clareté ou le sens de mes propos à 2am. Désolé ;-)