2020-01-06

シミュレーテッド分岐マシン(SBM)で巡回セールスマン問題を解く

はじめに

東芝シミュレーテッド分岐マシンによる最大カット問題のベンチマークの記事では、最大カット問題をSBMで実行してみました。

今回は、組み合わせ最適化問題の具体例として取り上げられることの多い「巡回セールスマン問題(TSP)」を、SBMで解いてみました。

巡回セールスマン問題(TSP)

巡回セールスマン問題とは、セールスマンが都市を訪問する際、全ての都市に1度ずつ訪問する最短経路を求める問題です。

都市の数を $N$とすると解の候補となる経路の数は $N!$通りあり、 $N$が増えると組み合わせの数は爆発的に増えてしまうため、全探索で最適解を求めるのは不可能になってしまいます。

この問題をQUBO形式で表現し、SBMで解いてみようと思います。

目的関数

TSPのQUBO表現での目的関数を作成します。詳しい説明はこちらのページを参照してください。

今回用いる方法では、「何番目に」「どの都市に」訪問するかを1つのQUBO変数とします。


この続きは Fixstars Tech Blog /proc/cpuinfo で読むことができます。