Multi-fragment algorithm: Difference between revisions
Content deleted Content added
add basic description of the algorithm. |
|||
| Line 10: | Line 10: | ||
}} |
}} |
||
The '''multi-fragment (MF) algorithm''' is an [[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 '''multi-fragment (MF) algorithm''' is an [[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 |
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>. |
||
==References== |
==References== |
||
Revision as of 00:53, 16 November 2018
| Class | Approximation algorithm |
|---|---|
| Data structure | Graph |
| Worst-case performance | |
| Optimal | No |
The multi-fragment (MF) algorithm is an 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. |