1.2 État de l'art des recherches
arborescentes
Les performances d'une recherche arborescente varient de
façon significative selon les stratégies de branchement retenues,
c'est-à-dire l'ordre selon lequel les variables seront choisies, ainsi
que l'ordre dans lequel les valeurs pour cette variable seront
instanciées. On peut noter que ces stratégie dépendent en
partie de la nature du problème et de l'espace des solutions : dans le
cas où le problème n'a qu'une solution ou très peu de
solutions, on cherche généralement à trouver une de ces
solutions le plus rapidement possible; dans le cas où le problème
n'est pas résoluble, on cherche à ce que l'arbre de recherche
soit le plus petit possible afin de prouver l'absence de solution de
manière relativement rapide; enfin, dans le cas pour lequel le
problème possède un nombre de solutions très important, on
cherche généralement la meilleure de ces solutions (selon un
objectif donné). On voit donc qu'une méthode efficace pour un
type de problème peut être inefficace pour un autre type de
problème.
Puisque toutes les variables d'un problème doivent
être instanciées pour obtenir une solution, une réduction
de la taille de l'arbre de recherche peut être obtenue en choisissant en
premier la variable qui contraint le plus l'espace de recherche. Ce choix est
souvent implémenté en choisissant en premier la variable ayant le
plus petit domaine (dom). Pour départager les variables
jugées équivalentes par l'heuristique du plus petit domaine, on
choisit la variable qui appartient au plus grand nombre de contraintes (on
définit le degré d'une variable comme le nombre de contraintes
dans lesquelles apparaît une variable). On peut aussi appliquer une
combinaison de ces deux critères (dom/deg, (Smith et Grant,
1998)) (plus petit domaine divisé par le degré de la variable).
Il a été montré par Haralick et Elliot (1980) que le fait
de calculer des mises à jour des domaines et du degré des
variables à chaque noeud permet de prendre de meilleures
décisions lors de l'exploration (dom/ddeg). En suivant cette
politique, on essaie de contraindre au maximum les variables et ainsi limiter
la taille de l'arbre. Concernant le choix de l'ordre dans lequel les valeurs
sont instanciées, ce choix ne semble pas important dans le cas où
le problème ne possède pas de solution. Cependant, dans le cas
contraire, on pourra atteindre plus rapidement une solution si l'on choisit la
valeur qui tend à maximiser le nombre de possibilités pour les
choix futurs. Enfin, il est facile de se rendre compte que le choix des
variables qui sont au sommet de l'arbre est prépondérant. On a
donc intérêt à choisir les premières variables sur
lesquelles brancher avec précaution.
L'idée d'accélérer l'exploration de
l'arbre de recherche n'est pas nouvelle. Plusieurs techniques ont
été proposées ces dernières années; ces
techniques peuvent être basées sur :
- un parcours réduit de l'arbre de recherche,
- une politique de branchement sur l'ordre des valeurs, - une
politique de branchement sur l'ordre des variables, - une combinaison des
techniques précédentes.
Les paragraphes qui suivent offrent une présentation de
certaines de ces techniques.
1.2.1 Méthode de parcours de l'arbre de
recherche
La plupart des méthodes de parcours d'un arbre de
recherche sont connues depuis déjà plusieurs années. La
différence entre deux stratégies de recherche réside
principalement dans la taille de l'arbre de recherche
généré et donc dans le temps de résolution du
problème traité. Les stratégies appliquées sont la
plupart du temps différentes selon la nature du problème. On
distingue les problèmes d'optimisation combinatoire avec une fonction
objectif et un nombre généralement important de solutions et les
problèmes de satisfaction de contraintes pour lesquels on ne cherche la
plupart du temps qu'une seule solution.
On peut citer différentes stratégies de
recherche (pour plus de détails, voir (Hooker, 2000)). Pour les
méthodes de parcours de l'arbre de recherche, on peut citer, entre
autres, les politiques suivantes :
Depth-first: la méthode
depth-first search est une méthode couramment utilisée.
Elle consiste en une exploration en profondeur de l'arbre de recherche. Les
variables sont fixées une à une itérativement,
jusqu'à obtenir une solution ou jusqu'à ce qu'une variable ait un
domaine vide. Lorsque c'est le cas, on revient sur la dernière
décision qui a été prise et on prend une autre
décision, si cela est possible. Dans le cas contraire, on remonte plus
haut dans les décisions prises. Cette technique est appelée
Backtrack. Lorsque le nombre de solutions est important, cette
méthode permet de trouver très rapidement une solution. Cette
méthode est très classique dans l'implémentation d'un
Branch and Bound. En terme d'occupation mémoire, cette méthode
est la plus intéressante.
Best bound first: on choisit parmi les noeuds
restant à traiter celui qui a la plus petite borne inférieure.
Cette borne peut être calculée par exemple, par relaxation de
contraintes, par une méthode heuristique, ... Ce choix est efficace
lorsque les bornes calculées sont de bonne qualité. Elle
présente par contre l'inconvénient de traiter des noeuds
successifs très différents (valeurs et variables
différentes) et donc de ne présenter que peu
d'incrémentalité dans les calculs, notamment les calculs de
bornes inférieures. De plus, cette méthode n'est applicable que
lorsqu'une borne est calculable, ce qui peut ne pas être le cas pour
certains problèmes de satisfaction de contraintes, dans lesquels il n'y
a pas de fonction objectif.
Breadth-first: cette méthode est la
méthode opposée à la méthode depth-first search.
Elle consiste à explorer l'arbre en largeur. Le parcours en largeur
correspond à un parcours par niveau de noeuds de l'arbre. Un niveau est
un ensemble de noeuds ou de feuilles situés à la même
distance du noeud racine. Ce type de parcours est rarement utilisé, du
fait de l'occupation mémoire trop importante.
Les méthodes présentées ci-dessus
décrivent des politiques d'exploration de l'arbre de recherche. Une fois
l'arbre créé, elles permettent d'ordonner une liste de noeuds
à traiter. Elles ne modifient en aucun cas la structure propre de
l'arbre. Néanmoins, deux politiques de parcours d'arbre de recherche
peuvent donner des résultats différents en terme de
rapidité d'exécution et en terme d'occupation mémoire. En
effet, on peut associer à ces méthodes des calculs de bornes qui
pourront amener à la troncature de sous-espaces de l'arbre de recherche
(par exemple, lorsque la borne inférieure calculée
à un noeud est supérieure à la borne
supérieure). Ainsi, si la structure de l'arbre n'est pas
modifiée, les espaces explorés de l'arbre peuvent être
modifiés par les schémas d'exploration.
| 
