Recherche par force brute - Brute-force search

En informatique , la recherche par force brute ou recherche exhaustive , également appelée générer et tester , est une technique très générale de résolution de problèmes et un paradigme algorithmique qui consiste à énumérer systématiquement tous les candidats possibles à la solution et à vérifier si chaque candidat satisfait l'énoncé du problème. .

Un algorithme de force brute qui trouve les diviseurs d'un nombre naturel n énumérerait tous les entiers de 1 à n et vérifierait si chacun d'eux divise n sans reste. Une approche par force brute pour le puzzle des huit reines examinerait tous les arrangements possibles de 8 pièces sur l'échiquier de 64 cases et pour chaque arrangement, vérifier si chaque pièce (reine) peut attaquer une autre.

Alors qu'une recherche par force brute est simple à mettre en œuvre et trouvera toujours une solution si elle existe, les coûts de mise en œuvre sont proportionnels au nombre de solutions candidates - qui, dans de nombreux problèmes pratiques, a tendance à croître très rapidement à mesure que la taille du problème augmente ( § Explosion combinatoire ). Par conséquent, la recherche par force brute est généralement utilisée lorsque la taille du problème est limitée ou lorsqu'il existe des heuristiques spécifiques au problème qui peuvent être utilisées pour réduire l'ensemble de solutions candidates à une taille gérable. La méthode est également utilisée lorsque la simplicité de mise en œuvre est plus importante que la rapidité.

C'est le cas, par exemple, dans les applications critiques où toute erreur dans l' algorithme aurait des conséquences très graves ou lors de l' utilisation d'un ordinateur pour prouver un théorème mathématique . La recherche par force brute est également utile comme méthode de base lors de l' analyse comparative d' autres algorithmes ou métaheuristiques . En effet, la recherche par force brute peut être considérée comme la métaheuristique la plus simple . La recherche par force brute ne doit pas être confondue avec le retour en arrière , où de grands ensembles de solutions peuvent être écartés sans être explicitement énumérés (comme dans la solution informatique classique au problème des huit reines ci-dessus). La méthode de la force brute pour trouver un élément dans une table - à savoir, vérifier toutes les entrées de cette dernière, séquentiellement - est appelée recherche linéaire .

Implémentation de la recherche par force brute

Algorithme de base

Dans l'ordre candidat pour P après l'actuel c .

valide ( P , c ): vérifier si le candidat c est une solution pour P .
sortie ( P , c ): utiliser la solution c de P en fonction de l'application.

La procédure suivante doit également indiquer quand il n'y a plus de candidats pour l'instance P , après celle actuelle c . Une manière pratique de le faire est de renvoyer un «candidat nul», une valeur de données conventionnelle Λ qui est distincte de tout candidat réel. De même , la première procédure devrait revenir Λ s'il n'y a pas candidats à tous pour l'instance P . La méthode de la force brute est alors exprimée par l'algorithme

c ← first(P)
while c ≠ Λ do
    if valid(P,c) then
        output(P, c)
    c ← next(P, c)
end while

Par exemple, lorsque vous recherchez les diviseurs d'un entier n , les données d'instance P sont le nombre n . L'appel first ( n ) doit renvoyer l'entier 1 si n ≥ 1, ou Λ sinon; l'appel suivant ( n , c ) doit retourner c + 1 si c < n , et Λ sinon; et valid ( n , c ) doit retourner true si et seulement si c est un diviseur de n . (En fait, si nous choisissons Λ pour être n + 1, les tests n ≥ 1 et c < n ne sont pas nécessaires.) L'algorithme de recherche par force brute ci-dessus appellera la sortie pour chaque candidat qui est une solution à l'instance P donnée . L'algorithme est facilement modifié pour s'arrêter après avoir trouvé la première solution ou un nombre spécifié de solutions; ou après avoir testé un nombre spécifié de candidats, ou après avoir passé un certain temps CPU .

Explosion combinatoire

Le principal inconvénient de la méthode de la force brute est que, pour de nombreux problèmes du monde réel, le nombre de candidats naturels est prohibitif. Par exemple, si nous recherchons les diviseurs d'un nombre comme décrit ci-dessus, le nombre de candidats testés sera le nombre donné n . Donc, si n a seize chiffres décimaux, par exemple, la recherche nécessitera l'exécution d'au moins 10 ¹⁵ instructions informatiques, ce qui prendra plusieurs jours sur un PC classique . Si n est un nombre naturel aléatoire de 64 bits , qui compte environ 19 chiffres décimaux en moyenne, la recherche prendra environ 10 ans. Cette forte croissance du nombre de candidats, à mesure que la taille des données augmente, se produit dans toutes sortes de problèmes. Par exemple, si nous recherchons un réarrangement particulier de 10 lettres, alors nous en avons 10! = 3 628 800 candidats à considérer, qu'un PC typique peut générer et tester en moins d'une seconde. Cependant, l'ajout d'une lettre supplémentaire - ce qui ne représente qu'une augmentation de 10% de la taille des données - multipliera le nombre de candidats par 11, soit une augmentation de 1000%. Pour 20 lettres, le nombre de candidats est de 20 !, soit environ 2,4 × 10 ¹⁸ ou 2,4 quintillions ; et la recherche prendra environ 10 ans. Ce phénomène indésirable est communément appelé l' explosion combinatoire ou la malédiction de la dimensionnalité .

Un exemple de cas où la complexité combinatoire conduit à une limite de solvabilité est la résolution des échecs . Les échecs ne sont pas un jeu résolu . En 2005, toutes les fins de parties d'échecs avec six pièces ou moins ont été résolues, montrant le résultat de chaque position si elle est jouée parfaitement. Il a fallu dix ans de plus pour compléter la base de table avec une autre pièce d'échecs ajoutée, complétant ainsi une base de table de 7 pièces. Ajouter une pièce de plus à une fin d'échecs (créant ainsi une base de table de 8 pièces) est considéré comme insoluble en raison de la complexité combinatoire supplémentaire.

Accélérer les recherches par force brute

Une façon d'accélérer un algorithme de force brute consiste à réduire l'espace de recherche, c'est-à-dire l'ensemble des solutions candidates, en utilisant des heuristiques spécifiques à la classe de problème. Par exemple, dans le problème des huit reines, le défi consiste à placer huit reines sur un échiquier standard afin qu'aucune reine n'attaque une autre. Puisque chaque reine peut être placée dans n'importe laquelle des 64 cases, il y a en principe 64 ⁸ = 281 474 976 710 656 possibilités à considérer. Cependant, comme les reines se ressemblent toutes, et que deux reines ne peuvent pas être placées sur la même case, les candidats sont tous les moyens possibles de choisir un ensemble de 8 cases parmi l'ensemble des 64 cases; ce qui signifie 64 choisir 8 = 64! / (56! * 8!) = 4 426 165 368 solutions candidates - environ 1/60 000 de l'estimation précédente. De plus, aucun arrangement avec deux reines sur la même ligne ou la même colonne ne peut être une solution. Par conséquent, nous pouvons restreindre davantage l’ensemble des candidats à ces arrangements.

Comme le montre cet exemple, un peu d'analyse conduira souvent à des réductions spectaculaires du nombre de solutions candidates et peut transformer un problème insoluble en un problème insignifiant.

Dans certains cas, l'analyse peut réduire les candidats à l'ensemble de toutes les solutions valides; c'est-à-dire qu'il peut produire un algorithme qui énumère directement toutes les solutions souhaitées (ou trouve une solution, selon le cas), sans perdre de temps avec des tests et la génération de candidats invalides. Par exemple, pour le problème «trouver tous les nombres entiers entre 1 et 1 000 000 qui sont divisibles par 417», une solution de force brute naïve générerait tous les nombres entiers de la plage, en testant chacun d'eux pour la divisibilité. Cependant, ce problème peut être résolu beaucoup plus efficacement en commençant par 417 et en ajoutant à plusieurs reprises 417 jusqu'à ce que le nombre dépasse 1 000 000 - ce qui ne prend que 2398 (= 1 000 000 ÷ 417) étapes, et aucun test.

Réorganiser l'espace de recherche

Dans les applications qui ne nécessitent qu'une seule solution, plutôt que toutes les solutions, la durée d' exécution prévue d'une recherche par force brute dépendra souvent de l'ordre dans lequel les candidats sont testés. En règle générale, il faut d'abord tester les candidats les plus prometteurs. Par exemple, lors de la recherche d'un diviseur propre d'un nombre aléatoire n , il est préférable d'énumérer les diviseurs candidats dans l'ordre croissant, de 2 à n - 1 , que l'inverse - car la probabilité que n soit divisible par c est 1 / c . De plus, la probabilité qu'un candidat soit valide est souvent affectée par les précédents essais infructueux. Par exemple, considérons le problème de trouver un 1 bit dans une chaîne P donnée de 1000 bits . Dans ce cas, les solutions candidates sont les indices 1 à 1000, et un candidat c est valide si P [ c ] = 1 . Maintenant, supposons que le premier bit de P soit également susceptible d'être 0 ou 1 , mais chaque bit par la suite est égal au précédent avec une probabilité de 90%. Si les candidats sont énumérés par ordre croissant, de 1 à 1000, le nombre t de candidats examinés avant le succès sera d'environ 6, en moyenne. En revanche, si les candidats sont énumérés dans l'ordre 1,11,21,31 ... 991,2,12,22,32 etc., la valeur attendue de t ne sera qu'un peu plus de 2. en général, l'espace de recherche doit être énuméré de telle manière que le candidat suivant soit le plus susceptible d'être valide, étant donné que les essais précédents ne l'étaient pas . Donc, si les solutions valides sont susceptibles d'être «groupées» dans un certain sens, alors chaque nouveau candidat doit être aussi éloigné que possible des précédents, dans ce même sens. L'inverse est vrai, bien sûr, si les solutions sont susceptibles d'être réparties plus uniformément que prévu par hasard.

Alternatives à la recherche par force brute

Il existe de nombreuses autres méthodes de recherche, ou métaheuristiques, qui sont conçues pour tirer parti de divers types de connaissances partielles que l'on peut avoir sur la solution. L'heuristique peut également être utilisée pour effectuer une coupure précoce de certaines parties de la recherche. Un exemple de ceci est le principe minimax pour la recherche d'arbres de jeu, qui élimine de nombreux sous-arbres à un stade précoce de la recherche. Dans certains domaines, tels que l'analyse du langage, des techniques telles que l' analyse des graphiques peuvent exploiter les contraintes du problème pour réduire un problème de complexité exponentielle en un problème de complexité polynomiale. Dans de nombreux cas, comme dans les problèmes de satisfaction de contraintes , on peut réduire considérablement l'espace de recherche au moyen de la propagation de contraintes , qui est efficacement implémentée dans les langages de programmation de contraintes . L'espace de recherche des problèmes peut également être réduit en remplaçant le problème complet par une version simplifiée. Par exemple, aux échecs sur ordinateur , plutôt que de calculer l' arbre de minimax complet de tous les coups possibles pour le reste du jeu, un arbre plus limité de possibilités de minimax est calculé, l'arbre étant élagué à un certain nombre de coups, et le reste de l'arbre étant approximé par une fonction d'évaluation statique .

En cryptographie

En cryptographie , une attaque par force brute consiste à vérifier systématiquement toutes les clés possibles jusqu'à ce que la bonne clé soit trouvée. Cette stratégie peut en théorie être utilisée contre toutes les données cryptées (à l'exception d'un pad ponctuel ) par un attaquant incapable de tirer parti de toute faiblesse d'un système de cryptage qui, autrement, faciliterait sa tâche.

La longueur de clé utilisée dans le chiffrement détermine la faisabilité pratique d'effectuer une attaque par force brute, avec des clés plus longues exponentiellement plus difficiles à déchiffrer que les plus courtes. Les attaques par force brute peuvent être rendues moins efficaces en masquant les données à encoder, ce qui rend plus difficile pour un attaquant de reconnaître quand il a déchiffré le code. L'une des mesures de la force d'un système de cryptage est le temps qu'il faudrait théoriquement à un attaquant pour monter une attaque par force brute réussie contre lui.

Languages

In other projects