Recherche exhaustive

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La recherche exhaustive ou recherche par force brute est un terme qui s'applique à une catégorie de méta-algorithmes.

Méthode[modifier | modifier le code]

La recherche au sens unification entre deux théories[modifier | modifier le code]

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 combinaison 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[modifier | modifier le code]

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[modifier | modifier le code]