巡回セールスマン問題とは与えられた複数の都市をすべて1回ずつ通り, 出発点に戻ってくるような最短経路を求める問題である。この問題はNP困難のクラスに属し, 都市数が増えたとき実用的な時間(多項式時間)で最短経路(最適解)を求めるのは不可能と予想される代表例になっている。この問題やその一般化した問題に対し, どのような条件をみたしていれば多項式時間で解けるのかについて数学の側面から研究を行った。この研究では, 最適解が持つ経路の形の特徴付けとその証明, および具体的に最適解を求めるアルゴリズムの両方が必要である。また, これに関連する円順列, 順列, 集合の均等分割に関する問題にもいくつかの成果を得た。
The Traveling Salesman Problem is the problem to find a shortest route which starts from some city, visits each city exactly once and comes back to the initial city. This problem is one of the most famous NP-hard problems. This shows that when the number of cities increases it becomes to be hard to find a shortest route (optimal solution) in a reasonable time (polynomial time). In this work, we studied those problems from mathematical points of view and found polynomial time solvable cases for the problem and its extended routing problems. In this research area, we need not only characterizations of optimal solutions for those cases together with proofs but also algorithms to compute a shortest routes among all solutions. Also, we worked several problems on balanced partitions for cyclic permutations, permutations and sets of finite integers which relate to the Traveling Salesman Problem.
|
