2.5 Intégration d'heuristiques
Les algorithmes que nous venons d'étudier choisissent,
à chaque étape, la prochaine variable à instancier parmi
l'ensemble des variables qui ne sont pas encore instanciées, ensuite,
une fois la variable choisie, ils essayent de l'instancier avec les
différentes valeurs de son domaine. Ces algorithmes ne disent rien sur
l'ordre dans lequel on doit instancier les variables, ni sur l'ordre dans
lequel on doit affecter les valeurs aux variables. Ces deux ordres peuvent
changer considérablement l'efficacitéde ces algorithmes :
imaginons qu'àchaque étape on dispose d'une heuristique parfaite
qui nous dit quelle valeur choisir sans jamais se tromper, dans ce cas, la
solution serait trouvée sans jamais retourner en arrière...
Malheureusement, le problème général de la satisfaction
d'un CSP sur les domaines finis étant NP-complet, il est plus
qu'improbable que cette heuristique fiable à 100% puisse jamais
être »programmé». En revanche, on peut intégrer
des heuristiques pour déterminer l'ordre dans lequel les variables et
les valeurs doivent être considérées : une heuristique est
une règle non systématique (dans le sens oùelle n'est pas
fiable à 100%) qui nous donne des indications sur la direction à
prendre dans l'arbre de recherche.
Les heuristiques concernant l'ordre d'instanciation des
valeurs sont généralement dépendantes de l'appli-cation
considérée et difficilement généralisables. En
revanche, il existe de nombreuses heuristiques d'ordre d'instanciation des
variables qui permettent bien souvent d'accélérer
considérablement la recherche. L'idée générale
consiste à instancier en premier les variables les plus
»critiques», c'est-à-dire celles qui interviennent dans
beaucoup de contraintes et/ou qui ne peuvent prendre que très peu de
valeurs. L'ordre d'instanciation des variables peut être
:
- statique, quand il est fixéavant de
commencer la recherche.
Par exemple, on peut ordonner les variables en fonction
du nombre de contraintes portant sur elles : l'idée est d'instancier en
premier les variables les plus contraintes, c'est-à-dire celles
qui
29
participent au plus grand nombre de contraintes.
- ou dynamique, quand la prochaine variable
à instancier est choisie dynamiquement à chaque étape de
la recherche.
Par exemple, l'heuristique Ȏchec
d'abord» (»first-fail» en anglais) consiste à choisir,
à chaque étape, la variable dont le domaine a le plus petit
nombre de valeurs localement consistantes avec l'affectation partielle en
cours. Cette heuristique est généralement couplée avec
l'algorithme »anticipation», qui filtre les domaines des variables
à chaque étape de la recherche pour ne garder que les valeurs qui
satisfont un certain niveau de consistance locale.
| 
