ハト、曲線、そして巡回セールスマン問題

モー・ウィレムスの児童書「ハトにバスを運転させないで！」では、主人公（もちろんハト）が、普通の人間の運転手が急にいなくなったらバスを運転させてあげるべきだと読者を説得するために、あらゆるトリックを（文字通り）使います。ウィレムスの本は、2012年に、まったく信頼できるジャーナル「ヒューマン・コグニション」にまったく信頼できる研究者であるブレット・ギブソン、マシュー・ウィルキンソン、デビー・ケリーによるまったく信頼できる論文が掲載されたときに、意図していなかった科学的結果を生みました。彼らは、有名な数学的好奇心である巡回セールスマン問題の簡単なケースに対して、ハトがほぼ最適解を見つけることができることを実験で示しました。そのタイトルは「ハトにバスを運転させよう：ハトは部屋の中で将来のルートを計画できる」でした。

科学者にはユーモアのセンスがないなどと言うのはやめましょう。あるいは、かわいいタイトルは宣伝効果がないなどと言うのもやめましょう。

巡回セールスマン問題は単なる好奇心ではありません。これは、組合せ最適化と呼ばれる、実用上非常に重要な問題群の重要な例です。数学者は、一見些細なことでも深く重要な問いを投げかける傾向があります。

この記事の着想の元となった重要な豆知識は、ご想像の通り、巡回セールスマン向けの役立つ本に端を発しています。訪問販売員です。1832年のドイツの巡回セールスマン（当時は常に男性でした）は、賢明なビジネスマンとして、時間の有効活用とコスト削減を重視していました。幸いなことに、マニュアルという形で役立つ情報がありました。それは、ある老巡回セールスマンが書いた『巡回セールスマン ― 注文を獲得し、ビジネスを成功させるために、どうあるべきか、何をすべきか』です。

この年配の放浪商人は次のように指摘した。

仕事で旅行するセールスマンは、あちこちと移動するため、発生するすべてのケースに適した旅行ルートを適切に示すことはできません。しかし、ツアーを適切に選択して手配することで、多くの時間を節約できる場合があり、この点でもいくつかのルールを示すことは避けられないと思います... 重要な点は、同じ場所に2度行かずに、できるだけ多くの場所を常に訪れることです。

マニュアルではこの問題を解決するための数学的な提案は何もありませんでしたが、最適とされる 5 つのツアーの例が含まれていました。

巡回セールスマン問題（TSP）として知られるようになったこの問題は、後に性差別を避けるため「巡回セールスマン問題」と改名されましたが、都合よく同じ頭字語を持つため、これは現在「組合せ最適化」として知られる数学分野の創始例です。これは「一度に一つずつ検証するにはあまりにも膨大な選択肢の中から、最良の選択肢を見つけること」を意味します。

不思議なことに、TSP という名前は、数学者間の非公式な議論ではそれよりずっと以前からよく使われていたにもかかわらず、1984 年までこの問題に関する出版物では明示的に使われていなかったようです。

インターネット時代において、企業が商品を販売するために、スーツケースいっぱいのサンプルを携えた人を街から街へと派遣することは稀です。あらゆるものをウェブ上に公開するのです。いつものことながら（理不尽なほど効果的ですが）、この文化の変化によってTSPが時代遅れになったわけではありません。オンラインショッピングが飛躍的に成長するにつれ、小包からスーパーマーケットの注文、ピザに至るまで、あらゆるものにおいて、ルートとスケジュールを効率的に決定する方法への需要はますます高まっています。

数学の可搬性も関係してきます。TSP の応用範囲は、町から町へ、あるいは街路沿いを移動するだけにとどまりません。かつては著名な天文学者たちはそれぞれが望遠鏡を所有するか、数人の同僚と共有していました。望遠鏡は簡単に方向を変えて新しい天体に向けることができたため、臨機応変に対応するのは容易でした。しかし、天文学者が使用する望遠鏡が巨大で、途方もなく高価で、オンラインでアクセスできるようになった今では、そうはいきません。望遠鏡を新しい天体に向けるには時間がかかり、望遠鏡を移動させている間は観測に使用できません。間違った順序でターゲットを訪問すると、望遠鏡を長距離移動させた後、出発地点の近くまで戻すという作業に多くの時間が無駄になってしまいます。

DNAシーケンシングでは、DNA塩基の断片的な配列を正しくつなぎ合わせる必要があり、その順序はコンピュータの時間を無駄にしないよう最適化されなければなりません。その他の応用分野としては、航空機の効率的な経路決定から、コンピュータ用マイクロチップやプリント回路基板の設計・製造まで多岐にわたります。TSPの近似解は、ミールズ・オン・ホイールズの効率的な経路探索や、病院への血液供給の最適化に利用されてきました。TSPの一種は『スター・ウォーズ』にも登場しました。正確には、ロナルド・レーガン大統領が構想した戦略防衛構想です。地球を周回する強力なレーザーが、飛来する一連の核ミサイルを標的としていました。

1956年、オペレーションズ・リサーチの先駆者であるメリル・フラッドは、TSP（都市問題解決計画）は困難になりそうだと主張しました。1979年、マイケル・ギャリーとデイビッド・ジョンソンは、彼の主張が正しいことを証明しました。つまり、「最悪のケース」において問題を解く効率的なアルゴリズムは存在しないということです。しかし、最悪のシナリオは往々にして非常に不自然で、現実世界の典型的な例とはかけ離れていることが判明します。そこで、オペレーションズ・リサーチの数学者たちは、現実世界の問題に対してどれだけの都市を扱えるかを探ろうとしました。

1980 年の記録は 318 都市でしたが、1987 年には 2,392 都市になりました。1994 年までには記録は 7,397 都市にまで上がり、この答えを出すのに非常に高性能なコンピュータのネットワークで約 3 年の CPU 時間かかりました。2001 年には 110 個のプロセッサのネットワークを使用して 15,112 のドイツの都市の正確な解が得られました。これは通常のデスクトップでは 20 年以上かかります。2004 年には、スウェーデンのすべての 24,978 の都市を巡る TSP が解かれました。2005 年には、コンコルド TSP ソルバーがプリント回路基板上のすべての 33,810 点を巡る TSP を解きました。記録を樹立することがこのような研究の唯一の目的ではありません。記録を樹立するために使用された方法は、小さな問題では非常に高速に動作します。

もう一つの選択肢は、妥協することです。つまり、最善からそれほど遠くなく、かつ見つけやすい解決策です。場合によっては、1890年に行われた驚くべき発見を利用することでこれを実現できます。その分野は数学において非常に斬新であったため、当時の多くの第一人者はその価値を見出せず、より先見の明のある数学者らが徐々に見つけていた答えを信じないことも多かったのです。さらに悪いことに、彼らが取り組んだ問題は「数学そのもの」のようで、現実世界の何とも目に見える関係がありませんでした。彼らの結果は非常に人為的であると広くみなされ、彼らが構築した新しい幾何学的形状は「病的」と評されました。たとえそれらの結果が正しかったとしても、数学の大義を少しも前進させていないと感じた人も少なくありませんでした。彼らは、論理的な細部へのこだわりに溺れ、進歩に対する愚かな障害を作り出しただけだったのです。

問題の発見は曲線であるが、古代ギリシャの時代から存在していた従来の曲線の概念とは全く異なる。この曲線には隠された深遠さが見出された。円、楕円、放物線といった従来の曲線の例はそれぞれ独自の魅力を持ち、目覚ましい進歩をもたらした。しかし、家畜化された動物が地球の熱帯雨林や砂漠の荒野の生活を誤解させるように、これらの曲線は数学のジャングルを徘徊する野生動物を表現するにはあまりにもおとなしかった。連続曲線の潜在的な複雑さを示す例としては、あまりにも単純で、あまりにもおとなしかったのだ。

曲線の最も基本的な特徴の一つは、あまりにも明白で誰も疑問を抱かなかったことですが、その線は細いのです。ユークリッドが『原論』で述べたように、「直線とは厚みを持たないものである」のです。しかし1890年、ジュゼッペ・ペアノは正方形の内部を完全に埋め尽くす連続曲線の構築法を提示しました。23 この曲線は、正方形の内部を複雑な線で走り回り、任意の点に近づくわけではありません。正方形内のすべての点を通り、正確にその点に当たるのです。ペアノの曲線は確かに「厚みを持たない」のです。つまり、先端が単一の幾何学的点である鉛筆で線をなぞることで曲線を描くという意味です。しかし、その線は非常に複雑にうねり、以前通過した領域を繰り返し訪れます。ペアノは、この曲線を注意深く制御された方法で無限にうねらせれば、正方形全体を埋め尽くすことができると気づきました。

この発見は素朴な直感にとって衝撃的なものでした。当時、この種の曲線は「病的」と呼ばれ、多くの数学者は私たちが病理学に抱くのと同じように、恐怖と嫌悪感をもって反応しました。その後、数学者たちはこれらの曲線に慣れ、そこから得られる深い位相幾何学的教訓を吸収していきました。

今日、ペアノ曲線はフラクタル幾何学の初期の例として認識されており、フラクタルが決して異常でも病理学的なものではないことが認識されています。フラクタルは数学の世界でも広く見られ、現実世界では雲、山、海岸線といった自然界の非常に複雑な構造の優れたモデルとなっています。

この新しい数学の時代の先駆者たちは、連続性や次元といった古くからの直感的な概念を検証し、難問を問い始めた。この懐疑的なアプローチは、多くの主流派数学者を苛立たせ、彼らはそれをそれ自体が否定的だとみなした。「私は、微分のない連続関数というこの恐ろしい災厄に、恐怖と戦慄を覚えて背を向ける」と、シャルル・エルミートは1893年に友人のトーマス・スティルチェスに書き送った。

しかし1930年代には、このより厳密なアプローチの価値が明らかになり、1960年代にはほぼ完全に普及しました。ここでは、次元の概念に焦点を当てたいと思います。

私たちは皆、空間が 3 次元、平面が 2 次元、直線が 1 次元であると学びます。この概念を理解するために、「次元」という言葉を定義し、空間または平面がいくつの次元を持つかを数えるわけではありません。厳密にはそうではありません。そうではなく、空間が 3 次元であると言うのは、任意の点の位置を正確に 3 つの数値で指定できるためです。特定の点 (原点) と 3 つの方向 (南北、東西、上下) を選びます。次に、それぞれの方向について、原点から選んだ点までの距離を測るだけです。これで 3 つの数値 (選択した方向に対する座標) が得られ、空間内の各点は、このような 3 つの数値のうち 1 つだけに対応します。同様に、平面が 2 次元であるのは、上下の数値など、そのうちの 1 つを省略できるためであり、直線は 1 次元です。

そこから、より深い疑問が湧いてきます。飛行機の計算に必要な最小の数字が2だと、どうして分かるのでしょうか？ 完全に明白なわけではありません。さて、堰を切ったように疑問が湧いてきます。宇宙の計算に必要な最小の数字が3だと、どうして分かるのでしょうか？ 独立した方向を選べば必ず3つの数字になる、とどうして分かるのでしょうか？ そもそも、3つの数字で十分だと、どれほど確信できるのでしょうか？

この三番目の問いは、実際には実験物理学の領域であり、アインシュタインと彼の一般相対性理論を経て、物理空間は実際にはユークリッドの平坦な三次元空間ではなく、曲がったバージョンであるという示唆に至ります。あるいは、弦理論家が正しければ、時空は10次元または11次元を持ち、そのうち4次元を除くすべての次元は私たちが認識できないほど小さすぎるか、アクセス不可能です。最初の問いと二番目の問いは、三次元ユークリッド空間を3つの数値を持つ座標系で定義し、任意の数の座標が可能なベクトル空間に関する大学の講義を5～6週間かけて学び、ベクトル空間の次元が一意であることを証明することで、十分に解決できますが、決して簡単ではありません。

ベクトル空間アプローチに内在する考え方は、座標系が直線に基づいており、空間は平坦であるというものです。実際、これは「線型代数」とも呼ばれています。では、アインシュタインの法則に倣って座標系を曲げることを認めたらどうなるでしょうか？滑らかに曲がる場合（古典的には「曲線座標」と呼ばれます）、すべては順調です。しかし、1890年にイタリアの数学者ジュゼッペ・ペアノは、座標系が極端に曲がる場合（滑らかではなくなり、連続性を保つほどに曲がる場合）、2次元空間は1つの数値だけを持つ座標系を持つことができることを発見しました。3次元空間でも同様です。このより一般的で柔軟な設定では、突如として次元数が可変になります。

この奇妙な発見に対する一つの反応は、それを無視することです。明らかに滑らかな座標を使う必要がある、などと。しかし、奇妙さを受け入れて何が起こるかを見る方が、はるかに創造的で、有用で、そして実に楽しいことが分かりました。伝統主義的な批評家たちはむしろ清教徒的で、若い世代に全く楽しみを与えたくなかったのです。

ペアノが正方形のすべての点を通る連続曲線を発見したことで、正方形のすべての点を、連続的に変化する一つの数で指定できるようになりました。つまり、この観点から見ると、正方形は実際には一次元なのです！

空間充填曲線は、多次元データの保存や検索など、コンピューティングにも応用できます。基本的な考え方は、空間充填曲線の近似に従うことで多次元配列を走査し、問題を1次元の場合に簡略化できるというものです。別の応用として、巡回セールスマン問題の簡略な解が得られます。この場合の考え方は、都市を含む領域に空間充填曲線の有限近似を適用し、曲線に沿って都市を順番に並べ、各ステップで最短の経路を使ってその順番に都市を訪問するというものです。この方法で得られる経路は、通常、最適な経路よりも25%以内の長さになります。

ギブソン、ウィルキンソン、ケリーによる『Human Cognition』誌に掲載されたあの論文に戻りましょう。彼らは冒頭で、TSPが最近、ヒトや動物の認知機能、特に行動を計画する能力を調べるために用いられたと述べています。しかし、この能力が霊長類に限定されているかどうかは明らかではありませんでした。

他の動物も事前に計画を立てることができるのでしょうか？それとも、進化によって発達した厳格なルールに従っているだけなのでしょうか？研究者たちは、ハトを用いて、2つまたは3つの目的地（給餌器）を持つ単純なTSP（移動時間計画）を提示する実験を行いました。ハトはある場所から出発し、一定の順序で各給餌器へ移動し、最終目的地まで移動します。研究チームは、「ハトは次の場所への近さを重視しますが、非効率的な行動による移動コストが増加すると思われる場合は、複数段階にわたって事前に計画を立てているようです。この結果は、霊長類以外の動物も洗練された移動経路を計画できることを明確かつ強力に証明しています」と結論付けました。

研究者たちはインタビューで、バスを運転するハトとの関連性について説明した。彼らは、運転手が反対した理由は2つあると示唆した。1つは安全上の懸念、もう1つはバスが市内を走行する際にハトが乗客を効率的に乗せるルートを辿れないのではないかという懸念だ。論文のタイトルが示すように、研究チームは実験の結果、後者の懸念は根拠がないと結論付けた。

鳩にバスを運転させましょう。

記事内のリンクから商品やサービスを購入された場合、手数料が発生する場合があります。これは私たちのジャーナリズムを支えるものです。 詳細はこちらをご覧ください。

WIREDのその他の素晴らしい記事

• 📩 テクノロジー、科学などの最新情報: ニュースレターを購読しましょう!
• ハリネズミのインスタグラムのダークサイド：羽根ペンのように見える
• ロボットが溢れる農業の未来は悪夢か、それともユートピアか?
• 自動的に消えるメッセージを送信する方法
• ディープフェイクがビジネスに活用される
• カーゴパンツを復活させる時が来た
• 👁️ 新しいデータベースで、これまでにないAIを探索しましょう
• 🎮 WIRED Games: 最新のヒントやレビューなどを入手
• 🏃🏽‍♀️ 健康になるための最高のツールをお探しですか？ギアチームが選んだ最高のフィットネストラッカー、ランニングギア（シューズとソックスを含む）、最高のヘッドフォンをご覧ください