巡回セールスマン問題

In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation (2011/12/27) William J. Cook

「巡回セールスマン問題」．
セールスマンが回るべきいくつかの都市があるとき，各都市に一回ずつ寄って元の場所へ戻ってくる経路のうち，最も距離が短くなるものを求めよ，という問題だ．

本書では，その巡回セールスマン問題の何が難しく，どこまで解けていて，なぜ長い間人々の関心を集めるのか等
，「巡回セールスマン問題」のあらゆる面が語り尽くされている．
最近，『驚きの数学 巡回セールスマン問題』（2013 青土社）というタイトルで邦訳が出ている．

「巡回セールスマン問題」は，
・問題自体は，小学生でも理解できるほど明快で，一見，誰でも簡単に解けそうに見える．
・ところが，実は，（少なくともナイーブな発想に基づいた方法では）最新のコンピュータを使っても（現実的な時間内には）解けない．
という，象徴的な問題なのだ．

本書に読むと，巡回セールスマン問題が，グラフ理論や組み合わせ最適化，線形計画法，計算量理論など，情報数学のさまざまな分野の発展を促す起爆剤となってきたことが分かる．


「巡回セールスマン問題」と聞いて思い出すのは，大学院のときの「適応システム」という講義で，遺伝的アルゴリズムを使ってこの問題を解くプログラムを書かされたことだ．（そのときは，「ずいぶんマニアックな宿題を出すな」と思った．）
驚いたことに，その講義の先生（東工大の永田裕一先生）が，巡回セールスマン問題のエキスパートの一人として，本書に何回も登場していた．