佐藤和夫>旅> ☆2006/12/9版 JR最長経路問題･厳密解
今回の改訂 
- (06/12/09)厳密解061209版: ・1，3，5章を改訂しました。 改訂部分は下線および取消線で示します。
・葛西隆也さんからのご指摘「予想が少ないほうがよい」を踏まえて、新しい一筆書き定理3およびJR定理2を発見し、予想2をなくすことに成功しました。 予想1も、JR定理1を見いだし、予想ではなく未計算部分であり、それを計算すれば完全解になるという証明までにこぎ着け、歯切れが良くなりました。
はじめに
それは、つねに新しい経路(ルート)をたどりながら、稚内駅から肥前山口までの総延長14347.0kmを、一筆書きで乗りつくす旅です。 数的解析の結果分かったことですが、行き止まりの路線を除きすべてのJRの乗り換え駅をたどる旅でもありました。 この記事は、その経路をどのようにして求めたかを説明するものです。14347.0kmは地球半周よりも更に約2800km以上長くて、日本から地球の反対側のブラジルを越えて、大西洋のど真ん中までたどり着ける距離に相当します。 日本は広いですね。 また、JRの四分の三を乗り尽くします。 我が駅、平城山(ならやま)駅も通過することになっていたので、安心しました。
1. JRの旅へのお誘い
途中下車をせずに、JRの異なる経路を次々と乗り継いで旅をしたら、一筆書き出来る最長経路の乗車距離は何キロメートルぐらいになるのでしょうか？ いったい何駅から乗車し、最後にどこで下車することになるのでしょうか？ また、途中にどんな情景が待ち受けているのでしょうか？ これからご案内します。この旅は結論から言うと、稚内駅から肥前山口までの、乗車距離合計14347.0営業キロ[引用1.1]を、途中下車することなく乗り続けることになります。 最長経路は新幹線が出来たり、新駅が出来たり、ローカル線が廃止されるたびに変化します。 新駅が出来たらなぜ最長経路は変わるのだろう？と思われるかもしれませんが、新駅が出来るとそれにより新しい経路が出来上がるので、総延長距離は増える可能性が高いのです。
最近では、東北新幹線が八戸まで延伸されたり、九州新幹線が八代まで暫定開業されていますので、上の数字よりも更に長く旅を楽しめるはずですが、最新のデータでの最長経路の発表はいましばらく楽しみにお待ちください。
関連記事
関連記事[引用1.1]: ^ 営業キロ､ウィキペディア
2. JR最長経路問題とは何か
ここでは、JRの「ある経路は一度だけ通過できる」こととして、ある特定日の一筆書きできる最長経路のルート、その時の乗車距離、発駅、着駅を求めようとします。なお、JRには最長片道切符[引用2.1]なるものがありますが、これは「ある駅は一度だけ通過できる」という条件で、一筆書きできる最長経路のルートを求めようとするものです。 これの数的解析はすでに行われています。
それによると、という記述があります。
またご本人による説明もWEBに記載されています[引用2.2]｡
関連記事
関連記事[引用2.1]: ^最長片道切符､ウィキペディア
[引用2.2]: ^最長片道きっぷの経路を求める、葛西隆也
3. 一筆書きJR最長経路はこれだ！
2001年5月現在のものは、次の通りです。 最新版については近々計算したいですが、なにせ1回計算するのにとぎれなく働いて2ヶ月以上かかるので・・・。稚内から乗車し肥前山口までの総延長で、乗車距離合計14347.0営業キロです。 ここでは、北海道内と、本州および九州とを分けて表示しました。
稚内,竜飛海底,1569.0営業キロ,
| (稚内=*宗谷本線=新旭川=*石北本線=東釧路=*根室本線=新得=*根室本線=富良野=*富良野線=旭川=*函館本線=深川=*函館本線=滝川=*函館本線=岩見沢=*室蘭本線=追分=*室蘭本線=沼ノ端=*千歳線=南千歳=*千歳線=白石=*函館本線=桑園=*函館本線=長万部=*函館本線=竜飛海底) |
竜飛海底,肥前山口,12778.0営業キロ,
| (竜飛海底=*海峡線=青森=*東北本線=野辺地=*東北本線=八戸=*東北本線=好摩=*花輪線=大館=*奥羽本線=川部=*五能線=東能代=*奥羽本線=追分=*奥羽本線=秋田=*奥羽本線=大曲=*秋田新幹線=盛岡=*山田線=茂市=*釜石線=新花巻=*東北新幹線=北上=*北上線=横手=*奥羽本線=新庄=*山形新幹線=天童=*奥羽本線=南出羽=*奥羽本線=羽前千歳=*仙山線=仙台=*東北本線=小牛田=*東北本線=一ノ関=*東北新幹線=古川=*陸羽東線=新庄=*奥羽本線=天童=*山形新幹線=山形=*山形新幹線=米沢=*山形新幹線=福島=*東北新幹線=仙台=*仙石線=前谷地=*気仙沼線=気仙沼=*大船渡線=一ノ関=*東北新幹線=北上=*東北本線=花巻=*釜石線=新花巻=*東北新幹線=盛岡=*田沢湖線=大曲=*秋田新幹線=秋田=*羽越本線=余目=*羽越本線=坂町=*米坂線=米沢=*奥羽本線=福島=*東北新幹線=郡山=*東北新幹線=新白河=*東北新幹線=那須塩原=*東北本線=黒磯=*東北本線=新白河=*東北本線=安積永盛=*水郡線=水戸=*常磐線=いわき=*常磐線=岩沼=*東北本線=福島=*東北本線=郡山=*磐越西線=会津若松=*磐越西線=喜多方=*磐越西線=新津=*羽越本線=新発田=*白新線=新潟=*信越本線=新津=*信越本線=東三条=*信越本線=長岡=*信越本線=宮内=*信越本線=柏崎=*越後線=吉田=*越後線=新潟=*上越新幹線=燕三条=*上越新幹線=長岡=*上越新幹線=浦佐=*上越線=越後湯沢=*上越線=新前橋=*両毛線=小山=*東北本線=自治医大=*東北本線=宇都宮=*東北本線=那須塩原=*東北新幹線=宇都宮=*東北新幹線=小山=*東北本線=大宮=*上越新幹線=高崎=*上越新幹線=越後湯沢=*上越新幹線=浦佐=*上越線=小出=*上越線=越後川口=*飯山線=飯山=*飯山線=信濃淺野=*飯山線=豊野=*信越本線=直江津=*北陸本線=糸魚川=*大糸線=松本=*篠ノ井線=長野=*長野新幹線=佐久平=*八ヶ岳高原線=小淵沢=*中央本線=岡谷=#中央本線=辰野=#中央本線=塩尻=#中央本線=多治見=#中央本線=金山=#東海道本線=三河安城=#東海道本線=豊橋=#東海道本線=掛川=#東海道本線=静岡=#東海道本線=富士=*見延線=甲府=*中央本線=八王子=*横浜線=橋本=*相模線=茅ヶ崎=*東海道本線=大船=*根岸線=横浜=*東海道本線=東神奈川=*東海道本線=新子安=*横須賀線=品川=*山手線=大崎=#山手線=代々木=#中央本線=御茶ノ水=#総武本線=秋葉原=#山手線=神田=#山手線=東京=#東海道本線=田町=*東海道本線=品川=*東海道本線=川崎=*東海道本線=鶴見=*鶴見線=尻手=*南武線=府中本町=*南武線=立川=*青梅線=拝島=*八高線=八王子=*中央本線=立川=*中央本線=西国分寺=*中央本線=新宿=#山手線=池袋=#山手線=田端=#京浜東北線=赤羽=#東北本線=日暮里=#常磐線=新松戸=#武蔵野線=西船橋=#武蔵野線=南船橋=#京葉線=蘇我=#内房線=大網=#外房線=蘇我=#内房線=千葉=#総武本線=佐倉=#総武本線=成東=#総武本線=成田=#総武本線=我孫子=#常磐線=友部=*水戸線=小山=*東北新幹線=大宮=*埼京線=武蔵浦和=*武蔵野線=南浦和=*京浜東北線=大宮=*川越線=高麗川=*八高線=倉賀野=*高崎線=大宮=*東北新幹線=上野=*東北新幹線=東京=*総武線=錦糸町=*総武本線=西船橋=*京葉線=市川塩浜=*京葉線=東京=*東海道新幹線=新横浜=*東海道新幹線=小田原=*東海道新幹線=熱海=*東海道新幹線=三島=*東海道本線=熱海=*東海道本線=小田原=*東海道本線=国府津=*御殿場線=沼津=*東海道本線=三島=*東海道新幹線=静岡=*東海道新幹線=掛川=*東海道新幹線=豊橋=*東海道新幹線=三河安城=*東海道新幹線=名古屋=*東海道新幹線=米原=*東海道新幹線=京都=*東海道本線=新大阪=*東海道本線=大阪=*大阪環状線=京橋=*大阪環状線=天王寺=*阪和線=和歌山=*紀勢本線=亀山=*関西本線=桑名=*関西本線=名古屋=*東海道本線=岐阜=*高山本線=美濃太田=*高山本線=富山=*北陸本線=敦賀=?小浜線=綾部=?山陰本線=京都=?東海道新幹線==新大阪=?山陽新幹線=西明石=*山陽本線=尼崎=*JR東西線=京橋=?片町線=木津=?奈良線=京都=?東海道本線=山科=?湖西線=近江塩津=?北陸本線=米原=?東海道本線=草津=?草津線=柘植=?関西本線=木津=?関西本線=奈良=?桜井線=高田=?和歌山線=王寺=?関西本線=天王寺=?大阪環状線=大阪=?山陽本線=尼崎=*福知山線=谷川=*加古川線=加古川=*山陽本線=西明石=*山陽新幹線=姫路=*播但線=和田山=*山陰本線=鳥取=*因美線=東津山=*姫新線=姫路=*山陽新幹線=相生=*山陽本線=東岡山=*赤穂線=相生=*山陽新幹線=岡山=*吉備線=総社=*伯備線=倉敷=*山陽本線=新倉敷=*山陽新幹線=福山=*山陽本線=新倉敷=*山陽新幹線=岡山=*津山線=津山=*姫新線=新見=*伯備線=備中神代=*伯備線=伯耆大山=*山陰本線=宍道=*木次線=備後落合=*福塩線=塩町=*福塩線=福山=*山陽本線=尾道=*山陽本線=三原=*山陽本線=海田市=*呉線=三原=*山陽新幹線=広島=*山陽本線=岩国=*山陽本線=櫛ヶ浜=*山陽本線=徳山=*山陽本線=小郡=*山口線=益田=*山陰本線=江津=*三江線=三次=*芸備線=広島=*山陽新幹線=徳山=*山陽新幹線=小郡=*宇部線=居能=*小野田線=小野田=*山陽本線=宇部=*山陽本線=小郡=*山陽新幹線=厚狭=*山陽本線=新下関=*山陽本線=幡生=*山陰本線=長門市=*美弥線=厚狭=*山陽新幹線=新下関=*山陽新幹線=小倉=*山陽新幹線=博多=*鹿児島本線=原田=*筑豊本線=桂川=*篠栗線=長者原=*篠栗線=吉塚=*鹿児島本線=香椎=*鹿児島本線=折尾=*筑豊本線=新飯塚=*後藤寺線=田川後藤寺=*日田彦山線=城野=*日豊本線=大分=*阿蘇高原線=熊本=*鹿児島本線=千丁=*鹿児島本線=八代=*鹿児島本線=西鹿児島=*日豊本線=隼人=*肥薩線=吉松=*えびの高原線=都城=*日豊本線=南宮崎=*日豊本線=宮崎=*日豊本線=大分=*ゆふ高原線=夜明=*ゆふ高原線=久留米=*鹿児島本線=鳥栖=*長崎本線=久保田=*長崎本線=肥前山口=*諫早=*長崎本線=大村線=早岐=*佐世保線=肥前山口) |
注）
・データはJTB時刻表2001年5月号、2001年4月21日発行に依ります。
・「経路」とは、この時刻表P18〜P35の経路図に表示されたものを指します。 ここでは、実際には物理的に別線であるものが、一つの経路として記入されている例、たとえば横須賀線の大船横浜間がありますが、経路図通りに一つの経路として入力しています。 また。逆に実際には物理的に一つの路線であるものが、二つの経路として記入されている例、たとえば秋田新幹線と田沢湖線がありますが、経路図通りに二つの経路として入力しています。 また、この経路図には、新子安から品川間が横須賀線であり、新子安に停車するかのように表示されていますが、その通りに新子安と品川間を一つの経路として扱っています。 他にも類似の例がありますが、すべて経路図通りに経路を入力しています。
・一部の区間で一つの経路に複数の路線が乗っている場合、たとえば山手線と京浜東北線の日暮里〜品川間がありますが、便宜上片方のみを経路名として使用しました。
・四国は計算から除外しています。 つまり、四国のどこかの駅が着駅にはならないという仮定をおいて計算しています。 次回の最新時刻表の時は四国を入れて計算しようと思っています。
4. JR最長経路問題の数的解析は大変
数的解析で最長経路を求めようとすると、計算量が大きすぎるという問題が立ちはだかります。何故なら、JR最長経路問題はその問題の定義上、ある駅は複数回通過可能です。 言い換えればループ解
残るは全探索ですが、上の葛西さんの最長片道きっぷの経路を求めたときの説明を参照2より引用します。 ・・・これは何も考えずにすべての組み合わせを列挙し、その中から、その中から一番いいものを探そう、というごく単純なもので、だれでも思いつく「おバカ」な方法です。 ただし、この問題をそのまま全探索で解くと、現在のコンピュータの性能では答えが出る前に地球の寿命が来る恐れがあります。 少なくともコンピュータの寿命は来るでしょう。・・・
全検索でJR最長経路問題を解くには、経路数をnとすると、2のn乗の組み合わせで一筆書きできるかどうか検査することが必要です。 経路数が2であれば2x2で4通りですが、経路数が10になると2x2x2x2x2x2x2x2x2x2x2x2で1024通りになります。 実際にはJR経路数は400程度ありますので、2xが400程度並び、考えるのも恐ろしいほどの計算量が必要です。
計算量削減のために行った工夫を、つぎに述べます。
4.1 一筆書きできるかどうか、すばやく検査する方法
経路群とその乗り換え駅を用意したときに、すべての経路を通過した一筆書きが可能かどうかは、次のようにして判定しました。 以下の定理で、JRの駅と経路のみならず、一般的なグラフでも成立すると考えられるものは、エッジとノードという、グラフ理論の用語で示します。 エッジは経路、ノードは駅に相当します。 各ノードは、それぞれノードを出入りするエッジを1以上の複数持っているとします。 ここでは前提として、エッジ同士は連結されているかどうかは不明としています。 そうすると連結グラフで有名なオイラーの一筆書き定理は成立しません。 ご注意ください。
一筆書き定理1： あるエッジの組み合わせが一筆書き出来るのは、奇数の出入りノードを持つエッジの合計数aが2
なおエッジ合計数が2の解はここでは直線解と呼び、合計数が0のものはループ解と呼ぶことにします。
証明： 二つ以上の島に分かれても合計数が2、0のものが作成できるため、 十分条件については成立しません。
例として、JR最長経路問題の実測では約552倍高速になりました。 といっても、単位時間で9経路強余分に計算できることになっただけですが・・・
一筆書き定理2：一筆書き定理1から導き出されるものですが、つぎの定理が成立します。
通過出来ないエッジ数 = (a-2)/2個 ただし、a=0,1は除きます。また、割り切れないときは切り上げします。
例として、JR最長経路問題の実測では約3倍高速になりました。 といっても、単位時間で1経路弱余分に計算できることになっただけですが・・・
一筆書き定理3： 連結グラフでは、加算法則（x+y=zが成立する、線形性を持つとも言います）が成り立つ場合には、最長経路は必ず直線解です。 ただし例外として、すべてのノードがループ経路に含まれる場合のみ、ループ解が最長経路となります。
証明： ループ解が最長経路解になったとします。 すると、それに含まれるすべてのアークは経路開始アークとなり得ます。 ループ解に属するあるノードに、別のアークが接続していると、そのアークから出発することにより、より長い経路が作成可能です。
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： 発駅は北海道内にあります。
発駅に関しては現在のところは異論がないでしょう。 北海道から本州は、経路が1つしかありませんし、北海道内の経路総延長は、日本全体の1割を占めますから、これを通過しない手はありません。 この定理は現時点では自明と思われますが、新幹線が青函トンネルを越え、かつ在来線も残れば、複数経路が北海道と本州間に出来るため、自明ではなくなります。
JR定理2： JR定理1と一筆書き定理3を組み合わせれば、JRの場合は直線解のみを求めれば最長経路が見つかります。
4.43.3 藩分割による方法
上の定理群を利用しても、僕の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 |
| 東中国 | 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の場合にはその可能性はありません。
4.53.4 発駅、着駅の地方固定による方法
上の方法ではまだ現実に数的解析で答えを得るには至りません。 ここでは更に予想と定理を追加することにより
予想1：
この予想により、北海道内、九州、もしくは青森を除く藩では、行き止まり経路の切り捨てを行います。 2001年5月時刻表を用いた計算では、四国も経路から削除しています。 四国については、次の計算では、着駅の可能性があるという予想に変更する予定です。 PCを買い換えれば、他の藩も着駅の候補に加えることが出来ますので、それをすれば完全解という保証が出来ます。
計算は九州側から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定理2を前提条件としてですが、それでよいということの証明は、葛西さんが、「最長片道きっぷの経路を求める」の「[3-5] 全探索で（分割編２）最長片道きっぷの経路を求める」中「連結でない」問題への対応、で証明されていらっしゃいますのでご覧ください。
例で示すと、上の例の上から7〜10行目（g＝3)の経路群については最適化が、九州側のみで行われていますが、これが関所定理4を利用している
| 八代,千丁,3920,(千丁=*鹿児島本線=八代=#肥薩線=吉松=#えびの高原線=都城=#日豊本線=隼人=#日豊本線=西鹿児島=#鹿児島本線=八代) 志布志,宮崎,915,(宮崎=*日豊本線=南宮崎=*日南線=志布志) ****,0, 上の経路群は：g=3 関所=1:千丁 関所=2:宮崎 |
これにより、つぎのように3.4
日本全国の計算量＝ 南九州の計算量 + 島原地方の計算量 + ・・・+ 北海道の計算量
関連記事
関連記事[引用4.1]: ^ 整数計画法､ウィキペディア
[引用4.2]: ^ モンテカルロ法、ウィキペディア
[引用4.3]: ^ 連結グラフにおける迷路の解法、ウィキペディア
[引用4.4]: ^ グラフ理論、ウィキペディア
[引用4.5]: ^ オイラーの一筆書き定理、ウィキペディア
5. JR最長経路問題・残る課題とその解決
・予想1は、北海道と本州を結ぶ経路が1である限りは、あまり課題になるとは思いませんが、経路が2になるとその瞬間に「いったいどの藩・計算時間短縮のためには、整数計画法の採用が有効と思われますが、必ず解けると言うわけではないようです。 今回、ループ解は最長経路解となり得ないという証明ができましたので、この採用にある程度の見通しが出てきました。
計算結果を検討してみると、行き止まりの路線を除きすべてのJRの乗り換え駅を通過しています。 その時に、通過していない経路を見てみると、そちらのほうが良さそうだという、明確な感触は見えませんでした。 それを総合すると、正解であるもしくはたかだか1経路改良するのがありえるかなという「予想」をします。
予想2を取り払うにはどうすればよいでしょうか？ 各藩内の経路数を大きくすることにより、切り口の関所数を5程度に抑えることが出来れば可能です。 現状は最大11関所です。
予想2については葛西さんが、「最長片道きっぷの経路を求める」の「[3-5] 全探索で（分割編２）最長片道きっぷの経路を求める」中「連結でない」問題への対応で、問題なく成立していると述べているように見えます。 が、ループ経路を含む場合にも成立しているかどうか、僕にはまだ証明が出来ません。 どなたか、ご教授頂けると助かります。
関連記事
関連記事[引用5.1]: ^ 竜飛海底駅､ウィキペディア
[引用5.2]: ^ 開業・廃止予定線一覧、鉄道の旅・情報館
[引用5.3]: ^ 山田線､ウィキペディア
[引用5.4]: ^ 上野東京ライン､ウィキペディア
[引用5.5]: ^ 留萌本線､ウィキペディア
[引用5.6]: ^ 三江線､ウィキペディア
[引用5.7]: ^ おおさか東線､ウィキペディア
[引用5.8]: ^ 石勝線､ウィキペディア
[引用5.9]: ^ 日高線､ウィキペディア
謝辞
執筆にあたり、次の方々に貴重なご助言をいただきました。 感謝いたします。 なお、敬称は省略させて頂きました。 また､肩書きは2006年当時のものです｡
- SWA[引用2.2] : 葛西隆也
- 静岡大学情報学部: 山田文康
- 静岡大学情報学部: 新谷 誠