Programmation dynamique vs Diviser pour régner vs Algorithmes gloutons
La programmation dynamique, l'approche diviser pour régner et les algorithmes gloutons sont des techniques d'optimisation algorithmique qui peuvent être utilisées pour résoudre des problèmes complexes. Chacune a ses propres caractéristiques, forces et faiblesses.
Les trois approches en bref
Programmation dynamique
La programmation dynamique est généralement utilisée pour les problèmes d'optimisation combinatoire, où une solution doit être trouvée parmi un grand nombre de possibilités.
Principe : Décomposer le problème en sous-problèmes plus petits et résoudre chaque sous-problème de manière récursive, en mémorisant les résultats pour éviter les calculs redondants (mémoïsation).
Exemples : Plus court chemin, LCS, sac à dos, Fibonacci optimisé.
Diviser pour régner
La technique de diviser pour régner est souvent utilisée pour les problèmes où une solution peut être facilement trouvée en combinant les solutions de sous-problèmes plus petits et indépendants.
Principe : Diviser le problème en sous-problèmes plus petits, résoudre chaque sous-problème de manière récursive et combiner les résultats.
Exemples : Tri fusion, tri rapide, recherche binaire, multiplication de matrices.
Algorithmes gloutons
Les algorithmes gloutons sont une technique d'optimisation qui consiste à faire des choix locaux optimaux à chaque étape, dans l'espoir que ces choix locaux conduiront à une solution globale optimale.
Principe : Prendre la décision qui semble la meilleure sur le moment, sans jamais revenir en arrière.
Exemples : Dijkstra, Kruskal, rendu de monnaie (systèmes canoniques), sac à dos fractionnaire.
Tableau comparatif détaillé
| Caractéristique | Programmation dynamique | Diviser pour régner | Algorithmes gloutons |
|---|---|---|---|
| Type de problèmes | Optimisation combinatoire | Problèmes divisibles indépendants | Optimisation locale |
| Structure des sous-problèmes | Superposés (overlapping) | Indépendants | Un seul sous-problème à chaque étape |
| Mémoïsation / Cache | Essentielle (stockage des résultats) | Non nécessaire | Non nécessaire |
| Approche | Top-down ou bottom-up | Top-down récursif | Séquentiel (pas à pas) |
| Retour en arrière | Oui (explore toutes les possibilités) | Oui (via récursion) | Non (décisions définitives) |
| Garantie d'optimalité | Oui (si structure optimale) | Oui (pour les problèmes adaptés) | Pas toujours (dépend du problème) |
| Complexité temporelle | Souvent polynomiale (O(n²), O(n³)) | Souvent O(n log n) ou exponentielle | Souvent linéaire ou O(n log n) |
| Complexité spatiale | Peut être élevée (stockage des résultats) | Liée à la profondeur de récursion | Généralement faible (O(1) ou O(n)) |
| Facilité d'implémentation | Complexe (choix des états, récurrence) | Moyenne (récursion + combinaison) | Simple (choix local évident) |
Points communs entre les trois approches
Les trois approches visent à résoudre des problèmes complexes en décomposant ou en simplifiant le problème initial, afin de réduire la complexité temporelle et/ou spatiale.
Les trois techniques peuvent être appliquées à divers problèmes d'optimisation et de recherche. Leur efficacité dépend de la nature du problème et de ses contraintes.
Dans certains cas, les trois techniques peuvent être combinées pour résoudre un problème spécifique. Par exemple, un algorithme de programmation dynamique peut utiliser une approche de diviser pour régner pour réduire la taille des sous-problèmes.
Les trois approches font des compromis entre temps d'exécution et utilisation mémoire, mais de manières différentes : la PD privilégie la mémoire pour gagner du temps, DPR est souvent équilibré, et les gloutons minimisent les deux.
Différences fondamentales
1. Gestion des sous-problèmes
| Critère | Programmation dynamique | Diviser pour régner | Algorithmes gloutons |
|---|---|---|---|
| Relation entre sous-problèmes | Superposés (dépendants) | Indépendants | Un seul chemin exploré |
| Nombre de sous-problèmes | Nombre limité d'états uniques | Souvent une arborescence complète | Un seul sous-problème par étape |
| Réutilisation des résultats | Essentielle (mémoïsation) | Aucune (chaque sous-problème est unique) | Sans objet |
Illustration des différences
Problème
/ \
A B
\ /
C
(C partagé)
Problème
/ \
A B
/ \ / \
A1 A2 B1 B2
(indépendants)
Étape 1 → Étape 2 → Étape 3 → ...
(un seul chemin, pas de retour)
2. Optimalité des solutions
Garantissent généralement des solutions optimales pour les problèmes qu'elles résolvent, car elles explorent (explicitement ou implicitement) toutes les possibilités.
Ne fournissent pas toujours des solutions optimales. Cependant, dans certains cas, ils peuvent produire des solutions optimales ou des solutions proches de l'optimal.
Avantage : Ils sont souvent plus simples et plus rapides, ce qui les rend attrayants quand une solution approchée suffit ou quand les ressources sont limitées.
3. Compromis temps/mémoire
| Aspect | Programmation dynamique | Diviser pour régner | Algorithmes gloutons |
|---|---|---|---|
| Tendance | Réduit le temps au prix de la mémoire | Équilibre souvent bon | Minimise les deux |
| Stockage intermédiaire | Élevé (tableaux, dictionnaires) | Pile de récursion uniquement | Minimal (quelques variables) |
| Exemple typique | Floyd-Warshall: O(n²) mémoire | Merge sort: O(n) mémoire temporaire | Dijkstra: O(n) pour les distances |
Exemples concrets comparés
Exemple 1 : Calcul de Fibonacci
| Méthode | Code | Complexité temps | Complexité mémoire |
|---|---|---|---|
| Diviser pour régner (naïf) | return fib(n-1) + fib(n-2) | O(2ⁿ) - exponentiel | O(n) - pile |
| Programmation dynamique | memo[n] = fib(n-1) + fib(n-2) | O(n) - linéaire | O(n) - cache |
| Glouton | Non applicable (pas de choix local évident) | ||
Exemple 2 : Plus court chemin
| Méthode | Algorithme | Caractéristiques | Optimalité |
|---|---|---|---|
| Programmation dynamique | Floyd-Warshall | Calcule toutes les paires, O(n³), O(n²) mémoire | Optimale |
| Diviser pour régner | Non standard pour ce problème | Peu adapté | - |
| Glouton | Dijkstra | Source unique, O((V+E)log V) avec tas | Optimale (poids positifs) |
Exemple 3 : Sac à dos
| Méthode | Version | Complexité | Optimalité |
|---|---|---|---|
| Programmation dynamique | Sac à dos 0/1 | O(n × capacité) | Optimale |
| Diviser pour régner | Non adapté | - | - |
| Glouton | Sac à dos fractionnaire | O(n log n) | Optimale |
| Glouton | Sac à dos 0/1 | O(n log n) | Pas optimale en général |
Comment choisir la bonne approche ?
- Le problème a-t-il une sous-structure optimale ?
- Non → Peut-être diviser pour régner si indépendance, sinon chercher autre chose
- Oui → Passer à l'étape suivante
- Y a-t-il superposition des sous-problèmes ?
- Oui → Programmation dynamique (exploite la superposition)
- Non → Peut-on faire un choix local optimal définitif ?
- Le choix local optimal mène-t-il à l'optimum global ?
- Oui → Algorithme glouton (efficace et simple)
- Non → Diviser pour régner (si sous-problèmes indépendants)
Résumé des critères de choix
| Critère | Programmation dynamique | Diviser pour régner | Algorithmes gloutons |
|---|---|---|---|
| Sous-structure optimale | Requise | Requise | Requise |
| Sous-problèmes superposés | Requis | Indépendants | N/A |
| Propriété de choix glouton | Non nécessaire | Non nécessaire | Requise |
| Exploration exhaustive | Oui (implicitement) | Oui (explicitement) | Non (un seul chemin) |
Choisir la bonne technique
Pour chacun des problèmes suivants, indiquez quelle technique (programmation dynamique, diviser pour régner, ou glouton) serait la plus appropriée et justifiez votre réponse :
- Problème A : Trier une liste de nombres.
- Problème B : Trouver la plus longue sous-séquence croissante dans une séquence.
- Problème C : Trouver l'arbre couvrant de poids minimum d'un graphe.
- Problème D : Calculer le nombre de façons de monter un escalier de n marches (pas de 1 ou 2).
- Problème E : Rechercher un élément dans un tableau trié.
- Problème F : Problème du voyageur de commerce (TSP) pour une solution exacte.
- Problème A - Tri de nombres : Diviser pour régner(Merge sort, Quick sort).
Les sous-problèmes (trier des sous-tableaux) sont indépendants et peuvent être combinés facilement. La programmation dynamique n'apporterait rien car il n'y a pas de superposition. Les gloutons ne fonctionnent pas pour le tri général.
- Problème B - Plus longue sous-séquence croissante : Programmation dynamique.
Ce problème a une sous-structure optimale et des sous-problèmes superposés (la LIS pour une position dépend des LIS pour les positions précédentes). La solution classique est O(n²) par PD, ou O(n log n) avec une approche plus sophistiquée.
- Problème C - Arbre couvrant minimum : Algorithme glouton(Kruskal, Prim).
La propriété de choix glouton est vérifiée : ajouter la plus petite arête qui ne crée pas de cycle (Kruskal) ou le plus petit sommet connecté à l'arbre courant (Prim) mène à l'optimum global. Les deux sont des gloutons optimaux.
- Problème D - Montée d'escalier : Programmation dynamique.
Ce problème est similaire à Fibonacci : ways(n) = ways(n-1) + ways(n-2). Il y a superposition des sous-problèmes. La PD donne une solution O(n) alors que la récursion naïve serait exponentielle.
- Problème E - Recherche dans tableau trié : Diviser pour régner(recherche binaire).
La recherche binaire divise le problème en deux moitiés indépendantes et n'en explore qu'une. C'est l'archétype de diviser pour régner. Pas de superposition, pas de choix glouton.
- Problème F - Voyageur de commerce (TSP) exact : Programmation dynamique(Held-Karp).
Le TSP a une sous-structure optimale et des sous-problèmes superposés (les mêmes sous-ensembles de villes apparaissent dans différents chemins). L'algorithme de Held-Karp utilise la PD en O(n²2ⁿ). Les gloutons donnent des approximations seulement.
- Diviser pour régner : Tri, recherche binaire
- Programmation dynamique : LIS, escalier, TSP exact
- Glouton : MST (Kruskal/Prim)
- La programmation dynamique est idéale pour les problèmes avec sous-structure optimale et sous-problèmes superposés (ex: LCS, sac à dos, Floyd-Warshall).
- L'approche diviser pour régner convient aux problèmes où les sous-problèmes sont indépendants et peuvent être combinés (ex: tri fusion, recherche binaire).
- Les algorithmes gloutons s'appliquent quand un choix local optimal mène à une solution globale optimale (ex: Dijkstra, Kruskal, rendu de monnaie canonique).
- La PD et DPR garantissent généralement l'optimalité, tandis que les gloutons ne l'offrent que sous certaines conditions.
- La PD fait un compromis temps/mémoire explicite en stockant les résultats intermédiaires.
- Les trois approches peuvent être combinées : par exemple, un algorithme de PD peut utiliser DPR pour réduire la taille des sous-problèmes.
- Le choix de la technique dépend de la nature du problème : indépendance des sous-problèmes, présence de superposition, validité de la propriété de choix glouton.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.