2013年08月12日
今年は猛暑ですね。どこかでは40度を超えたとかなんとか。
ってなわけで、巡回セールスマン問題的な感じで
ポケモンスタンプラリー2013の最短ルートを求めてみようと思いました。ビバ効率厨ですね。
まぁ個人的なあれですけど、windowsパソコンが壊れたのでmac book airを買ったのです。
その設定の一環でプログラムでもしてみようかと。
結論からいうと厳密解ではありません。近似解ですかね。
遺伝的アルゴリズムとかいうのを使いました。
ここから本題です。
そもそもポケモンスタンプラリー。
24都市を回るとコンプリートで、スタンプ受付時間は9時半から16時まで。
JRのサイトにある画像を見るとこんな感じですけど

実際並べるとこんなんですね。(大船って結構遠いよね)

八王子、大船、千葉と結構えげつない感じですけど
一日でフルコンはできるんでしょうか。
という思いで始めた最短ルート検索。
できるだけJR縛りで探索してみました。(バスも混じってます)
巡回セールスマンなので、1と24は繋がってると考えてください。
(巡回なので)スタート位置は1でも10でもどこでもよいです。

- 1: 八王子->立川
- [JR中央線快速・東京行] (16min)
- 2: 立川->吉祥寺
- [JR中央線快速・東京行] (25min)
- 3: 吉祥寺->渋谷
- [京王井の頭線急行] (17min)
- 4: 渋谷->四ツ谷
- [JR山手線外回り・新宿・池袋方面, JR総武線・千葉行] (14min)
- 5: 四ツ谷->秋葉原
- [JR総武線・千葉行] (10min)
- 6: 秋葉原->錦糸町
- [JR京浜東北・根岸線・大船行, JR横須賀・総武線快速・千葉行] (21min)
- 7: 錦糸町->津田沼
- [JR総武線] (28min)
- 8: 津田沼->千葉
- [JR横須賀・総武線快速] (11min)
- 9: 千葉->吉川美南
- [JR横須賀・総武線快速・久里浜行, JR総武線・三鷹行, JR武蔵野線・府中本町行] (55min)
- 10: 吉川美南->武蔵浦和
- [JR武蔵野線・府中本町行] (22min)
- 11: 武蔵浦和->川口
- [JR武蔵野線・東京行, JR京浜東北線快速・蒲田行] (18min)
- 12: 川口->赤羽
- [JR京浜東北・根岸線快速・磯子行] (3min)
- 13: 赤羽->池袋
- [JR京浜東北線・蒲田行, JR山手線内回り・池袋・新宿方面] (23min)
- 14: 池袋->日暮里
- [JR山手線外回り・上野・東京方面] (12min)
- 15: 日暮里->北千住
- [JR常磐線快速・取手行] (7min)
- 16: 北千住->東京
- [東京メトロ日比谷線・中目黒行, 徒歩, JR山手線外回り・東京・品川方面] (22min)
- 17: 東京->浜松町
- [JR京浜東北線・蒲田行] (6min)
- 18: 浜松町->品川
- [JR山手線外回り・品川・渋谷方面] (5min)
- 19: 品川->蒲田
- [JR京浜東北線] (9min)
- 20: 蒲田->羽田空港第2ビル
- [京急バス・羽田空港第1ターミナル行, 東京モノレール区間快速] (43min)
- 21: 羽田空港第2ビル->横浜
- [東京モノレール・浜松町行, 連絡バス] (51min)
- 22: 横浜->桜木町
- [JR京浜東北・根岸線・大船行] (3min)
- 23: 桜木町->大船
- [JR京浜東北・根岸線快速・大宮行, JR東海道本線・熱海行] (21min)
- 24: 大船->八王子
- [JR東海道本線・東京行, JR横浜線快速] (74min)
スタンプ押す時間も考慮していないのにトータル8時間ちょいとなりました。
たぶん(6〜7時間で回れる)もっと最短があるんでしょうね。
個体数50、世代数200、40%の確率で淘汰→同数を単純な一点交叉、30%を2-opt、20%を突然変異(ランダム)でやりました。
言語はphpです。
今回のアルゴリズムだと世代も50を超えると完全に収束してしまうような微妙なデキでした。
ソーシャルブックマーク
はてな
Livedoor
del.icio.us
関連してそうな記事
同じカテゴリーの別の記事
タグ
GA,
php,
ポケモンスタンプラリー,
遺伝的アルゴリズム
トラックバックURL
コメント