Discussion :

[proc02]

Bonjour à tous,
Je voudrais implémenter le problème du voyageur de commerce en java en utilisant l'algorithme glouton ,et mon problème c'est que je n'arrive pas à bien cerner la notion de l'algorithme glouton je voudrais que voudrais que vous m'expliquiez cette notion
et je voudrais savoir aussi comment m'y prendre pour mon code pour une liste de villes données .
je serai vraiment heureux d'avoir des réponses merci à vous.

[thelvin]

Ça doit être parce qu'il existe de nombreuses manière d'utiliser un algorithme glouton sur le problème du voyageur de commerce.

Il faudrait d'abord que tu nous dises ce que tu en sais, puis à partir d'où ça devient un peu confus dans ta tête. On verra ce qu'on pourra y faire.

[proc02]

Ça doit être parce qu'il existe de nombreuses manière d'utiliser un algorithme glouton sur le problème du voyageur de commerce.

merci à vous
je sais que c'est une méthode heuristique permettant d'obtenir une solution optimale laquelle obtenu par une suite de choix de solution optimale
mais là n'est vraiment plus le problème ,mon problème c'est comment m'y prendre pour l'implémentation.

[thelvin]

je sais que c'est une méthode heuristique permettant d'obtenir une solution optimale laquelle obtenu par une suite de choix de solution optimale

Non. Une heuristique consiste justement à ne pas chercher de solution optimale, mais une solution qui fera l'affaire.
La raison pour laquelle on utilise une heuristique au lieu de chercher la solution optimale est variable, dans le cas du voyageur de commerce c'est évidemment pour que ce soit moins long à calculer. Passer de O(n² * 2^n) à plus efficace.

obtenu par une suite de choix de solution optimale

Donc, dans le problème du voyageur de commerce, quel genre de choix de solutions pourrait-on faire à la suite, et que choisir comme optimal ? (Indice : laisse tomber, il n'y a pas de choix optimal, il n'y a qu'éviter des choix stupides.)

mais là n'est vraiment plus le problème ,mon problème c'est comment m'y prendre pour l'implémentation.

Si tu ne sais pas où tu vas tu ne risques pas d'y arriver.
Tu ne peux pas possiblement avoir d'autre problème que mieux comprendre ce qui t'est demandé.
À partir du moment où tu as un problème ça ne peut pas être autre chose que ne pas avoir compris quelque chose.

[professeur shadoko]

globalement un algo "glouton" prend la solution qui lui semble immédiatement la plus favorable: il prèfère la "courte vue" à une stratégie plus élaborée qui regarde les conséquences plusieurs coups à l'avance.
on peut avoir plusieurs degrés de gloutonnerie en se donnant une profondeur maximum d'exploration de l'arbre des possibles.