全探索という方法について、その特徴を明らかにします。 全探索は「遅いが単純」な方法で、 問題のサイズを小さくできれば有効な手段であるということを示しています。
これからやろうとしている「全探索」とは、文字どおり、 考えられる経路を全部列挙して、その中から一番長い経路を探そうという、 非常に単純な方法です。 整数計画法のように、見込みのないものを早々に切り捨てることはせず、 明らかに見込みのないものまで列挙します。
以上を読めば分かると思いますが、
全探索の欠点は莫大な時間がかかるということに尽きます。
たとえば分岐駅が１つあれば、そこから先の経路は少なくとも二手に分かれます。
かりに発駅が１つ決まっても、分岐駅にたどり着くたびに経路が二手に分かれれば、
考え得る経路の総数は爆発的に増えていきます。
分岐駅が100あれば経路の数は単純に考えて２の100乗。
これは10進数にして30ケタほどの数であり、１秒間に１兆通りの経路を列挙できても、
なお何百万年(！)単位で時間がかかります。
実際には、分岐駅をたどっていけば終端駅にもぶつかるわけで、
接続駅１つで経路２倍、という計算は必ずしも正確ではありませんが、
実際に全探索をやってみたら首都圏だけで数億通りを試すはめになったので、
これを全国に拡大すればどうなるかは自明でしょう。
１回１回はたったの２倍でも、何回も繰り返せばそれは膨大な数になる…
この恐ろしさは「今日は米１粒でいいから、明日は２粒、
あさっては４粒くれ」というとんち話を思い出せば分かるとは思いますが、
実は私、実際に計算を始めるまでは
「そうはいってもコンピュータの進歩も指数関数的だし」などと楽観視してました。
と、ここまで書くと全探索にはメリットがなさそうに見えますが、
そうでもありません。
方法が単純であるという、非常に大きなメリットがあります。
実際、
マトモな方法である「整数計画を用いた解法」にひととおり目を通した人の中には、
「最長片道きっぷの経路を出すにはこんなにヤヤコシイことをしなければならないのか」
と落胆した人もいるのではないかと思います。
整数計画問題を解く過程はソルバー任せなので、
この部分をブラックボックスと考えることにしても、
定式化には少なくとも数学への「耐性」がある程度必要です。
私自身も、２年前にはこんな手法を試す気にはならなかったでしょう。
かりにこれらの条件をクリアしたとしても、ソルバーがふつうの人に入手できるか、
という問題があります。
整数計画問題を解けるソルバーは一般的なアプリケーションソフトとはいえず、
しかも高価で、研究者や一部の企業以外では入手は困難です。
フリーのソルバーもありますが、性能の面で「売り物」にかなうはずもなく、
規模の大きいこの問題ではけっこう苦しいものがあります。
そんなわけで、
整数計画を用いた解法で実際に解を求めることのできる人はかなり限られてきますが、
単純な全探索ならだいじょうぶ。
コンピュータと多少のプログラミング能力があれば解答可能なのです。
また、この問題に限った話ですが、
全探索には「解き直し」が不要というメリットがあります。
整数計画を用いた解法を理解した人なら分かると思いますが、
整数計画では、線形の不等式で制約式を書ききることができず、
一度解いただけでは条件を満たさない解がしばしば出てきます。
そういった解を除去するためには、
出てきた解を見ながら何度も何度も解き直す作業が必要で、
これが主に大変なところでした。
しかし、全探索ならこの作業は不要です。
ふつうのプログラム言語でプログラムを組むのですから、
たいていの条件は記述することができます。
ですから、条件を満たさない解は確実にブロックできるのです。
このため、プログラムとデータさえ整えば、
あとはコンピュータに解かせておしまい、ということが可能になります。
こき使われるコンピュータはたまったものではありませんが、人間は非常に楽です。
「でも、全探索じゃ私の生きているうちには答えが出ないんじゃないの？」
…たしかに、何の工夫もなしに全探索をやったらそうなります。
少なくとも、問題が解けるより CPU の寿命が来るほうが先でしょう。
が、工夫しだいでは全探索で解けなくもありません。
最も有効な工夫は問題を分割することです。
「問題を分割しても総量は変わらないから同じことでは？」
…いえ、この問題に限ってはそんなことはありません。
問題が小さくなればなるほど、加速度的に解きやすくなるのです。たとえば、
分岐駅が100個ある問題をそのまま解けば２の100乗通りを列挙しなければなりませんが、
「分岐駅が50個ある問題」２つに分割できれば、
それぞれの問題で２の50乗通りを列挙すれば済みます。
２の50乗通りを２回列挙しても、合計で２の51乗通り。分割前と全然ちがいます。
さらに「分岐駅が25個ある問題」４つに分割できたなら、
４問題の合計で２の27乗通りにまで減ります。２の27乗は約１億ですから、
このぐらいなら現在のコンピュータでもわりあい容易に列挙することができます。
ですから全探索では、問題を細かく分割できれば解けたも同然なのです。
具体的にどうやって問題を分割するかについては、追い追い考えていきます。