Multi-Fragment
The Multi-Fragment Algorithm works as follows:
1. Consider
a distance matrix (such as the type at the back of a road atlas of Britain),
containing all the distances between all cities on the tour.
2. Find the shortest distance and link these two cities together.
3. Then, find the second shortest distance, and link these two cities.
4. Now, find the next smallest edge whose cities conform to the following
criteria:
a) Both must have an edge degree ratio <=1 (i.e. neither can already be linked
to more than one other city)
b) Adding an edge between the cities must not result in a closed tour, which does not already include all the cities on the tour.
5. Repeat until all cities end up being connected to two other cities.
 |
 |
| Identify the two closest cities (shown in red). | Join the closest cities together. They now have one edge each (signified by grey colouring). Now find the next two closest cities (red). |
 |
 |
| Join them together. Now find the two closest cities, where joining them will not result in a closed tour, and where each has an edge degree of either one (denoted by grey shading) or zero (transparent circles). | If a city has an edge degree of two
(shown in black), it cannot be connected to any further cities. Repeat the previous step... |
 |
 |
| ...until there only remain two cities with an edge degree less than two... | ...and these are joined to complete the tour... |