前に書いた膜アルゴリズムのブログ
で取り上げた巡回セールスマン問題に関するアルゴリズムアニメーションを作りました。貪欲算法で解くと失敗する様子がわかります。
この動画では他にも、頂点(都市)を少し動かしただけで解(巡回路)がガラッと変わる様子も示しています。巡回セールスマン問題の複雑さを感じていただけると幸いです。
次にしらみつぶし(全数探索)法で問題の大きさが大きくなるとどのくらい計算時間がかかるようになるか体感できる動画をあげました。
問題のサイズ(頂点の数)が一つ増えるごとに計算時間は何倍にも長くなります。それと前のブログで紹介した膜アルゴリズムによる近似計算が速いことも見て取れると思います。一つ注意したいのは、アルゴリズムの計算時間評価をする時、実際に動かして何秒かかったというナイーブな方法は論外で、きちんと理論的に定まった手法があるということです。詳しくは教科書、参考書を参照ください。この動画はあくまで参考です。
