記事には、最長距離片道ルートを求めるアルゴリズムが開設されていますが、概念レベルが書かれているだけなので、具体的なロジックはわかりません。文末にデータ作成作業をしてくれた人達への謝辞が書かれています。当時は今日のような路線検索サイトがある訳ではありませんから、おそらく時刻表を利用して、必要な情報を拾ってグラフ構造を作ったのでしょう。楽な作業ではないと思いますが、本文中でも「まず、駅の集合をVとする。実際には分岐点や行きどまりの駅だけを考えれば充分であることは明らかであろう。」と書かれているように、旧国鉄の全駅のデータが必要になるわけではなく、グラフ構造を作り上げるために必要な分岐駅や末端駅の名前と区間距離だけで良いわけです（それでも膨大なデータになることは違いないでしょう）。
アルゴリズムの解説では、サブブロック化に重点がおかれています。北は北海道から南は鹿児島までの旧国鉄の路線網をグラフ構造にしたとしても、現実の日本列島を考えれば、全体を一気に計算するよりも、一部分（これをブロックと呼んでいる）を計算して、最後に全体を統合すれば、最終的な計算量が削減されることが期待できます。
例えば、北海道と本州は青函連絡船を使うしかないし、九州と本州は関門トンネルを使うしかないわけです。だから、北海道内や九州内のルートを計算する場合には、それ以外の地域の事を考えなくてよいことになります。
北海道、四国、九州は、上述したようなサブブロックとして計算できますが、本州をどうするかが問題です。サブブロックに分けられそうでもあり、分けるのは困難のようでもあり、なんとかしたいところです。ブロックに分けようとする意図は、全体を闇雲に計算すると計算量が爆発し、その当時の計算機では処理が終わらなくなる恐れがあるからでしょう。当時の計算機よりも、今日のパソコンの方が性能が圧倒的に良いと思うので、もしかすると余計なサブブロックを考えなくても、計算できるかもしれません。
プログラムはFORTRANで組んだようです。その当時なら、このような計算をするならFORTANに決まっているでしょう。この記事には、それ以外（プログラムリストとか、実行時間など）の具体的なことは何も書かれていません。CiNiiで探してみたら、京都大学学術情報リポジトリに「長い片道切符について（計算機によるパズル・ゲームの研究）」というメモが「数理解析研究所講究録(1976), 263:75-76」として見ることができました。手書きなのが時代を反映しているところですが、「使用言語はFORTRANで使用計算機はFACOM 270-20(LOAD/ADD 4.8μs)での時間である」とあります。
面白そうなので、自分でもやってみたくなりました。プログラムはFORTRANでも良いのですが、今ならPythonを使ってみたいところです。グラフ構造を取り扱うためのPythonモジュールがあれば、いろいろと楽ができるでしょう。
ここで行く手に大きな問題があることに注意が必要です。1975年当時の国鉄と、2019年現在のJR各社とでは、事情が大きく変わっているのです。特に次の点が重要です。
- 新幹線開業にともない並行在来線がJRから切り離されている。
- 鉄道網が衰退（特にJR北海道）しており、グラフ構造で最長片道ルートを計算するというほど路線が残っていない。
2番目の問題は、計算量が少なくてガッカリするという程度の話にすぎませんが、1番目の問題は重大です。北海道新幹線が開通したことにより、JR北海道から切り離された道南いさりび鉄道の扱いが問題になるからです。新幹線が開業したことによりJRから切り離された路線は他にもありますし、長野新幹線の開業により横川と軽井沢の間は在来線が無くなりました。このような事情を考えると、どのような方針を採用するか考えておく必要があります。
- 全ての新幹線もルート検討に加える。ただし、路線の距離は、「営業キロ」なのか「実キロ」なのか、混乱しないようにすべきである。
- JRから切り離された第三セクター路線を、ルート検討に含めるか、除外するか決めておく。もし新幹線も除外し、第三セクター路線も除外するならば、北海道から本州に抜けるルートが無いということになります。
- いっそのこと全ての私鉄もルート検索の対象に含める。しかし「最長片道切符」の本来の意図は、「一枚の切符で最長距離」となることに意義があるため、ちょっとやり過ぎなのかもしれません。
最長片道切符のルート問題は、グラフ理論の応用問題です。ここで日本の鉄道網であるという知識を利用すると、すっきりしたグラフ理論のアルゴリズムというより、個別事情の集合という汎用性の乏しい問題に堕ちてしまいそうではあります。いずれにせよ、面白そうなので、なんとかものにしてみたいと思います。
0 件のコメント:
コメントを投稿