Labo Algo
Labo Algo
Cet algorithme est simple et rapide, mais il n'est efficace que pour un nombre de villes assez réduit.
Il est souvent utilisé pour constituer rapidement un trajet acceptable servant de base à un autre algorithme.
Pour un nombre de villes important on obtient généralement une solution plus longue de 50% ou moins au dessus
de la solution optimale.
Le trajet est initialement vide (pas de villes visitées)
On part d'une ville au hasard, que l'on met dans la liste des villes visitées.
On recherche la ville la plus proche que l'on ajoute dans la liste des villes visitées.
On recherche la ville la plus proche de la cette nouvelle ville. Si la ville est déjà dans la liste des villes visitées,
on prend la deuxième ville plus proche, la troisième si besoin, etc.
et ainsi de suite...
Une manière d'accélerer fortement le calcul de ces solutions est de calculer auparavant le tableau des villes les plus proches (pour chaque ville, contient la liste des autres villes triées dans l'ordre du plus proche au plus éloigné).
Labo Algo
Alexandre Aupetit, Avril 2004