最長片道きっぷの経路を求める
[3-6] 全探索で(泥沼編)

あらまし

 前ページまでに本州を4分割することができましたが、 実際にはこれでは不十分でした。そこで、無理やりもう1回分割を試みます。 この結果、各エリアの最長経路はなんとか計算可能となりました。


目次

  1. 問題の分析
  2. 整数計画法で
  3. 全探索で
  4. これが最長ルートだ!
  5. よくある質問と答え
  6. その他

来た! 「組合せ爆発」

 紆余曲折のすえ、前ページまでになんとか本州を4分割することができました。 各エリアへの出入り順序を考えるために、 1つのエリアに対して何度か計算が必要になりますが、 ともかく、あとは計算するだけです。そして実際、エリアA、エリアDの計算は、 出入り口を指定するとほぼ一瞬で終わりました。
 が…そうです。 首都圏の複雑な路線網を含む関東甲信越エリアでひっかかりました。 関東甲信越エリアの頂点数は79、枝数は129。 エリアDの規模の3倍程度なので、やばいかな、とはちょっと思いましたが、 いざ計算を始めて、計算時間の見積もりが500日と出たときには、 さすがに落胆しました。これが「組合せ爆発」か、と…。

 この計算時間の見積もりはかなりイイカゲンなものです。 具体的には、計算を始めてから半日後に見たとき、 探索の「木」を描いたときに根から10レベル下のところを探索していて、 それより上のレベルの探索状況は開始時と何ら変わりがなかったので、 あと2の10乗倍、つまり1024倍の時間がかかるかな、と予想したものです。
 だから、実際には500日もかからず、 もっとずっと早く終わることもあり得るとは思いますが、 ひとまず計算を続行する気にならない結果であったことはたしかです。


泥沼の「断面5本通過」へ

 この問題を解決するためにやるべきことは分かっています。 関東甲信越エリアをさらに分割することです。 おそらく、路線網の複雑な首都圏を分離すればなんとかなるでしょう。
 しかし、複雑な路線網をうまく切り取る方法はなかなか見つかりません。 考えたすえにようやく見つかったのが、以下の5路線を通る分割です。

各エリアの概要

 形式的には、この分割によって本州は5つのエリアに分かれました。 首都圏をエリアC、 それ以外の関東甲信越エリアをエリアBと呼ぶことにすると、 それぞれの頂点数、枝数は以下のようになります。

エリア名 主な地域 頂点数 枝数
東北 24 40
甲信越 34 48
関東 46 76
中部・近畿 29 45
中国 26 39

 こうしてみると、5つに分割したあとも、 やはり首都圏を含むエリアCの規模の大きさが突出しています。 実際、出入口を1つ決めて計算したところ、 エリアBは1秒程度で最長経路が出ましたが、 エリアCでは出入口によっては10分前後かかることもありました。 この場合、試す経路は数億通りにものぼり、 「組合せ爆発」の恐ろしさを見せつける結果となりました。

「断面通過5本」がもたらすもの

 「ともかく分かれたんだし、それぞれのエリアは計算可能なんだから、 これでいいじゃないか」と思う人もいるかもしれませんが、 5本もの路線を横切って分割したツケを忘れてはいけません。 5本の路線はすべてエリアBとの出入口なのですが、 これだけ出入口があると、「出戻り」のパターン数が膨大になります。 何せ、「エリアCに入って、出て、また入って、 また出て」なんてことも十分可能なのです。
 とはいえ、 出入口さえ定めれば各エリアの計算はできるようになったのは事実なので、 これから先の問題は、分割して求めた最長経路をどう統合していくか、 そこに絞られます。



(c) SWA / KASAI TakayaSWA へメールを送る
最終更新: 2000年10月11日
簡易包装にご協力ください。