本州を2分割しただけではまだ計算ができそうにないため、 さらに本州を分割し、4つのエリアにします。 その際に「出戻り」という問題が発生するため、その対策についてもふれます。
前節では都合よく本州を分割できたので、ほかにもこういう分割がないだろうか、 と考えることになりますが、 さすがに「断面を通過する路線が2本だけ」という分割(で、 有意義なもの)はほかにありません。
しかし、ちょっと条件をゆるめて「断面を通過する路線が3本だけ」 という分割を探すと、これは都合のいいものが2カ所で見つかります。 1つは中部地方縦断、もう1つは東北地方横断で、 具体的には以下のようになります(図32・33)。
以下、東北横断線よりも北側をエリアA、中部縦断線より西、 エリアEまでの間をエリアDと呼ぶことにします。
「おぉ、これで各エリアがかんたんに計算できるようになった、
もう終わったも同然」…と考えるのは早計です。
断面通過が2本と3本では、ややこしさの度合がちがいます。
主な問題は、3本の路線があると「出戻り」が可能になるということです。
つまり、たとえばエリアAからいったん出て、その後エリアAに戻って、
またエリアAを出ていく、という経路があり得ます(図34)。
この問題を解決するため、以下のような場合分けを行いました。
以下では、例としてエリアAについて考えます。また、エリアAとその南のエリア
(関東甲信越)との3本の出入口に1〜3の番号をつけます。
まず、「出戻り」のない場合。これは単純です。
これら3つを計算すれば事足ります。 もちろん、エリアAからの経路を受け取る関東甲信越エリアでも、 同様の場合分けをして最長経路を求めることが必要です。
次に「出戻り」のある場合。 「どこから出てどこから入るか」の組合せは6通りありますから、
と、単純に6通りを計算します。
なんだ、それだけ? …いえいえ。
しかし、よく考えるとちょっとした問題がひそんでいます。 「出戻り」がある場合にはエリア内の経路が連結ではないため、 そのままでは前述のアルゴリズムで探索することができないのです(図35)。
そこで、 1度目の出口と入口の間にダミーの枝を設けることでこれに対応しました (図36)。 ダミーの枝の長さは何でもいいのですが、ここでは0としておきましょう。
たとえば「1から出て2から入って最後に3から出る」場合には、
出入口1と出入口2の間にダミーの枝を作ります。
そして、「この枝を1→2の順序で通り、最後に3から出ていくものだけを出力する」
という条件を全探索のプログラムに付け加えます。これで、
「1→2→3」という順序で出入口を通過していく経路だけが出てきます。
ダミーの枝にあたる部分が実際にどんな経路になるかは分かりませんが、
少なくとも1から2までの経路はエリアAではなく、
となりの関東甲信越エリアですから、エリアAの関知するところではありません。
今は「分業」で計算しているのですから、エリアAを計算するときには、
「何か分からないけど、とりあえず1から2へは外部で経路が用意されているようだ」
と思って計算を進めればよいことになります。
同様に、これを受け取るエリアでは、 出口と2度目の入口の間にダミーの枝を作ればいいのです。 この場合、「1→2→3」という順序で枝を通るので、 関東甲信越エリアのほうでダミーの枝を作るのは2と3の間。 1から入って、ダミーの枝を「2→3」 の順序で通るような経路のうちで最長のものを探せばいいのですね。 例によって2と3の間の経路を考える必要はありません (エリアAのほうで考えてくれるでしょう)。
分かりにくい人のために、 「エリアA」「関東甲信越エリア(図37では便宜的にエリアBと記す)」 がそれぞれ独立の電子部品であると考えてみましょう(図37)。
双方の部品からはそれぞれ3本の端子が出ていて、
この3本の端子を介して信号をやりとりします。
お互いの部品からは相手の部品の中身は見えません。
が、「関東甲信越の1に信号を流すと、
2から出てくる」「エリアAの2に信号を流すと、
3から出てくる」という「出入りに関する挙動(仕様)」
が分かっていればそれで十分なんですよね。
「1→2→3」という順序で出入口を通過していくという条件だけを与えて、
それぞれの部品が内部で最善を尽くしていれば、
2つの部品を合わせたときに全体として最善の結果が得られますから。
あとは、すべての出入り方法(「1→3→2」とか「3→2→1」とか)を尽くして、
その中で最長のものを選べばいいわけです。
この発想は以後の展開で非常に重要になってきます。