日記帳だ! with Tux on Libserver

二度目の大改造!! 日記帳…か?を継承し、より柔軟でパワフルなBlogに変身しました。

RSSに対応しています。リンク・コメント・トラックバックは自由にしていただいてほぼ問題ありません。
RSS購読方法、僕のリンク・コメント・トラックバックについての考えを読むことをおすすめします。

大阪市営地下鉄でLOP!

大阪市営地下鉄で取り得る最長ルートはどんなルートかという問いはたいへん難しい。

まず、どんな形のルートかも予想も付かない。

JRの最長ルートなら、北海道から本州を経て九州へ至るルートという想像は付く。

近鉄にしても八木~中川は含むことぐらいはわかる。けど大阪の地下鉄はそうもいかない。

結局これこそ総当たりで当たるしかないことなんですね。


最長ルートを求めた先行事例としては葛西隆也さんらの求めたJRの最長片道きっぷが有名ですね。

最長片道きっぷの経路を求める (SWAのWebページ)

ここではJRの最長片道きっぷのルートについて整数計画法および全探索で求めたことが書いてあります。

僕はソルバーなんて持ってないから全探索の方法を参考に求めてみようと思った。

ところがここには重大なことが書かれていた。

それは北海道から本州を経て九州へ至るルートが最長であるという仮定です。

どうもそうしないとやってられないらしい。まぁそれもそうだ。

これを使えば北海道区間は長万部からの最長ルート、九州区間は小倉からの最長ルートを考えればいいなどなる。

ところが、大阪の地下鉄は全くそういうことがわからない。なのでスタート地点はどこかわからないと。


はて、どうしたものか。というわけで話を戻すことにしました。

問題の分析の章で最長ルートにはLOPの三類型があると書いてある。

Lの場合は発駅・着駅ともに終端駅が最長のはずであるが、Pの場合はそうではないこともあるとある。

Pの場合は終端駅が発駅になる場合(Pe)と、分岐駅の1つ隣が発駅になる場合(Pn)があると書いてある。

だから千日前線しか通ってない鶴橋が最長ルートの発駅になることはあり得るんですね。

分岐駅である谷町九丁目の隣で今里の隣でもあるから。

ただ、JRの最長ルートを全探索で求めるときには分岐駅の1つ隣が発駅になることを考えて求めることはやらなかったわけです。

しかし今回は一応考えないとまずいかなと思った。


というわけで路線を定義していく。

分岐駅とその隣の駅で区切って、区切られたそれぞれの区間の距離を入力していく。

梅田,淀屋橋,13

0.1kmを1とする単位で距離は入力していった。

西梅田・梅田・東梅田はそれぞれ別々の駅として書いて、西梅田・梅田間、梅田・東梅田間をそれぞれ0kmの線路で結んでおいた。

そうやって区切っても73個で済んだ。

ここから駅名を読み取って、登録されてなかった駅名だけ登録して、それでそれぞれの区間を読み込んで、それから全探索するプログラムを書いた。

全探索の方法はJRの方法と一緒ですね。二度同じ駅を通るか終点にたどり着いたら終わりってルールね。

初めこれをPerlで書いてたのだがどうにも遅いのでC++で書き直した。

それで登録された駅全てからの最長ルートを求め、その中で最長のルートを答えにした。


それで求まった答えだが、LOPでいえばLだった。

なかもず―(御堂筋線)→天王寺―(谷町線)→谷町九丁目―(千日前線)→今里―(今里筋線)→緑橋―(中央線)→森ノ宮―(長堀鶴見緑地線)→蒲生四丁目―(今里筋線)→太子橋今市―(谷町線)→谷町六丁目―(長堀鶴見緑地線)→長堀橋―(堺筋線)→動物園前―(御堂筋線)→大国町―(四つ橋線)→住之江公園―(ニュートラム)→コスモスクエア―(中央線)→阿波座―(千日前線)→なんば―(御堂筋線)→江坂

結局のところなかもず~江坂という御堂筋線を縦断すれば済むようなルートが出てきた。

距離で言うと78.9kmです。これは営業キロで実際の距離は違ったりするらしいのけどささいな問題よね。

ちなみにL型ならその特性上逆に乗っても片道きっぷにはなることができるので江坂からなかもずのルートでもいいですね。

それを路線図で表してみた。(元とした路線図 : 大阪市営地下鉄・ニュートラム路線図 (大阪市交通局))
大阪市営地下鉄最長ルート

大国町となんばとか谷町六丁目と谷町九丁目とか隣の駅であるところをぐるっと回ってるなというのがよくわかる。


乗ってみたいと思った人もいるかも知れない。

そのためには運賃が必要ですね。

運賃は江坂~なかもずの運賃でOKです。最短距離で計算した運賃で遠回りしてもOKのようです。

具体的には360円で済みますね。

ついでに北大阪急行の最長ルートにも挑戦してはいかがでしょうか。

江坂から千里中央までの一本道ですね。たった120円で済みます。あわせて480円ですね。

御堂筋線に乗って終点まで乗るだけで達成できますね!


しかしまぁ、こういうのはコンピュータで計算してみないとなかなかわからんもんです。

初めはO型になるんじゃないかとか思ってたんですけど、結局の所L型になりましたからね。

計算してみて初めてわかったことですね。


Author : Hidemaro
Date : 2010/03/11(Thu) 23:59
コンピュータ・インターネット | Comment | trackback (0)

Tools