From Implicit to Explicit Pavings
Résumé
A combinatorial search can either be performed by using an implicit search tree, where an initial state is recursively transformed until some goal state is reached, or by using an explicit search tree, where an initial tree structure containing the root state is iteratively expanded until the leaves match the set of goal states. This paper proposes an exploratory study aimed at showing that explicit search trees can play a distinguished role in the field of numerical constraints. The first advantage of an explicit search is expressiveness: we can write new algorithms or reformulate existing ones in a simple and unified way. The second advantage is efficiency, since an implicit search may also lead to a blowup of redundant computations. This is illustrated through various examples.
Une recherche combinatoire peut être réalisée soit en utilisant un arbre de recherche implicite, où l'état initial est récursivement transformé jusqu'à atteindre un état but, soit en utilisant un arbre de recherche explicite, où la structure d'arbre initiale contenant l'état racine est itérativement étendue jusqu'aux feuilles qui satisfont l'ensemble des états buts. Ce rapport propose une étude exploratoire visant à montrer que les arbres de recherche explicites peuvent jouer un rôle notable dans le cas des contraintes numériques. Le premier avantage de la recherche explicite est son expressivité : on peut écrire de nouveaux algorithmes ou reformuler des algorithmes existants d'une manière simple et unifiée. Le second avantage est l'efficacité car une recherche explicite permet d'éviter, dans certains cas, une explosion de calculs redondants. Ceci est illustré à travers plusieurs exemples
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...