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. 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. 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. À 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.