☆2007/1/14版　JR最長経路問題･厳密解

←旅/記事目次　　訪問:

 佐藤和夫>　旅>

☆2007/1/14版　JR最長経路問題･厳密解

はじめに

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

1.　JRの旅へのお誘い

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

タグ: #佐藤和夫ようこそ #JR最長経路問題 #JR最長経路問題･厳密解 #JR最長経路の旅 #私鉄､廃線の旅 #JR #最長経路問題 #厳密 #最適解 #鉄道ファン #一筆書き #数的解析 #ルート #計算 #ルート動画 #グラフ #最長経路 #静岡大学 　最近では、東北新幹線が八戸まで延伸されたり、九州新幹線が八代まで暫定開業されていますので、上の数字よりも更に長く旅を楽しめるはずですが、最新のデータでの最長経路の発表はいましばらく楽しみにお待ちください。

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

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

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

　理論的には、稚内から若井までの総延長（ただ今計算中）14805.9kmとなるはずということが、2006年12月16日に分かりました。　したがって、四国を含めた計算を改めて実行中で、2007年1月6日現在南関東を通過中です。　下のものは四国を含めないで、計算したときのものです。　
　2001年5月現在のものは、次の通りです。　最新版については近々計算したいですが、なにせ1回計算するのにとぎれなく働いて2ヶ月以上かかるので・・・。

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

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

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

注）
・データはJTB時刻表2001年5月号、2001年4月21日発行に依ります。
・「経路」とは、この時刻表P18～P35の経路図に表示されたものを指します。　ここでは、実際には物理的に別線であるものが、一つの経路として記入されている例、たとえば横須賀線の大船横浜間がありますが、経路図通りに一つの経路として入力しています。　また。逆に実際には物理的に一つの路線であるものが、二つの経路として記入されている例、たとえば秋田新幹線と田沢湖線がありますが、経路図通りに二つの経路として入力しています。　また、この経路図には、新子安から品川間が横須賀線であり、新子安に停車するかのように表示されていますが、その通りに新子安と品川間を一つの経路として扱っています。　他にも類似の例がありますが、すべて経路図通りに経路を入力しています。
・一部の区間で一つの経路に複数の路線が乗っている場合、たとえば山手線と京浜東北線の日暮里～品川間がありますが、便宜上片方のみを経路名として使用しました。
・四国は計算から除外しています。　つまり、四国のどこかの駅が着駅にはならないという仮定をおいて計算しています。　次回の最新時刻表の時は四国を入れて計算しようと思っています。

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

　数的解析で最長経路を求めようとすると、計算量が大きすぎるという問題が立ちはだかります。
　　何故なら、JR最長経路問題はその問題の定義上、ある駅は複数回通過可能です。　言い換えればループ解の存在が許されます。　そうすると、最長片道きっぷの経路を求めたときの整数計画法（Integer Programming）を用いることは出来無いと思っていました。　しかし、2006/12/8にループ解は連結グラフにおいては、最長解とはなりえないという証明に成功したので、今後整数計画法も検討したいと思います。　また、モンテカルロ法は、これが最長経路だ！という保証はなく、38年前に試みたことがあるのですが、今回は見送りました。
　残るは全探索ですが、上の葛西さんの最長片道きっぷの経路を求めたときの説明を参照2より引用します。　・・・これは何も考えずにすべての組み合わせを列挙し、その中から、その中から一番いいものを探そう、というごく単純なもので、だれでも思いつく「おバカ」な方法です。　ただし、この問題をそのまま全探索で解くと、現在のコンピュータの性能では答えが出る前に地球の寿命が来る恐れがあります。　少なくともコンピュータの寿命は来るでしょう。・・・
　全検索でJR最長経路問題を解くには、経路数をnとすると、2のn乗の組み合わせで一筆書きできるかどうか検査することが必要です。　経路数が2であれば2x2で4通りですが、経路数が10になると2x2x2x2x2x2x2x2x2x2x2x2で1024通りになります。　実際にはJR経路数は400程度ありますので、2xが400程度並び、考えるのも恐ろしいほどの計算量が必要です。
計算量削減のために行った工夫を、つぎに述べます。

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

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

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

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

一筆書き定理3：　連結グラフでは、加算法則（x+y=zが成立する、線形性を持つとも言います）が成り立つ場合には、最長経路は必ず直線解です。　ただし例外として、すべてのノードがループ経路に含まれる場合のみ、ループ解が最長経路となります。
証明：　ループ解が最長経路解になったとします。　すると、それに含まれるすべてのエッジは経路開始エッジとなり得ます。　ループ解に属するあるノードに、別のエッジが接続していると、そのエッジから出発することにより、より長い経路が作成可能です。
行き止まり経路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：　行き止まり経路を除いたすべての駅を通過する一筆書き経路を作成できた場合には、発駅は稚内、着駅は若井の直線解のみを求めれば最長経路が見つかります。
証明：　現時点で行き止まり経路は、最長が北海道の稚内から青森（1632.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を前提条件としてですが、それでよいということの証明は、葛西さんが、「最長片道きっぷの経路を求める」の「[3-5] 全探索で（分割編２）最長片道きっぷの経路を求める」中「連結でない」問題への対応、で証明されていらっしゃいますのでご覧ください。
例で示すと、上の例の上から7～10行目（g＝3)の経路群については最適化が、九州側のみで行われていますが、これが関所定理4を利用しているところです。

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

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

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

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

・計算結果は、行き止まり経路を除く、通過できるすべての駅を通過しています。　福知山駅は通過していませんが、これは通過できない駅です。　したがって、JR定理1の適用が可能です。
・上では計算に2ヶ月必要だったと書きましたが、JR定理1「若井が必ず着駅だと分かったこと」を執筆の途中で発見したことにより、四国を含めた再計算では、それまで2ヶ月要していたものが、1ヶ月弱になりました。
・現状では多大な計算時間が必要です。　計算時間短縮のためには、整数計画法の採用が有効と思われますが、必ず解けると言うわけではないようです。　今回、ループ解は最長経路解となり得ないという証明ができましたので、この採用にある程度の見通しが出てきました。
・また、今回採用した全探索についても、　現状のプログラムでは、ループ解も求められるし、発駅、着駅はどこでも良いと言ったアルゴリズムを採用しています。　が、今回発見した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年当時のものです｡

改訂履歴






>詳細目次