TSP Algorithm

Creator

Creator

Seonglae Cho

Created

Created

2023 Sep 6 8:44

Editor

Editor

Seonglae Cho

Edited

Edited

2024 Jan 31 13:8

Refs

Refs

Minimum spanning tree

Traveling salesman problem

Finding minimal cost

Hamiltonian cycle. Optimal solution is only found by

Brute-force Search(exponential).

The weight between two cities can be

Ticket cost (asymmetric)

Travel time (asymmetric)

Euclidean distance (symmetric)

TSP Algorithm Notion

Travelling salesman problem

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

Travelling salesman problem

https://en.wikipedia.org/wiki/Travelling_salesman_problem

Travelling salesman problem

Researchers Approach New Speed Limit for Seminal Problem | Quanta Magazine

Integer linear programming can help find the answer to a variety of real-world problems. Now researchers have found a much faster way to do it.

Researchers Approach New Speed Limit for Seminal Problem | Quanta Magazine

https://www.quantamagazine.org/researchers-approach-new-speed-limit-for-seminal-problem-20240129/

Researchers Approach New Speed Limit for Seminal Problem | Quanta Magazine

Recommendations

/////