こんばんは，ゴドーです。
GIGAZINEにおもしろい記事が乗っていました。
「巡回セールスマン問題」の近似解を求める最良アルゴリズムが，数十年ぶりに更新されたとのことです。
「巡回セールスマン問題」というのは有名な数学・グラフ理論の問題。
営業サラリーマンがいくつかの都市を回っていくのですが，一筆書きで全ての都市を巡り出発した都市まで帰ってくるための最短経路を求める問題です。
都市の数が少ないときは総当たりで最適解を見つけることができますが，都市の数Nに対して考えうる経路の総数はN!のオーダーで増えていくので，現実的な時間内で最適解を見つけるのは絶望的です。
そこで，最適ではないにせよ比較的よい解「近似解」を探すためのアルゴリズムが色々考えられているのですね。
論文タイトルは「A (Slightly) Improved Approximation Algorithm for Metric TSP」。
1976年に提案された「クリストフィードのアルゴリズム」がこれまでの最良アルゴリズムだったのですが，これより僅かに良いアルゴリズムが新しく提案されたと。
何より興味深いのは，論文タイトルに「(Slightly)」とあるように，新しいアルゴリズムがクリストフォードのアルゴリズムを上回っているのは僅か「0.2 billionth of a trillionth of a trillionth of a percent(0.0000000000000000000000000000000002％)」だけであるということ。
日常生活において「僅か」と評されるどんなものであっても，これほどまでに僅かな数値というものはなかなか見られないでしょう。
しかし，更新の度合いが極々僅かであることよりも，数十年間破られなかった記録が更新されたことに大きな意味がありますね。
今回の成果を元に，更にアルゴリズムが進歩していく可能性もあるでしょう。
ニール・アームストロングの有名なセリフにもありますが，今回の僅かな一歩が，人類にとって偉大な一歩であったことは疑いようがないと思います。
それでは，また。
/ゴドー
