佐藤和夫> 旅>JR最長経路問題>
> 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.4
将来新幹線が青函トンネルを越え、かつ在来線も残れば、複数経路が北海道と本州間に出来るため、稚内は最長行き止まり経路で無くなります。 こうなれば、最長が四国の若井から岡山、2番が新大村から新鳥栖､3番が北海道の稚内から新旭川（255.7営業キロ）
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時間に短縮されました。
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 |