3.2.4 巡回セールスマン問題のエネルギー関数
巡回セールスマン問題の条件を満たすエネルギー関数について考えてみましょう。 表のそれぞれのマス目をあらわす時、都市をX、順番をiとしてxXi と書くことにします。

「同じ都市に2度いかない」という条件は、 同じ行に「1」が1つだけ存在するので式で表すと


となります。これを各行について見ていけばよいわけです。 同様に「同時に2都市にはいけない」という条件は、 同じ列に「1」が1つだけ存在するということなので、

とあらわすことができます。

各行、各列に「1」は1つずつしかないので、 この条件を満たす時「1」は都市数分しか存在しないということになります。 さて、もう1つの距離についての条件はどのようにあらわされるでしょうか?

ある1つの経路の距離は次のように表現できます。

これは、xXiについて見た時、その前後に「1」があれば、 都市間の距離を加えていくことになります。

以上の式より、巡回セールスマン問題のエネルギー関数は以下のように与えられることが分かります。

この式を展開しホップフィールドネットワークのエネルギー関数の式とと比較することにより、 結合荷重としきい値を求めます。 あとは、今まで通りにネットワークを動作させればネットワークは自然にエネルギーが小さくなる方向へ変化を続けるわけです。



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