ボルツマンマシンによる巡回セールスマン問題シミュレーティッド・アニーリンによる巡回セールスマン問題への適用 羽鳥研究室 45528 笹子昌治 45548 中村恵吾 1. はじめに 1.1 TSP TSPとはTraveling Salesman Problem（巡回セールスマン問題）の略で、複数の都市をそれぞれただ一度だけ訪問して出発点の都市に戻る巡回路のなかで、最短となる経路を求めるという問題である。最も単純な方法として、考えうる全ての巡回路を調べ、その中から移動距離が最小になるものを選ぶ列挙法(力ずく法)がある。この方法で調べると確実に最小解を求めることができるが、都市の数が多くなるにつれ、考えうる巡回路の数は爆発的に増加し、都市数N = 5のとき12通り、N = 10のとき181,440通り、N = 15のとき43,589,145,600通り、N = 20のとき243京2902兆81億7664万通りとなる。一般に、都市数Nに
