巡回セールスマン問題

学会で京都に出かけて久しぶりに京野菜やら鱧の湯引きやらを食べた。レベルが高いし、納得のお値段。

ウィリアム・クックの「驚きの数学　巡回セールスマン問題」を読む。

驚きの数学 巡回セールスマン問題

少し調べたいことがあって確率過程やら最適化について入門書を集めて読み進めている。この本は集めた中に入っていたのだが、大変面白い。ただし、たぶん25%くらいしか理解できていないと思う。
自分ではそこまで厳しいプログラムを書いたことがないので計算論という分野を真剣に考えたことことがないのだが、巡回セールスマン問題(TSP)は基礎論と計算論にまたがって、かつ視覚的に理解できるというcharmingな分野だということがよくわかった。

印象に残ったあたりを抜き書きしてみるとこんな感じになる。

わかったのは、第５章の線形計画法や第９章の複雑性のところなのでそのあたりを抜き書きしてみる。

「情報を似たような特性のいくつかの要素からなるグループにまとめるのは、データからパターンを抽出するデータマイニングという処理の分野では基本的な作業だ。そのような作業でTSP（巡回セールスマン問題）が採用されてきたのは、二つ一組のデータ点の間の類似度を表す優れた尺度がある場合だ。類似を表す数値を移動コストとして使うと、最大コストのハミルトン経路は、似たような点を互いに近い所に置く。そうして経路の中の区間はクラスターの候補として使われる。最後に区間にわけるのはふつう手作業で行い、並びの中の自然な切れ目を選ぶ」
これだけでも、ビックデータの時代にTSPがどんどん面白くなっていることが納得できる。

「巡回路の求め方の大きな構図を描き、TSPを探索問題一般の一例と見ることは、優れた巡回路をみつけるにも、多目的の手法を考案するのにも使えることが分かる。みそは、メタヒューリスティクス、つまりヒューリスティクスな方法を設計するためのヒューリスティクスな方法を生み出すことだ」
このあたりも哲学的すぎるかもしれないが、いろいろな意味で面白い。私はメタファーが大事ということか、と思った。

「一群の点を通る最善の巡回路を選び、それが最善であることを確かめるのがTSP全体の課題となる。あらゆる順列を並べ替える力任せのアルゴリズムを使えば確実にこの課題をこなすことができるが、そのような手法にはわかりにくいところもない代わりに、実用的な効率にかける。必要なのは、順列をいちいち調べなくても巡回路の質を保証する手段だ。この脈絡では、線形計画法という驚くほど効果的な方法がお勧めの道具となる。これによって、すべての巡回路が満たす多数の単純な条件を組み合わせて、「この点集合すべてを通る巡回路でｘより短くなりうるものはない」という形の単独の規則が得られる。数Xは直接に質を表わす尺度となる。長さXの巡回路を造ることもできれば、それは確かに最適解だと考えられる」

第５章の「線形計画 (LP) 法」はこの本の中でも特によい。中でもジョージ・ダンツィクの切れ味はすごい。

「ダンツィクは、最適化の分野でも複雑性の理論の分野でも根本となる論文を書き、最適化の分野で重要な問題の長いリストにあるそれぞれの問題が、どうすればLP問題としてモデル化できるかを示した。ダンツィクは1963年のLPの本で、その成果を次のように解説している『ここでの目的は、変数の一部あるいは全てが整数の値を持つ線形計画法に帰着できる問題を系統的に見渡し、分類することだ。難しくて一見しただけでは不可能なような、非線形で、非凸で、組み合わせ論的な性格の大量の問題が、今や直接に攻略できることを示す』」

この本の副旋律はたぶんP対NP問題だろう。だいたいこんな調子である。

「ある問題の答えが正しいことを確かめるのが容易なら、その問題を解くのも容易か。これがP対NP問題の本質である。Nか所の都市を車で訪れるとして、同じ都市を再度訪れずに回るにはどうすればよいかというハミルトン経路問題はNP問題の典型だ。あなたが答えを出せば、私はそれが正しいかどうか、すぐに確かめることができる。ところが、答えを求めるとなると（私が知っている方法では）簡単にはできない」

ここから始めて使えるところまで持っていくのは少し時間がかかるかもしれないが、いろいろいいソフトが出ているし、勉強すればするほど役に立ちそうなのでこの機会にしっかり勉強しておこう。