3.2.3 巡回セールスマン問題とは?
組合せ最適化問題の代表的なものとして、巡回セールスマン問題があります。

 

巡回セールスマン問題

ある会社のセールスマンがいます。このセールスマンは受け持ちの都市をすべて訪問して、 仕事が終ったら戻ってこなければいけません。
同じ都市を2度訪問せずに、 最短距離ですべての都市をまわる経路を求めなさい。


この問題をすべての都市間の距離を単純に比較して解くと、 5都市の場合12とおりで解けそうですが、 10都市になると、その組合せは181440通りにもなります。

ボルツマンマシンを用いると、最適解が得られないかもしれませんが、 比較的満足できる解を求めることができます。

この問題では都市名と訪問する順序を左の表のようにして表します。 表を縦方向にみれば、「1度に訪問できる都市は1つだけ」という条件を、 表を横方向にみれば、「同じ都市には2度行けない」という条件を表しています。

そして、表の中に「1」が都市数しかないことは、「すべての都市を訪問する」 という条件を表すことになりますね。

この問題を解くとき、いままでのように単純にネットワークのエネルギーを最小化するだけでは、 この問題の条件を満たすことができません。 どのようなエネルギー関数を用意すればよいのでしょうか?



Copyright(c) Iwata-Lab. N.I.T. All rights reserved.