Solving the Traveling Salesman Problem (TSP) Part 1

0. References

[1]http://www.msi.co.jp/nuopt/glossary/term_7f64c2f2bb1c2d3b292564b789b90e0d7193c8ec.html Numerical Optimizer Mathematical Programming Glossary Traveling Salesman Problem

[2]Series [Mathematics for Today's People]12 Invitation to the Traveling Salesman Problem Yoshitsugu Yamamoto and Mikio Kubo Asakura Shoten First Edition February 20, 1997 1.

What is the traveling salesman problem (TSP)?

Given a set of cities and the cost of traveling between two cities, the Traveling Salesman Problem (TSP) is the problem of finding a way to minimize the total cost of traveling among the routes that pass through all cities once and return to the first city. [1] In today's world, it can be applied, for example, in deciding which course to take when traveling with friends or loved ones.

This kind of problem is called a combinatorial optimization problem. If you want to know more about it, please refer to Reference [2].

2 When movement is restricted to the ground

It can be solved by viewing it as a planar graph coloring problem -> Go to Part 2.

3 When movement is restricted to underground, air, etc.

You can solve this problem by treating it as a coloring problem of a three-dimensional graph → Go to Part 3.