La recherche exhaustive ou recherche par force brute est une méthode algorithmique qui consiste principalement à essayer toutes les solutions possibles.
L'objectif de cette activité est d'implémenter en Python l'algorithme par force brute afin de trouver la solution à certains problèmes.
Recherche d'un code secret ou d'un mot de passe |
Aucun algorithme particulier existe pour trouver un code secret que l'on ne connaît pas. La seule solution consiste à tester un par un tous les codes possibles, ce qui correspond à l'algorithme par force brute.
 |
|
|
Tri d'une liste par force brute |
Pour trier une listes différents algorithmes performents existent (tri fusion, tri rapide, Timsort, etc.).
Mais on peut aussi utiliser l'algorithme par force brute consistant à comparer toutes les combinaisons possibles de la liste au résultat attendu (liste triée).
Pour obtenir toutes les permutations d'une liste on utilisera la fonction permutations() du module itertools de Python.
|
Le problème du sac à dos |
Les problèmes de type "problème du sac à dos" peuvent se résoudre avec un algorithme glouton. Problèmes alors rencontrés : quel est le meilleur choix à faire à chaque étape ? L'algorithme glouton donne-t-il forcément la solution optimale ?
L'algorithme par force brute lui, s'il est bien implémenté, donnera forcément la solution optimale.
|
Résolution d'un carré magique |
En mathématiques, un carré magique d'ordre n est composé de n2 entiers strictement positifs, écrits sous la forme d'un tableau carré de dimension nxn . Il faut disposer ces nombres entiers dans les cases de telle sorte que :
Cette somme unique est appelée la constante magique.
Voici un exemple de carré magique d'ordre 3 (dimension 3x3) et de constante magique 15 (chacune des 8 sommes vaut 15) :
Et voici un exemple de carré magique d'ordre 4 (dimension 4x4) et de constante magique 34 :
Mais combien existe-t-il de carrés magiques différents d'ordre 3 ? Et d'ordre 4 ? La recherche par force brute peut apporter une réponse.
Voici des exemples de résolution de carré magique en Python en implémentant une recherche par force brute :
|
|
|
|
|
|
|
|
|
Pour plus d'informations sur les carrés magiques cliquez ici
Résolution d'un problème logique |
Un problème logique (ou problème avec contraintes) possède un énoncé contenant un grand nombre de contraintes à satisfaire simultanément, et peut ête vu comme une expression logique complexe.
Voici des exemples de problèmes logiques :
 |
Et voici quelques exemples de résolution en Python en implémentant une recherche par force brute :
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Nouveaux problèmes à résoudre |
Voici de nouveaux problèmes logiques à résoudre.
Où est le panda ?
Dans une rue, 5 maisons sont alignées. Dans chaque maison habite un animal, qui joue d'un instrument de musique et qui mange un fruit particulier.
Les données du problème sont :
Et voici les 3 problématiques à résoudre :
Où est le koala ?
Dans une rue 3 maisons voisines sont de couleurs différentes. Des personnes vivent dans ces maisons et elles ont chacune un animal de compagnie différent.
Les données du problème sont :
La problématique à résoudre est :
Où est le pharmacien ?
Les données du problème sont :
Trois commerçants habitent dans 3 maisons situées aux numéros 21, 23 et 25 de la même rue. Le boucher habite dans la maison jaune, qui est à côté de la rouge mais qui n’est pas à côté de la verte. L’épicier, qui n’est pas suisse, habite à côté du Français. L’Italien habite au numéro 21 et sa maison n’est pas jaune.
La problématique à résoudre est :
Quelle est la nationalité du pharmacien, quelle est la couleur de sa maison, et où habite-t-il ?
Où est la maison blanche ?
Dans une rue, il y a quatre maisons voisines de 4 couleurs différentes. Dans chaque maison vit une personne de nationalité différente ; chacun des 4 propriétaires a un métier différent.
Les données du problème sont :
La problématique à résoudre est :
Où est le kangourou ?
Dans une ruelle, il y a cinq maisons voisines de 5 couleurs différentes, et dans chaque maison vit une personne de nationalité différente. Chacun des 5 propriétaires boit un certain type de boisson, joue d'un certain type d'instrument de musique et garde un certain animal domestique.
Les données du problème sont :
La problématique à résoudre est :
Vous en voulez encore ?
Voici de nouveaux problèmes logiques à résoudre. Pour chacun d'entre eux il est vivement conseillé de comparer les solutions obtenues par différentes méthodes :
Ces 3 techniques de résolution mènent-elles systématiquement au même résultat pour chacun des problèmes ci-dessous ?
 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Avant de tester ces problème avec une intelligence artificielle vous devez posséder la solution exacte (soit après réflexion intellectuelle sur un papier, soit en utilisant Python). La question posée à l'intelligence artificielle n'est pas "Quelle est la solution du problème ?" mais c'est "L'intelligence artificielle arrive-t-elle à résoudre un tel problème ?". De plus, les différentes intelligences artificielles donnent-elles systématiquement les mêmes solutions pour un problème donné ? Chacun se fera une idée.
Voici quelques liens externes pour tester ces problèmes avec une intelligence artificielle :
 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Conclusion |
Bien que Python ne soit pas spécialement adapté pour résoudre des problèmes logiques, il y parvient instantanément si on implémente proprement un algorithme par force brute démélant le vrai du faux à partir des données de l'énoncé.
Réalisé par Jean-Christophe MICHEL
© Décembre 2024