数学の難問「巡回セールスマン問題」の近似解を求める最良のアルゴリズムが数十年ぶりに更新される

巡回セールスマン問題とは、「複数の都市を移動するセールスマンが全都市をちょうど一度ずつ巡り、総移動コストが最小の経路を求める」という数学の難問です。長年にわたり「クリストフィードのアルゴリズム」が巡回セールスマン問題の近似度が最も高いアルゴリズムとされてきましたが、新たに「クリストフィードのアルゴリズムを上回る近似度のアルゴリズムがあると証明された」という論文を、コンピューターサイエンスの研究者が発表しています。

[2007.01409] A (Slightly) Improved Approximation Algorithm for Metric TSP
https://arxiv.org/abs/2007.01409

Computer Scientists Break Traveling Salesperson Record | Quanta Magazine
https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/

巡回セールスマン問題は多くの理論計算機科学者らが取り組んできた基本的な問題の一つです。「巡回セールスマン問題において、近似解ではない真に最適な解を求めるアルゴリズムは存在しない」と多くの科学者らは考えていますが、それでも最良のアルゴリズムを求めて研究が進められてきました。この科学者らの熱意に関して、計算複雑性理論の第一人者であるChristos Papadimitriou氏は巡回セールスマン問題について、「これは『問題』ではなく『中毒』です」と述べています。

長年にわたる研究により、局所探索アルゴリズムや焼きなまし法、遺伝的アルゴリズムを用いた方法など、近似解を求めるさまざまな方法が考案されました。その中でも、1976年に発見されたクリストフィードのアルゴリズムは、「最良の経路よりも最大で50％しか長くならない近似解」を求めることが可能であり、数十年にわたり最良のアルゴリズムとされていました。

クリストフィードのアルゴリズムが発表された当時のコンピューターサイエンス研究者らは、すぐに誰かがこのアルゴリズムを改良して、より精度が高いアルゴリズムを発見するだろうと考えていました。しかし、数十年にわたる努力にもかかわらず、クリストフィードのアルゴリズムを上回るアルゴリズムは発見されなかったとのこと。

長年にわたりクリストフィードのアルゴリズムが近似解を求める最良のアルゴリズムだった状態について、グルノーブル・アルプ大学の研究者であるAlantha Newman氏は、「誰もが簡単なアルゴリズムを知っています。それを知っていれば、あなたは最先端を知っていることになります」と述べています。

2010年、ジョージア工科大学の研究者だったAmin Saberi氏やShayan Oveis Gharan氏、Mohit Singh氏らの研究チームは、クリストフィードのアルゴリズムを改善した新たなアルゴリズムを開発。経路の一部についてより効率的な探索が可能となる新たなアルゴリズムは、直感的に考えると以前の方法より効率的であるように感じられました。ところが、「新たなアルゴリズムがクリストフィードのアルゴリズムより効率的だ」と証明することが、新たな難問として立ちはだかったとのこと。

Saberi氏らの研究チームは2011年になって、限定的な範囲の巡回セールスマン問題において、新たなアルゴリズムがクリストフィードのアルゴリズムより優れていることを証明しました。しかし、この証明を一般的な巡回セールスマン問題に拡張することができず、10年近くそのままになっていたそうです。

しかしOveis Gharan氏は、「一般的な巡回セールスマン問題においても、自分たちのアルゴリズムがクリストフィードのアルゴリズムより優れているはずだ」と考え続けていました。Oveis Gharan氏は、理論計算機科学の世界ではほとんど知られていないgeometry of polynomials(多項式の幾何学)と呼ばれる分野に、証明の手がかりがあるのではないかと疑っていたとのこと。

そんな中、ワシントン大学に移ったOveis Gharan氏の研究室に、Nathan Klein氏という優秀な大学院生が入ってきました。指導教官であるAnna Karlin教授と共に研究対象のアドバイスを求められたOveis Gharan氏は、自分が長年考え続けてきた巡回セールスマン問題のアルゴリズムについて一緒に研究しないかと誘いました。当時のKlein氏は、たとえ問題が解決できなくてもその過程で多くのことが学べると考え、提案を受け入れたそうです。指導教官のKarlin教授は、「この問題を本当に解決できるとは思っていませんでした」と述べています。

最初の1年目で、研究チームは問題をさらに簡略化したバージョンの解決に取り組み、自分たちが直面している課題を理解したとのこと。その後も多項式の幾何学を基にしたアプローチで取り組み続けた結果、ようやく「10年前に考案されたアルゴリズムが、クリストフィードのアルゴリズムをわずかに上回る精度で、一般的な巡回セールスマン問題の近似解を求めることができる」ことを証明しました。論文は査読前ですが、専門家らはこの論文が正しいと確信しているそうです。

分析の結果、新たなアルゴリズムがクリストフィードのアルゴリズムを上回っているのは、ほんの「0.2 billionth of a trillionth of a trillionth of a percent(0.0000000000000000000000000000000002％)」というわずかな数値だと判明したそうです。しかし、これは巡回セールスマン問題における大きな進歩であり、理論的な壁だけでなく心理的な壁も突破すると研究チームは期待しています。Oveis Gharan氏は、この論文が完成するとかつての指導教官だったAmin Saberi氏に電子メールを送り、「これでようやく卒業できると思います」と冗談を飛ばしたと述べました。