2014年08月
2014年08月12日
はじめに
この内容は、7月12日の7/12 プログラミング生放送 + CLR/H + Sapporo.cpp 勉強会＠札幌の参加記録と、そこで発表したものの補遺（完全版）です。
この日の発表の時点では、「最小乗車距離でJR線全線を乗り尽くして出発駅まで戻る」問題をJR北海道を対象として解くことはできたものの、JR全線を対象に解くのは問題の大きさゆえ不可能でした。そのため改良版の制作に取り組んでおり、このたび完成した（おそらく）ので発表するものです。
勉強会について
プログラミング生放送という、ニコ生で配信される勉強会である。札幌では2年前に開催された以来の開催で、今回もCLR/Hならびにsapporo.cppとの共催となった。私はsapporo.cppの一員として参戦した。
Twitterまとめはこちら（私のまとめではありません）
- プログラミング生放送+CLR/H+Sapporo.cpp 勉強会＠札幌 ユビキタス協創広場 U-cala #pronamaclrhsapporocpp #pronama - Togetterまとめ
- 暮井 慧タクシー #プロ生ちゃん - Togetterまとめ
また、札幌で痛タクシーを走らせている長栄交通様の協力で、プロ生ちゃん（暮井慧）タクシーが実現することに。
内容
ソースコードはこちらに公開しています。maraigue/cpp-chinese-postman (github)
詳細、ならびにアルゴリズムの概要はこちらのスライドに掲載しています。
問題設定の要約は以下の通りになります。「中国人郵便配達問題」という名前が付いています。
- 「JR線全線を乗り尽くして出発駅まで戻る」ことを、最短の乗車距離で行う。
- JR以外の交通機関は使わないものとする。
- 「札幌-白石間の函館本線・千歳線並走区間」のように、路線が分かれていても営業上同一となる区間については、同一の路線と扱う（どれか1路線乗ればよい）とする。ただし、ミニ新幹線を除く新幹線に限っては別路線と扱う。
