Multi-fragment algorithm: Difference between revisions
Content deleted Content added
m Added/removed/changed tags, possibly other edits, added orphan tag |
|||
| Line 13: | Line 13: | ||
}} |
}} |
||
The '''multi-fragment (MF) algorithm''' is |
The '''multi-fragment (MF) algorithm''' is a [[heuristic]] or [[approximation algorithm|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.<ref name="johnson1997">{{cite journal |last1=Johnson |first1=David |last2=A. McGeoch |first2=Lyle |title=The Traveling Salesman Problem: A Case Study in Local Optimization |journal=Local Search in Combinatorial Optimization |date=1997 |volume=1 |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.1635&rep=rep1&type=pdf}}</ref> |
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.<ref name="johnson1997">{{cite journal |last1=Johnson |first1=David |last2=A. McGeoch |first2=Lyle |title=The Traveling Salesman Problem: A Case Study in Local Optimization |journal=Local Search in Combinatorial Optimization |date=1997 |volume=1 |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.1635&rep=rep1&type=pdf}}</ref> |
||
Revision as of 08:14, 13 February 2019
 | It has been suggested that this article be merged into Travelling salesman problem. (Discuss) Proposed since November 2018. |
| 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. |