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