← 図31 意外にも横切る路線は２本だけ。
点線の左側が「エリアＥ」です。
北海道と九州はともかく、 本州を全探索のアルゴリズムでまとめて解くのは無謀です。 そこで、問題を分割することを考えます。 このページでは、非常に都合のいい分割例を１つ扱います。
前ページまでに全探索のアルゴリズムを説明しましたので、
いよいよ実際に最長経路を探してみましょう。
前述のとおり、問題は北海道、本州、九州の３つに容易に分割できます。
この３つのうち、まずは規模の小さい北海道、九州についてやってみました。
北海道は長万部、九州は小倉を発駅として与え、
考え得る経路を前述のアルゴリズムで列挙したのです。
その結果、どちらも１秒としないうちに最長経路が得られました。
具体的な経路については「[4] これが最長経路だ！」を参照してください。
このうち、規模の大きい九州について計算結果を見てみると、
列挙した最長候補は16126通り。意外と少ないものです。
北海道と九州は、はっきりいって全探索でも楽勝でした。 とすると、本州も一発で…と考えるのはさすがに無謀ですね。 規模が２倍だから計算時間も２倍、という世界ではないのですから、 そのままでは確実に組合せの数が爆発します。 何らかの方法で問題を分割せねばならないでしょう。
なお、以下では本州内の経路として「東→西」の向きのみを考えます。 これは、北海道の最長経路がタイプＬ、 九州の最長経路がタイプＰである（つまり九州側を発駅にできない） ことが前節で判明したからですが、かりにそうでないとしても、 本州内はタイプＬ＝逆方向も可能なので、どちら向きを考えても変わりはありません。
さて、どこをとってもたくさんの路線が走っている本州。 これをどうやって分割したものかな、と地図を眺めていると、 ちょっと意外なことに気付きます。兵庫県中部を南北に縦断する線を引くと、 この線を横切る路線はわずか２本しかないのです（図31）。 より具体的には、
の両方を通るように兵庫県を縦断する線を引くと、 他の路線がこの線をまたがないようにすることができます。 以後、この縦断線以西をエリアＥと呼びます。
← 図31 意外にも横切る路線は２本だけ。
点線の左側が「エリアＥ」です。
この「横切る路線が２つだけ」というのはかなり重大な事実です。
関西以東からエリアＥへの出入口が２つしかなく、
それぞれ１回ずつしか通れないうえ、九州への入口があるのはエリアＥなので、
いったんエリアＥに入ったら、もう関西以東に戻れないのです。
そして、「加古川・姫路間」「福知山・和田山間」
のどちらか１つだけを必ず通らなければならないことも分かるでしょう。
このことを利用すると、
本州全体の最長経路は以下の２つのうちの長いほうであることが分かります。
関西以東、エリアＥについて、「加古川・姫路間を通る場合」 「福知山・和田山間を通る場合」の２通りの最長経路を求めることになります。 ここで青森は北海道との接点、幡生（山口県下関市）は九州との接点です。
これを見て、「解くべき問題が増えてかえって大変じゃないか！」
なんて思っている人はいませんか。たしかに一見めんどうですが、
前にも書いたとおり、問題の規模が少しでも小さくなれば、
組合せは劇的に減るので、２通りの場合を考えるにしても、
分割後のほうがずっと計算は早く済みます。
たとえば、分割によって２方向への分岐が10個減っただけで、
計算の手間が２の10乗分の１（つまり1024分の１）になるんです。
1000日かかっていた計算が１日で、
1000年かかっていた計算が１年でできるようになると考えると、
劇的というしかありません。
せっかく分割できたのですから、実際に最長経路を求めてみましょう。
といっても関西以東はまだ大きすぎるので、エリアＥだけです。
エリアＥの最長経路を前述のアルゴリズムで求めると、
姫路発にしろ和田山発にしろ、またも１秒以内で最適解が求まりました。
これで、あとは青森から兵庫県までの最長経路が求まればよいことになりました。