前回の話題のヒント

書いている時間がないのでヒントを

1. 巡回セールスマン問題は対称群を引数に持つコスト関数の最小化問題とみなせる。
2. 対称群は隣同士の互換から生成できる。

という事実をアニーリングに適用すると得られる。

ただし、スケーリングに関しての収束性のよさは不明。 すこし調べた感じでは、誰もこの方法をやっていなかった*1。

改善方法としては、互換全体を元とするということも考えられる。 収束が若干早くなる可能性がある。

もちろん巡回セールスマン問題は、この上なくよく考察されている問題の一つなので、 ほかにもいろいろな解法や準解法がある。 とくに、近似アルゴリズムは考えておくべき。

*1:やっぱり、スケーリングに対する収束速度が悪いのかな？