Multi-fragment algorithm - Revision history

Jlwoodwa: Adding short description: "Travelling salesman problem heuristic"

2024-09-14T23:39:44Z

Adding short description: "Travelling salesman problem heuristic"

← Previous revision		Revision as of 23:39, 14 September 2024
Line 1:		Line 1:
			{{Short description\|Travelling salesman problem heuristic}}
	{{one source \|date=May 2024}}		{{one source \|date=May 2024}}
	{{Infobox Algorithm		{{Infobox Algorithm

Jlwoodwa: tag as one source

2024-05-03T23:34:11Z

tag as one source

← Previous revision		Revision as of 23:34, 3 May 2024
Line 1:		Line 1:
			{{one source \|date=May 2024}}
	{{Infobox Algorithm		{{Infobox Algorithm
	\|class=[[Approximation algorithm]]		\|class=[[Approximation algorithm]]

Citation bot: Add: citeseerx. Removed URL that duplicated unique identifier. | You can use this bot yourself. Report bugs here. | Activated by User:AManWithNoPlan | via #UCB_webform

2020-03-05T23:02:18Z

Add: citeseerx. Removed URL that duplicated unique identifier. | You can use this bot yourself. Report bugs here. | Activated by User:AManWithNoPlan | via #UCB_webform

← Previous revision		Revision as of 23:02, 5 March 2020
Line 12:		Line 12:
	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 '''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 \|~~url=http://~~citeseerx~~.ist.psu.edu/viewdoc/download?doi~~=10.1.1.92.1635~~&rep=rep1&type=pdf~~}}</ref>		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 \|citeseerx=10.1.1.92.1635 }}</ref>

	==References==		==References==

Klbrain: Closing 2018 merge proposal; uncontested objections; also, it is no longer an orphan; see Talk:Travelling salesman problem#Proposed merge with Multi-fragment algorithm

2019-12-07T21:54:37Z

Closing 2018 merge proposal; uncontested objections; also, it is no longer an orphan; see Talk:Travelling salesman problem#Proposed merge with Multi-fragment algorithm

← Previous revision		Revision as of 21:54, 7 December 2019
Line 1:		Line 1:
	{{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		{{Infobox Algorithm
	\|class=[[Approximation algorithm]]		\|class=[[Approximation algorithm]]

John of Reading: /* top */Typo fixing, replaced: an heuristic → a heuristic as in the linked article.

2019-02-13T08:14:41Z

top: Typo fixing, replaced: an heuristic → a heuristic as in the linked article.

← Previous revision		Revision as of 08:14, 13 February 2019
Line 13:		Line 13:
	}}		}}

	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 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 \|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.1635&rep=rep1&type=pdf}}</ref>		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>

I dream of horses: Added/removed/changed tags, possibly other edits, added orphan tag

2019-01-09T11:04:19Z

Added/removed/changed tags, possibly other edits, added orphan tag

← Previous revision		Revision as of 11:04, 9 January 2019
Line 1:		Line 1:
			{{Orphan\|date=January 2019}}

	{{merge to\|Travelling salesman problem\|discuss=Talk:Travelling salesman problem#Proposed merge with Multi-fragment algorithm\|date=November 2018}}		{{merge to\|Travelling salesman problem\|discuss=Talk:Travelling salesman problem#Proposed merge with Multi-fragment algorithm\|date=November 2018}}
	{{Infobox Algorithm		{{Infobox Algorithm
Line 11:		Line 13:
	}}		}}

	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 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>.		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==
	<references />		<references />

		⚫	[[Category:Travelling salesman problem]]
		⚫	[[Category:Approximation algorithms]]


	{{algorithm-stub}}		{{algorithm-stub}}

⚫	[[Category:Travelling salesman problem]]
⚫	[[Category:Approximation algorithms]]

Daiyusha: Added {{merge to}} tag to article (TW)

2018-11-17T05:08:56Z

Added {{merge to}} tag to article (TW)

← Previous revision		Revision as of 05:08, 17 November 2018
Line 1:		Line 1:
			{{merge to\|Travelling salesman problem\|discuss=Talk:Travelling salesman problem#Proposed merge with Multi-fragment algorithm\|date=November 2018}}
	{{Infobox Algorithm		{{Infobox Algorithm
	\|class=[[Approximation algorithm]]		\|class=[[Approximation algorithm]]

Pichpich: add basic description of the algorithm.

2018-11-16T00:53:58Z

add basic description of the algorithm.

← Previous revision		Revision as of 00:53, 16 November 2018
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 ~~name~~ ~~"multi-fragment"~~ ~~comes~~ ~~from~~ the ~~fact~~ ~~that~~ ~~this~~ ~~algorithm~~ ~~constructs~~ ''multiple'' ~~intermediate~~ ~~partial~~ ~~tours~~ (or ~~"''fragments''")~~ <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>.		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==

Pichpich: +Category:Travelling salesman problem; +Category:Approximation algorithms using HotCat

2018-11-16T00:43:38Z

+Category:Travelling salesman problem; +Category:Approximation algorithms using HotCat

← Previous revision		Revision as of 00:43, 16 November 2018
Line 16:		Line 16:
	==References==		==References==
	<references />		<references />

	{{uncategorized\|date=November 2018}}


	{{algorithm-stub}}		{{algorithm-stub}}

			[[Category:Travelling salesman problem]]
			[[Category:Approximation algorithms]]

Rpyle731: stub sort

2018-11-15T08:22:41Z

stub sort

← Previous revision		Revision as of 08:22, 15 November 2018
Line 17:		Line 17:
	<references />		<references />
	{{uncategorized\|date=November 2018}}		{{uncategorized\|date=November 2018}}

⚫	{{stub}}

		⚫	{{algorithm-stub}}