Multi-fragment algorithm: Difference between revisions
Content deleted Content added
Closing 2018 merge proposal; uncontested objections; also, it is no longer an orphan; see Talk:Travelling salesman problem#Proposed merge with Multi-fragment algorithm |
|||
| Line 1: | Line 1: | ||
{{Orphan|date=January 2019}} |
|||
{{merge to|Travelling salesman problem|discuss=Talk:Travelling salesman problem#Proposed merge with Multi-fragment algorithm|date=November 2018}} |
|||
{{Infobox Algorithm |
{{Infobox Algorithm |
||
|class=[[Approximation algorithm]] |
|class=[[Approximation algorithm]] |
||
Revision as of 21:54, 7 December 2019
| Class | Approximation algorithm |
|---|---|
| Data structure | Graph |
| Worst-case performance | |
| Optimal | No |
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.
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]
References
- ^ Johnson, David; A. McGeoch, Lyle (1997). "The Traveling Salesman Problem: A Case Study in Local Optimization". Local Search in Combinatorial Optimization. 1.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |