Multi-fragment algorithm
Travelling salesman problem heuristic
From Wikipedia, the free encyclopedia
The multi-fragment (MF) algorithm is a heuristic or approximation algorithm for the travelling salesman problem (TSP) (and related problems). This algorithm is also sometimes called the "greedy algorithm" for the TSP.
| Class | Approximation algorithm |
|---|---|
| Data structure | Graph |
| Worst-case performance | |
| Optimal | No |
The algorithm builds a tour for the traveling salesman one edge at a time and thus maintains multiple tour fragments, each of which is a simple path in the complete graph of cities. At each stage, the algorithm selects the edge of minimal cost that either creates a new fragment, extends one of the existing paths or creates a cycle of length equal to the number of cities.[1]
