Algorithme Glouton appliqué au problème du voyageur de commerce

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.

Ç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.

Citation:

---

Envoyé par 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.

---

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.:aie:

Citation:

---

Envoyé par proc02

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.

Citation:

---

Envoyé par proc02

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.)

Citation:

---

Envoyé par proc02

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.

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.