ポケモンスタンプラリーの最短ルートを模索してみた

trash-area.com ≫ blog ≫ プログラミング ≫ php ≫ ポケモンスタンプラリーの最短ルートを模索してみた

2013年08月12日 0

今年は猛暑ですね。どこかでは40度を超えたとかなんとか。
ってなわけで、巡回セールスマン問題的な感じで
ポケモンスタンプラリー2013の最短ルートを求めてみようと思いました。ビバ効率厨ですね。

まぁ個人的なあれですけど、windowsパソコンが壊れたのでmac book airを買ったのです。
その設定の一環でプログラムでもしてみようかと。
結論からいうと厳密解ではありません。近似解ですかね。
遺伝的アルゴリズムとかいうのを使いました。

ここから本題です。
そもそもポケモンスタンプラリー。
24都市を回るとコンプリートで、スタンプ受付時間は9時半から16時まで。
ＪＲのサイトにある画像を見るとこんな感じですけど

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

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

1: 八王子->立川

[ＪＲ中央線快速・東京行] (16min)

2: 立川->吉祥寺

[ＪＲ中央線快速・東京行] (25min)

3: 吉祥寺->渋谷

[京王井の頭線急行] (17min)

4: 渋谷->四ツ谷

[ＪＲ山手線外回り・新宿・池袋方面, ＪＲ総武線・千葉行] (14min)

5: 四ツ谷->秋葉原

[ＪＲ総武線・千葉行] (10min)

6: 秋葉原->錦糸町

[ＪＲ京浜東北・根岸線・大船行, ＪＲ横須賀・総武線快速・千葉行] (21min)

7: 錦糸町->津田沼

[ＪＲ総武線] (28min)

8: 津田沼->千葉

[ＪＲ横須賀・総武線快速] (11min)

9: 千葉->吉川美南

[ＪＲ横須賀・総武線快速・久里浜行, ＪＲ総武線・三鷹行, ＪＲ武蔵野線・府中本町行] (55min)

10: 吉川美南->武蔵浦和

[ＪＲ武蔵野線・府中本町行] (22min)

11: 武蔵浦和->川口

[ＪＲ武蔵野線・東京行, ＪＲ京浜東北線快速・蒲田行] (18min)

12: 川口->赤羽

[ＪＲ京浜東北・根岸線快速・磯子行] (3min)

13: 赤羽->池袋

[ＪＲ京浜東北線・蒲田行, ＪＲ山手線内回り・池袋・新宿方面] (23min)

14: 池袋->日暮里

[ＪＲ山手線外回り・上野・東京方面] (12min)

15: 日暮里->北千住

[ＪＲ常磐線快速・取手行] (7min)

16: 北千住->東京

[東京メトロ日比谷線・中目黒行, 徒歩, ＪＲ山手線外回り・東京・品川方面] (22min)

17: 東京->浜松町

[ＪＲ京浜東北線・蒲田行] (6min)

18: 浜松町->品川

[ＪＲ山手線外回り・品川・渋谷方面] (5min)

19: 品川->蒲田

[ＪＲ京浜東北線] (9min)

20: 蒲田->羽田空港第２ビル

[京急バス・羽田空港第１ターミナル行, 東京モノレール区間快速] (43min)

21: 羽田空港第２ビル->横浜

[東京モノレール・浜松町行, 連絡バス] (51min)

22: 横浜->桜木町

[ＪＲ京浜東北・根岸線・大船行] (3min)

23: 桜木町->大船

[ＪＲ京浜東北・根岸線快速・大宮行, ＪＲ東海道本線・熱海行] (21min)

24: 大船->八王子

[ＪＲ東海道本線・東京行, ＪＲ横浜線快速] (74min)

スタンプ押す時間も考慮していないのにトータル8時間ちょいとなりました。
たぶん（6〜7時間で回れる）もっと最短があるんでしょうね。

個体数50、世代数200、40%の確率で淘汰→同数を単純な一点交叉、30%を2-opt、20%を突然変異(ランダム)でやりました。
言語はphpです。
今回のアルゴリズムだと世代も50を超えると完全に収束してしまうような微妙なデキでした。

ポケモンスタンプラリーの最短ルートを模索してみた

ソーシャルブックマーク

関連してそうな記事

同じカテゴリーの別の記事

タグ

トラックバックURL

コメント

人気の記事

PR

最近の記事

ゴミ置き場

使用中のプラグイン

カテゴリー

月別アーカイブ

タグ

つぶやき (twitter)