最長片道きっぷの経路を求める
[3-5] 全探索で(分割編2)

あらまし

 本州を2分割しただけではまだ計算ができそうにないため、 さらに本州を分割し、4つのエリアにします。 その際に「出戻り」という問題が発生するため、その対策についてもふれます。


目次

  1. 問題の分析
  2. 整数計画法で
  3. 全探索で
  4. これが最長ルートだ!
  5. よくある質問と答え
  6. その他

本州の4分割

 前節では都合よく本州を分割できたので、ほかにもこういう分割がないだろうか、 と考えることになりますが、 さすがに「断面を通過する路線が2本だけ」という分割(で、 有意義なもの)はほかにありません。

「3択」なら、あと2回分割可能

 しかし、ちょっと条件をゆるめて「断面を通過する路線が3本だけ」 という分割を探すと、これは都合のいいものが2カ所で見つかります。 1つは中部地方縦断、もう1つは東北地方横断で、 具体的には以下のようになります(図32・33)。

図32図32 点線の左がエリアD。
図33図33 点線の上がエリアA。

 以下、東北横断線よりも北側をエリアA、中部縦断線より西、 エリアEまでの間をエリアDと呼ぶことにします。


要「出戻り対策」

 「おぉ、これで各エリアがかんたんに計算できるようになった、 もう終わったも同然」…と考えるのは早計です。 断面通過が2本と3本では、ややこしさの度合がちがいます。
 主な問題は、3本の路線があると「出戻り」が可能になるということです。 つまり、たとえばエリアAからいったん出て、その後エリアAに戻って、 またエリアAを出ていく、という経路があり得ます(図34)。

図34図34 エリアAをいったん出て、入って、また出て。 出入口が3つあるとこんなこともできちゃう。

出戻りする? しない?

 この問題を解決するため、以下のような場合分けを行いました。
 以下では、例としてエリアAについて考えます。また、エリアAとその南のエリア (関東甲信越)との3本の出入口に1〜3の番号をつけます。

 まず、「出戻り」のない場合。これは単純です。

 これら3つを計算すれば事足ります。 もちろん、エリアAからの経路を受け取る関東甲信越エリアでも、 同様の場合分けをして最長経路を求めることが必要です。

 次に「出戻り」のある場合。 「どこから出てどこから入るか」の組合せは6通りありますから、

と、単純に6通りを計算します。
 なんだ、それだけ? …いえいえ。

「連結でない」問題への対応

 しかし、よく考えるとちょっとした問題がひそんでいます。 「出戻り」がある場合にはエリア内の経路が連結ではないため、 そのままでは前述のアルゴリズムで探索することができないのです(図35)。

図35図35 エリアごとに見てみると、あれれ、経路が切れてます。 こんな経路をエリア内で探索するにはどうすればいい?

 そこで、 1度目の出口と入口の間にダミーの枝を設けることでこれに対応しました (図36)。 ダミーの枝の長さは何でもいいのですが、ここでは0としておきましょう。

図36図36 赤線で示したダミーの枝を加えれば、 双方ともにエリア内の経路は連結に。

 たとえば「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)。

図37図37 エリアの中の経路がどうなっているかは分からない。 でも、エリア間をどの枝で移動するかは分かっている。実はこれで十分なのです。

 双方の部品からはそれぞれ3本の端子が出ていて、 この3本の端子を介して信号をやりとりします。 お互いの部品からは相手の部品の中身は見えません。
 が、「関東甲信越の1に信号を流すと、 2から出てくる」「エリアAの2に信号を流すと、 3から出てくる」という「出入りに関する挙動(仕様)」 が分かっていればそれで十分なんですよね。 「1→2→3」という順序で出入口を通過していくという条件だけを与えて、 それぞれの部品が内部で最善を尽くしていれば、 2つの部品を合わせたときに全体として最善の結果が得られますから。 あとは、すべての出入り方法(「1→3→2」とか「3→2→1」とか)を尽くして、 その中で最長のものを選べばいいわけです。

 この発想は以後の展開で非常に重要になってきます。



(c) SWA / KASAI TakayaSWA へメールを送る
最終更新: 2000年 3月 1日
簡易包装にご協力ください。