IMPLEMENTATION DE L'ALGORITHME GOURMAND
cs_Matt67
Messages postés
549
Date d'inscription
samedi 6 septembre 2003
Statut
Membre
Dernière intervention
6 mars 2010
-
6 juil. 2007 à 22:45
cs_rebiai Messages postés 2 Date d'inscription jeudi 22 novembre 2007 Statut Membre Dernière intervention 10 février 2008 - 27 déc. 2007 à 16:37
cs_rebiai Messages postés 2 Date d'inscription jeudi 22 novembre 2007 Statut Membre Dernière intervention 10 février 2008 - 27 déc. 2007 à 16:37
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/43359-implementation-de-l-algorithme-gourmand
https://codes-sources.commentcamarche.net/source/43359-implementation-de-l-algorithme-gourmand
27 déc. 2007 à 16:37
9 juil. 2007 à 13:14
7 juil. 2007 à 16:23
Les algorithmes gourmands (greedy, gloutons, voraces ...) sont une catégorie d'algorithmes qui ont pour stratégie de base de choisir à chaque étape l'option qui paraît la plus avantageuse dans l'immédiat, donc sans tenir compte de l'impact potentiellement négatif sur les choix qui pourront être faits plus tard.
Parfois, cette stratégie donne une solution optimale (exemple académique typique: recherche d'arbre de recouvrement optimal dans un graphe: algorithmes de kruskal et de prim). Parfois, pas. Quand la "solution" proposée n'est pas optimale, on dira plutôt que l'algorithme glouton est une heuristique, et un exemple typique est le choix du plus proche voisin dans la recherche d'un chemin pour le problème du voyageur de commerce (travelling salesman problem). Le 2-opt est une amélioration de cette heuristique: on fait le meilleur choix possible en tenant compte du choix qu'on pourra faire juste après aussi (je ne suis pas tout à fait sûr que c'est ça qu'on appelle le 2-opt ceci dit).
La question à poser à ayaha est donc: à quel problème as-tu appliqué cet algorithme gourmand? Et la solution obtenue est-il optimale?
Kirua
7 juil. 2007 à 02:40
A+
6 juil. 2007 à 22:45
Et, qu'est ce que l'algorithme Gourmand ???
Matt...