PPC > Notions de Bases > La recherche

A la recherche de la solution perdue...

Pour choisir entre plusieurs modèles, il peut être utile de comprendre comment fonctionne un solveur.
La PPC se base sur l’idée simple d’un parcours de l’arbre des affectations partielles :

  • Generate-and-test : on essaie tous les nœuds de l'arbre.
  • Backtracking (ou retour-arrière) : on vérifie les contraintes dont les variables sont déjà affectées.
  • Look Ahead (ou anticipation) : on raisonne au fur et à mesure de la recherche dans l’arbre.

Generate & Test (ou Générer Tester)

Pour chaque variable, on essaye de lui affecter une des valeurs de son domaine, puis on affecte la deuxième variable, etc... Quand toutes les variables ont une valeur, on vérifie la faisabilité de l'affectation. On stoppe la recherche dès qu'une affectation est consistante. Dans le cas d'un problème d'optimisation, on est obligé de parcourir tout l'arbre afin de trouver l'affectation générant une valeur de la fonction objective la plus intéressante. Pour un problème à N variables ayant chacune des domaines de tailles M, on va ainsi tester M puissance N solutions potentielles. Pour des problèmes de grandes tailles, cette stratégie est bien évidement inadaptée.

Backtracking (ou retour-arrière)

Cet algorithme améliore l'algorithme précédement décrit et permet de ne développer que les affectations partielles consistantes. A chaque affectation partielle du problème, on teste le jeu de contrainte et dès qu'une affectation partielle est inconsistante, on stoppe la recherche dans cette branche et on revient en arrière sans même tester les autres variables. En effet, il est inutile de continuer à l'étendre en une affectation totale car elle sera nécessairement inconsistante.

Look Ahead (ou anticipation)

Cet algorithme améliore l'algorithme "retour-arrière" en anticipant les conséquences de l'affectation partielle en cours de construction sur les domaines des variables qui ne sont pas encore affectées. Il existe 2 méthodes principales : le forward checking et le maintien de l'arc consistance (encore appelé filtrage) .

Forward Checking (ou Vérification en Avant)

Avant d'affecter une variable x à une valeur v, on vérifie que toutes les autres variables non affectées et liées par au moins une contrainte à x possède au moins une valeur de leur domaine compatible avec v.

Arc Consistency (ou Filtrage)

Filtrer les domaines des variables non affectées va consister à retirer les valeurs "localement inconsistantes". Différents types de filtrage peuvent être réalisés, qui seront plus ou moins coûteux et qui réduiront plus ou moins le domaine des autres variables.

  • Notion de Filtrage

    Pour réaliser un filtrage, on considère les contraintes comme un ensemble de tuples autorisés.

  • L'algorithme AC1

    Cet algorithme, le plus naïf, consiste à anticiper d'une étape l'énumération des valeurs :
    Pour chaque variable Xi non affectée, on retire de v Di / A U { ( Xi , v ) } soit inconsistante.
    Autrement dit, on retire du domaine de Xi toutes les variables sans support.

    Faire
    NouveauFiltrage = Faux
    Pour chaque couple de variables x et y Faire
    Si il existe une valeur de x sans support dans y ou inversement Alors
    Retirer la valeur sans support
    NouveauFiltrage = Vrai
    Tant que ( NouveauFiltrage = Vrai )

La complexité* de cet algorithme est O(ned3)
avec n : nb variables, e : nb contraintes, d = |domaine|.

  • L'algorithme AC3

    Cet algorithme est une version améliorée du précédent.

    Atester = {Liste des contraintes à vérifier}.
    Pour chaque contrainte C de Atester Faire
    Soit x et y les variables de C.
    Si il existe une valeur du domaine de x sans support dans y (ou inv.) Alors
    Retirer la valeur sans support.
    Ajouter les contraintes sur la variable modifiée dans Atester.

    Cette fois-ci on sait quelle variable a été modifiée.
    La complexité* de cet algorithme est O(ed3) avec e : nb contraintes, d = |domaine|.

  • L'algorithme AC4

    Cet algorithme est une version améliorée du précédent.

    Pour chaque valeur (x, v)
    Supports( x, v ) = { ( y, v’ ) | il existe Cxy, telle que Cxy( v, v’ ) est vraie }
    Tant qu’il existe ( x, v ) et y tels que Supports( x, v ) Dy est vide Faire
    Retirer la valeur ( x, v )
    Retirer ( x, v ) des supports de ( z, v’’ ) contenus dans Supports( x, v )

    Cette fois on connaît le variable modifiée mais aussi la valeur concernée.
    La complexité* de cet algorithme est O(ed2) avec e : nb contraintes, d = |domaine|.

  • Les autres algorithmes AC

    I    l existe d’autres améliorations : AC6, AC7, AC2001… mais sont spécifiques à l’utilisation de contraintes en extension. La plupart de solveurs utilisant des contraintes en intension exploite l’algorithme AC4. L’AC peut paraître puissant, mais il ne suffit pas pour détecter toutes les valeurs inconsistantes.

Conclusion

On appelera Propagation, l'algorithme qui consiste donc à appliquer des filtrages jusqu'à l'obtention d'un point fixe. On utilisera des « mondes » qui stockent l’état courant d’une résolution à chaque fois qu’un choix est pris pour optimiser la remontée dans l’arbre de recherche.

La PPC est donc bien l’union d’un algorithme de recherche (profondeur d’abord) avec des algorithmes de filtrage. Une contrainte réagit à l’envoi d’un événement.

Les événements classiques sont :

  • Modification d’une des bornes : awakeOnInf et awakeOnSup (Choco),
  • Retrait d’une valeur (en plein milieu du domaine) : awakeOnRem (Choco),
  • Instanciation de la variable, il ne reste qu’une seule valeur : awakeOnInst (Choco).

La recherche s’effectue comme suit :

Tant qu’on n’a pas de contradiction Alors

On propage
Quand on ne peut plus rien déduire (pile d’événements vide) on fait un choix
On ajoute la contrainte (ou on fait les modifications directement sur la variable)
Et on recommence

En cas de contradiction, on remonte dans l’arbre

 

* Ici les complexités sont exprimés si on considère qu'on a que des contraintes binaires.

 

Voici le plan de cette présentation sur la programmation par contraintes

Cette page a été co-réalisée avec Guillaume Rochart, docteur en mathématiques dans mon équipe de recherche au Bouygues e-lab.10/03/2009.