2021년 2월 17일 (수) 08:28에 Pythagoras0님의 편집

2021-02-17T08:28:07Z

Pythagoras0: /* 메타데이터 */ 새 문단

2020-12-26T12:27:11Z

메타데이터: 새 문단

Pythagoras0: /* 노트 */ 새 문단

2020-12-21T05:09:49Z

노트: 새 문단

새 문서

== 노트 ==

===위키데이터===
* ID : [https://www.wikidata.org/wiki/Q322212 Q322212]
===말뭉치===
# The Travelling Salesman Problem (TSP) is the challenge of finding the shortest yet most efficient route for a person to take given a list of specific destinations.<ref name="ref_dfc9457d">[https://blog.routific.com/travelling-salesman-problem Understanding the Travelling Salesman Problem (TSP)]</ref>
# The traveling salesman problem was defined in the 1800s by the Irish mathematician W. R. Hamilton and by the British mathematician Thomas Kirkman.<ref name="ref_f32655a5">[https://simple.wikipedia.org/wiki/Travelling_salesman_problem Travelling salesman problem]</ref>
# The Travelling Salesman Problem describes a salesman who must travel between N cities.<ref name="ref_f32655a5" />
# The Traveling Salesman Problem is typical of a large class of "hard" optimization problems that have intrigued mathematicians and computer scientists for years.<ref name="ref_f32655a5" />
# In general, the traveling salesman problem is hard to solve.<ref name="ref_f32655a5" />
# The multiple traveling salesman problem (mTSP) is a generalization of the well-known traveling salesman problem (TSP), where more than one salesman is allowed to be used in the solution.<ref name="ref_3e51fe23">[https://www.sciencedirect.com/science/article/pii/S0305048304001550 The multiple traveling salesman problem: an overview of formulations and solution procedures]</ref>
# The origins of the travelling salesman problem are unclear.<ref name="ref_c8857d23">[https://en.wikipedia.org/wiki/Travelling_salesman_problem Travelling salesman problem]</ref>
# The travelling salesman problem was mathematically formulated in the 1800s by the Irish mathematician W.R. Hamilton and by the British mathematician Thomas Kirkman.<ref name="ref_c8857d23" />
# The Beardwood–Halton–Hammersley theorem provides a practical solution to the traveling salesman problem.<ref name="ref_c8857d23" />
# The bottleneck traveling salesman problem is also NP-hard.<ref name="ref_c8857d23" />
# The traveling salesperson problem is one of a handful of foundational problems that theoretical computer scientists turn to again and again to test the limits of efficient computation.<ref name="ref_6584ab4c">[https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/ Computer Scientists Break Traveling Salesperson Record]</ref>
# Unlike the regular traveling salesperson problem, this fractional problem can be solved efficiently.<ref name="ref_6584ab4c" />
# Nevertheless, Oveis Gharan emerged from that collaboration with an unshakable belief that their algorithm should beat Christofides’ algorithm for the general traveling salesperson problem.<ref name="ref_6584ab4c" />
# Oveis Gharan had himself cut his teeth on the traveling salesperson problem as a graduate student back in 2010.<ref name="ref_6584ab4c" />
# As said above, these are only two of the most basic algorithms used to obtain an approximate solution to the travelling salesman problem and there are many more sophisticated methods.<ref name="ref_8363c567">[https://www.lancaster.ac.uk/stor-i-student-sites/libby-daniells/2020/04/21/the-travelling-salesman-problem/ The Travelling Salesman Problem – Libby Daniells]</ref>
# The resulting tree is not a possible solution to the traveling salesman problem because it does not create a round-trip route.<ref name="ref_a499543c">[https://www.wired.com/2013/01/traveling-salesman-problem/ Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem]</ref>
# However, this round-trip route is, at worst, twice as long as the best solution to the traveling salesman problem.<ref name="ref_a499543c" />
# The Travelling Salesman Problem (TSP) reflects the routing decisions that a salesman has to take.<ref name="ref_156f3fdc">[http://www.scielo.org.co/scielo.php?pid=S0120-56092019000300044&script=sci_arttext&tlng=en Performance measurement of a solution for the travelling salesman problem for routing through the incorporation of service time variability]</ref>
# They therefore defined and formulated the Sequence Dependent Travelling Salesman Problem (SDTSP).<ref name="ref_156f3fdc" />
# Travelling salesman problem is the most notorious computational problem.<ref name="ref_293c9d46">[https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_travelling_salesman_problem.htm Travelling Salesman Problem]</ref>
# The answer is that both problems can be formulated in terms of the mathematical problem known as the Traveling Salesman Problem (TSP).<ref name="ref_490c5a30">[http://www.ams.org/publicoutreach/feature-column/fcarc-tsp AMS :: Feature Column from the AMS]</ref>
# For example, the Bottleneck Traveling Salesman Problem (bottleneck TSP) arises as a variant of the usual TSP by changing the objective function.<ref name="ref_490c5a30" />
# Garfinkel, R. and K. Gilbert, The bottleneck traveling salesman problem: algorithms and probabilistic analysis, J. Assoc.<ref name="ref_490c5a30" />
# Lawler, E., A solvable case of the traveling salesman problem, Math.<ref name="ref_490c5a30" />
# lower bound is the solution to the linear programming relaxation of the standard integer Programming formulation of the traveling salesman problem (TSP).<ref name="ref_22a38911">[https://www.osti.gov/servlets/purl/6223080 The cost-constrained traveling salesman problem (Technical Report)]</ref>
# Was it called the Travelling Salesman Problem?<ref name="ref_0edbc88e">[https://www.theorsociety.com/about-or/or-methods/heuristics/a-brief-history-of-the-travelling-salesman-problem/ A brief History of the Travelling Salesman Problem]</ref>
# I am sure you already heard about the traveling salesman problem or TSP.<ref name="ref_3ca8509b">[https://towardsdatascience.com/how-to-solve-the-traveling-salesman-problem-a-comparative-analysis-39056a916c9f How to Solve the Traveling Salesman Problem — A Comparative Analysis]</ref>
# The traveling salesman problem is a classic problem in combinatorial optimization.<ref name="ref_3ca8509b" />
# If you want to solve traveling salesman problem with a large number of cities the dynamic programming method is not the best choice.<ref name="ref_3ca8509b" />
# The genetic algorithms are useful for NP-hard problems, especially the traveling salesman problem.<ref name="ref_38e9bda5">[https://www.hindawi.com/journals/cin/2017/7430125/ Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator]</ref>
# To tackle the traveling salesman problem using genetic algorithms, there are various representations such as binary, path, adjacency, ordinal, and matrix representations.<ref name="ref_38e9bda5" />
# In this article, we propose a new crossover operator for traveling salesman problem to minimize the total distance.<ref name="ref_38e9bda5" />
# The traveling salesman problem (TSP) is one of the most famous benchmarks, significant, historic, and very hard combinatorial optimization problem.<ref name="ref_38e9bda5" />
# The traveling salesman problem: a deterministic algorithm using tabu search.<ref name="ref_ad79dc89">[https://www.scielo.sa.cr/scielo.php?pid=S1409-24332014000100008&script=sci_abstract The traveling salesman problem: a deterministic algorithm using tabu search]</ref>
# Keywords : tabu search; deterministic algorithm; frequencies matrix; diversification; permutation; traveling salesman problem.<ref name="ref_ad79dc89" />
# The Travelling Salesman Problem (TSP) is a classical optimization problem that has been evolved to real-life vehicle routing problems (VRP).<ref name="ref_8d734d9e">[https://www.frontiersin.org/research-topics/10851/santa-claus-travelling-salesman-problem-challenge Santa Claus Travelling Salesman Problem Challenge]</ref>
# The Traveling Salesman Problem (TSP) is among the most widely studied problems in network optimization and has a wide variety of practical applications 2), (5), (20), (24.<ref name="ref_40cb9d0c">[http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382018000300499 MODELING AND SOLVING THE TRAVELING SALESMAN PROBLEM WITH PRIORITY PRIZES]</ref>
# When penalty terms for unvisited nodes are also added to the objective function, the problem is known as the PrizeCollecting Traveling Salesman Problem 3), (9.<ref name="ref_40cb9d0c" />
# Other two related problems in which customers have to be selected are the Traveling Purchaser Problem and the Generalized Traveling Salesman Problem.<ref name="ref_40cb9d0c" />
# k,i p ki x ki in the objective function of the traveling salesman problem.<ref name="ref_40cb9d0c" />
===소스===
<references />

@@ 47번째 줄: / 47번째 줄: @@
   <references />
-== 메타데이터 ==
+==메타데이터==
 ===위키데이터===
 * ID :  [https://www.wikidata.org/wiki/Q322212 Q322212]

← 이전 판		2020년 12월 26일 (토) 12:27 판
46번째 줄:		46번째 줄:
	===소스===		===소스===
	<references />		<references />
		+
		+	== 메타데이터 ==
		+
		+	===위키데이터===
		+	* ID : [https://www.wikidata.org/wiki/Q322212 Q322212]

외판원 문제 - 편집 역사

2021년 2월 17일 (수) 08:28에 Pythagoras0님의 편집

Pythagoras0: /* 메타데이터 */ 새 문단

Pythagoras0: /* 노트 */ 새 문단