今年は猛暑ですね。どこかでは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を超えると完全に収束してしまうような微妙なデキでした。

ソーシャルブックマーク

はてな Livedoor del.icio.us

関連してそうな記事

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

• [php] PHPMailer で SPF対応メールの送信。
• twitter – twitter拡張検索β
• メール受信時にスクリプトを起動する
• twitter – 2chnewsbot2
• IEEE-754形式のバイナリをPHPのfloatに変換する

タグ

GA, php, ポケモンスタンプラリー, 遺伝的アルゴリズム

トラックバックURL

コメント

コメントをどうぞ

お名前

メールアドレス (非公開)

ホームページ(非公開)

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