Description du problème :
Un état d'un CSP est une liste d'assignations variable = valeur où chaque variable n'est assignée qu'au plus une fois.
L'état initial : Liste vide.
Un état intermédiaire : Une liste d'assignations variable = valeur
Un état but : Une liste d'assignations variable = valeur complète et cohérente (c-à-d couvrant toutes les variables et satisfaisant les contraintes).
On assigne une variables à une valeur satisfaisant les contraintes, en les essayants dans un ordre quelconque. Si ce choix n'est pas possible pour la variable en cours, alors on recommencer depuis le début sans réinitialiser la graine du hasard.
La fonction `"AVANCE"(e)` appliqué à l'état `e` retourne l'état dans lequel on a ajouter une assignation d'une nouvelle variable non encore assignée avec une valeur qui respecte les contraintes, ou bien si pas possible, retourne échec .
CSP-SHADOK(problème, graine) :| Répéter indéfiniment : `e:=`liste vide
|
La complexité en logique Shadok est baséz sur un calcul de probabilité, c'est pourquoi il y a un paramètre supplémentaire qui est la graine du générateur de nombre aléatoire.
`p` : Probabilité de trouver une solution au hasard au cours d'un seul essai.
`N` : Nombre d'essais
La probabilité `P` de trouver une solution au hasard au cours de `N` essais est :
`P = 1-(1-p)^N`
Si `p` est petit et `N` grand, alors on utilise l'aproximation `(1-p)^N = e^(-Np)`, et nous avons l'approximation suivante :
`P ≈ 1- e^(-Np)`
Et si `Np` est lui-même petit alors nous avons l'approximation suivante :
`P ≈ Np`
Ou si l'on choisit `N "=" 1/p` alors la probabilité de trouver une solution au hasard au cours de ces essais est :
`P ≈ 1-e^-1 ≈ 63"%"`
Il y a `n` étapes. A chaque étape, on choisit d'assigner une variable non encore assignée dans l'ordre, ce qui nous assure de parcourir un arbre. Pour chaque valeur possible de cette variable on crée en pensée l'état fils correspondant que l'on empile dans la frontière pour un parcours en profondeur d'abord. On définit 3 fonctions qui nous permettent de nous déplacer de noeud en noeud dans ce graphe :
Fonction `"FILS"(e)` : retrourne le premier fils de `e` ou bien échec s'il n'a pas de fils. Le noeud premier fils de `e` est obtenu en choisissant la variable suivante encore non-assignée, et en lui assignant la première valeur qui satisfait les contraintes.
Fonction `"SUCCESSEUR"(e)` : retrourne le noeud frère suivant de `e` ou bien échec s'il n'y a plus de possibilité. Le noeud frère suivant de `e` est obtenu en assignant la prochaine valeur non encore explorée à la dernière variable qui est en cours de traitement dans l'état `e`, et qui satisfait les contraintes.
Fonction `"BACKTRACKING"(e)` : retourne le noeud père de `e` ou bien échec s'il n'y en a pas. Le noeud père de `e` est obtenu en enlevant la dernière assignation.
On ajoute une fonction `B` pour reconnaitre les états complets. Ainsi `B(e)` retourne vrai si l'état `e` assigne toutes les variables.
CSP-BACKTRACKING(problème) :| `e :=` l'état vide Répéter indéfiniment :
|
`d` : taille des domaines
`n` : nombre de variables
Le nombre d'états complets à tester dans le pire des cas est alors `d^n`
Heuristique MRV (Minimum Remaning Value) : Cette heuristique consiste à choisir la prochaine variable à assigner, qui a le moins de valeurs légales restantes. Une valeur est dite légale si elle respecte les contraintes.
Heuristique des degrés : Si plusieurs variables ne peuvent pas être départagées par l'heuristique MRV, on choisie une variable qui impose des contraintes à un nombre minimum d'autres variables non encore assignées.
Heuristique de la valeur la moins contraignante : On choisie la valeur qui invalide le moins de valeurs possibles pour les autres variables non encore assignées.
Heuristique Vérification Avant : On garde en mémoire le domaine légale des valeurs légales de chaque variables non encore assignées. Lorsque une variable `X` est assignée. Pour chaque variable `Y` non assignées qui partage une contrainte avec `X`, à partir du domaine de `Y` on calcul le domaine légale des seules valeurs légales pour `Y`. Si ce domaine légale ce reduit à vide, on lance de suite le retours arrière.
L'algorithme vérifit s'il n'y a pas de conflit entre les variables qui n'ont pas encore été assignées.
Le graphe des contraintes relit par des arrêtes les variables non-assignées qui partagent une contrainte. Chaque arrête `X"---"Y` peut être interprété comme constituant deux arcs `X"→"Y` et `Y"→"X`. L'arcs `X"→"Y` est dit cohérent (ou consistant) si quelque soit la valeur `x` assigné à `X` il existe au moins une valeur `y` pour `Y` qui est autorisée.
L'algorithme AC-3 consiste à rendre cohérent tous les arcs du graphe des contraintes en réduisant les domaines des variables par suppression des valeurs rendant l'un de ces arcs incohérent. Il procède comme suit : Il met tous les arcs entre variables non assignées dans une file. Puis pour chaque arc sortant de la file, `X"→"Y`, pour chaque valeur `x` de `X`, s'il n'y a pas de valeur autorisé pour `Y`, alors il retire la valeur `x` du domaine de `X` et il ajoute dans la file s'ils n'existent pas déjà tous les arcs allant sur `"→"X` autre que `Y"→"X`.
`"AC-3"("csp")` : # Rend les domaines cohérents. Retourne `"faux"` si un domaine a été réduit à vide.| `F :=` l'ensemble des arcs de contrainte du `"csp"` Tant que `F` n'est pas vide faire :
|
| `b:="faux"` Pour chaque `x` dans le domaine de `X` faire :
|
`c` : Nombre de contraintes
`d` : Taille des domaines
Complexité de `"REVISER"` : `O(d^2)`
Complexité de `"AC-3"` : `O(cd^3)`
L'AC-3 peut être lancer avant l'exploration sur le csp complet initial, ou après chaque assignation sur le csp réduit aux seules arcs partant d'une variables non-assignées pour aller sur une variable quelconque.