数学の難問「巡回セールスマン問題」の近似解を求める最良のアルゴリズムが数十年ぶりに更新される

コメント

注目のコメント

• 高橋 直大

  AtCoder株式会社 代表取締役社長

  ・2020年10月13日

  巡回セールスマン問題の近似解が更新されたニュース。
  巡回セールスマン問題は、「スタート地点からN個の地点を辿って帰ってくるための経路をできるだけ短くするために、どういう順序で辿るべきか」というのを求める問題。
  0.0000000000000000000000000000000002%の改善なんだけど、数学的には大きく意味がある、という感じ。
  
  ここで言う「近似解」というのは、「最も良い解より○%以上悪い解であることはありえない」というのが証明されている解が必ず見つけ出せる、ということで、実用的に優れている解とは限らない。このアルゴリズムは古くから知られていたものであるが、それが「どれだけの保証が出来るか」という数学の証明部分に苦労していたものが解けた、というニュース。実用的に早くなったというニュースではない。
  
  ただ、この「保証出来る」というのは数学的にとても大切
  世の中のアルゴリズムは、実用的に価値のあるものと、数学的に価値のあるものが、行ったり来たりで使えるようになっていくもの。この発展がいきなり実用に繋がるわけではないが、巡回セールスマン問題の発展の第一歩には確実に繋がると思う。