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