Gradual inclusion
The Successive inclusion is an algorithm for solving combinatorial optimization problems such as the Traveling Salesman Problem . This heuristic opening method provides an approximate solution for these problems . It was developed in 1964 by Robert L. Karg and Gerald L. Thompson.
The successive inclusion belongs to the greedy algorithms and therefore does not allow any statement about the quality of the result. In practice, however, the results are usually better than those of other methods, such as the nearest-neighbor heuristic .
The algorithm begins with an arbitrary circle made up of 2 points and successively inserts further points into the circle , so that at the end a Hamilton circle is created that contains all points.
Example of the algorithm
There are 6 points that are located in a 2-dimensional coordinate system. Any two points A and B, which form the circle A - B - A, serve as a starting point.
In the first step, the minimum distance from another point to the points contained in the circle is calculated. In this case these are points A and B. This procedure is repeated for all points that have not yet been integrated. Then the maximum is formed from the minimum distances and the corresponding point is inserted into the circle. In the existing example this is point C.
The new circle now forms the route A - B - C - A.
At this point it is irrelevant for the length of the path between which points point C is inserted into the route. However, if there are 3 or more points, point C is integrated into the circle in such a way that the resulting length for it is minimal.
In the next step, the minimum distances from the remaining points are calculated again. This time, in addition to points A and B, point C is also taken into account, as this is now included in the circle.
Point E is included in the circle. It is crucial here where this point is inserted. It is therefore checked which option results in the shortest route. In this case, point E can be integrated into the entire circle as follows:
- A - B - C - E - A
- A - B - E - C - A
- A - E - B - C - A
The latter option results in the minimum route length and is therefore chosen. This procedure is repeated until all points have been integrated into the circle. Figure 3 shows the route that the algorithm has calculated for this example.
Individual evidence
- ^ RL Karg, GL Thompson: A Heuristic Approach to Solving Traveling Salesman Problems . In: Management Science . 10, No. 2, 1964, ISSN 0025-1909 , pp. 225-248. doi : 10.1287 / mnsc.10.2.225 .