← 図22 ３島の関係はこうなっています。
全体の最長経路を求めたければ、各島内の最長経路を求めて、
それをくっつければ十分です。
全探索で求めたのは、実は厳密でない最適解です。
厳密な最適解を求めるという試みは放棄しました。
このページでは、どんなところをサボって厳密さを損ねたのか、
サボることによって何が楽になったのかを説明（弁解？）します。
全探索で LOP の最適解を求めるにあたっては、１つの仮定をおいています。
それは「最長ルートの発着駅は片方が北海道、もう片方が九州である」
というものです。
「そんなのインチキじゃん！」…はい、そうです。スミマセン。
が、本州発着の場合を考えると問題が非常に複雑になるので、
今回は上記の仮定のもとで問題を解き進めることにしました。
なお、上記の仮定が正しいことは整数計画を用いて証明できたので、
全探索によっても真の最長ルートが得られています。もちろんこれは結果論なので、
これをもって「LOP の厳密な最適解を全探索で求めた」とは主張しません。
ともかく、この仮定をおいたことで問題が非常に単純化できます。
その結果、最適解のタイプを限定できることになりました。
ちょっと話が飛躍するので、順を追って説明しましょう。
本州と四国を結ぶ路線は１本しかないので、 「最適解の発着駅が北海道と九州」という仮定をおいたことにより、 四国を考慮する必要はなくなります。また、本州と北海道を結ぶ路線は１本だけ、 本州と九州を結ぶ路線も実質的には１本だけなので、 以下のように問題を容易に３分割することができます（図22）。
← 図22 ３島の関係はこうなっています。
全体の最長経路を求めたければ、各島内の最長経路を求めて、
それをくっつければ十分です。
以上３つの最長経路を個別に求めて、それを最後にくっつければ、 それが全体の最長経路となります。
問題を分割することの大きなメリットは、前にも述べたとおり、 それだけで組合せの数が劇的に減少するということですが、 この場合、（本質的には同じことかもしれませんが） それ以外にもメリットがあります。最適解のタイプが限られることです。
まず本州については、 「北海道への出入口」「九州への出入口」がそれぞれ１本だけで、 最長経路は必ずこれらの枝を通るので、本州部分だけを見れば、 最適解の発着駅は必ず終端駅（それぞれ北海道、九州との接点）となります。 つまり、本州内の最長経路はタイプ Lee の経路に限られます。 本州内がタイプＰということはあり得ません（図23）。
← 図23 本州内の経路は、発着駅がどちらも終端駅。
つまりタイプ Lee です。
また、北海道と九州についても、 「本州への出入口」は１本しかなく、最長経路はここを必ず通るので、 島内の最長経路のうちの少なくとも片方は「本州との接点」という終端駅です。 したがって、北海道、九州の最長経路はタイプ Lee かタイプ Pe のどちらかとなり、タイプ Pn はあり得ません。
このようにタイプが限定できると、
全探索に用いるグラフもずいぶん簡略化することができます。
なお、路線図をグラフに直すことについては「[2-2] 線形計画法で（定義編）」
を参考にしてください。
まず、前節で得られた結果によると、タイプ Pn の経路は北海道、本州、 九州のいずれにおいても最適解とはなり得ません。このことから、 グラフには終端駅と分岐駅があれば十分ということが分かります。 「分岐駅に隣接する駅」は不要です。 これでグラフの規模が非常に小さくなります。
線形計画法を用いたときにも、扱ったのは終端駅と分岐駅のみのグラフでしたが、
あちらは本来必要な「分岐駅に隣接する駅」をグラフから削ったために、
タイプ B やタイプ B8 といった補助的なタイプを考えるなど、
それなりの工夫とややこしい作業が必要でした。
しかし全探索のほうでは、このようなややこしいことを考える必要もなく、
ごく自然にこのシンプルなグラフを用いることができます。
大胆な仮定をおいて厳密な求解をサボったからではありますが、
こんなメリットがあるなら、サボったかいがあるというものでしょう(？)。
これに加え、本州ではさらに大胆なグラフの簡略化ができます。 終端駅に接続する枝はいらないのです（図24）。
← 図24 発着駅ともに決定済みなので、
ほかの終端駅は通ろうにも通れません。
前述のとおり、本州内の最長経路はタイプ Lee しかあり得ないうえ、 発駅、着駅ともにすでに固定されています（北海道、九州との接点）。 終端駅は経路の途中に来られないので、 「北海道との接点」「九州との接点」以外の終端駅は、 この時点で最長経路に含まれないことが確定してしまいます。 ですから、終端駅とそれに接続する枝をグラフから削除しても、 算出される最長経路には何も影響を及ぼしません。