男「今日の浴衣…きれいだよ」
女「ｷｬｯ抱いてｯ」
とかいうやり取りにイラッ☆と来ているわけでは決してありません。ありません。
大事な事なので二回言いました。
祇園祭は日本の祭りのなかでもトップクラスの有名っぷりで、今もオレがプログラミングしている間に三条〜四条ではカップルが闊歩している。
そこでは32の山鉾(大船鉾はあったりなかったりで除外した。自分で見に行けって?ううううるせー)が三条〜四条の各所に配置されている。これを見たり露店でたこやきを買ってカップルでふ〜ふ〜するのが通例となっている。
がしかし、ここでできる男は
男「山鉾をすべて見て回ろうっていう問題は、セールスマン巡回問題に帰着する。32のポイントを回るだけなら計算量も大したことないし、簡単に解けるぜ…」
女「ｷｬｯ抱いてｯ」
という展開を夢見て取り組む。
こちらから、32の山鉾についての kml ファイルをダウンロードする。
適当なテキストエディタで kml ファイルを開き、Googleマップ KML/CSV相互変換を用いて適当に txt にする。
めんどくさい人は一番下のデータセット。
Rでセールスマン巡回問題を参考に、TSPをやる。
TSP パッケージでできる。
本当はGoogle map と連携させたかったけど、ubuntu が悪いのか R 3.0.1 が悪いのか使えなかったので保留。
hoko <- read.csv("clipboard") library(TSP) tsp0 <- TSP(dist(hoko[, c("lat", "lng")])) # 手法をすべてやってみる。 m0 <- c("nearest_insertion", "cheapest_insertion", "farthest_insertion", "arbitrary_insertion", "nn", "repetitive_nn", "2-opt") tours <- lapply(m0, FUN=function(m) solve_TSP(tsp0, method=m)) names(tours) <- m0 tour_length <- c(sapply(tours, FUN=attr, "tour_length")) minlen <- sort(tour_length)[1] # 距離が最小のものだけプロットすることにしよう。 gionhoko <- sapply(tours, as.integer) root <- c(gionhoko[, names(minlen)], gionhoko[1, names(minlen)]) plot(hoko[root, c("lat", "lng")], type="l", main=names(minlen), lwd=3) text(hoko[head(root, -1L), c("lat", "lng")], as.character(hoko[head(root, -1L), "hoko"]), col=2)
三条や四条は格子状になっているので、格子的移動しかできないような制限的な何かをいれたい。
実はこんなことをしなくても、Google map 先生は既にTSPを解くためのアプリを作っている。
しかも道を守ったタイプで計算できる。
OptiMap - Fastest Roundtrip Solver に経度緯度をぶち込めば、それっぽい最適巡回経路を解いてくれる。
しかし、これは100ヶ所までしか対応していないので、それ以上になったら R とか Python とかでがんばるしかない。
hoko lat lng 長刀鉾 135.761032 35.003689 函谷鉾 135.758926 35.003696 菊水鉾 135.758102 35.004002 月鉾 135.757095 35.003662 鶏鉾 135.758163 35.002663 放下鉾 135.756668 35.004005 岩戸山 135.756668 35.000488 船鉾 135.756699 35.001404 山伏山 135.758102 35.005836 孟宗山 135.759628 35.004128 太子山 135.753708 35.00116 郭巨山 135.755997 35.003716 保昌山 135.761078 34.999859 油天神山 135.753647 35.001587 四条傘鉾 135.754379 35.003662 蟷螂山 135.755096 35.003944 伯牙山 135.755997 35.00246 木賊山 135.754196 35.001263 霰天神山 135.75766 35.004913 白楽天山 135.758133 35.001369 芦刈山 135.754761 35.002449 占出山 135.758865 35.004929 綾傘鉾 135.757614 35.002476 北観音山 135.756683 35.006569 南観音山 135.756683 35.005486 橋弁慶山 135.758865 35.006138 役行者山 135.758072 35.009449 鯉山 135.758118 35.00658 八幡山 135.756668 35.007511 鈴鹿山 135.759552 35.009647 黒主山 135.758102 35.007713 浄妙山 135.759109 35.007298
