ITとかCockatielとか

技術のこととか。飼鳥(オカメインコ)のこととか。気になったこととか。基本的には備忘録。

巡回セールスマン問題の最良アルゴリズムが更新される

ソース

gigazine.net

 

概要

  • 上回った値は、「0.2 billionth of a trillionth of a trillionth of a percent(0.0000000000000000000000000000000002%)」だけ。
  • 従来のベストは、1976年に発見された「クリストフィード」のアルゴリズムである。
  • わずかな進歩だが、長年突破できなかった壁が破られたことから、心理的な壁も突破できると期待されている。

所感

巡回セールスマン問題は量子コンピュータの話題でよく出てきます。


量子アニーリングでは、「焼きなまし法」というアルゴリズムが用いられますが、これはさまざまなアルゴリズムの一つに過ぎないということです。


今回言及されいているクリストフィードのアルゴリズムは、

 「最良の経路よりも最大で50%しか長くならない近似解」を求めることが可能

とのことで、非常に精度の高いアルゴリズムであることがわかります。

実際、量子アニーリングを含む量子コンピュータは、古典コンピュータに勝ったことがありません。 巡回セールスマン問題の計算量は、単純計算をすると非常に膨大になると言われますが、実際はこのような優れたアルゴリズムがあるため、単純比較はできないということがわかります。

量子コンピュータによる量子超越、量子加速はまだまだ先になりそうです。