易しくて、奥深い - 作品メモランダム

★ウィリアム・J・クック『驚きの数学巡回セールスマン問題』（松浦俊輔訳、青土社、2013/06、ISBN:4791767101）
　William J. Cook, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation (Princeton University press, 2012)

数学とは、数や図形や論理の性質を調べ、そこに潜む謎の解決を目指す学問だ。学校数学に適応しすぎてしまうと、数学とは公式や証明法を記憶して、出された問題に的確に答えるものだという話になってしまうかもしれない。しかし、それは数学の門前というか、すでに解明された謎の結果を学んでいるに過ぎない。数学は、あらゆる学術と同様に、いまだ人類の誰も解いたことのない問題に取り組み、その過程で新たな着想を得たり、発見に辿り着くという営みなのである。そして、そこが面白い。

ダヴィド・ヒルベルトは、1900年に開催された国際数学者会議の講演で、数学における問題の意義と重要性を説いて、こう述べていた。

科学の分野に問題が豊富にある限り、その分野の命は保たれます。問題が見当たらないということは、こうした分野が消滅するか独立的な発展が停止するかの前兆なのです。人間のすべての活動が特定の目的を追求しているように、数学の研究にも問題が必要なのです。問題を解決することによってこそ、研究者の力が鍛えられます。研究者は、新たな手法と新たな展望を発見し、より広く自由な地平に到達できるのです。

（「ヒルベルトの講演」、ジェレミー・J・グレイ『ヒルベルトの挑戦』、好田順治＋小野木明恵訳、青土社、2003、所収）

そんなわけで、数学がいまもって研究されているということは、未解決の問題があるという証左でもある。そうした未解決問題の一つが、本書でテーマとなっている「巡回セールスマン問題（Traveling Salesman Problem）」だ。それは、こんなふうに述べることができる。

トゥーディとマルドゥーンが車で全国を回り、課題地図上の丸印で表された33の都市を一つ一つ訪れますが、その際、移動距離はできるかぎり短くしたいとします。2人がイリノイ州シカゴを出発して、またイリノイ州シカゴに戻ってくる合計の距離が最短になるようにルートを計画してください。

（ウィリアム・J・クック『驚きの数学巡回セールスマン問題』）

つまり、地図上にいくつかの場所がある。そのうちの特定の場所から出発し、全ての場所を通って、出発点に戻ってきたい。さて、ありうる順路のうち、最短距離で巡れるのはどのルートだろうか、という問題である。

この問題、一見すると易しく、数学が苦手な人が見ても、何を問われているのかは分かると思う。なんなら、巡る場所が二つとか三つの場合について、図を描いて考えてみることさえできるかもしれない。

しかし、これを解決しようと思うと一筋縄ではゆかないのである。「そんなことないだろう」と思ったら、巡るべき場所を10、20、30と増やして考えてみるとよい。問題文を読む限り、とても単純に見えた謎が、一挙にもつれた毛糸玉のようにどうしてよいか分からなくなってしまうから！

ところで、数学において、ある問題を「解決する」という場合、特に断りがなければ、その問題を一般的に解けるということを意味する。「一般的に」というのは、この巡回セールスマン問題で言えば、「巡るべき場所の数がｎの場合」（ただしｎは任意の自然数）に解けるということだ。つまり、場所の数がいくつであっても、それを解決できる方法を発見できるということなのである。たとえ、巡るべき場所が1万の場合を解決できたとしても、それは特殊な場合が解けたというに過ぎない、という次第だ。ここが数学の凄まじいところ。そして、「巡回セールスマン問題」は、目下のところ解決されていない。難問である。

先ほどのヒルベルトの言葉をもう一度借りよう。彼は、数学の問題についてこんなふうにも言っている。

数学の問題は難しくなければ魅力を感じませんが、努力がむだに終わらぬよう、まったく近づきがたいものであってはなりません。それは隠れた真実に通じる曲がりくねった小道に立つ道しるべであり、最終的に解決をみれば喜びが得られるものでなくてはなりません。

（「ヒルベルトの講演」、ジェレミー・J・グレイ『ヒルベルトの挑戦』、好田順治＋小野木明恵訳、青土社、2003、所収）

このような意味でも、「巡回セールスマン問題」は魅力的な問題であるといえるだろう。

さて、本書はこの一見単純な問題の面白さと奥深さを、懇切丁寧に案内してくれる好著だ。読者は、読み進めるにつれて、問題がさまざまに変形されたり、見直されるのに遭遇して、「そんな角度からも眺めることができるのか！」と驚くこと請け合い。問題の表面からは思いもかけないような複雑さや、それを取り扱うさまざまな発想や技法が現れる道中は、まさにワンダーランドを巡る冒険である。

しかも、著者が紹介しているように、この「巡回セールスマン問題」は、単に数学の難問というだけではない。これが解決された暁には、最短経路が問題となる各種の事柄も、改善や効率向上が期待されるのだ。例えば、ゲーム開発者を悩ませる問題の一つに、ディスクのような記憶媒体からデータを読み出すための「ロード時間」をいかに短縮できるかというものがある。ディスク上のデータが記録された位置を、訪れるべき「都市」に、データを読み取るヘッドやレーザーの動きを「セールスマン」に見立てればお分かりのように、これもまた立派な「巡回セールスマン問題」というわけだ。