Seul un état but est recherche, le chemin y amenant n'a pas d'importance. Le principe consiste à modifier l'état courant en l'amméliorant au fur et à mesure.
On se déplace toujours vers le point le plus haut de notre voisinage.
On s'arrète lorsque auncun point de notre voisinage n'est strictement supérieur.
ESCALADE(problème) :| Initialiser l'état courant à l'état initial. Répéter indéfiniment :
|
« retourner `x` » signifie terminer la fonction en retournant la valeur `x`.
Déplacement lattéraux : On autorise des mouvements latéraux c'est à dire à valeur constante, mais seulement un nombre de fois consécutifs (par exemple 100 fois) pour éviter les boucles sans fin.
Escalade stochastique : On choisi au hasard un voisin de valeur strictement supérieure.
Escalade du premier choix : Générer des successeurs au hasard jusqu'à que l'un d'eux soit meilleur que l'état courant.
Escalade avec reprise aléatoire : Lors d'un blocage, recommencer l'escalade à partir d'un autre état initiale choisi au hasard.
Choisir au hasard un voisin, si celui-ci amméliore la situation alors il est accepté. Sinon il est accepté seulement avec une probabilité
`p=e^((DeltaE)/T)`
Où `DeltaE` est négatif et désigne la baisse de l'évaluation `f(X')-f(X)`. Le parmètre `T` est la température. Elle est élevé au début, puis diminue et finit par tendre vers zéro.
RECUIT-SIMULE(problème) :| Initialiser l'état courant `e` à l'état initial. Pour `t":="1` jusqu'à `oo` faire :
|
Exploration locale en faisceau : On mémorise `k` états courant au lieu d'un seul. On commence par `k` états au hasard. A chaque étape, tous les successeurs des `k` états sont générés. si l'un deux est un but l'algorithme s'arrête. Sinon elle selectionne les `k` meilleurs successeurs parmi la liste complète.
Exploration locale en faisceau stochastique : Sinon elle choisit les `k` successeurs au hasard parmi la liste complète selon une probabilité proportionnelle à la valeur du successeur.
Description du problème :
Un état (ou un noeud) d'un CSP est une assignation de valeurs à des variables.
L'état initial : Assignation vide.
Un état intermédiaire : Une liste d'assignations de variables.
Un état but : Assignation complète et cohérente (c-à-d satisfaisant les contraintes).
On assigne les variables à des valeurs satisfaisant les contraintes, et 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 `"ASSIGNE"(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 `"nada"` .
CSP-SHADOK(problème, graine) :| Répéter indéfiniment : `e:=`état vide
|
La complexité en logique Shadok est basé 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 alors nous avons l'approximation suivante :
`P ≈ e^-Np`
Et si `Np` est lui-même petit alors nous avons l'approximation suivante :
`P ≈ Np`
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 potentiellement 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 `"nada"` s'il n'a pas de fils. Le noeud fils de `e` est obtenu en choisissant la variable suivante encore non-assignée, et en lui assignant une valeur qui satisfait les contraintes.
Fonction `"SUCCESSEUR"(e)` : retrourne le noeud frère suivant de `e` ou bien `"nada"` s'il n'y a plus de possibilité. Le noeud frère 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 `"nada"` s'il n'y en a pas. Le noeud père de `e` est obtenu en enlevant la dernière assignation.
CSP-BACKTRACKING(problème) :| `e =` l'état vide Répéter indéfiniment :
|
---- 5 juin 2026 ----
.
Nous avons une liste de variable `[X_1,X_2,...,X_n]`.
Les domaines sont des listes (commençant aussi par l'indexe 1). On note `D_i[j]` la `j`-ème valeur du domaine `D_i`.
L'état est une liste d'indexes des valeurs assignées aux `n` variables.
L'état initiale est `[1,1,...,1]`, avec `X_1=D_1[1]`, `X_2=D_2[1]`, ...,`X_n=D_n[1]`.
La fonction `"SUIVANT"(e)` appliqué à l'état `e` retourne l'état but suivant. L'état but suivant s'obtient en incrémentant le dernier index, et si cet index est déjà au maximum, alors on le ramène à `1` et on incrémente l'index à sa gauche, et si cet index est déjà au maximum, alors on le ramène à `1` et on incrémente l'index à sa gauche, et ainsi de suite, et si il n'y a plus d'indexe à gauche devant être incrémenter alors la fonction retourne une fin_de_transmission, sinon elle construit l'état correspondant à `[j_1,j_2,...,j_n]` en effectuant pour `i"="1` à `n`, l'affectation `X_i=D_i[j_i]`.
CSP-BRUT(problème) :| Initialiser l'état-courant `e := [ 1,1,...,1]` 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`
Nous avons une liste de variable `[X_1,X_2,...,X_n]`.
Les domaines sont des listes (commençant aussi par l'indexe 1). On note `D_i[j]` la `j`-ème valeur du domaine `D_i`.
L'état est une liste d'indexes des valeurs assignées aux premières variables.
L'état initiale est `[ ]`.
L'état est une liste d'indexes des valeurs assignées aux premières variables. Par exemple : l'état `[5,7,6]` désigne l'état où `X_1"="D_1[5]`, `X_2"="D_2[7]`, `X_3"="D_3[6]`. Sauf pour l'état initial, sa longueur donne l'indexe `i"="3` de la variable en cours de traitement, et le dernier indexe donne l'indexe de la valeur en cours de traitement `j"="6`.
`[1]` c'est à dire où `X_1=D_1[1]`, et où la variable en cours d'analyse est `X_1` et où la valeur en cours d'analyse est `D_1[1]`.
La fonction `"SUIVANT"(e)` appliqué à l'état `e` commme indiqué, retourne l'état suivant.
| Etat-initiale = `[ ]` Répéter indéfiniment :
|
Le Backtracking (recherche à retour arrière) évite de parcourire toute les états énumérés par `"SUIVANT"`. Si La taille des domaines est `d`, cette énumération comprend `d^n` états.
CSP-PROFONDEUR (problème) :
| Etat-initiale = [1] Pour `i in [1,2,...,n]` : # Pour chaque variable X_i
|
On parcours les variables selon une liste, puis les valeurs selon une liste, puis les contraintes selon une liste.
CSP-PROFONDEUR-LIMITE(problème) :
| Etat-initiale vide Pour `i in [1,2,...,n]` : # Pour chaque variable X_i
|
Si `T"=="0` alors retourner l'état-courant. |
On choisi la variable qui a le moins de choix de valeurs possibles (MRV).
Si égalité, on choisi la variable impliquée par des contraintes sur le plus grand nombre de variables non assignées. (Heuristique des degrés)
On lui choisit une valeur qui invalide le moins de valeurs possibles pour les variables non encore assignées.
On regarde si les variables non-assignées ont encore des valeurs permises, pour lancer un éventel reour en arière (Vérification Avant).
Choix de la prochaine variable à aasigner
Choix de la prochaine valeur à lui donner
Détecter le plus tôt possible les assignations conflictuelle.
Heuristique MRV (minimum Remaning Values)
+ Heuristique de dégrés : choisir la variable impliqué dans le plus grand nombre de conraintes sur les autres variables non asignés.
Heuristique de la valeur la moins contraignante
Heuristique "Forward checking" (détecte les conflit )