「巡回セールスマン問題」を解くアルゴリズムを可視化したムービー

by Gaël Sacré いくつもの都市を移動するセールスマンが、すべての都市を最も効率よく(最小の移動コストで)移動できる方法を求める問題を「巡回セールスマン問題」といいますが、その解き方をビジュアル化したムービーがYouTubeで公開されています。 Traveling Salesman Problem Visualization - YouTube たとえば8つの都市があるとき、これを結ぶルートは5040通りが考えられます。 解法の一つが「欲張り法(Greedy Algorithm)」という、1つの都市から常に最寄りの都市へ移動しようと考える方法。 「最適」ではないものの、最適に近い答えを導き出してくれます。 ここで、組み合わせて使うのが「2-opt法」という方法。かなり単純なアルゴリズムで、2辺を繋ぎ直していきます。このとき、ルートに重なりがあると解消して新しいルートを作ります。

[stet]

"今回はわずかに最適化することができ、1万4167kmまで減らせました"って翻訳おかしいだろ。「しかし、実際には1万4167kmというより良いルートがあります」じゃないのか

[sousou_mo]

こんなにセールスしたら死ぬ。お家に帰らせて。

[p-2yan]

図だけみてなんか覚えがあると思ったら、点を数字順につないでいくと絵が完成するクイズ？みたいなやつだった。

[moriconomori]

ほほー

[yetch]

観よう

[spacefrontier]

見出しに「解く」とあったので、厳密解を求める効率の良い方法が見つかったのかと思ったら、従来のアルゴリズムの最適化過程の動画化か。結構面白い。

[tanakh]

やっぱり焼きなましなんだよなあ。しかしこれだとただのメタヒューリスティックの話でセールスマン問題じゃなくてもいい感(´･_･`)

[hpptms]

可視化ってやっぱいいよね

[negima1976]

おもしろい！

[John_Kawanishi]

pic.twitter.com/1mL4AimcIo

[kenzy_n]

フーテンのサラリーマン