巡回セールスマン問題に興味を持つ

継続してブログを書くといいつつ、２回めの記事が２ヶ月後となってしまいました。論文とかもあったので許してください。

巡回セールスマン問題

巡回セールスマン問題とは、複数の点とその距離が与えられたとき、すべての点を通りつつ、最初の点に戻ってくる総移動距離を最小にする最適化問題のことです。(巡回セールスマン問題 - Wikipedia) ようするに、以下の図のような６点が与えられた時に、移動距離が最小となるような経路を探せという問題ですね。この例だとこの経路が一番移動距離が短いようです。

この問題は、点の数が多くなるほど、総当りで解くのが困難になります。なぜならば、nの点に対する経路の組み合わせはn!通りとなるからです。以下の表にnとn!の関係を表してみたところ、点の数が１５の時点で１兆パターンを超えてしまっています。 このことを考えると５０個や１００個の点の経路を総当りで解くのは不可能ですね。そのせいかはわからないですが、この巡回セールスマン問題はNP困難とかいうとてもむずかしい問題のひとつとなっています。

n	n!
1	1
5	120
10	3628800
15	1307674368000
20	2432902008176640000

巡回セールスマン問題に興味を持ったきっかけ

私が、巡回セールスマン問題に興味を持ったきっかけは、「理系が恋をしたので証明してみた」という漫画を読んだからです。漫画では、遊園地のアトラクションを効率よく回るルートを調べる方法として、巡回セールスマン問題が登場していました。

巡回セールスマン問題を応用したアプリの構想

これを見た時に、自分の周りでも巡回セールスマン問題を応用できるのではないかと考えたところ、あるひとつの解を思いつきました。 そう、聖地巡りです。 というわけで、アニメ聖地の緯度経度情報から、最適な聖地巡りのルートを算出するアプリケーションを作っていきたいなと思います。

おわりに

まだ概要しかきまっていないため、いつになるかはわかりませんが、開発が進めば記事として紹介していきます。 おそらく、まだまだ進まないので、当分の記事は、今まで作ってきたアプリの紹介や、いま興味を持っているものなどになりそうです。 ではでは