Nearest neighbour algorithm - Revision history

18.29.96.92: Changed instances of neighbor to neighbour for consistency.

2024-12-09T20:53:14Z

Changed instances of neighbor to neighbour for consistency.

← Previous revision		Revision as of 20:53, 9 December 2024
Line 12:		Line 12:
	\|complete=		\|complete=
	}}		}}
	The '''nearest ~~neighbor~~ algorithm''' was one of the first [[algorithm]]s used to solve the [[travelling salesman problem]] approximately. In that problem, the salesman starts at a random city and repeatedly visits the nearest city until all have been visited. The algorithm quickly yields a short tour, but usually not the optimal one.		The '''nearest neighbour algorithm''' was one of the first [[algorithm]]s used to solve the [[travelling salesman problem]] approximately. In that problem, the salesman starts at a random city and repeatedly visits the nearest city until all have been visited. The algorithm quickly yields a short tour, but usually not the optimal one.

	==Algorithm ==		==Algorithm ==
Line 27:		Line 27:
	The nearest neighbour algorithm is easy to implement and executes quickly, but it can sometimes miss shorter routes which are easily noticed with human insight, due to its "greedy" nature. As a general guide, if the last few stages of the tour are comparable in length to the first stages, then the tour is reasonable; if they are much greater, then it is likely that much better tours exist. Another check is to use an algorithm such as the [[Upper and lower bounds\|lower bound]] algorithm to estimate if this tour is good enough.		The nearest neighbour algorithm is easy to implement and executes quickly, but it can sometimes miss shorter routes which are easily noticed with human insight, due to its "greedy" nature. As a general guide, if the last few stages of the tour are comparable in length to the first stages, then the tour is reasonable; if they are much greater, then it is likely that much better tours exist. Another check is to use an algorithm such as the [[Upper and lower bounds\|lower bound]] algorithm to estimate if this tour is good enough.

	In the worst case, the algorithm results in a tour that is much longer 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 '''r''' times the length of the optimal tour. Moreover, for each number of cities there is an assignment of distances between the cities for which the nearest ~~neighbor~~ heuristic produces the unique worst possible tour. (If the algorithm is applied on every vertex as the starting vertex, the best path found will be better than at least N/2-1 other tours, where N is the number of vertices.)<ref>G. Gutin, A. Yeo and A. Zverovich, 2002</ref>		In the worst case, the algorithm results in a tour that is much longer 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 '''r''' times the length of the optimal tour. Moreover, for each number of cities there is an assignment of distances between the cities for which the nearest neighbour heuristic produces the unique worst possible tour. (If the algorithm is applied on every vertex as the starting vertex, the best path found will be better than at least N/2-1 other tours, where N is the number of vertices.)<ref>G. Gutin, A. Yeo and A. Zverovich, 2002</ref>

	The nearest neighbour algorithm may not find a feasible tour at all, even when one exists.		The nearest neighbour algorithm may not find a feasible tour at all, even when one exists.

JJMC89 bot III: Moving :Category:Algorithms in graph theory to :Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

2024-10-12T19:57:19Z

Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

← Previous revision		Revision as of 19:57, 12 October 2024
Line 45:		Line 45:
	[[Category:Approximation algorithms]]		[[Category:Approximation algorithms]]
	[[Category:Heuristic algorithms]]		[[Category:Heuristic algorithms]]
	[[Category:~~Algorithms~~ ~~in graph theory~~]]		[[Category:Graph algorithms]]

JJMC89 bot III: Moving :Category:Graph algorithms to :Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

2024-10-12T02:24:32Z

Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

← Previous revision		Revision as of 02:24, 12 October 2024
Line 45:		Line 45:
	[[Category:Approximation algorithms]]		[[Category:Approximation algorithms]]
	[[Category:Heuristic algorithms]]		[[Category:Heuristic algorithms]]
	[[Category:~~Graph~~ ~~algorithms~~]]		[[Category:Algorithms in graph theory]]

LucasBrown: Adding local short description: "Algorithm for the travelling salesman problem", overriding Wikidata description "used to determine solution to travelling salesman problem"

2024-05-10T23:22:19Z

Adding local short description: "Algorithm for the travelling salesman problem", overriding Wikidata description "used to determine solution to travelling salesman problem"

← Previous revision		Revision as of 23:22, 10 May 2024
Line 1:		Line 1:
			{{Short description\|Algorithm for the travelling salesman problem}}
	{{About\|an approximation algorithm to solve the [[travelling salesman problem]]\|\|Nearest neighbor (disambiguation){{!}}Nearest neighbor}}		{{About\|an approximation algorithm to solve the [[travelling salesman problem]]\|\|Nearest neighbor (disambiguation){{!}}Nearest neighbor}}

2.100.56.85: In "mark v as visited" (line 2, steps of the algorithm) changed "v" to "u"

2024-03-31T17:04:50Z

In "mark v as visited" (line 2, steps of the algorithm) changed "v" to "u"

← Previous revision		Revision as of 17:04, 31 March 2024
Line 17:		Line 17:
	These are the steps of the algorithm:		These are the steps of the algorithm:
	# Initialize all vertices as unvisited.		# Initialize all vertices as unvisited.
	# Select an arbitrary vertex, set it as the current vertex '''u'''. Mark '''v''' as visited.		# Select an arbitrary vertex, set it as the current vertex '''u'''. Mark '''u''' as visited.
	# Find out the shortest edge connecting the current vertex '''u''' and an unvisited vertex '''v'''.		# Find out the shortest edge connecting the current vertex '''u''' and an unvisited vertex '''v'''.
	# Set '''v''' as the current vertex '''u'''. Mark '''v''' as visited.		# Set '''v''' as the current vertex '''u'''. Mark '''v''' as visited.

206.174.16.178: /* Algorithm */

2023-12-12T23:29:33Z

Algorithm

← Previous revision		Revision as of 23:29, 12 December 2023
Line 17:		Line 17:
	These are the steps of the algorithm:		These are the steps of the algorithm:
	# Initialize all vertices as unvisited.		# Initialize all vertices as unvisited.
	# Select an arbitrary vertex, set it as the current vertex '''u'''. Mark '''u''' as visited.		# Select an arbitrary vertex, set it as the current vertex '''u'''. Mark '''v''' as visited.
	# Find out the shortest edge connecting the current vertex '''u''' and an unvisited vertex '''v'''.		# Find out the shortest edge connecting the current vertex '''u''' and an unvisited vertex '''v'''.
	# Set '''v''' as the current vertex '''u'''. Mark '''v''' as visited.		# Set '''v''' as the current vertex '''u'''. Mark '''v''' as visited.

192.245.1.4 at 08:14, 2 December 2023

2023-12-02T08:14:41Z

← Previous revision		Revision as of 08:14, 2 December 2023
Line 11:		Line 11:
	\|complete=		\|complete=
	}}		}}
	The '''nearest ~~neighbour~~ algorithm''' was one of the first [[algorithm]]s used to solve the [[travelling salesman problem]] approximately. In that problem, the salesman starts at a random city and repeatedly visits the nearest city until all have been visited. The algorithm quickly yields a short tour, but usually not the optimal one.		The '''nearest neighbor algorithm''' was one of the first [[algorithm]]s used to solve the [[travelling salesman problem]] approximately. In that problem, the salesman starts at a random city and repeatedly visits the nearest city until all have been visited. The algorithm quickly yields a short tour, but usually not the optimal one.

	==Algorithm ==		==Algorithm ==

103.39.29.144: /* Algorithm */

2023-04-03T12:34:20Z

Algorithm

← Previous revision		Revision as of 12:34, 3 April 2023
Line 22:		Line 22:
	# If all the vertices in the domain are visited, then terminate. Else, go to step 3.		# If all the vertices in the domain are visited, then terminate. Else, go to step 3.

	The sequence of the visited vertices is the output of the ~~algorithmic~~.		The sequence of the visited vertices is the output of the algorithm.

	The nearest neighbour algorithm is easy to implement and executes quickly, but it can sometimes miss shorter routes which are easily noticed with human insight, due to its "greedy" nature. As a general guide, if the last few stages of the tour are comparable in length to the first stages, then the tour is reasonable; if they are much greater, then it is likely that much better tours exist. Another check is to use an algorithm such as the [[Upper and lower bounds\|lower bound]] algorithm to estimate if this tour is good enough.		The nearest neighbour algorithm is easy to implement and executes quickly, but it can sometimes miss shorter routes which are easily noticed with human insight, due to its "greedy" nature. As a general guide, if the last few stages of the tour are comparable in length to the first stages, then the tour is reasonable; if they are much greater, then it is likely that much better tours exist. Another check is to use an algorithm such as the [[Upper and lower bounds\|lower bound]] algorithm to estimate if this tour is good enough.

103.39.29.144: /* Algorithm */

2023-04-03T12:33:39Z

Algorithm

← Previous revision		Revision as of 12:33, 3 April 2023
Line 22:		Line 22:
	# If all the vertices in the domain are visited, then terminate. Else, go to step 3.		# If all the vertices in the domain are visited, then terminate. Else, go to step 3.

	The sequence of the visited vertices is the output of the ~~algorithm~~.		The sequence of the visited vertices is the output of the algorithmic.

	The nearest neighbour algorithm is easy to implement and executes quickly, but it can sometimes miss shorter routes which are easily noticed with human insight, due to its "greedy" nature. As a general guide, if the last few stages of the tour are comparable in length to the first stages, then the tour is reasonable; if they are much greater, then it is likely that much better tours exist. Another check is to use an algorithm such as the [[Upper and lower bounds\|lower bound]] algorithm to estimate if this tour is good enough.		The nearest neighbour algorithm is easy to implement and executes quickly, but it can sometimes miss shorter routes which are easily noticed with human insight, due to its "greedy" nature. As a general guide, if the last few stages of the tour are comparable in length to the first stages, then the tour is reasonable; if they are much greater, then it is likely that much better tours exist. Another check is to use an algorithm such as the [[Upper and lower bounds\|lower bound]] algorithm to estimate if this tour is good enough.

G.Gutin: Undid revision 1009414014 by G.Gutin (talk)

2021-02-28T13:22:20Z

Undid revision 1009414014 by G.Gutin (talk)

← Previous revision		Revision as of 13:22, 28 February 2021
Line 31:		Line 31:

	==Notes==		==Notes==
			<references />
	<references /> G. Gutin, A. Yeo and A. Zverovitch, Exponential Neighborhoods and Domination Analysis for the TSP, in The Traveling Salesman Problem and Its Variations, Kluwer (202) and Springer (2007).

	==References==		==References==