Une Stratégie de Résolution Orientée par la Topologie des CSPs Numériques - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2005

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

Résumé

Les 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.
Fichier principal
Vignette du fichier
38.pdf (261.68 Ko) Télécharger le fichier

Dates et versions

inria-00000087 , version 1 (26-05-2005)

Identifiants

  • HAL Id : inria-00000087 , version 1

Citer

Heikel Batnini, Michel Rueher, Claude Michel. Une Stratégie de Résolution Orientée par la Topologie des CSPs Numériques. Premières Journées Francophones de Programmation par Contraintes, CRIL - CNRS FRE 2499, Jun 2005, Lens, pp.211-218. ⟨inria-00000087⟩
57 Consultations
37 Téléchargements

Partager

Gmail Facebook X LinkedIn More