Algorithmes gloutons

1. Glouton : Fait un choix définitif à chaque étape sans retour en arrière.
2. Programmation dynamique : Explore plusieurs sous-problèmes et stocke les résultats pour éviter les calculs redondants, garantissant l'optimum.

💡 À retenir : Glouton = choix immédiat ; Dynamique = choix réfléchi avec mémoire.

Oui, en général, les algorithmes gloutons sont très rapides car ils ne font qu'un seul passage sur les données sans explorer toutes les combinaisons possibles. Cependant, leur rapidité ne garantit pas l'exactitude de la solution.

💡 À retenir : La rapidité est l'atout majeur, mais la précision dépend de la structure du problème.

Il n'y a pas de règle magique. Il faut prouver mathématiquement que le choix local optimal conduit toujours à l'optimum global. Si le problème est "matroïde", alors le glouton marche à 100%.

💡 À retenir : Si le problème est complexe, testez avec des contre-exemples.

Kruskal sert à trouver l'arbre couvrant minimal d'un graphe. 1. On trie les arêtes par poids croissant. 2. On ajoute l'arête si elle ne forme pas de cycle.

💡 À retenir : Kruskal = tri des arêtes + Union-Find pour éviter les cycles.

Oui, il peut échouer à trouver la solution optimale, par exemple dans le problème du sac à dos 0/1 (où on ne peut pas couper les objets).

💡 À retenir : Le glouton donne souvent une solution "acceptable" mais pas forcément la meilleure.

La complexité dépend principalement de deux phases : 1. Le tri des éléments (souvent $O(n \log n)$). 2. La boucle de sélection des éléments ($O(n)$). La complexité totale est donc dominée par le tri.

💡 À retenir : $T(n) = O(\text{Tri}) + O(\text{Boucle})$.

Le tri permet de mettre en évidence l'élément qui respecte le mieux le critère glouton (le plus grand, le plus petit, le meilleur ratio).

💡 À retenir : Sans tri, on ne peut pas identifier efficacement le meilleur candidat local.

Oui, on peut utiliser une approche gloutonne (toujours aller vers la ville la plus proche), mais cela ne garantit pas le chemin le plus court global.

💡 À retenir : C'est une heuristique, pas une solution optimale.

Non, les algorithmes gloutons s'appliquent à divers problèmes : ordonnancement, rendu de monnaie, compression de données (Huffman), etc.

💡 À retenir : Le glouton est une méthode de conception, pas une structure de données.

Huffman utilise une approche gloutonne pour créer un arbre binaire de codage optimal, minimisant la taille totale du message compressé.

💡 À retenir : Huffman = compression optimale par fréquence.

Non, si le tri est nécessaire, il est au minimum $O(n \log n)$. S'il n'y a pas de tri, il peut être $O(n)$.

💡 À retenir : La complexité dépend de la structure initiale des données.

Oui, mais attention : si la récursivité sert à explorer plusieurs branches, ce n'est plus un algorithme glouton pur. Le glouton est par nature itératif.

💡 À retenir : Le glouton est une stratégie de décision, pas une technique d'implémentation.