Il y a beaucoup de problèmes qui surviennent dans notre vie quotidienne. De même, il y a beaucoup de problèmes dans le domaine de la programmation.
Il existe de nombreuses méthodes pour résoudre un problème particulier lié aux algorithmes et à la programmation. La force brute et la programmation dynamique sont des types de techniques permettant de résoudre un problème et de trouver une solution.
Faits marquants
- Les algorithmes de force brute recherchent de manière exhaustive toutes les solutions possibles, tandis que la programmation dynamique divise les problèmes en petits sous-problèmes qui se chevauchent et stocke les solutions pour les réutiliser.
- La programmation dynamique offre une efficacité améliorée et une complexité de calcul réduite par rapport aux approches par force brute.
- Les méthodes de force brute sont plus faciles à mettre en œuvre, tandis que la programmation dynamique nécessite une compréhension plus approfondie du problème pour identifier la sous-structure optimale et les sous-problèmes qui se chevauchent.
Brute Force vs programmation dynamique
La différence entre Brute Force et la programmation dynamique est l'efficacité. Les deux techniques ont leur efficacité. Le la force brute La méthode itère plusieurs fois sur l'ensemble de données donné, ce qui entraîne une faible efficacité, tandis que la méthode de programmation dynamique itère sur l'ensemble de données une seule fois, ce qui conduit à une bonne efficacité. Mais oui, les deux méthodes sont utiles dans des situations différentes.
L'approche Brute Force trouve toutes les solutions possibles liées à un problème donné jusqu'à ce qu'elle trouve une solution satisfaisante. C'est toujours le moyen le plus simple de mettre en place et de garantir une solution si elle existe.
Cette nature de la technique de la force brute conduit à ralentir son fonctionnement. L'approche de la force brute est toujours l'approche la plus simple pour obtenir une solution.
La programmation dynamique est une version optimisée de la résolution d'un problème en moins de temps et avec moins d'effort. C'est l'optimisation de la récursivité car, en récursivité, nous résolvons plusieurs fois le même ensemble d'entrées, alors qu'en programmation dynamique, nous ne résolvons que les cas non résolus du problème donné.
Tableau de comparaison
| Paramètres de comparaison | Brute Force | Programmation dynamique |
|---|---|---|
| Méthodologie | Il trouve toutes les solutions possibles à un problème donné. | Il ne trouve qu'une seule solution optimale. |
| Complexité temporelle | O(mn), où m est le nombre de caractères à trouver et n est la taille de l'entrée. | O(n), où n est le nombre de sous-problèmes uniques |
| Exemple | Tri de sélection | Floyd Warshell |
| Itérations | Le nombre d'itérations est plus | Le nombre d'itérations est inférieur |
| Efficacité | Moins efficace | Plus efficace |
Qu'est-ce que la force brute ?
Dans le domaine de Informatique, Brute Force est une technique populaire pour trouver une solution. La méthode Brute Force garantit une solution à un problème donné, mais son exécution prend beaucoup de temps et est inefficace.
Il commence par énumérer systématiquement tous les cas et vérifier s'ils satisfont ou non à la condition.
Si nous prenons un exemple de tri des éléments d'un tableau, puis par l'approche de la force brute, nous traverserons le tableau plusieurs fois jusqu'à ce que nous obtenions la solution souhaitée. Cela entraînera une perte de temps.
C'est la raison pour laquelle on l'appelle chronophage.
La technique Brute Force est utilisée lorsque l'ensemble de données est limité car cela entraînera de nombreuses complications si nous appliquons de nombreux calculs plusieurs fois sur d'énormes quantités de données. Chaque fois qu'un nouveau problème est créé dont la solution appropriée n'est pas connue, la technique Brute Force est utilisée comme méthode de référence.
L'inconvénient majeur de Brute Force pour résoudre des problèmes réels est qu'il augmente le nombre de cas à vérifier. Par exemple, si nous voulons trouver un diviseur d'un nombre, et disons que son diviseur est 16, alors la force brute effectuera 10^15 calculs pour trouver la solution.
Qu'est-ce que la programmation dynamique ?
La programmation dynamique est une méthode optimisée pour résoudre des problèmes mathématiques et informatiques. Il a été développé par Richard Bellman dans les années 1950.
Aujourd'hui, il trouve des applications dans divers domaines en raison de son pouvoir d'optimisation.
Il résout un problème complexe en le décomposant en sous-problèmes plus simples de manière récursive. Ensuite, chaque sous-problème est résolu récursivement.
Le point principal est que si un sous-cas "a" se produit 4 fois dans un problème complexe, alors la programmation dynamique ne le résoudra qu'une seule fois, alors que la récursivité le résoudra 4 fois.
C'est la raison pour laquelle la programmation dynamique est préférée. Dans le cas des mathématiques, la programmation dynamique consiste à simplifier une décision en la décomposant en sous-problèmes.
Dans le cas de l'informatique, nous avons deux termes importants où nous appliquons la programmation dynamique, le premier est la sous-structure optimale, l'autre est le sous-problème qui se chevauche.
La sous-structure optimale signifie que la solution du problème d'optimisation est obtenue en combinant une solution optimisée de tous les sous-problèmes. Le chevauchement des sous-problèmes signifie que l'espace des sous-problèmes doit être petit.
Il a aussi des inconvénients, comme toute pièce de monnaie a deux faces. Comme nous le savons, il stocke le résultat intermédiaire tout en résolvant le sous-problème, ce qui entraîne une forte utilisation de la mémoire.
Principales différences entre la force brute et la programmation dynamique
- L'approche Brute Force résout le problème en itérant sur l'ensemble de données un grand nombre de fois. Alors que la programmation dynamique n'itère qu'une seule fois et donne une solution optimale.
- La solution fournie par Brute Force n'est pas garantie d'être optimale car elle fournit toutes les solutions possibles. Alors que la solution apportée par la Programmation Dynamique sera toujours optimale.
- La méthode Brute Force résout en considérant tous les ensembles de données à la fois, tandis que la programmation dynamique résout un problème en divisant le problème donné en plusieurs sous-problèmes.
- L'approche de la force brute n'utilise pas le concept de sous-structure optimale et de sous-problèmes qui se chevauchent. La programmation dynamique utilise ces concepts.
- La méthode de la force brute n'est pas optimale et efficace. Elle résout plusieurs fois le même calcul, alors que la programmation Dynamin est optimale et efficace car elle ne résout qu'une seule fois un calcul et utilise la mémorisation.
- https://www.science.org/doi/abs/10.1126/science.153.3731.34
- https://dl.acm.org/doi/fullHtml/10.1145/3107239
Dernière mise à jour : 14 juillet 2023
J'ai mis tellement d'efforts à écrire ce billet de blog pour vous apporter de la valeur. Cela me sera très utile, si vous envisagez de le partager sur les réseaux sociaux ou avec vos amis/famille. LE PARTAGE C'EST ♥️
Sandeep Bhandari est titulaire d'un baccalauréat en génie informatique de l'Université Thapar (2006). Il a 20 ans d'expérience dans le domaine de la technologie. Il s'intéresse vivement à divers domaines techniques, notamment les systèmes de bases de données, les réseaux informatiques et la programmation. Vous pouvez en savoir plus sur lui sur son page bio.
