Table des matières:
Définition - Que signifie l'algorithme gourmand?
Un algorithme gourmand est une stratégie algorithmique qui fait le meilleur choix optimal à chaque petite étape dans le but de conduire finalement à une solution globalement optimale. Cela signifie que l'algorithme choisit la meilleure solution pour le moment sans tenir compte des conséquences. Il sélectionne la meilleure sortie immédiate, mais ne prend pas en compte la situation dans son ensemble, il est donc considéré comme gourmand.
Techopedia explique l'algorithme gourmand
Un algorithme gourmand fonctionne en choisissant la meilleure réponse possible à chaque étape, puis en passant à l'étape suivante jusqu'à la fin, sans égard à la solution globale. Elle espère seulement que la voie qu'elle emprunte est la plus optimale au niveau mondial, mais comme il a été prouvé à maintes reprises, cette méthode ne propose pas souvent une solution globalement optimale. 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 prenant beaucoup de raccourcis dans une entreprise manufacturière: à court terme, de grandes quantités sont économisées dans les coûts 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 à mesure que 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 gourmand fonctionne le mieux pour trouver ou se rapprocher de la solution optimale au niveau mondial, comme dans la construction d'un arbre de Huffman ou d'un arbre d'apprentissage des décisions.
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 de données candidat qui a besoin d'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 objective qui attribue une valeur à une solution partielle
- Une fonction de solution qui indique que la solution optimale a été découverte
