Une Stratégie de Résolution Orientée par la Topologie des CSPs Numériques

http://www710.univ-lyon1.fr/~csolnonLes méthodes classiques de résolution de CSPs numériques sont basées sur un algorithme combinant une technique de bissection et un filtrage par consistance locale. En général, le filtrage est basé sur la Hull-consistance ou la Box-consistance. Les algorithmes de filtrage correspondants identifient souvent des trous dans les domaines, c'est-à-dire des intervalles sur lesquels certaines contraintes ne sont pas satisfaites. Ces trous sont cependant utilisés uniquement pour déterminer le plus petit intervalle englobant les solutions. Ce papier présente une stratégie de recherche, nommée TopSearch (Topological Search), qui exploite les trous identifiés par ces filtrages. TopSearch utilise ces informations pour sélectionner la direction de coupe ainsi que pour définir le point de coupe dans le domaine sélectionné. Si aucun trou n'est identifié une bissection standard est mise en oeuvre. Les premiers résultats expérimentaux montrent que cette heuristique de recherche dont le sur-coût est minime, peut améliorer de manière très significative les performances de la bissection classique