☆2008/4/14版　JR最長経路問題･厳密解

←旅/記事目次　　訪問:

 佐藤和夫>　旅>

☆2008/4/14版　JR最長経路問題･厳密解

はじめに

　それは、つねに新しい経路(ルート)をたどりながら、稚内駅から若井駅までの総延長14507.0kmを、一筆書きで乗りつくす旅です。　数的解析の結果分かったことですが、行き止まりの路線を除きすべてのJRの乗り換え駅をたどる旅でもありました。　この記事は、その経路をどのようにして求めたかを説明するものです。
　14507.0kmは地球半周よりも更に約2800km以上長くて、日本から地球の反対側のブラジルを越えて、大西洋のど真ん中までたどり着ける距離に相当します。　日本は広いですね。　また、JRの四分の三を乗り尽くします。　我が駅、平城山(ならやま)駅も通過することになっていたので、安心しました。

1.　JRの旅へのお誘い

　途中下車をせずに、JRの異なる経路を次々と乗り継いで旅をしたら、一筆書き出来る最長経路の乗車距離は何キロメートルぐらいになるのでしょうか？　いったい何駅から乗車し、最後にどこで下車することになるのでしょうか？　また、途中にどんな情景が待ち受けているのでしょうか？　これからご案内します。
　この旅は結論から言うと、稚内駅から若井駅までの、乗車距離合計14507.0 営業キロ[参照1.1]を、途中下車することなく乗り続けることになります。　最長経路は新幹線が出来たり、新駅が出来たり、ローカル線が廃止されるたびに変化します。　新駅が出来たらなぜ最長経路は変わるのだろう？と思われるかもしれませんが、新駅が出来るとそれにより新しい経路が出来上がるので、総延長距離は増える可能性が高いのです。

タグ: #佐藤和夫ようこそ #JR最長経路問題 #JR最長経路問題･厳密解 #JR最長経路の旅 #私鉄､廃線の旅 #JR #最長経路問題 #厳密 #最適解 #鉄道ファン #一筆書き #数的解析 #ルート #計算 #ルート動画 #グラフ #最長経路 #静岡大学 　最近では、東北新幹線が八戸まで延伸されたり、九州新幹線が八代まで暫定開業されていますので、2007年1月号の時刻表を買ってきて計算してみたところ、残念ながら2001年5月に比べ短くなっていました。

2.　JR最長経路問題とは何か

　ここでは、JRの「ある経路は一度だけ通過できる」こととして、ある特定日の一筆書きできる最長経路のルート、その時の乗車距離、発駅、着駅を求めようとします。
　なお、JRには最長片道切符[参照2.1]なるものがありますが、これは「ある駅は一度だけ通過できる」という条件で、一筆書きできる最長経路のルートを求めようとするものです。　これの数的解析はすでに行われています。
　それによると、2000年当時東大大学院生であった葛西隆也は、整数計画法と全探索という数学的に厳密な二つの方法で最長切符の経路（稚内→肥前山口、11､925.9キロ）を求めた。[引用2.1]という記述があります。　
またご本人による説明もWEBに記載されています[参照][参照2.2]

3.　一筆書きJR最長経路はこれだ！

　2007年1月現在の最新の経路は、次の通りです。　今回は新しい計算法をやってみましたが、予想に反して11日間かかりました。　前回せっかく、JR定理1の2006年12月発見のおかげで8日間に計算が短縮されましたが、一歩後退です。

　稚内駅から乗車し若井駅までの総延長で、乗車距離合計14507.0営業キロです。 ここでは、北海道内と、本州および九州とを分けて表示しました。

稚内,竜飛海底,1569.0営業キロ,
(稚内=*宗谷本線=新旭川=*石北本線=東釧路=*根室本線=新得=*根室本線=富良野=*富良野線=旭川=*函館本線=深川=*函館本線=滝川=*函館本線=岩見沢=*室蘭本線=追分=*室蘭本線=沼ノ端=*千歳線=南千歳=*千歳線=白石=*函館本線=桑園=*函館本線=長万部=*函館本線=竜飛海底)

竜飛海底,若井,12938.0営業キロ,
(竜飛海底=*海峡線=青森=*奥羽本線=川部=*五能線=東能代=*奥羽本線=秋田=*秋田新幹線=大曲=*秋田新幹線=盛岡=*東北新幹線=新花巻=*釜石線=花巻=*東北本線=北上=*東北本線=一ノ関=*気仙沼線=前谷地=*仙石線=仙台=*東北本線=小牛田=*東北本線=一ノ関=*東北新幹線=古川=*陸羽東線=新庄=*山形新幹線=天童=*奥羽本線=新庄=*奥羽本線=横手=*北上線=北上=*東北新幹線=新花巻=*釜石線=盛岡=*田沢湖線=大曲=*奥羽本線=秋田=*羽越本線=余目=*羽越本線=坂町=*米坂線=米沢=*奥羽本線=福島=*山形新幹線=米沢=*奥羽本線=山形=*山形新幹線=天童=*奥羽本線=南出羽=*奥羽本線=羽前千歳=*仙山線=仙台=*東北新幹線=福島=*東北新幹線=郡山=*東北本線=福島=*東北本線=岩沼=*常磐線=いわき=*常磐線=水戸=*水郡線=安積永盛=*東北本線=新白河=*東北本線=黒磯=*東北本線=那須塩原=*東北本線=宇都宮=*東北本線=自治医大=*東北本線=小山=*東北新幹線=宇都宮=*東北新幹線=那須塩原=*東北新幹線=新白河=*東北新幹線=郡山=*磐越西線=会津若松=*磐越西線=喜多方=*磐越西線=新津=*羽越本線=新発田=*白新線=新潟=*信越本線=新津=*信越本線=東三条=*信越本線=長岡=*上越新幹線=燕三条=*上越新幹線=新潟=*越後線=吉田=*越後線=柏崎=*信越本線=宮内=*信越本線=長岡=*上越新幹線=浦佐=*上越線=越後湯沢=*上越新幹線=高崎=*上越新幹線=大宮=*川越線=高麗川=*八高線=倉賀野=*高崎線=大宮=*東北新幹線=上野=*山手線=秋葉原=*山手線=神田=*中央本線=御茶ノ水=*中央本線=代々木=*山手線=大崎=*山手線=品川=*横須賀線=鶴見=*鶴見線=尻手=*南武線=府中本町=*武蔵野線=西国分寺=*武蔵野線=武蔵浦和=*埼京線=大宮=*京浜東北線=南浦和=*武蔵野線=武蔵浦和=*埼京線=北赤羽=*埼京線=赤羽=*京浜東北線=田端=*山手線=池袋=*山手線=新宿=*中央本線=西国分寺=*中央本線=立川=*青梅線=拝島=*八高線=八王子=*中央本線=甲府=*見延線=富士=*東海道本線=静岡=*東海道新幹線=豊橋=*東海道新幹線=三河安城=*東海道本線=豊橋=*東海道本線=静岡=*東海道新幹線=三島=*東海道本線=沼津=*御殿場線=国府津=*東海道本線=小田原=*東海道新幹線=三島=*東海道本線=小田原=*東海道新幹線=新横浜=*横浜線=橋本=*相模線=茅ヶ崎=*東海道本線=大船=*根岸線=横浜=*東海道本線=東神奈川=*横浜線=新横浜=*東海道新幹線=東京=*京葉線=市川塩浜=*京葉線=西船橋=*武蔵野線=新松戸=*武蔵野線=三郷=*武蔵野線=南浦和=*京浜東北線=赤羽=*東北本線=日暮里=*山手線=上野=*東北新幹線=東京=*総武線=錦糸町=*総武本線=西船橋=*武蔵野線=南船橋=*京葉線=蘇我=*外房線=大網=*内房線=蘇我=*内房線=千葉=*総武本線=佐倉=*総武本線=成東=*総武本線=成田=*総武本線=我孫子=*常磐線=友部=*水戸線=小山=*東北新幹線=大宮=*東北本線=小山=*両毛線=新前橋=*上越線=越後湯沢=*上越新幹線=浦佐=*上越線=小出=*上越線=越後川口=*飯山線=豊野=*信越本線=直江津=*北陸本線=糸魚川=*大糸線=松本=*篠ノ井線=長野=*長野新幹線=佐久平=*八ヶ岳高原線=小淵沢=*中央本線=岡谷=*中央本線=辰野=*中央本線=塩尻=*中央本線=多治見=*中央本線=金山=*東海道本線=三河安城=*東海道新幹線=名古屋=*関西本線=桑名=*関西本線=亀山=*紀勢本線=和歌山=*阪和線=天王寺=*大阪環状線=京橋=*片町線=木津=*関西本線=柘植=*草津線=草津=*東海道本線=米原=*北陸本線=近江塩津=*湖西線=山科=*東海道本線=京都=*東海道本線=新大阪=*山陽新幹線=西明石=*山陽本線=尼崎=*JR東西線=京橋=*大阪環状線=大阪=*東海道本線=新大阪=*東海道新幹線=京都=*東海道新幹線=米原=*東海道新幹線=名古屋=*東海道本線=岐阜=*高山本線=美濃太田=*高山本線=富山=*北陸本線=敦賀=*小浜線=綾部=*山陰本線=京都=*奈良線=木津=*関西本線=奈良=*桜井線=高田=*和歌山線=王寺=*関西本線=天王寺=*大阪環状線=大阪=*山陽本線=尼崎=*福知山線=谷川=*加古川線=加古川=*山陽本線=西明石=*山陽新幹線=姫路=*播但線=和田山=*山陰本線=鳥取=*因美線=東津山=*姫新線=姫路=*山陽本線=相生=*山陽本線=東岡山=*赤穂線=相生=*山陽新幹線=岡山=*津山線=津山=*姫新線=新見=*伯備線=総社=*吉備線=岡山=*山陽本線=倉敷=*山陽本線=新倉敷=*山陽新幹線=福山=*福塩線=塩町=*福塩線=備後落合=*芸備線=備中神代=*伯備線=伯耆大山=*山陰本線=宍道=*山陰本線=江津=*三江線=三次=*芸備線=広島=*山陽新幹線=徳山=*山陽新幹線=新山口=*山陽新幹線=厚狭=*山陽本線=新下関=*山陽新幹線=小倉=*鹿児島本線=西小倉=*鹿児島本線=折尾=*鹿児島本線=香椎=*鹿児島本線=吉塚=*篠栗線=長者原=*篠栗線=桂川=*筑豊本線=新飯塚=*後藤寺線=田川後藤寺=*日田彦山線=城野=*日豊本線=大分=*日豊本線=南宮崎=*日豊本線=都城=*えびの高原線=吉松=*肥薩線=隼人=*日豊本線=鹿児島中央=*鹿児島本線=川内=*九州新幹線=新八代=*鹿児島本線=熊本=*阿蘇高原線=大分=*ゆふ高原線=夜明=*ゆふ高原線=久留米=*鹿児島本線=鳥栖=*鹿児島本線=原田=*鹿児島本線=博多=*山陽新幹線=*鹿児島本線=小倉=幡生=*山陽本線=新下関=*山陽新幹線=厚狭=*美祢線=長門市=*山陰本線=益田=*山口線=新山口=*山陽本線=宇部=*山陽本線=小野田=*小野田線=居能=*宇部線=新山口=*山陽本線=徳山=*山陽本線=櫛ヶ浜=*岩徳線=岩国=*山陽本線=広島=*山陽新幹線=三原=*呉線=海田市=*山陽本線=三原=*山陽本線=尾道=*山陽本線=福山=*山陽本線=新倉敷=*山陽新幹線=岡山=*瀬戸大橋線=宇多津=*高徳線=佐古=*徳島線=佃=*土讃線=多度津=*予讃線=若井)

注）
・データはJTB時刻表2008年3月号、2008年3月1日発行に依ります。
・「経路」とは、この時刻表P4〜P22の経路図に表示されたものを指します。　ここでは、実際には物理的に別線であるものが、一つの経路として記入されている例、たとえば横須賀線の大船横浜間がありますが、経路図通りに一つの経路として入力しています。　また。逆に実際には物理的に一つの路線であるものが、二つの経路として記入されている例、たとえば秋田新幹線と田沢湖線がありますが、経路図通りに二つの経路として入力しています。　また、この経路図には、新子安から品川間が横須賀線であり、新子安に停車するかのように表示されていますが、その通りに新子安と品川間を一つの経路として扱っています。　他にも類似の例がありますが、すべて経路図通りに経路を入力しています。
・一部の区間で一つの経路に複数の路線が乗っている場合、たとえば山手線と京浜東北線の日暮里〜品川間がありますが、便宜上片方のみを経路名として使用しました。
・JTB時刻表2001年5月号当時の最長経路は2007/1/14版　JR最長経路問題･厳密解3章をご覧ください 。

>4.　JR最長経路問題の数的解析は大変

5.　JR最長経路問題・残る課題とその解決

・計算結果は、行き止まり経路を除く、通過できるすべての駅を通過しています。　福知山駅は通過していませんが、これは通過できない駅です。　したがって、JR定理1の適用が可能です。
・上では計算に2ヶ月必要だったと書きましたが、JR定理1「若井が必ず着駅だと分かったこと」を執筆の途中で発見したことにより、四国を含めた再計算では、それまで2ヶ月要していたものが、1ヶ月弱になりました。　更に、最新の計算では8日間に短縮されました。
・現状では多大な計算時間が必要です。　計算時間短縮のためには、整数計画法の採用が有効と思われますが、必ず解けると言うわけではないようです。　今回、ループ解は最長経路解となり得ないという証明ができましたので、この採用にある程度の見通しが出てきました。
・また、今回採用した全探索についても、　現状のプログラムでは、ループ解も求められるし、発駅、着駅はどこでも良いと言ったアルゴリズムを採用しています。　が、今回発見したJR定理1を前提としたアルゴリズム、たとえば発駅、着駅が固定できる場合の、連結グラフにおける迷路の解法を採用すれば、飛躍的に計算時間が短縮できると思います。　多分1日程度になるのもわりとすぐではないでしょうか。
　今回の追記：連結グラフにおける迷路の解法で今回解いてみましたが、予想と異なり逆に遅くなる結果となりました。　このあたり常識とは異なりますが、なぜそういう結果になるのかは、書き残しておくと後世のためになると思いますので、後で加筆します。

参照､引用

　　[参照1.1]営業キロ､ウィキペディア
　　[参照2.1][引用2.1]最長片道切符､ウィキペディア
　　[参照2.2][引用2.2]最長片道きっぷの経路を求める[参照]、葛西隆也
　　[参照4.1] 整数計画法､ウィキペディア
　　[参照4.2] モンテカルロ法、ウィキペディア
　　[参照4.3] 連結グラフにおける迷路の解法、ウィキペディア　リンク切れ
　　[参照4.4] グラフ理論、ウィキペディア
　　[参照4.5] オイラーの一筆書き定理、ウィキペディア　リンク切れ
　　[参照5.1] 竜飛海底駅､ウィキペディア
　　[引用5.2] 開業・廃止予定線一覧[引用5.2]､鉄道の旅・情報館
　　[引用5.3] 山田線､ウィキペディア
　　[参照5.4] 上野東京ライン､ウィキペディア
　　[引用5.5] 留萌本線､ウィキペディア
　　[参照5.6] 三江線､ウィキペディア
　　[参照5.7] おおさか東線､ウィキペディア
　　[参照5.8] 石勝線､ウィキペディア
　　[参照5.9] 日高線､ウィキペディア

謝辞

　執筆にあたり、次の方々に貴重なご助言をいただきました。　感謝いたします。　なお、敬称は省略させて頂きました。　また､肩書きは2006年当時のものです｡

改訂履歴










>詳細目次