トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

2016.7.18 名古屋市営地下鉄最小距離完乗

これは何ですか

ある路線網において、「その路線網を通り、必ず全区間を1回以上通って出発駅まで戻ってくる」ことを考える。この移動距離が最小となる通り方を求める問題は中国人郵便配達問題と呼ばれる。これを名古屋市営地下鉄で実践したものである。

名古屋市営地下鉄の最小距離完乗の方法。太線の区間は2回、細線の区間は1回乗ればよい。←名古屋市営地下鉄の最小距離完乗の方法。太線の区間は2回、細線の区間は1回乗ればよい。

旅行記

こちらをご覧ください。

名古屋市営地下鉄最小距離完乗 - SlideShare(2016.7.23の勉強会「わんくま同盟 名古屋勉強会 #39」におけるライトニングトーク資料)

計算方法(ダイジェスト)

Maraigueのメモ倉庫 - 名古屋市営地下鉄を最小距離の乗車で「乗りつくして出発駅に戻る」

計算方法(詳細 & C++での実装。ソースコードあり)

Boost.GraphでJR全線乗り尽くしプランを立てる - SlideShare(2014.7.12の勉強会「プログラミング生放送+CLR/H+Sapporo.cpp 勉強会@札幌」における発表資料)