情報処理学会 第78回全国大会講演要旨

巡回セールスマン問題とは、複数の都市を一度ずつ訪問し、出発地点に戻るときの移動コストが最小のものを求める問題である。この問題は、世界中で研究されてきたが多項式時間で最適解を求めることは不可能だとされている。そこで、ある程度の精度を持った近似解を短時間で求める近似アルゴリズムが研究されてきた。
本研究では、球面上における巡回セールスマン問題の近似アルゴリズムの開発と評価を行う。