Problèmes de satisfaction de contraintes (CSP)

4. Résolution d'un CSP

  • La résolution de CSP est généralement combinatoire dans le sens où il faut envisager un très grand nombre de combinaisons avant d'en trouver une qui satisfasse toutes les contraintes.
  • Bien souvent, la puissance de calcul des ordinateurs ne suffit pas pour examiner toutes les combinaisons possibles en un temps acceptable, et il est nécessaire d'introduire des raisonnements et des heuristiques.

Algorithmes de résolution de CSP:

  • Recherche systématique
    • genere et teste (GET)
    • simple retour arrière (SRA) ou (backtracking (BT))
  • Techniques de filtrage
    • consistance de nœud (NC), d’arc (AC), de chemin (PC) · · ·
  • Techniques de propagation de contraintes
    • forward checking (FC)
    • look ahead (LH)
  • Techniques basées sur l’ordre des variables et des valeurs 
    • heuristiques