6.5 Les nombres conspirants
return min ;
}
int phiSum (node n) {
int sum = 0;
}
pour chaque fi 1 s {
}
TI .look (fils , phi , delta );
sum += phi ;
return sum ;
6.5 Les nombres conspirants
129
L' algorithme des nombres conspirants est dû à D.A. Mac Allester [59]. Une autre description a été donnée par J. Schaeffer [77]. C 'est un algorithme qui utilise une fonction
d'évaluation aux feuilles et qui construit un arbre de recherche de profondeur variable sans
connaissances du domaine. Le principe de l ' algorithme est de déterminer dans quelle mesure l ' approfondissement de la recherche d 'un sous-arbre est utile. Cette mesure est faite
par les nombres conspirants qui représentent le nombre minimum de feuilles qui doivent
changer leur valeur (en approfondissant la recherche) pour que la valeur minimax du
sous-arbre change. Cette recherche est contrôlée par le seuil conspirant (CT), le nombre
minimum de nombres conspirants au dessus duquel il est considéré comme improbable
que la valeur du sous-arbre change.
Pour une feuille, changer sa valeur ne demande la conspiration que de cette feuille
elle-même, son nombre conspirant est alors de 1. Si la valeur ne doit pas être changée,
alors le nombre conspirant est O. Si la feuille est une feuille terminale on ne peut pas
changer sa valeur, son nombre conspirant est alors Infini.
Pour un noeud interne à un niveau Max, augmenter sa valeur jusqu' à v ne nécessite
d' augmenter qu'un seul fils jusqu' à v. Le nombre minimum de nombres conspirants pour
augmenter la valeur du noeud est donc le minimum des nombres conspirants des fils pour
augmenter la valeur à v. Si v est inférieur ou égal à m la valeur minimax du noeud son
nombre conspirant est O.
Pour faire décroître la valeur d' un noeud Max à von doit faire décroître les valeurs de
tous les fils qui ont une valeur supérieure à v. Le nombre minimum de conspirateurs pour
faire décroître la valeur d' un noeud est la somme de tous les nombres conspirants des fils
pour faire décroître la valeur vers v. Si v est supérieur ou égal à m, le nombre conspirant
est O.
Pour un noeud interne Min, on prend les relations duales, à savoir la somme des
nombres conspirants pour faire croître vers une valeur v supérieure à m, et le minimum
des nombres conspirants pour faire décroître vers une valeur v inférieure à m, 0 sinon.
return min ;
}
int phiSum (node n) {
int sum = 0;
}
pour chaque fi 1 s {
}
TI .look (fils , phi , delta );
sum += phi ;
return sum ;
6.5 Les nombres conspirants
129
L' algorithme des nombres conspirants est dû à D.A. Mac Allester [59]. Une autre description a été donnée par J. Schaeffer [77]. C 'est un algorithme qui utilise une fonction
d'évaluation aux feuilles et qui construit un arbre de recherche de profondeur variable sans
connaissances du domaine. Le principe de l ' algorithme est de déterminer dans quelle mesure l ' approfondissement de la recherche d 'un sous-arbre est utile. Cette mesure est faite
par les nombres conspirants qui représentent le nombre minimum de feuilles qui doivent
changer leur valeur (en approfondissant la recherche) pour que la valeur minimax du
sous-arbre change. Cette recherche est contrôlée par le seuil conspirant (CT), le nombre
minimum de nombres conspirants au dessus duquel il est considéré comme improbable
que la valeur du sous-arbre change.
Pour une feuille, changer sa valeur ne demande la conspiration que de cette feuille
elle-même, son nombre conspirant est alors de 1. Si la valeur ne doit pas être changée,
alors le nombre conspirant est O. Si la feuille est une feuille terminale on ne peut pas
changer sa valeur, son nombre conspirant est alors Infini.
Pour un noeud interne à un niveau Max, augmenter sa valeur jusqu' à v ne nécessite
d' augmenter qu'un seul fils jusqu' à v. Le nombre minimum de nombres conspirants pour
augmenter la valeur du noeud est donc le minimum des nombres conspirants des fils pour
augmenter la valeur à v. Si v est inférieur ou égal à m la valeur minimax du noeud son
nombre conspirant est O.
Pour faire décroître la valeur d' un noeud Max à von doit faire décroître les valeurs de
tous les fils qui ont une valeur supérieure à v. Le nombre minimum de conspirateurs pour
faire décroître la valeur d' un noeud est la somme de tous les nombres conspirants des fils
pour faire décroître la valeur vers v. Si v est supérieur ou égal à m, le nombre conspirant
est O.
Pour un noeud interne Min, on prend les relations duales, à savoir la somme des
nombres conspirants pour faire croître vers une valeur v supérieure à m, et le minimum
des nombres conspirants pour faire décroître vers une valeur v inférieure à m, 0 sinon.