巡回セールスマン問題にみる実践と学習のギャップ

概要

組合せ最適化問題の代表的な問題は？と聞かれると、「巡回セールスマン問題」と答える人が多いかもしれません。一方、アニーリングマシンが組合せ最適化問題に適していると言いますが、実世界にある巡回セールスマン問題をアニーリングマシンで解くことが必ずしも有効とは限りません。

今回は巡回セールスマン問題を例に、アニーリングマシンの学習と実践にどのようなギャップがあるのかを解説したいと思います。

巡回セールスマン問題がアニーリングマシンの教育によく使われる理由

巡回セールスマン問題は、数学的にも解き甲斐があり数多くの数学者を魅了してきました。

一般的な巡回セールスマン問題は、「都市数$n$を各1回ずつ訪問し全都市を巡回する最も距離が短くて済む経路を求める」問題で、全ての経路を探索する大変さが一言で言える点で、組合せ最適化問題の難しさを説明するのに好まれています。

例えば、都市数を$n$とすると$n!/2n$回の計算が必要になりますが、このような数式は解の候補が爆発的に増えることが容易に想像できます。

解くのに非常に時間がかかる、つまり「多項式時間に解けない問題」を『NP問題』といい、巡回セールスマン問題は、「NP問題と同等あるいはそれ以上に難しい」という意味の『NP困難』に分類される問題と言われています。問題を現実的な時間で解けるコンピュータがあることを説明するのに巡回セールスマン問題がよく使われるのです。

巡回セールスマン問題解法の数学的な探求

巡回セールスマン問題（以降TSP）は「数学的に解く」という意味では様々な解法が研究されてきました。

例えば

• 1962年にはP&G社がTSPの最も良い解を出した人には賞金1万ドルを贈るというキャンペーンを出したことがある^※1
• 1960年代に解き明かされたTSPは49都市の問題だったが、別の手法を加える工夫により1980年代に2,392地点のTSPという記録がもたらされた。2006年には「コンコルド」というプログラムで85,900都市のTSPを解けるようになった^※1,※2

などのムーブメントがあり、他にもヒューリスティックと呼ばれる必ずしも最適な答えが見つかるわけではないがある程度正しい答えが早く求まる手法（貪欲法や局所探索法、焼きなまし法など）が様々検討されています。

アニーリングマシンは焼きなまし法の理論を量子スピンやCMOSスピンで実装された手法であるため、TSPを解くことが試みられているのも自然な流れというわけです。

実践とのギャップ

しかし実課題の解法として、数学的な解法のまま問題を解く必要はありません。

数学の世界におけるTSPは厳密な問題であり、与えられた制約（各都市を1回廻る）を守らなければならないから解き甲斐があり、解ける都市数が増えることにより学術的進歩が人々に感動をもたらしている側面があります。

一方で、実社会の課題を考えると「同じ場所を2回廻っても良い」など制約がゆるくなることもあれば逆に「廻る順番に制約がある」などと部分的に細かく複雑に制約が入ることもあり、TSPの計算式がそのまま適用できないことが多くなります。

そのため、現実的な「最適経路の探索」を行うにあたっては、制約の数・複雑さ・問題の規模によって、数学的な手法と、課題に応じた個別の工夫（解法）を組み合わせることによって解決しています。

実践に適した手段を知る

このように「学習」と「実践」にギャップがあるケースがあります。

熟練した技術者は解きたい問題に対して、「適切な手段」を探して取捨選択し、知識と経験を常にアップデートすることで問題解決の確度を高めます。そして問題が複雑になればなるほど、より一層日々の技術探求が求められることになります。

Annealing Cloud Webでは「問題解決」にあたる技術者の方々に対し、このようなアニーリングマシンや最適化問題の解決について学習段階ではなかなか先回りして気づくことができないような情報も積極的に発信していきます。

参考文献

※1：驚きの数学 巡回セールスマン問題　ウィリアム・J・クック著 松浦俊輔訳　青土社より
※2：Traveling Salesman Problem (uwaterloo.ca)

関連記事