Recherche exhaustive

La recherche exhaustive ou recherche par force brute est une méthode algorithmique qui consiste principalement à essayer toutes les solutions possibles. Par exemple pour trouver le maximum d'un certain ensemble de valeurs, on consulte toutes les valeurs. En cryptanalyse on parle d'attaque par force brute, ou par recherche exhaustive pour les attaques utilisant cette méthode.

Principes et exemples

Le principe de cet algorithme est d'essayer toutes les possibilités dans un intervalle. Un exemple courant est l'attaque par force brute des mots de passe. Si on sait que le mot de passe contient obligatoirement 4 chiffres, alors on essaie tous les nombres de 0000 à 9999 jusqu'à trouver le bon mot de passe.

Théorie

La recherche au sens unification entre deux théories

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

À supposer qu'il y a un problème et n variables dont il est possible d'obtenir une grandeur. Alors un objectif sera de découvrir les p variables significatives 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 la sélection séquentielle des p variables significatives. Cela consiste à entrainer un modèle sur une seule des n variables et d'ajouter unitairement celles restantes si et seulement si elles minimisent le score de perte tel que l'erreur quadratique moyenne pour une problématique de régression ou l'entropie croisée pour de la classification.

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.

Article connexe

Attaque par force brute en cryptanalyse