前ページまでに本州を４分割することができましたが、 実際にはこれでは不十分でした。そこで、無理やりもう１回分割を試みます。 この結果、各エリアの最長経路はなんとか計算可能となりました。
紆余曲折のすえ、前ページまでになんとか本州を４分割することができました。
各エリアへの出入り順序を考えるために、
１つのエリアに対して何度か計算が必要になりますが、
ともかく、あとは計算するだけです。そして実際、エリアＡ、エリアＤの計算は、
出入り口を指定するとほぼ一瞬で終わりました。
が…そうです。
首都圏の複雑な路線網を含む関東甲信越エリアでひっかかりました。
関東甲信越エリアの頂点数は79、枝数は129。
エリアＤの規模の３倍程度なので、やばいかな、とはちょっと思いましたが、
いざ計算を始めて、計算時間の見積もりが500日と出たときには、
さすがに落胆しました。これが「組合せ爆発」か、と…。
この計算時間の見積もりはかなりイイカゲンなものです。 具体的には、計算を始めてから半日後に見たとき、 探索の「木」を描いたときに根から10レベル下のところを探索していて、 それより上のレベルの探索状況は開始時と何ら変わりがなかったので、 あと２の10乗倍、つまり1024倍の時間がかかるかな、と予想したものです。
だから、実際には500日もかからず、 もっとずっと早く終わることもあり得るとは思いますが、 ひとまず計算を続行する気にならない結果であったことはたしかです。
この問題を解決するためにやるべきことは分かっています。
関東甲信越エリアをさらに分割することです。
おそらく、路線網の複雑な首都圏を分離すればなんとかなるでしょう。
しかし、複雑な路線網をうまく切り取る方法はなかなか見つかりません。
考えたすえにようやく見つかったのが、以下の５路線を通る分割です。
形式的には、この分割によって本州は５つのエリアに分かれました。 首都圏をエリアＣ、 それ以外の関東甲信越エリアをエリアＢと呼ぶことにすると、 それぞれの頂点数、枝数は以下のようになります。
| エリア名 | 主な地域 | 頂点数 | 枝数 |
|---|---|---|---|
| Ａ | 東北 | 24 | 40 |
| Ｂ | 甲信越 | 34 | 48 |
| Ｃ | 関東 | 46 | 76 |
| Ｄ | 中部・近畿 | 29 | 45 |
| Ｅ | 中国 | 26 | 39 |
こうしてみると、５つに分割したあとも、 やはり首都圏を含むエリアＣの規模の大きさが突出しています。 実際、出入口を１つ決めて計算したところ、 エリアＢは１秒程度で最長経路が出ましたが、 エリアＣでは出入口によっては10分前後かかることもありました。 この場合、試す経路は数億通りにものぼり、 「組合せ爆発」の恐ろしさを見せつける結果となりました。
「ともかく分かれたんだし、それぞれのエリアは計算可能なんだから、
これでいいじゃないか」と思う人もいるかもしれませんが、
５本もの路線を横切って分割したツケを忘れてはいけません。
５本の路線はすべてエリアＢとの出入口なのですが、
これだけ出入口があると、「出戻り」のパターン数が膨大になります。
何せ、「エリアＣに入って、出て、また入って、
また出て」なんてことも十分可能なのです。
とはいえ、
出入口さえ定めれば各エリアの計算はできるようになったのは事実なので、
これから先の問題は、分割して求めた最長経路をどう統合していくか、
そこに絞られます。