Graphes et réseauxSalesman

L’algorithme Greedy (ou l’algorithme du voisin le plus proche) est très simple: vous commencez dans une ville aléatoire et vous vous déplacez ensuite dans la ville la plus proche que vous n’avez jamais visitée. Une fois que vous avez visité toutes les villes, vous vous arrêtez.

Animation à venir…

Vous pouvez montrer qu'en moyenne, les chemins trouvés à l'aide de l'algorithme glouton sont 25% plus longs que le chemin le plus court possible.