Multi-fragment algorithm: Difference between revisions

Revision as of 05:08, 17 November 2018

Latest revision as of 23:39, 14 September 2024

(5 intermediate revisions by 5 users not shown)

Line 1:

{{mergeShort todescription|Travelling salesman problem|discuss=Talk:Travelling salesman problem#Proposed merge with Multi-fragment algorithm|date=November 2018heuristic}}

{{one source |date=May 2024}}

{{Infobox Algorithm

|class=[[Approximation algorithm]]

Line 11 ⟶ 12:

}}

The '''multi-fragment (MF) algorithm''' is ana [[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>.

==References==

<references />

[[Category:Travelling salesman problem]]

[[Category:Approximation algorithms]]

{{algorithm-stub}}

[[Category:Travelling salesman problem]]

[[Category:Approximation algorithms]]