前ページまでに、各エリアへの出入りパターンを1つ定めれば、 すべてのエリアの最長経路が計算できるようになりました。そこでこのページでは、 すべての出入りパターンについて全エリアの計算結果を統合し、 いよいよ本州の最長経路を求めます。
そんなわけで、あとは5つのエリアを統合するだけです。 統合の作業自体は、各エリアの距離を足すだけなので単純ですが、 すべての「出戻り」パターンを尽くす必要があり、 ここに注意を払う必要があります。
まず、各エリアの接続状況がどうなっているかを確認しましょう(図38)。 カッコ内の数字は、エリア間を移動する枝につけた番号です。
このうち、エリアDについてすべての出入りパターン
(B・D間が出戻りの有無も考慮して9通り、
D・E間が2通りなので計18通り)をあらかじめ計算したところ、
B・D間をどのように行き来しても、D・E間は12番(福知山・和田山)
を通過したほうが最長経路が長くなることが分かりました。
このため、12番の枝を使うことは確定します。
また、これにより、全体の最適解のうちエリアEの部分は確定しました。
以上により、エリアD・E間についてはこれから先は考えません。
本州内の最長経路はエリアAから始まり、エリアEで終わります。
前述のとおりエリアEはもう考えなくていいので、
エリアEに接するエリアDまでの経路をこれから考えるわけですが、
さて、各エリアの通過順序、
およびエリア間の枝の使いかたは全部で何通りあるでしょう?
この問題自体は、原理的には何も難しいことはありません。
手で計算するなら、「A・B間で『出戻り』がない場合で、
B・C間で『出戻り』が2回ある場合で、
C・D間で『出戻り』が1回ある場合」などと場合分けをして、
あとはそれぞれのエリア間で何通りあるかを計算、かけ合わせ、
最後にすべての場合を合計するだけです。
が、これだけ枝の数があると、答えはけっこうな数になります。
実際にやってみたところ、実に71937通りと出ました。
手計算のほかに、プログラムを書いて確かめてもみましたが、
やはり71937通りあるようです。
といっても、
すべてのエリアに対して70000回以上の計算が必要なわけではありません。
71937回の計算が必要なのはエリアBだけです。
というのは、エリアA、C、DはエリアBとのみ接しているからです。
たとえばエリアAは、エリアBとの間に3本の「端子」を持っているだけです。
ですから、エリアAの内部に関する計算は、
前にふれたとおり9通り(「出戻り」のないときが3通り、
1回「出戻り」するときが6通り)だけで済みます。
以下、同様に計算すると、各エリアの計算回数は以下のようになります。
エリアBはすべてのエリアと接しているので、 全体の「出戻り」パターン1つに対してエリアBの出入り方法1つが対応することとなり、 結局、71937通りの出入り方法が存在します。
これでようやく、本州全体の最長経路を全探索で計算できるようになりました。
実際に計算してみると、エリアAとエリアDはすぐに終わります。
1回の計算が1秒程度であるうえ、出入りのパターンもわずか9通りですから、
全部合わせても30秒もかかりません。
問題はまずエリアBです。1回の計算はだいたい1秒以内でできますが、
何せ71937回も計算しなくてはなりません。これには半日程度を要しました。
また、エリアCは路線網が複雑なので、1回に数分、
多いときでは10分以上を要しました。
このため、70通りすべてを計算するにはやはり約半日弱かかりました。
まぁ、当初予想の500日とはくらべものになりませんが、
整数計画では(解き直しはあるものの)2分で答えが出るんですから、
雲泥の差ですよね。
ともかく、こうして得られた各エリアの答えを71937通りの方法で組み合わせ、
71937通りの最長経路候補を作ります。
その中で最長のものが本州内の最長経路です。
組み合わせの実例を1つ挙げましょう。
たとえばエリアBの通りかたが「1→5→7→9→11→8→4→3→2→10」だったとき、
対応する他エリアの通りかたは以下のようになります。
それぞれのエリアが、自分と関係のある枝だけを取り出しているわけです。
で、這々の体で計算を終えてみたら、
「最長経路は0km」なんて答えがけっこうあるんです。え、どうして?
たとえば、エリアAでは「2→3→1」「2→1→3」の2つについて、
最長経路が0kmとなりました。
つまりこのパターンは実行不可能ということです。
とある発表会のあとで指摘されたのですが、 ここで結果が0kmとなったのは単なる全探索プログラムの仕様でした。 全探索プログラムでは、 見つかった中で最長の経路の距離を保持するための変数を用意していますが、 この変数の初期値(仮の最大値)がたまたま0であり、 探索したら発売規則を満たす経路が1つも見つからなかったので、 初期値である0が出てきた、というだけの話です。 この変数を−1で初期化しておけば結果は−1kmと出たはずで、 「0km」の「0」に特に意味はありません。
そう言われて見てみると、たしかに実行は無理そうです。 真ん中からいったん出て、端からふたたび入って、反対の端からまた出るのですから、 立体交差がないとどこかでぶつかってしまうと直観的に分かりますね(図39)。 たしかにエリアA・Bには、グラフを平面上で表しきれない箇所、 つまり立体交差する箇所はありません(エリアC・Dには存在します)。
今にして思うと、 エリアAでこのように実行不可能なものがあると分かっていたのですから、 エリアBの計算回数を大ざっぱにいって9分の7にできたのでした。 エリアAとの間を「2→3→1」 と行き来することはエリアAの都合で不可能なのですから、 それに対応するエリアBの経路はもはや試す必要がないわけです。
こうした「実行不可能なパターン」はエリアBでも多く、
71937通りのうち実に69766通りが実行不可能でした。
統合すると、この実行不可能なパターンはさらに増えるので
(4エリアのうち1つでも実行不可能なら、全体として実行不可能!)、
結局、実際に出てきた「本州の最長候補」はわずか883通りでした。
で、その中で最長のものは…次ページでじっくりご覧ください。