Algorithme du plus proche voisin
Voici les étapes de l’algorithme:
- initialise tous les sommets comme non visités.
- sélectionnez un sommet arbitraire, définissez-le comme le sommet actuel U. Marquez u comme visité.
- trouvez le bord le plus court reliant le sommet actuel u et un sommet non visité v.
- définissez v comme sommet actuel U. Marquez v comme visité.
- si tous les sommets du domaine sont visités, terminez. Sinon, passez à l’étape 3.
la séquence des sommets visités est la sortie de l’algorithme.,
l’algorithme du voisin le plus proche est facile à mettre en œuvre et s’exécute rapidement, mais il peut parfois manquer des itinéraires plus courts qui sont facilement remarqués avec la perspicacité humaine, en raison de sa nature « gourmande ». En général, si les dernières étapes de la tournée sont comparables en longueur aux premières étapes, alors la tournée est raisonnable; si elles sont beaucoup plus grandes, alors il est probable que de bien meilleures visites existent. Une autre vérification consiste à utiliser un algorithme tel que l’algorithme de la limite inférieure pour estimer si cette visite est assez bonne.,
dans le pire des cas, l’algorithme donne une visite beaucoup plus longue que la visite optimale. Pour être précis, pour chaque constante r, Il existe une instance du problème Travelling salesman telle que la longueur de la visite calculée par l’algorithme le plus proche voisin est supérieure à r fois la longueur de la visite optimale. De plus, pour chaque nombre de villes, il existe une attribution de distances entre les villes pour lesquelles l’heuristique du voisin le plus proche produit le pire tour possible., (Si l’algorithme est appliqué sur chaque sommet en tant que sommet de départ, le meilleur chemin trouvé sera meilleur qu’au moins N/2-1 autres tours, où N est le nombre de Sommets.)
l’algorithme du voisin le plus proche peut ne pas trouver un tour réalisable du tout, même lorsqu’il en existe un.