祇園祭の山鉾の最適巡回経路

MikuHatsune2013-07-15

男「今日の浴衣…きれいだよ」
女「キャッ抱いてッ」
 
とかいうやり取りにイラッ☆と来ているわけでは決してありません。ありません。
大事な事なので二回言いました。
 
祇園祭は日本の祭りのなかでもトップクラスの有名っぷりで、今もオレがプログラミングしている間に三条〜四条ではカップルが闊歩している。
そこでは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