佐藤和夫>散策､旅>☆2016年度版　JR最長経路問題･厳密解

佐藤和夫>散策､旅> ☆2016年度版　JR最長経路問題･厳密解

目次

今回の改訂　RSS1.0

　└→もっと見る


はじめに

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


1.　JRの旅へのお誘い

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

　最近では、北海道新幹線が新函館北斗まで開業され､代わりに海峡線が廃止されていますので、2016年4月号の時刻表を買ってきて計算してみたところ、2015年3月に比べ26.4km短くなっていました。　最近では、北陸新幹線が金沢まで延伸されたり、山田線が移管されていますので、2015年3月号の時刻表を買ってきて計算してみたところ、2011年4月に比べ268.9km短くなっていました。

関連記事


　　[引用1.1]: ^　 営業キロ､ウィキペディア

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

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

関連記事


　　[引用2.1]: ^　最長片道切符､ウィキペディア
　　[引用2.2]: ^　最長片道きっぷの経路を求める、葛西隆也

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


　目で見るJR最長経路2016年4月現在版を次に示します。　地球の3／4を走る長さの、スローな旅をお楽しみください。動画では、次々に経路を青い線でたどります。　静止画はその最終形をお見せします。
　また､いくつかの駅は実際に出かけて様子を取材してきました｡　もし興味があれば､ JR最長経路の旅をご覧ください｡


3.1　動画で見るJR最長経路


　拡大北海道動画へ


　拡大本州動画へ


　拡大九州動画へ


　拡大四国動画へ


　なお動画青線描画中に現れる緑線は、秋田新幹線と田沢湖線のように、物理的に同じ線を走るが、JR時刻表では別の線として紹介されているものをたどる場合と、新幹線と在来線がきわめて近いところを並列に走るために、地図上では複数線として紹介しぬくいものを、往復で通過していることを表しています。
　

3.2　静止画で見るJR最長経路



　各地の静止画です。→　北海道へ　本州へ　九州へ　四国へ
　
　例として次に本州の静止画をお見せします。　
各静止画中の青線が、最長経路で通過する経路を示します。　また、緑線は複数の経路が隣接していて描ききれないときに、あたかも往復されたと見える経路を緑で示します。　新幹線と在来線が並行している場合がそれにあたります。　JR_G_honsh.jpg(92198 byte)



3.3　最長経路解

　2016年4月2015年3月現在の最新の最長経路は、次の通りです。　2014/4/1版では前回計算法の改良により、計算時間は1時間程度になりました。　今回はそれと同じです｡
　2007年1月現在の最新の経路は、次の通りです。　今回は新しい計算法をやってみましたが、予想に反して11日間かかりました。　前回せっかく、JR定理1の2006年12月発見のおかげで8日間に計算が短縮されましたが、一歩後退です。

　JR最長経路の旅>稚内駅から乗車しJR最長経路の旅>若井駅までの総延長で、乗車距離合計14402.414429.0営業キロです。 ここでは、北海道内と、本州→九州→本州→四国を分けて表示しました。

北海道内：稚内,木古内,1497.11513.7営業キロ,
(JR最長経路の旅>稚内駅=*宗谷本線=新旭川=*石北本線=東釧路=*根室本線=新得=*根室本線=富良野=*富良野線=旭川=*函館本線=深川=*函館本線=滝川=*函館本線=岩見沢=*室蘭本線=追分=*室蘭本線=沼ノ端=*千歳線=南千歳=*千歳線=白石=*函館本線=桑園=*函館本線=長万部=*函館本線+北海道新幹線=木古内=*本州へ)

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

九州
(新下関=*山陽新幹線=小倉=*鹿児島本線=西小倉=*鹿児島本線=折尾=*鹿児島本線=香椎=*香椎線=長者原=*篠栗線=吉塚=*鹿児島本線=博多=*九州新幹線=新鳥栖=*長崎本線=鳥栖=*鹿児島本線=久留米=*鹿児島本線=筑後船小屋=*鹿児島本線=熊本=*九州新幹線=新八代=*九州新幹線=川内=*鹿児島本線=鹿児島中央=*日豊本線=隼人=*肥薩線=吉松=*えびの高原線=都城=*日豊本線=南宮崎=*日豊本線=大分=*阿蘇高原線=熊本=*九州新幹線=筑後船小屋=*九州新幹線=久留米=*ゆふ高原線=夜明=*ゆふ高原線=大分=*日豊本線=JR最長経路の旅>別府駅=*日豊本線=城野=*日田彦山線=田川後藤寺=*後藤寺線=新飯塚=*筑豊本線=桂川=*筑豊本線=原田=*鹿児島本線=博多=*山陽新幹線=小倉=*鹿児島本線=幡生)

四国
(岡山=*瀬戸大橋線=宇多津=*高徳線=佐古=*徳島線=佃=*土讃線=多度津=*予讃線=JR最長経路の旅>若井駅)

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

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


　数的解析で最長経路を求めようとすると、計算量が大きすぎるという問題が立ちはだかります。
　何故なら、JR最長経路問題はその問題の定義上、ある駅は複数回通過可能です。　言い換えればループ解の存在が許されます。　そうすると、最長片道きっぷの経路を求めたときの整数計画法（Integer Programming）[引用4.1]を用いることは出来無いと思っていました。　しかし、2006/12/8にループ解は連結グラフにおいては、最長解とはなりえないという証明に成功したので、今後整数計画法も検討したいと思います。　また、モンテカルロ法[引用4.2]は、これが最長経路だ！という保証はなく、38年前に試みたことがあるのですが、今回は見送りました。

　残るは全探索ですが、上で出てきた葛西さんの､最長片道きっぷの経路を求めたときの説明を引用します。
　・・・これは何も考えずにすべての組み合わせを列挙し、その中から、その中から一番いいものを探そう、というごく単純なもので、だれでも思いつく「おバカ」な方法です。　ただし、この問題をそのまま全探索で解くと、現在のコンピュータの性能では答えが出る前に地球の寿命が来る恐れがあります。　少なくともコンピュータの寿命は来るでしょう。・・・[引用2.2]

　全検索でJR最長経路問題を解くには、経路数をnとすると、2のn乗の組み合わせで一筆書きできるかどうか検査することが必要です。　経路数が2であれば2x2で4通りですが、経路数が10になると2x2x2x2x2x2x2x2x2x2x2x2で1024通りになります。　実際にはJR経路数は400程度ありますので、2xが400程度並び、考えるのも恐ろしいほどの計算量が必要です。
計算量削減のために行った工夫を、つぎに述べます。

4.1　一筆書きできるかどうか、すばやく検査する方法

　経路群とその乗り換え駅を用意したときに、すべての経路を通過した一筆書きが可能かどうかは、次のようにして判定しました。　以下の定理で、JRの駅と経路のみならず、一般的なグラフでも成立すると考えられるものは、エッジとノードという、グラフ理論[引用4.4]の用語で示します。　エッジは経路、ノードは駅に相当します。　各ノードは、それぞれノードを出入りするエッジを1以上の複数持っているとします。
　
　次に述べる一筆書き定理1および2では前提として、エッジ同士は連結されているかどうかは不明としています。　そうすると連結グラフで有名なオイラーの一筆書き定理[引用4.5]は成立しません。　ご注意ください。

一筆書き定理1：　あるエッジの組み合わせが一筆書き出来るのは、奇数の出入りノードを持つエッジの合計数aが2もしくは0の時です。　この逆は成立しません。
なおエッジ合計数が2の解はここでは直線解と呼び、合計数が0のものはループ解と呼ぶことにします。
証明：　二つ以上の島に分かれても合計数が2、0のものが作成できるため、　十分条件については成立しません。
例として、JR最長経路問題の実測では約552倍高速になりました。　といっても、単位時間で9経路強余分に計算できることになっただけですが・・・

一筆書き定理2：一筆書き定理1から導き出されるものですが、つぎの定理が成立します。
通過出来ないエッジ数 = (a-2)/2個 ただし、a=0,1は除きます。また、割り切れないときは切り上げします。
例として、JR最長経路問題の実測では約3倍高速になりました。　といっても、単位時間で1経路弱余分に計算できることになっただけですが・・・

一筆書き定理3：　連結グラフでは、エッジの属性が線形性を持つ（距離など）場合には、最長経路は必ず直線解です。　ただし例外として、すべてのノードがループ経路に含まれる場合のみ、ループ解が最長経路となります。
証明：　ループ解が最長経路解になったとします。　すると、それに含まれるすべてのエッジは経路開始エッジとなり得ます。　ループ解に属するあるノードに、別のエッジが接続していると、そのエッジから出発することにより、より長い経路が作成可能です。
行き止まり経路uから出発する場合には注意が必要です。　uと接続するノードが元々偶数のエッジと接続していた場合には、uの長さが、uを追加することにより追加できなくなるエッジ長より長いことが必要です。

一筆書き定理4：　連結グラフでは、通過可能なすべてのノードを通過する経路解が存在すれば、その解中の一つが最長経路です。　この逆は成立しません。
通過できないノードとは、つぎの条件を満たしているものです。
①そのノードが奇数のエッジと接続し、さらに接続するすべてのノードが奇数のエッジと接続しており、かつ
②そのノードと接続しているエッジが、接続するすべてのノードから見て最短である。
証明：　通過可能なすべてのノード中のどれか一つをはずす一筆書き経路解を作成したとします。　すると、そのノードを通過するすべてのエッジは通過できなくなり、その分、経路は短くなります。
奇数のエッジを持つノードは、必ず一つ通過できないエッジを持ちます。　最短のエッジを通過すると、必ず他よりも短い経路となるので、通過しないほうが選ばれます。　どの方向から来てもそうであるので、通過できなくなります。

4.2　経路数を削減する方法

　エッジ数を1つ減らせれば、計算時間は半分になります。　この節では、エッジの属性が線形性を持つ場合について、該当する定理について述べます。

簡約定理1：　あるノードが2つのエッジと接続している場合は、そのノードは削除し、2つのエッジを加算法則によって合併させ、1つにすることが出来ます。
例として、平城山駅は、奈良駅までと、木津駅までの二つの経路を持っていますが、削除して奈良駅から（平城山駅を中抜きして）木津駅までの一つの経路に簡約することが可能です。

簡約定理2：　2つのノードが2つのエッジと接続することが繰り返され、しかも2つのエッジの属性が同じ場合は、繰り返しをすべて削除し、2つのノードと2つのエッジに簡約出来ます。
例として、豊橋、浜松、掛川、静岡は、新幹線と在来線が並行して走っていますが、簡約定理1を使用すると、簡約定理2の適用が可能になります。　簡約定理2により、この4つの駅と6個の経路は中抜きされて、2つの駅（豊橋、静岡）と2つの豊橋～浜松の経路に簡約されます。

　ここまでで、計算量は次のようになります。

日本全国の計算量＝おおよそ比例（　2の日本全国の経路数（約400）乗　）

4.3　JR独特の制約を生かす方法

　これは、つぎの4.4節のための準備になります。

JR定理1：　行き止まり経路を除いたすべての駅を通過する一筆書き経路を作成できた場合には、発駅は稚内、着駅は若井の直線解のみを求めれば最長経路が見つかります。
証明：　現時点での行き止まり経路は、最長が北海道の稚内から新青森（1610.41632.9営業キロ）、2番が四国の若井から岡山（585.2営業キロ）、3番が島原地方の肥前山口から鳥栖（187.9営業キロ）です。　それらを除いた本州および九州経路ですべての駅を通過できた場合には、一筆書き定理4により、それが本州・四国最長経路となります。　それに行き止まり経路を追加することにより、さらに長い経路を作成可能（一筆書き定理3）ですが、稚内を発駅、若井を着駅とすることにより、日本全体の最長経路となります。　なお、行き止まり経路は、一筆書き定理4の性質上、必ず本州・四国最長経路に接続可能です。
将来新幹線が青函トンネルを越え、かつ在来線も残れば、複数経路が北海道と本州間に出来るため、稚内は最長行き止まり経路で無くなります。　こうなれば、最長が四国の若井から岡山、2番が北海道の稚内から新旭川（255.7営業キロ）、3番が島原地方の肥前山口から鳥栖と変化します。　発駅、着駅は変化しません。

4.4　藩分割による方法

　上の定理群を利用しても、僕のPCでは36エッジ程度を計算するのがせいぜいでした。　日本全国約400経路の数的解析はとても手が出ません。　しからば、次の手はエッジ群をいくつかのドメインに分割して計算し、あとで結果を貼り合わせると言う方法が、グラフ理論では良く用いられています。　
　ここでは、少し異なった方法を取っています。　日本列島が細長いことを利用して、大根の輪切りのように各地方を、駅を切り口に切ってゆきます。　そうすると、切り取られた各地方（以下、藩と呼びます）には、その中に含まれる経路群、九州側の切り口と北海道側の切り口ができあがります。　「ドメインと、外との貼り合わせ」という代わりに、「ドメイン（各藩）と、外1（九州側切り口）および外2（北海道側切り口）」との2つに、外を分類してしまおうという訳です。
　なお切り口になった駅は、これから「関所」と呼ぶことにします。　九州側切り口に属する駅は九州側関所、北海道側切り口に所属するものは北海道側関所と呼ぶことにします。

　では、2001年5月のJTB時刻表を用いて、実際にどのように分割したかを紹介しましょう。下の表で九州側関所群とは、ある地方から見て、それの九州側関所群の通過方法すべてを指します。　その数はおおよそ、関所数が11であれば、おおよそ3x3x3x3x3x3x3x3x3x3x3（3の11乗）となりますが、実際には通過できない経路がかなりあるので、数はそれより少なくなります。　ちなみに計算時間は僕のPCで、東京を主とした南関東7日間、大阪を主とした東関西で5日間、北海道で10秒程度でした。

表4.4　分割された藩と、その切り口
各藩名　 九州側
関所群		 各藩内
経路数		 北海道側
関所数
南九州 0 11 2
島原地方 0 10 1
北九州 4 29 2
西中国 4 29 4
四国 0 8 1
東中国 37 26 4
西関西 37 20 4
東関西 37 32 4
中部 37 28 5
東海 109 20 6
西関東 377 31 9
南関東 16783 25 11
千葉 140383 18 10
埼玉 2576 25 7
新潟 1049 25 6
福島 379 30 6
南東北 381 20 5
北東北 115 25 1
北海道 1 28 0

　ここまでで、計算量は次のように変化します。　大分少なくなりましたが、PCが壊れるまでには計算できそうにないようです。

・各藩ごと計算量＝　おおよそ比例（九州側関所群x（2の各地方内の経路数乗）x　（3の北海道側関所数乗））
・日本全国の計算量＝　南九州の計算量　x　島原地方の計算量　x　・・・x　北海道の計算量

　上で、切り口の関所群はおおよそ3の関所数乗と述べましたが、それは次の定理に基づいています。

ある藩の九州側と北海道側切り口の合計関所数が1であり、かつエッジのプロパティに加算法則が適用される場合につぎのことが成り立ちます。

関所定理1：その藩のすべてのノードおよびエッジは簡約して、1つのノードと、それと関所を結ぶ1つの、最長経路解であるエッジに代えることが出来ます。
例として関所数1を持つ藩としては、島原地方および北海道があります。　島原地方は肥前山口駅に、北海道は稚内駅に簡約されます。　通過経路も固定されます。

また、九州側関所数が1，北海道側関所数が1の場合にも同様につぎのことが成り立ちます。

関所定理2：その藩のすべてのノードおよびエッジは簡約して、九州側関所、北海道側関所とそれらを結ぶ1つの、最長経路解であるエッジに代えることが出来ます。
例としては、北海道函館本線、森駅と七飯駅の間が挙げられます。

　関所門番から見ると、ある旅人は藩外からやってきて藩の中に入るか、逆に藩内からやってきて外に出るかです。　もしも、ある切り口の関所群全部を一人の門番が管理することが出来れば、その切り口を通るすべての旅人が、どちらから来て、どの関所を通過して藩内に入り、どの関所から出て行ったかが分かります。　中には何回か出入りした後に、出ていき再度戻ってこない旅人とかが分かります。　ここである関所は一度しか通過できないという制約を設けます。　この制約は計算量に影響を及ぼしません。

　制約：北海道側関所となりうる駅は、各藩内からの経路が1つのものを選択します。　これは関所がループ経路の途中に存在することを避けるためです。

　そうすると、すべての旅人は切り口を通過したあと、他の関所を通って戻ってゆくか、それとも切り口を通過した後に戻ってこないかのどちらかとなります。　戻ることはこれからU型経路と呼びます。　丁度、Uターンして故郷に戻ることに相当します。　故郷と大都会を何回も行きち戻りつ、Uターンを繰り返すことが可能です。　それに比べ、行きっぱなしの場合は、これからI型経路と呼ぶことにします。　また、旅人の通りうる、関所のすべての通過方法を関所群と呼ぶことにします。　そうすると、次の定理が成り立ちます。

関所定理3：ある切り口の関所数をsとしたときに、I型経路は最大2，U型経路は最大s/2経路取りえます。　関所群は、この制限の元でのすべての通過方法の組み合わせになります。　これがおおよそ3の関所数乗になるわけです。

　ただし、一生藩から出ない人とか、外に住んでいてその藩へ行かない人は門番には分かりません。　言い換えれば最長経路解が、あるドメイン内に潜んでいる場合には、ドメイン分割を下手におこなうと、その解を見逃す可能性が一般論としてはあります。　JRの場合にはJR定理1により、その可能性はありません。

4.5　発駅、着駅の地方固定による方法

　上の方法ではまだ現実に数的解析で答えを得るには至りません。　ここでは更に定理を追加することにより、やっと現実に計算が完了できる射程内に入ります。

　まず、JR定理1に基づき、稚内から青森、若井から岡山以外のすべての行き止まり経路の切り捨てを行います。
　次に、計算は九州側から3.4表の順番に上から下へ（北に向かって）行います。　まず、南九州の北海道側切り口に所属する関所を通過するすべての通過経路情報は、経路群ごとに整理され、九州側関所群として北九州に渡されます。　北九州ではそれと、北九州の北海道側関所群とのすべての組み合わせの基に、北九州の通過経路情報を計算します。

通過経路情報の例として、南九州から渡される通過経路情報を紹介します。　経路の発駅,着駅,最長経路距離（単位100m）,経路　が、合計4つの経路群として、北九州に引き渡されます。

志布志,千丁,4341,(千丁=*鹿児島本線=八代=*鹿児島本線=西鹿児島=*日豊本線=隼人=*肥薩線=吉松=*えびの高原線=都城=*日豊本線=南宮崎=*日南線=志布志)
****,0, 上の経路群は：g=1 関所=1:千丁
枕崎,宮崎,4699,(宮崎=*日豊本線=南宮崎=*日豊本線=都城=*日豊本線=隼人=*肥薩線=吉松=*肥薩線=八代=*鹿児島本線=西鹿児島=*指宿枕崎線=枕崎)
****,0, 上の経路群は：g=2 関所=2:宮崎
八代,千丁,3920,(千丁=*鹿児島本線=八代=*肥薩線=吉松=*えびの高原線=都城=*日豊本線=隼人=*日豊本線=西鹿児島=*鹿児島本線=八代)
志布志,宮崎,915,(宮崎=*日豊本線=南宮崎=*日南線=志布志)
****,0, 上の経路群は：g=3 関所=1:千丁 関所=2:宮崎
千丁,宮崎,3478,(宮崎=*日豊本線=南宮崎=*日豊本線=都城=*えびの高原線=吉松=*肥薩線=隼人=*日豊本線=西鹿児島=*鹿児島本線=八代=*鹿児島本線=千丁)
****,1, 上の経路群は：g=4 関所=3:千丁,宮崎

関所定理4：JR定理1の基で、北海道側関所群に残す通過経路情報としては、最長経路距離と、その経路の2つで十分です。
　これは、ある藩からみて、それまで通過してきた九州側情報から、部分的な最適化を図ることを意味しています。　北海道側の経路情報を含めた、日本全国視点からの最適化はしていません。　が、JR定理1を前提条件としてですが、それでよいということの証明は、葛西さんが、最長片道きっぷの経路を求める[引用2.2]の｢[3-5] 全探索で（分割編２）最長片道きっぷの経路を求める」中「連結でない」問題への対応、で証明されていらっしゃいますのでご覧ください。

例で示すと、上の例の上から7～10行目（g＝3)の経路群については最適化が、九州側のみで行われていますが、これが関所定理4を利用しているところです。

八代,千丁,3920,(千丁=*鹿児島本線=八代=*肥薩線=吉松=*えびの高原線=都城=*日豊本線=隼人=*日豊本線=西鹿児島=*鹿児島本線=八代)
志布志,宮崎,915,(宮崎=*日豊本線=南宮崎=*日南線=志布志)
****,0, 上の経路群は：g=3 関所=1:千丁 関所=2:宮崎

　これにより、つぎのように3.4節のxが+に変化し、やっと現実的に数的解析出来る程度の計算量となりました。　といっても、僕のPCで手作業部分も含め、やっと2ヶ月ぐらいに収まるようになったという事です。

日本全国の計算量＝　南九州の計算量　+　島原地方の計算量　+　・・・+　北海道の計算量

4.6　連結グラフにおける迷路の解法の採用

・上で説明した、藩内計算に用いた全探索法は、ループ解も求められるし、発駅、着駅はどこでも良いと言った利点があります。　しかしながら計算量がおおよそ2の各地方内の経路数乗に比例するため、藩を大きくする(エッジ数を増やす)ことは困難です。　実際にやってみると36エッジ程度が上限でした。

　一方今回発見したJR定理1を前提としたアルゴリズム、たとえば発駅、着駅が固定できる場合の、連結グラフにおける迷路の解法[引用4.3]を採用すれば、計算量がおおよそ<各地方内の経路数の2乗に比例するため、エッジ数が多くなると飛躍的に計算時間が短縮できるはずです。　ところが実際に2007年4月からプログラムを変更し、連結グラフにおける迷路の解法で解いてみましたが、予想と異なり逆に遅くなる結果となりました。　具体的にはその前の版で8日間だった計算時間が11日間となりました。　このあたり常識とは異なりますが、なぜそういう結果になるのかは、書き残しておくと後世のためになると思いますので、ここで加筆します。
2007年4月に採用した「連結グラフにおける迷路の解法」[引用4.3]ではたとえば8の字経路があると、まったく同じ長さを持つ4つのルートができあがり、重複します。　2011年4月今回この重複を除くようにプログラムを変更したことにより、おおざっぱに言って計算すべきルート数は1/5になりました。　その他、DB2チューニングおよび新PC採用により、その結果11日間要したものが8時間に短縮されました。　藩内エッジ数については、現PCで60ぐらいまでは現実的に計算可能な感触です。

　2014年4月にさらに新PCを採用し､その能力を生かすためDBMS(DB2)を廃止し配列演算に変更しました｡　結果8時間が1時間に短縮されました｡　藩内エッジ数については、現状54で実用的な限界でありました｡　すなわち､新潟福島地方を一つの藩にまとめられませんでした｡

表4.6　｢4.6　連結グラフにおける迷路の解法｣を採用して分割された藩と、その切り口
各藩名　 九州側
関所群		 各藩内
経路数		 北海道側
関所数
島原地方 0 10 1
九州 0 46 2
四国 0 8 1
中国 3 54 4
西関西 28 20 4
東関西 27 35 4
東海 28 44 6
西関東 187 29 9
南関東 6480 25 11
千葉 104096 18 10
埼玉 36886 22 7
新潟 959 28 6
福島 180 28 6
奥州 246 33 1
北海道 1 28 0

関連記事


　　[引用4.1]: ^　 整数計画法､ウィキペディア
　　[引用4.2]: ^　 モンテカルロ法、ウィキペディア
　　[引用4.3]: ^　 連結グラフにおける迷路の解法、ウィキペディア
　　[引用4.4]: ^　 グラフ理論、ウィキペディア
　　[引用4.5]: ^　 オイラーの一筆書き定理、ウィキペディア

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

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


改訂履歴




関連記事


　　[引用5.1]: ^　 竜飛海底駅､ウィキペディア
　　[引用5.2]: ^　 開業・廃止予定線一覧、鉄道の旅・情報館
　　[引用5.3]: ^　 山田線､ウィキペディア
　　[引用5.4]: ^　 上野東京ライン､ウィキペディア
　　[引用5.5]: ^　 留萌本線､ウィキペディア
　　[引用5.6]: ^　 三江線､ウィキペディア
　　[引用5.7]: ^　 おおさか東線､ウィキペディア
　　[引用5.8]: ^　 石勝線､ウィキペディア
　　[引用5.9]: ^　 日高線､ウィキペディア

謝辞

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