QCSP guidé par Monte Carlo
Résumé
We present in this article a cooperation between a solver for problems with quantified constraints and a Monte Carlo algorithm.
The latter acts as a heuristic on the order of the values of domains variables chosen during the search.
It samples the search space in order to focus on the areas which do not satisfy the underlying CSP.
It reorders the choice of values made by the solver, and gives a higher priority by duality to
the search space areas which seem to have the best chance of containing solutions.
Nous présentons dans cet article une coopération entre un solveur de contraintes quantifiées et un algorithme de type Monte Carlo.
Ce dernier sert d'heuristique sur l'ordre du choix des valeurs des domaines des variables lors de la résolution.
Il échantillonne l'espace de recherche pour se focaliser sur les zones qui ne satisfont pas le CSP sous-jacent. Il réordonne ensuite le choix des valeurs des domaines fait par le solveur, donnant la priorité par dualité aux zones de l'espace de recherche ayant le plus de chance de contenir une solution.