はじめに #
東芝シミュレーテッド分岐マシンによる最大カット問題のベンチマークの記事では、最大カット問題をSBMで実行してみました。
今回は、組み合わせ最適化問題の具体例として取り上げられることの多い「巡回セールスマン問題(TSP)」を、SBMで解いてみました。
巡回セールスマン問題(TSP) #
巡回セールスマン問題とは、セールスマンが都市を訪問する際、全ての都市に1度ずつ訪問する最短経路を求める問題です。
都市の数を \(N\) とすると解の候補となる経路の数は \(N!\) 通りあり、 \(N\) が増えると組み合わせの数は爆発的に増えてしまうため、全探索で最適解を求めるのは不可能になってしまいます。
この問題をQUBO形式で表現し、SBMで解いてみようと思います。
目的関数 #
TSPのQUBO表現での目的関数を作成します。詳しい説明はこちらのページを参照してください。
今回用いる方法では、「何番目に」「どの都市に」訪問するかを1つのQUBO変数とします。
この続きは Fixstars Tech Blog /proc/cpuinfo で読むことができます。