Une procédure générale d'élimination d'isomorphismes pour les problèmes de configuration

http://www710.univ-lyon1.fr/~csolnonUne difficulté intrinsèque à la résolution de problèmes de configuration réside dans l'existence de nombreux isomorphismes structurels dans les solutions. Nous définissons deux procédures de recherche permettant la suppression de grandes portions de l'espace de recherche dont on montre qu'elles ne renferment que des solutions non canoniques. On y parvient grâce à un test en chaque noeud de l'arbre de recherche de complexité temporelle linéaire. Nous présentons des résultats sur un exemple de configuration simple mais représentatif de ce qu'on pourra obtenir sur des problèmes réels