human
Veuillez expliquer ce qu'est la "recherche par force brute"
gpt
En informatique, la recherche par force brute ou recherche exhaustive, également appelée génération et test, 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 pour 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 à augmenter 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 des 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 des 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 référence 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 rejetés sans être explicitement énumérés (comme dans la solution informatique du manuel 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, de manière séquentielle – est appelée recherche linéaire.