hirax.net::Keywords::「TSP」のブログ

■巡回セールスマン問題の答が描く「一筆書きアート」　

　一年ほど前、「数百個の数字をエンピツで結んでいくアニメーション」を作ってみました（”点と点を結んで行くと浮かびあがる”スティーブ・ジョブス）。

　この"Connecting the dots"な一筆書きラクガキ…「散らばっているたくさんの点たちを結んでいく絵」は、ペン先が何回も・何度も同じような場所を往復しています。つまり、右往左往が繰り返される、あまり効率的でない「描き方」です。

　もしも、たくさんの点が散らばっている時、それらの点を「一番効率的に」「最も最短で描く」にはどうしたら良いでしょう？…ということを考え始めると、それは「巡回セールスマン問題」という問題に変わります。

　巡回セールスマン問題（じゅんかいセールスマンもんだい、Traveling Salesman Problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。

巡回セールスマン問題

　"TSP ART"（＝巡回セールスマン問題的アート）と画像検索すると、数多くの街を廻るセールスマンのように、たくさんの点群を結ぶという作業を、最も効率的に行った「たくさんの一筆書き」アートを見ることができます。画像の「濃い部分」に「”たくさんの点”」がばらまかれているようにした上で、それらの点を最も効率的に結んでいくのがTSP Artです（参考：TSP Art）。

　この巡回セールスマン問題的アート（TSP Art）を描くのは結構大変です。何しろ、たとえば16階調で256×256の絵を描こうとすると、16×256×256…つまり1万048千576の点を「辺り一帯」にばらまいて、その1万048千576もの点を最も効率的に移動するにはどうしたら良いか？という超大規模な巡回セールスマン問題を解かなければならないからです。

　しかし、巡回セールスマン問題的「一筆書きアート」は大変でありつつ、とても素朴で魅力的です。こんなラクガキ、何だか少し描いてみたくなりませんか？