Skip to Main content Skip to Navigation
Conference papers

Amélioration par apprentissage de la recherche à divergences limitées

Résumé : Dans le cadre de la résolution des problèmes de satisfaction de contraintes, nous présentons une nouvelle méthode complète basée sur des améliorations de " Limited Discrepancy Search " [Harvey & Ginsberg 1995]. Cette méthode, intitulée " Minimal Discrepancy Search " ( DS), peut être considérée comme la fusion de deux nouvelles variantes de LDS ; celles-ci mettent en oeuvre des techniques d'apprentissage au cours de la recherche : - " Permuted Limited Discrepancy Search " qui exploite les échecs rencontrés lors de l'exploration de l'arbre de recherche et en déduit un ordre sur les variables. Cet ordre minimise le nombre de divergences et accélère la résolution dans le cas d'un problème soluble. - " Restricted Discrepancy Search ", méthode permettant de déterminer, sans pour autant réaliser toutes les itérations de LDS, si le problème est sur-contraint. Dans ce cas, on abandonne la recherche prématurément (et avantageusement). Les performances de ces méthodes sont évaluées suivant le temps nécessaire pour aboutir à une solution, ou à la preuve de l'absence d'une solution, et le nombre de noeuds générés dans l'arbre de recherche correspondant. Pour attester de l'efficacité de DS, des comparaisons avec d'autres méthodes ont été menées, suivant la taille et le taux de contraintes des problèmes testés. " Forward Checking " est ainsi utilisé pour des problèmes de taille réduite et relativement peu contraints ; pour des problèmes de grande taille et plus fortement contraints, nous utilisons " mac3cache ", proposé par [Zhang et al. 2004]. Dans tous les cas, DS s'avère très performante et surclasse les autres méthodes.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/inria-00000051
Contributor : Christine Solnon <>
Submitted on : Wednesday, May 25, 2005 - 10:04:07 AM
Last modification on : Wednesday, October 28, 2020 - 2:20:03 PM
Long-term archiving on: : Thursday, April 1, 2010 - 9:31:29 PM

Files

Identifiers

  • HAL Id : inria-00000051, version 1

Citation

Wafa Karoui, Marie-José Huguet, Pierre Lopez, Wady Naanaa. Amélioration par apprentissage de la recherche à divergences limitées. Premières Journées Francophones de Programmation par Contraintes, CRIL - CNRS FRE 2499, Jun 2005, Lens, France. pp.109-118. ⟨inria-00000051⟩

Share

Metrics

Record views

410

Files downloads

221