These are the steps of the algorithm:
The nearest neighbour algorithm is easy to implement and can be done quickly, but it can sometimes miss shorter routes which are easily noticed with human hindsight. The results of the nearest neighbour algorithm should be checked before use, just in case such a shorter route has been missed.
In the worst case, the algorithm can compute tours that are by an arbitrary factor larger than the optimal tour. To be precise, for every constant r there is an instance of the traveling salesman problem such that the length of the tour computed by the nearest neighbour algorithm is greater than or equal to r times the length of the optimal tour.
Search Encyclopedia
|
Featured Article
|