Lesson plan
3-opt
In optimization, 3-opt is a simple local search heuristic for finding approximate solutions to the travelling salesperson problem and related network optimization problems. Compared to the simpler 2-opt algorithm, it is slower but can generate higher-quality solutions. 3-opt analysis involves deleting three edges from the current solution to the problem, creating three sub-tours. There are eight ways of connecting these sub-tours back into a single tour, one of which consists of the three deleted edges. These reconnections are analysed to find the optimum one. This process is then repeated for a different set of 3 connections, until all possible combinations have been tried in a network. A single pass through all triples of edges has a time complexity of O(n^3) . Iterated 3-opt, in which passes are repeated until no more improvements can be found, has a higher time complexity. In an array representation of a tour with k nodes S=[n_0, n_1, n_2, ..., n_{k-1}, n_k] , where n_0 = n_k , deleting three edges separates S into four segments S_1 , S_2 , S_3 and S_4 . Note that the segments S_1 and S_4 are connected. The reconnection of the Subtours is done by a combination of reversing one or both of S_2 and S_3 and switching their respective positions.…
Article summary
In optimization, 3-opt is a simple local search heuristic for finding approximate solutions to the travelling salesperson problem and related network optimization problems. Compared to the simpler 2-opt algorithm, it is slower but can generate higher-quality solutions. 3-opt analysis involves deleting three edges from the current solution to the problem, creating three sub-tours. There are eight ways of connecting these sub-tours back into a single tour, one of which consists of the three deleted edges. These reconnections are analysed to find the optimum one. This process is then repeated for a different set of 3 connections, until all possible combinations have been tried in a network. A single pass through all triples of edges has a time complexity of O(n^3) . Iterated 3-opt, in which passes are repeated until no more improvements can be found, has a higher time complexity. In an array representation of a tour with k nodes S=[n_0, n_1, n_2, ..., n_{k-1}, n_k] , where n_0 = n_k , deleting three edges separates S into four segments S_1 , S_2 , S_3 and S_4 . Note that the segments S_1 and S_4 are connected. The reconnection of the Subtours is done by a combination of reversing one or both of S_2 and S_3 and switching their respective positions.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.