Multi-fragment algorithm

Travelling salesman problem heuristic

This article relies largely or entirely on a single source . Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.
Find sources: "Multi-fragment algorithm" – news · newspapers · books · scholar · JSTOR (May 2024)

Multi-fragment algorithm
Class	Approximation algorithm
Data structure	Graph
Worst-case performance	$\Theta (N^{2}\log N)$ {\displaystyle \Theta (N^{2}\log N)}
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

[edit ]

^ Johnson, David; A. McGeoch, Lyle (1997). "The Traveling Salesman Problem: A Case Study in Local Optimization". Local Search in Combinatorial Optimization. 1. CiteSeerX 10.1.1.92.1635 .

Stub icon

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

v
t
e

Retrieved from "https://en.wikipedia.org/w/index.php?title=Multi-fragment_algorithm&oldid=1245765768"