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 |
Adding short description: "Travelling salesman problem heuristic" |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 1:
{{Short description|Travelling salesman problem heuristic}}
{{one source |date=May 2024}}
{{Infobox Algorithm
|class=[[Approximation algorithm]]
Line 12 ⟶ 14:
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 |
==References==
| |||