Recherche exhaustive
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de  |
Cet article est une ébauche à compléter concernant l'informatique, vous pouvez partager vos connaissances en le modifiant. |
La recherche par force brute est un terme qui s'applique à une catégorie de méta-algorithmes. On peut distinguer plusieurs formes de recherche par force brute (de manière non exhaustive).
Sommaire |
[modifier] Méthode
[modifier] 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 par force brute 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 par force brute. 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 "force brute" 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.
[modifier] 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 force brute.
En effet ce genre de problème contient très souvent de nombreuses contraintes implicite liée à 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és pour ce problème est l'ACP (Analyse en composante Principale).
Cette recherche est très souvent réalisé en robotique et en traitement automatique du langage naturel. Dans ces deux dernier il est très courant que les contraintes soit entrée 'à 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 ce fait souvent par force brute sur des corpus obtenue empiriquement.
[modifier] Voir aussi
- Attaque par force brute en cryptanalyse
