大富豪家2.0の日記全体に公開

2007年03月22日
11:16
 TSP Art
ドット絵の点で巡回セールスマン問題を解くらしい。なんかすごい!
http://www.cgl.uwaterloo.ca/~csk/projects/tsp/
http://www.oberlin.edu/math/faculty/bosch/tspart-page.html

 

コメント    

2007年03月22日
11:37
しゅんすけ
ええっと,ちょっと読んだ感じだと違いそうな...

基本的には,TSP を使った Art の話で,(少なくとも前者に関しては)half-toning をするのに TSP を使おう,っという話のようです.
2007年03月22日
11:45
しゅんすけ
(理屈としては) TSP の(近似)解を線として平面上に描くと,都市(ノード)が密なところでは経路(エッジ)も密になり,都市が疎なところでは経路も疎になるということを利用しているようです.

そこで,元の絵の(色の)濃いところには都市をたくさん配置したような TSP を準備し,それについてソルバを利用して近似解を出力した結果をアートとして鑑賞しようということだそうです.

ここで使われているソルバ(Concorde TSP Solver)の出力する近似解は,経路が重ならない(線が交差しない)のがミソで,与えられた絵を一本の線で表現した絵に変換しちゃえる,っというのがおもしろいようです.
2007年03月22日
12:13
大富豪家2.0
えっとそういう意味だと思ってましたが書き方が悪かったですね。ドット絵のデータに対して解くと言うべきでした。
絵を描くためには真面目にTSPを解く必要は全然なくて局所的な解もどきを並べていけばいいんでしょうね。
2007年03月22日
16:47
しゅんすけ
あ,なるほど,言われて見ればそのような書き方になっていますね(笑
#TSP を解く,っというキーワードに無駄に反応してしまったようです