最長片道きっぷの経路を求める
[1] 問題の分析

このページのあらまし

 最長片道きっぷの経路を求める問題を解くにあたって、 解きかたを決める手がかりになるよう、問題を少し分析します。


目次

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

LOP と呼んでください

 突然ですが、以下では、 最長片道きっぷの経路を求める問題を LOP(Longest Oneway-ticket Problem)と呼ぶことにします。 造語ですが、万が一これが定着したらうれしいなぁ。
 そして、発売条件を満たす経路を LOP の許容解、 許容解の中で最長のものを最適解と呼ぶことにします。 つまり、現在の目標は「LOP の最適解を求めること」です。


片道乗車券のトポロジー的分類

 まず最初に、導入部でちょっと触れた「片道乗車券の発売条件」 をもう少し詳しく考察してみます。そして、 どのような形状の経路なら片道乗車券が発売されるのかを明らかにします。 ちょっとエラソーに言えば「トポロジー的分類」です。

「一本道」だけじゃない!

 「片道乗車券」と聞くと「一本道」というイメージが浮かぶかもしれません。 しかし、必ずしもそうではありません。発売条件をよく読むと、 もっと別の形の片道乗車券も発売されることが分かってきます。

 前述のとおり、 ある経路に対して片道乗車券が発売されるための条件(発売条件)は、 その経路に対して

が同時に成り立つときのみでした。そして、この条件を満たす限りは、 任意の経路に対して片道乗車券が発売されます。
 この発売条件を満たすものとして、 まず真っ先に考えられるのは、同じ駅を2度通らない「一本道」の経路です。 このような経路が発売条件を満たすことは明らかです。
 が、同じ駅を2度通ったら必ずダメ、というわけでもありません。 発売条件で禁止されているのは「環状線一周を超えるとき」なので、 ちょうど「環状線一周」なら片道乗車券になるのです。 つまり、同じ駅を2度通っても、 2度目にその駅に到達したところで経路を打ち切れば、 それは発売条件を満たすのです。
 ですから、たとえば山手線一周(円形)は片道乗車券になりますし、 横浜から品川に至り、山手線を一周してまた品川に至る「6の字」 形の経路も片道乗車券になります(図1〜3)。

図1図1 これは単純な一本道。
図2図2 ぶつかっても、そこでやめればOK。
図3図3 でも、さらに続けるのはダメ。

 そのいっぽう、一般的な「一筆書き」では許容されている「8の字」「日の字」 は発売条件を満たしません。たとえば「8の字」に関して言えば、 「8」の中心で4本の線が交わっているので、 この場所を少なくとも2回訪問しますが、発売条件は「2回目の訪問のあと、 さらに先に進むこと」を許していません(図4)。

図4図4 「一筆書き」とは微妙にちがうんです。注意。

発売条件を満たすのは3タイプ

 以上から、発売条件を満たす経路、すなわち片道乗車券の発売される経路は、 トポロジー的に分類すると以下の3通りになります。 3種類をそれぞれアルファベットに見立て、名前をつけてみました。 これらの命名は宮代くんによるものです。

 L、O、Pときれいにそろいました。これが「LOP」の由来の1つです(図5)。

図5図5 きれいにオチがつきました。

タイプPの注意点

 このうちタイプPについては注意が必要です。 タイプPの経路は逆向きにできないのです。
 たとえばさきほどの例ですが、「横浜→品川→山手線一周→品川」 というタイプPの経路は発売条件を満たしていました。 品川駅を2度通るものの、2度目に通ったところで経路が終わっているからです。 しかし、これを逆向きにして「品川→山手線一周→品川→横浜」とすると、 発売条件を満たさなくなります。 品川を2度通るのに、2度目の品川で経路を打ち切っていないからです(図6、7)。

図6図6 こっち向きならOKですが…
図7図7 逆向きは×。品川で打ち切らねばなりません。

最適解はどんな形?

 片道乗車券が発売できる以上、その経路はタイプL、タイプO、 タイプPのいずれかである、ということが分かりました。 したがって、最適解はこの3つのうちのどれかということになります。
 が、実際にはもっと最適解の候補を狭めることができます。 この節では、最適解がどのタイプで、発着駅がどういった駅か、 ということを明らかにします。

タイプOは考えなくていい!

 まず、JRの具体的な路線図を見ると、 明らかにタイプOの経路は最適解になれないということが分かります。
 JRの路線図全体はタイプOではありませんし、JRの路線図は「連結」で、 ある部分が他の部分から孤立しているということもありません。 したがって、もしタイプOの経路が1つあれば、 それに1本「ひげ」を加えたタイプPの経路が最低1つは必ず作れます。 当然、そのタイプPの経路のほうが距離は長くなるので、 タイプOには出番がないことになります。

タイプLの発着駅

 また、残ったタイプLやタイプPにしても、どこを発駅にしてどこを着駅にするか、 ということに関してはそれほど選択の余地がありません。 具体的には、最適解の発着駅としては、 行き止まりの駅、分岐駅、分岐駅に隣接する駅のいずれかだけを考慮すればよいのです。

 まずタイプLに関して、 最適解の発着駅がどのような場所になるかを考えてみましょう。
 最適解というからには、 いかなる方法をもってしてもそれより長い経路を作れません。 したがって、最適解の発着駅は、 「そこから一歩でも進むともうダメ」という「限界の駅」になっているはずです。
 そのような駅として考えられるのは、 そこから一方向にしか線路の出ていない駅、つまり行き止まりの駅です。 以後、これを終端駅と呼ぶことにします。

タイプPの発着駅

 次にタイプPに関してです。 着駅は明らかに、3方向以上に線路の出ている駅(以後、 これを分岐駅と呼びます)しかあり得ませんが、 発駅に関しては選びようがあります。
 タイプLと同じく、終端駅は最適解の発駅となり得ますが、 その他の駅にも可能性はあります。 その駅から先に、まだ通ったことのない線路が残っているけれど、 1駅延長すると発売条件を満たさなくなる(タイプPでなくなる)、という場合です。 具体的には、分岐駅に隣接する駅が最適解の発駅となることが考えられます。 1駅延長すると、あとで通る分岐駅に行き当たってしまい、 タイプPでなくなるというわけです(図8、9)。

図8図8 これはNGですが…
図9図9 1駅だけ短くすればOK。 だから「ぶつかる1駅手前から出発する」という最適解もあり得るのです。

 このように「1駅延長するとタイプが変わる」ということはタイプLでもあり得るのですが、 タイプLの場合、タイプが変わったとしてもタイプPになるだけですから、 1駅延長しても依然として発売条件を満たしています。 したがってタイプLでは分岐駅の隣接駅発を考慮する必要がありません。

まとめ、そして新たな表記法

 以上の考察をまとめると、 最適解は以下の3つのうちのどれかであることが分かります。

 ここで「タイプ Lee」などの新たな表記法を導入しましたが、 「e」は終端駅、「n」は分岐駅に隣接する駅を表すと考えてください。 たとえばタイプLのうち、発駅が「e」、着駅が「e」のものがタイプ Lee です。
 前述のとおり、タイプ Len なんてのは考えなくてかまいません。



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