今回は膜アルゴリズムを使い巡回セールスマン問題を解きます。 巡回セールスマン問題は、都市がいくつか(nとします)あり、それらを全てちょうど一回ずつ訪れて出発都市に戻る、距離が最短の経路を見つける問題です。詳しいことは例によってWikipediaにお任せしましょう。巡回セールスマン問題の解はn都市からなる系列です。出発都市は固定してよく、距離は幾何学的距離とすれば逆に回っても距離は同じなので、可能な解の候補は(n-1)!/2となります。!は階乗で、3!=6, 4!=24, 5!=120, 6!=720, とnが大きくなるとすごい勢いで大きくなります。だから可能な解を全部調べて・・・というやり方は…
ja.wikipedia.org