ネットワーク問題を解くためのPythonライブラリは何が良い？

国鉄時代からありますが、日本国内を一筆書きで乗り継ぐ片道切符を考えるという問題があります。『最長片道切符の旅』が有名ですが、これが端緒ではありません。問題を考えるだけなら、時刻表と暇な時間があれば十分ですが、現実に旅行してみようとすると資金面でも現実の時間も必要ですし、体力も必要です。

 

この問題を解くために時刻表とにらめっこするのも一興ですが、コンピュータを使って解いてみるのも楽しそうです。これはネットワーク問題ということになると思いますが、アルゴリズムを最初から自分で実装するよりも、何か既存のライブラリを使う方が、不必要に苦労せずにすむでしょう。いろいろなライブラリがあるとは思いますが、Pythonで利用できるものを考えてみようかと思います。

 

Pythonでネットワーク問題を解くためのライブラリも、いろいろあると思います。何を使っても良いのですが、有名なところでは「NetworkX」があります。また『Python計算機科学新教本』では「3章制約充足問題」や「4章グラフ問題」が参考になりそうです。他にもライブラリはいろいろありそうですが、各ライブラリを比較検討するのが目的ではないので、横道に逸れないように注意して、NetworkXを使ってみようかとも考えています。

 

いきなり日本全国の鉄道路線網を扱おうとすると大変なので、最初に北海道、四国、九州のどこかを使って、具体的な実装を試してみようかと思います。それがうまくいったら、日本全国に広げようかと思います。

 

ただし、国鉄時代とは違い、現在のJR四国は、日本国内の一筆書きの片道切符では対象から外れています。なぜなら、国鉄時代には、四国と本州の間には連絡船が東西に2航路存在していましたが、現在は岡山から四国にわたることしかできません。一筆書きのルールは同じ路線を複数回使用できないため、いったん四国に入ってしまうと出ることが出来ないのです。

 

またJR北海道が路線廃止をすすめていますし、在来線だけでは北海道と本州を移動できなくなっています。このあたりは一筆書きのルールを定義するやり方でなんとかなるでしょう。