“Multi-fragment algorithm”的意思、由来-开放百科全书

词条

Multi-fragment algorithm

释义

References

{{Orphan|date=January 2019}}{{merge to|Travelling salesman problem|discuss=Talk:Travelling salesman problem#Proposed merge with Multi-fragment algorithm|date=November 2018}}{{Infobox Algorithm
|class=Approximation algorithm
|image=
|caption=
|data=Graph
|time=

|space=
|optimal=No
|complete=
}}

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

1. ^{{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}}

2 : Travelling salesman problem|Approximation algorithms

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。