Recherche exhaustive

La recherche exhaustive ou recherche par force brute, est un terme qui s'applique à une catégorie de méta-algorithmes. C'est une technique extrêmement simple, mais très générale, qui consiste à énumérer tous les candidats possibles, jusqu'à trouver le candidat qui satisfait au problème.

On peut distinguer plusieurs formes de recherche exhaustive.

Méthode

La recherche au sens unifications entre deux théories

exemple : trouver A et B tels que pour un prédicat à deux arguments f la propriété f(A, B) soit vraie. La recherche exhaustive est alors une méthode de recherche qui consiste à considérer l'ensemble des valeurs possibles pour A et B et à les tester toutes dans un ordre quelconque jusqu'à ce que la propriété soit vraie. Typiquement les algorithmes qui découvrent dynamiquement la structure des données pour optimiser leur calcul sont aussi considérés comme des algorithmes de recherche exhaustive. On peut citer SSS*, AlphaBeta, MinMax, A*, BackTrack, BackJump, BackMark, NC-AC(n), ForwardChecking, ... Dans cette catégorie on peut considérer que le terme "exhaustive" ne s'applique plus :

• si dans le pire des cas il est possible que la solution ne soit pas trouvée malgré son existence.
• si l'ensemble des valeurs à explorer est indénombrable.
• si une combinaisons de valeurs peut être testée plus d'une fois dans au moins un schéma d'exécution.

La recherche au sens sélection des paramètres influents dans un contexte inconnu

Supposons que l'on se donne un problème et n variables dont on peut obtenir une grandeur. Alors un objectif sera de découvrir les p variables significative de ce problème. Pour cela une des premières méthodes de réalisation à envisager est la recherche exhaustive.

En effet ce genre de problème contient très souvent de nombreuses contraintes implicites liées à la structure propre du problème. Il suffit alors de construire l'hypergraphe des contraintes et en déduire les paramètres les plus influents. La méthode brutale la plus employée pour ce problème est l'ACP (Analyse en Composantes Principales).

Cette recherche est très souvent réalisée en robotique et en traitement automatique du langage naturel. Dans ces deux derniers il est très courant que les contraintes soient entrées 'à la main' via un expert. En effet construire un programme qui découvre automatiquement les caractéristiques d'un robot ou d'une langue est très compliqué. Cependant l'ordonnancement des paramètres les plus influents se fait souvent par recherche exhaustive sur des corpus obtenus empiriquement.

Voir aussi

• Attaque par force brute en cryptanalyse