Définition - Que signifie l'algorithme glouton?
Un algorithme glouton est une stratégie algorithmique qui fait le meilleur choix optimal à chaque petite étape dans le but de mener à terme à une solution globale optimale. Cela signifie que l'algorithme choisit la meilleure solution pour le moment sans tenir compte des conséquences. Il choisit la meilleure sortie immédiate, mais ne considère pas la situation dans son ensemble, il est donc considéré comme gourmand.
Definir Tech explique l'algorithme glouton
Un algorithme gourmand fonctionne en choisissant la meilleure réponse possible à chaque étape, puis en passant à l'étape suivante jusqu'à ce qu'elle atteigne la fin, sans tenir compte de la solution globale. Il espère seulement que la voie à suivre est la meilleure au niveau mondial, mais comme cela a été prouvé à maintes reprises, cette méthode ne propose pas souvent une solution optimale au niveau mondial. En fait, il est tout à fait possible que les solutions à court terme les plus optimales conduisent au pire résultat mondial possible.
Pensez-y comme prendre beaucoup de raccourcis dans une entreprise de fabrication: à court terme, de grandes quantités sont économisées en coût de fabrication, mais cela conduit finalement à une baisse car la qualité est compromise, ce qui entraîne des retours de produits et de faibles ventes lorsque les clients se familiarisent avec le Produit «bon marché». Mais ce n'est pas toujours le cas, il existe de nombreuses applications où l'algorithme glouton fonctionne le mieux pour trouver ou se rapprocher de la solution globalement optimale comme dans la construction d'un arbre de Huffman ou d'un arbre d'apprentissage de décision.
Par exemple: prenez le chemin avec la plus grande somme globale. Un algorithme gourmand prendrait le chemin bleu, en raison de la myopie, plutôt que le chemin orange, qui donne la plus grande somme.
Composants:
- Un ensemble candidat de données nécessitant une solution
- Une fonction de sélection qui choisit le meilleur contributeur à la solution finale
- Une fonction de faisabilité qui facilite la fonction de sélection en déterminant si un candidat peut contribuer à la solution
- Une fonction objectif qui attribue une valeur à une solution partielle
- Une fonction de solution qui indique que la solution optimale a été découverte