Algorithme du voisin le plus proche - Nearest neighbour algorithm

Algorithme du voisin le plus proche

Classer	Algorithme d'approximation
Structure de données	Graphique
Pires performances des cas	${\ displaystyle \ Theta (N ^ {2})}$
Complexité spatiale dans le pire des cas	${\ displaystyle \ Theta (N)}$

L' algorithme du plus proche voisin a été l'un des premiers algorithmes utilisés pour résoudre approximativement le problème du voyageur de commerce . Dans ce problème, le vendeur commence dans une ville au hasard et visite à plusieurs reprises la ville la plus proche jusqu'à ce que tous aient été visités. L'algorithme donne rapidement une courte visite, mais généralement pas la meilleure.

Algorithme

Voici les étapes de l'algorithme:

1. Initialisez tous les sommets comme non visités.
2. Sélectionnez un sommet arbitraire, définissez-le comme sommet actuel u . Marquez- vous comme visité.
3. Trouvez l'arête la plus courte reliant le sommet actuel u et un sommet v non visité .
4. Définissez v comme le sommet actuel u . Mark v comme visité.
5. Si tous les sommets du domaine sont visités, alors 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 à implémenter et s'exécute rapidement, mais il peut parfois manquer des itinéraires plus courts qui sont facilement remarqués par la perspicacité humaine, en raison de sa nature «gourmande». En règle générale, si les dernières étapes de la tournée sont comparables en longueur aux premières étapes, alors la visite est raisonnable; s'ils sont beaucoup plus importants, il est probable que des circuits bien meilleurs existent. Une autre vérification consiste à utiliser un algorithme tel que l' algorithme de limite inférieure pour estimer si cette tournée est suffisamment bonne.

Dans le pire des cas, l'algorithme entraîne une tournée beaucoup plus longue que la tournée optimale. Pour être précis, pour chaque constante r, il existe une instance du problème du voyageur de commerce telle que la longueur du tour calculé par l'algorithme du plus proche voisin est supérieure à r fois la longueur du tour optimal. De plus, pour chaque nombre de villes, il y a une attribution de distances entre les villes pour lesquelles l'heuristique du plus proche voisin produit le pire tour possible. (Si l'algorithme est appliqué sur chaque sommet comme 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 plus proche voisin peut ne pas trouver du tout une visite réalisable, même si elle existe.

Remarques

Les références

• G. Gutin, A. Yeo et A. Zverovitch, Exponential Neighborhoods and Domination Analysis for the TSP, dans The Travelling Salesman Problem and Its Variations, G.Gutin and AP Punnen (eds.), Kluwer (2002) and Springer (2007) .
• G. Gutin, A. Yeo et A. Zverovich, Le voyageur de commerce ne doit pas être gourmand: analyse de domination des heuristiques de type gourmand pour le TSP . Mathématiques appliquées discrètes 117 (2002), 81–86.
• J. Bang-Jensen, G. Gutin et A. Yeo, Quand l'algorithme glouton échoue . Optimisation discrète 1 (2004), 121–127.
• G. Bendall et F. Margot, Résistance de type cupide des problèmes combinatoires , optimisation discrète 3 (2006), 288-298.