最長とは？/ レイク
[ 320] ＥＸＣＥＬによる最長片道ルート探索
[引用サイト] http://longest-route.hp.infoseek.co.jp/
|
「最長片道切符」とは、同じ駅を二度通らずになるべく遠回りする一筆書き切符で最長ルートのもののことである。 この時の最長ルートの探索は、全国を地域ブロックに分割し、各ブロックの最長ルートを求め、これを合算するという手法がとられたという。北海道と九州は、本州から切り離して計算し、また本州も列島方向に走る鉄道線が少ない地域で切断し、4ブロックに分割したらしい。 手計算で、少し複雑な最長片道ルート探索を行う場合、「ブロック分割」の考え方は必須のものであると思われる。しかし、実際に、探索過程と結果を示したものを私は見たことがない。 宮脇俊三氏の「最長片道切符の旅」（新潮文庫）では、電卓だけで最長片道ルート探索に挑戦しており、その時の様子について、「こういうのを順列組合せというのかどうかも知らないが、やってみると単位数が二倍になると組合せ数はその二乗くらいに増えるようであった。だから単位が九個しかない四国など簡単で一瞬にできてしまうし、四六個の北海道も六二個の九州もさしてむずかしくはない。（中略）けれども、国電区間が多く、線路の錯綜した東京付近から関東、中部にかけてはあまりに組合せが多すぎて、可能性のすべてを探るには一週間や一〇日でやれることではなかった。」と記している。 そこで、「ブロック分割による手計算での最長片道ルート探索」では、「さしてむずかしくはない」とされている北海道と九州の最長片道ルート探索について、実際の探索過程と結果を示すこととしたい。 2000年1月、当時東大大学院生であった葛西隆也氏は、整数計画法と全探索法によって最長ルート探索を行った。この結果は「最長片道きっぷの経路を求める」という表題でインターネット上に公開されており、これがおそらく最長ルート探索について最も丁寧に解説したものである。2004年5月のＮＨＫ番組「列島縦断 鉄道12000キロの旅−最長片道切符でゆく42日−」も彼の手法を使って東大鉄道研究会が行ったとのことである。 「ＥＸＣＥＬによる最長片道ルート探索」では、ＥＸＣＥＬの「ソルバー」によって、整数計画法を実行し、最長ルート探索する方法を示す。葛西隆也氏は整数計画法を高性能ソルバーで実行しているが、これでは一般人にはなかなか手が届かない （追記1参照）。ＥＸＣＥＬで計算できるのなら、一般人でも追試可能だろう。ここでは、通常の最長片道ルートに加え、新幹線を使わない最長片道ルート、本州循環型の最長片道ルート、東京近郊区間循環型最長片道ルートなどいくつかの応用例を示す（追記3参照）。 ＪＲの最長片道ルートの探索の類似問題として、「東京メトロ大回り乗車」の最長ルートを計算するというものがある。これは、「東京メトロの乗車ルートは同一駅を通過しない限り最短経路で計算する」というルールを活用して初乗り運賃の切符でどこまで長い距離を乗車できるかという遊びのことである。 「ＥＸＣＥＬによる最長片道ルート探索：東京メトロ編」は、これを整数計画法によって解いたものである。これを解くためには、� 崘ぐ佞僚蘊茲蟇芯其茣屐廚紡个靴萄把控�離を求める必要があること、�▲薀奪然鮎茣垢┐垢訃豺腓狼�点から当該駅までの運賃が初乗り運賃であること、などの制約をクリアーしなければならない。ここでは、この具体的な方法と結果を示す（追記4参照）。 また、ＪＲ最長片道ルートを計算する際に必ず問題となることに、運賃計算の特例により運賃計算キロと営業キロが異なるという現象があるが、今回は、時刻表記載の営業キロの最長を求めることに専念している。 しかし結果として、日暮里−尾久−赤羽と品川−西大井−鶴見だけは特定運賃計算キロを使用することになってしまった。日暮里−尾久−赤羽であれば、上野−尾久を東北本線下りページから、尾久−赤羽を東北本線上りページからキロ数を算出し、足し合わせた後、京浜東北線のページから算出した上野−日暮里のキロ数を引き算すれば正確な営業キロが求まるのであるが、最後の最後にそのことに気付いたので、時刻表記載の特定運賃計算キロを使用したままにしている(追記2参照)。 葛西隆也氏のウェブページに、新たに「2005年4月版（普及編）」が2005年4月9日付で掲載されていました。フリーのソフトウェアだけで、本州を分割することなくＪＲ全線を対象とした最長経路を求めることが可能になった、とのことです。「孤立ループが出現した場合、それを除去するための制約式を自動的に追加する」プログラムも準備されているところなど、さすがだと思いました。 ＥＸＣＥＬの「ソルバー」による最長片道ルート探索の決定版というべき「最長片道切符の変遷1961-2006」がデスクトップ鉄氏のウェブページに掲載された。これは、過去４５年間の国鉄・JRのネットワーク変遷の厳密な記録である同氏の「鉄道路線データベース」を駆使して、同氏自らがＥＸＣＥＬの「ソルバー」で計算したもので、その膨大な計算をこなし、最長片道切符変遷の全貌を纏めたことは驚嘆に値するといえよう。 また、計算結果の考察がいろいろと報告されており、東日本ブロックと東北ブロックの接続駅のパターンが路線の改廃によって大きく変動していることなどは興味深い。東北新幹線開業前の東北ブロックは非常に移ろいやすいルート選定だったようである。 本編の応用例として、デスクトップ鉄氏の「メトロ･都営ラッチ外接続駅全制覇260円最長ルート」がある。難しそうな問題であるが、発着駅の絞込みに工夫を凝らすことで、意外と簡単に解を求めることができるようである。 |
レイクのサイトです。
