組合せ最適化問題の代表的なものとして、巡回セールスマン問題があります。
巡回セールスマン問題
ある会社のセールスマンがいます。このセールスマンは受け持ちの都市をすべて訪問して、
仕事が終ったら戻ってこなければいけません。 |
この問題をすべての都市間の距離を単純に比較して解くと、 ５都市の場合１２とおりで解けそうですが、 １０都市になると、その組合せは１８１４４０通りにもなります。
ボルツマンマシンを用いると、最適解が得られないかもしれませんが、 比較的満足できる解を求めることができます。
この問題では都市名と訪問する順序を左の表のようにして表します。 表を縦方向にみれば、「１度に訪問できる都市は１つだけ」という条件を、 表を横方向にみれば、「同じ都市には２度行けない」という条件を表しています。
そして、表の中に「１」が都市数しかないことは、「すべての都市を訪問する」
という条件を表すことになりますね。
この問題を解くとき、いままでのように単純にネットワークのエネルギーを最小化するだけでは、 この問題の条件を満たすことができません。 どのようなエネルギー関数を用意すればよいのでしょうか？
