Multi-Fragment Algorithm

The multi-fragment algorithm is a heuristic approximation algorithm for the traveling salesman problem and related routing optimization problems. It builds a tour by repeatedly adding the lowest-cost available edge to a growing collection of path fragments, using each new edge to start a new fragment, extend an existing one, or close the final cycle connecting every city, while never allowing an edge that would create a premature cycle or a vertex of degree three. The algorithm runs in Theta(N squared log N) time in the worst case and, like other TSP heuristics, is not guaranteed to find the optimal tour, but it is a practical method for large routing problems. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/