コンピュータ科学者が「巡回セールスマン」の記録を破る

ネイサン・クライン氏が2年前に大学院に入学したとき、彼の指導教官は控えめな計画を提案した。それは、理論計算機科学における最も有名で長年にわたる問題の一つに協力して取り組むというものだ。

たとえ解けなくても、クラインはその過程で多くのことを学ぶだろうと彼らは考えた。彼はその考えに賛成した。「怖気づくなんて知らなかったよ」と彼は言った。「大学院1年生だったから、何が起こっているのか全く分からなかったんだ」

今回、7月にオンライン掲載された論文で、クライン氏とワシントン大学の指導教官であるアンナ・カーリン氏およびシャヤン・オベイス・ガラン氏は、コンピューター科学者が半世紀近く追い求めてきた目標、すなわち巡回セールスマン問題の近似解を見つけるためのよりよい方法をついに達成した。

複数の都市を巡る最短（または最も安価な）往復経路を求めるこの最適化問題は、DNA配列解析からライドシェアの物流まで、幅広い応用分野に広がっています。数十年にわたり、この問題はコンピュータサイエンスにおける最も根本的な進歩の多くに影響を与え、線形計画法などの手法の威力を明らかにすることに貢献してきました。しかし、研究者たちはその可能性を未だ十分に探求できていません。それは、試みが足りないからではありません。

計算複雑性の第一人者であるクリストス・パパディミトリウ氏がよく言うように、巡回セールスマン問題は「問題ではなく、依存症だ」。

ほとんどのコンピュータ科学者は、あらゆる都市の組み合わせに対して最適な解を効率的に見つけられるアルゴリズムは存在しないと考えています。しかし1976年、ニコス・クリストフィードは近似解、つまり最適な往復よりも最大50%長い往復を効率的に見つけるアルゴリズムを考案しました。当時、コンピュータ科学者たちは、誰かがすぐにクリストフィードのシンプルなアルゴリズムを改良し、真の解に近づくだろうと期待していました。しかし、期待された進歩は訪れませんでした。

「多くの人がこの結果を改善するために数え切れないほどの時間を費やした」とスタンフォード大学のアミン・サベリ氏は語った。

カーリン、クライン、そしてオベイス・ガランらは、10年前に考案されたアルゴリズムがクリストフィードの50%係数を上回ることを証明した。ただし、実際に減算できたのは1兆分の1の1兆分の2の10億分の1に過ぎない。しかし、このわずかな改善は、理論的な行き詰まりと心理的な行き詰まりの両方を打破するものだ。研究者たちは、これがさらなる改善への扉を開くことを期待している。

「これは私がキャリアを通じてずっと望んでいた結果だ」と、1980年代から巡回セールスマン問題を研究してきたコーネル大学のデイビッド・ウィリアムソン氏は語った。

巡回セールスマン問題は、理論計算機科学者が効率的な計算の限界を検証するために繰り返し取り組む数少ない基礎問題の一つです。ウィリアムソン氏は、今回の新たな結果は「効率的な計算の限界が実際には私たちが考えていたよりも優れていることを示す第一歩です」と述べています。

部分的な進歩

常に最短の移動経路を見つける効率的な方法はおそらく存在しないでしょうが、それとほぼ同等の効率性を持つ方法を見つけることは可能です。それは、すべての都市を結ぶ最短のツリー、つまり閉ループのない接続（または「エッジ」）のネットワークです。クリストフィードのアルゴリズムは、このツリーを往復ルートのバックボーンとして使い、追加のエッジを追加することで往復ルートに変換します。

往復ルートは、各都市への辺の数が偶数である必要があります。これは、到着ごとに出発があるためです。逆もまた真です。つまり、ネットワーク内の各都市が偶数の接続を持つ場合、ネットワークの辺は必ず往復経路を辿ります。

すべての都市を結ぶ最短木には、この偶数性がありません。枝の端にあるどの都市も、他の都市との接続は1つしかないからです。そこで、最短木を往復にするために、クリストフィード（昨年亡くなった）は、奇数の辺を持つ都市のペアを結ぶ最良の方法を見つけました。そして、結果として得られる往復は、最良の往復よりも50%以上長くなることはないことを証明しました。

そうすることで、彼は理論計算機科学においておそらく最も有名な近似アルゴリズムを考案しました。これは通常、教科書や講義の最初の例として挙げられるものです。

「シンプルなアルゴリズムは誰でも知っています」と、フランスのグルノーブル・アルプ大学と国立科学研究センターのアランサ・ニューマン氏は言う。そして、それを知れば「最先端の技術も知っている」と彼女は言う。少なくとも、今年の7月まではそうだった。

コンピュータ科学者たちは、クリストフィードのアルゴリズムよりも優れた近似アルゴリズムが存在するはずだと長年考えてきた。結局のところ、彼のシンプルで直感的なアルゴリズムは、巡回セールスマンのルートを設計する上で必ずしも効果的ではない。都市間を結ぶ最短のツリーが、必ずしも最適なバックボーンとは限らないからだ。例えば、このツリーに多くの枝がある場合、枝の先端にある各都市は別の都市とマッチングする必要があり、コストのかかる新たな接続が多数発生する可能性がある。

2010年、ジョージア工科大学のオベイス・ガーラン、サベリ、モヒット・シンは、すべての都市を結ぶ最短の木ではなく、厳選された集合からランダムに木を選ぶことで、クリストフィードのアルゴリズムを改良できるのではないかと考え始めました。彼らは巡回セールスマン問題の別のバージョンから着想を得ました。この問題では、複数の経路の組み合わせを移動することが許されています。例えば、シカゴからデンバーまでの経路の4分の3と、ロサンゼルスからデンバーまでの経路の4分の1を組み合わせてデンバーに到着するといった具合です。

通常の巡回セールスマン問題とは異なり、この分数問題は効率的に解くことができます。分数経路は物理的に意味をなさないものの、コンピュータ科学者は長年、最適な分数経路は良好な通常経路の輪郭線を大まかに示す指標となるはずだと信じてきました。

そこで、オベイス・ガラン、サベリ、シンは、アルゴリズムを作成するために、すべての都市を結ぶ木を選択するランダムプロセスを定義しました。このプロセスでは、特定のエッジがその木に含まれる確率が、最適な分数経路におけるそのエッジの割合に等しくなります。このようなランダムプロセスは多数存在するため、研究者たちは、均等に接続された都市を多数含む木を生成する傾向のあるものを1つ選びました。このランダムプロセスによって特定の木が吐き出された後、彼らのアルゴリズムはそれを、奇数個のエッジを持つ都市をマッチングするクリストフィードのスキームに挿入し、往復経路に変換します。

この手法は、3人の研究者だけでなく、他のコンピュータ科学者にとっても有望に思えた。「直感的にはシンプルです」とスイス連邦工科大学ローザンヌ校のオーラ・スヴェンソン氏は述べた。「しかし、それを証明するとなると、また別の難題が待ち受けています」

しかし翌年、オベイス・ガラン、サベリ、シンは、自らのアルゴリズムが「グラフィカル」巡回セールスマン問題においてクリストフィードのアルゴリズムを上回ることを証明することに成功した。グラフィカル巡回セールスマン問題とは、都市間の距離がネットワーク（必ずしもすべての接続を含むとは限らない）で表され、すべての辺の長さが同じになる問題である。しかし、研究者たちは、一部の辺が他の辺よりも大幅に長い場合がある一般的な巡回セールスマン問題に、この結果を拡張する方法を見つけられなかった。

「マッチングに超高価なエッジを追加しなければならないとしたら、基本的に困ったことになる」とカーリン氏は語った。

押し返す

それでも、オベイス・ガラン氏は、この共同研究から、一般的な巡回セールスマン問題において、彼らのアルゴリズムがクリストフィード氏のアルゴリズムに勝るはずだという揺るぎない信念を抱きました。「私は一度も疑ったことはありませんでした」と彼は言います。

オヴェイス・ガーランはその後何年もこの問題を頭の中で考え続けた。彼は、理論計算機科学の世界ではほとんど知られていない「多項式幾何学」という数学分野に、自分が必要とするツールがあるのではないかと考えていた。そのため、2年前、カーリンが数学とチェロをダブルメジャーしている優秀な新入生、ネイサン・クラインを共同指導するようガーランに提案したとき、ガーランは「よし、やってみよう。面白い問題があるんだ」と言った。

カーリンは、少なくとも多項式の幾何学についてもっと学ぶ楽しい機会になるだろうと考えました。「まさかこの問題を解けるとは思っていませんでした」と彼女は言いました。

彼女とオベイス・ガーランは、クラインをコンピュータサイエンス研究の深みに放り込むことに何の躊躇もなかった。オベイス・ガーラン自身も、2010年に大学院生として巡回セールスマン問題で経験を積んだ経験がある。そして二人の指導教官は、大学院生に難しい問題を課すこと、特に結果を出すプレッシャーがない最初の数年間は難しい問題を課すことのメリットについて意見が一致していた。

3人は熱心にコラボレーションに取り組みました。「2年間ずっとそればかり考えていました」とクラインは語りました。

彼らは最初の1年間、直面している課題を把握するために、問題の簡略化されたバージョンを解くことに費やしました。しかし、それを達成した後でも、全体的なケースは依然として「ムーンショット」のように感じられたとクライン氏は言います。

それでも、彼らはツール、特に多項式の幾何学的な感覚を掴んでいた。多項式とは、3 x ²y + 8 xz ⁷のように、数値と変数をべき乗した項の組み合わせである。巡回セールスマン問題を研究するために、研究者たちは都市の地図を、都市間の各辺に1つの変数、そしてすべての都市を結ぶ木に1つの項を持つ多項式へと分解した。そして、数値係数を用いてこれらの項に重み付けを行い、巡回セールスマン問題の分数解における各辺の値を反映した。

研究者たちは、この多項式が「実安定性」と呼ばれる待望の特性を持つことを発見しました。これは、多項式の評価結果がゼロになる複素数が、複素平面の上半分には決して存在しないことを意味します。実安定性の優れた点は、多項式に様々な変更を加えても、その特性が維持されることです。そのため、例えば、研究者が特定の都市に焦点を当てたい場合、ある都市につながる様々な辺を単一の変数で表し、重要でない辺の変数を1に設定することができます。これらの簡略化された多項式を操作しても、操作結果は依然として実安定性を示し、幅広い手法への道が開かれました。

このアプローチにより、研究者たちは、アルゴリズムがどの程度の頻度で遠く離れた2つの都市を接続せざるを得なくなるかといった疑問を解明することができました。約80ページに及ぶ分析で、彼らはこのアルゴリズムが一般的な巡回セールスマン問題においてクリストフィードのアルゴリズムを上回ることを実証しました（論文はまだ査読を受けていませんが、専門家はそれが正しいと確信しています）。論文が完成すると、オベイス・ガランはかつての博士課程の指導教官であるサベリに急いでメールを送りました。「やっと卒業できそうだな」と彼は冗談めかして言いました。

研究者たちが確立した改善はごくわずかですが、コンピュータ科学者たちはこの画期的な進歩がさらなる急速な進歩を促すことを期待しています。まさに2011年、オベイス・ガラン、サベリ、シンがグラフィカルなケースを解明した際に起こったことです。それから1年も経たないうちに、他の研究者たちが根本的に異なるアルゴリズムを考案し、グラフィカルなケースの近似係数を大幅に改善しました。現在では、クリストフィードの50%ではなく40%にまで低減されています。

「彼らが（グラフィカルケースに関する）結果を発表したとき、…それが可能だと私たちは思いました。それが私たちを奮い立たせました」と、そのケースでさらなる進歩を遂げた研究者の一人であるスヴェンソン氏は語った。彼は長年、一般的な巡回セールスマン問題におけるクリストフィードのアルゴリズムを破ろうと試みてきた。「可能だと分かったので、もう一度挑戦します」と彼は言った。

巡回セールスマン問題は、数十年にわたり、多くの新しい手法を世に送り出してきました。オベイス・ガーラン氏は、この手法が多項式幾何学にも応用されることを期待しており、熱心な伝道師となっています。このアプローチを学び始めてから約10年、ガーラン氏は幅広い定理の証明に役立ってきました。「このツールは私のキャリア全体を形作りました」と彼は言います。

ニューマン氏は、巡回セールスマンの新たな結果は、このアプローチの威力を浮き彫りにしていると述べ、「より詳しく調べてみようという意欲が湧くのは間違いありません」と続けた。

クライン氏はこれから、夢中になれる新たな問題を見つけなければならない。「あの問題を失うのは少し悲しいですね。頭の中にたくさんの構造が構築されていたのに、今は全部消えてしまったようなものですから」と彼は言った。しかし、彼にとってこれ以上ないほど満足のいくコンピュータサイエンス研究への入門だった。「未知のものに少しだけ踏み込んだような気がしました」

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。

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

📩 テクノロジー、科学、その他の最新情報を知りたいですか？ニュースレターにご登録ください！
西部の地獄は、火の仕組みに関する私たちの感覚を溶かしている
Amazonは「ゲームで勝つ」ことを望んでいる。では、なぜそれが実現していないのだろうか？
図書館の仮想棚から電子書籍が消えていくことに出版社は懸念を抱いている
写真はかけがえのないものです。携帯電話から取り出しましょう
Twitterはいかにして大規模なハッキングから逃れたのか、そして次のハッキングを阻止する計画は？
🎮 WIRED Games: 最新のヒントやレビューなどを入手
🏃🏽‍♀️ 健康になるための最高のツールをお探しですか？ギアチームが選んだ最高のフィットネストラッカー、ランニングギア（シューズとソックスを含む）、最高のヘッドフォンをご覧ください