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

2013年08月12日 0

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

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

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

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

staticmap01

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

staticmap02

    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
関連してそうな記事
同じカテゴリーの別の記事
タグ
, , ,
トラックバックURL
コメント

コメントをどうぞ

*反映されるまでに時間がかかることがあります。
*メールアドレスはアバターの使用に使います。