2004.07.14

最長片道切符を解く

NHKのテレビ番組で「最長片道切符の旅」というのをやっていた。
列島縦断 鉄道12000kmの旅 ~最長片道切符で行く42日~
これは毎朝リアルタイムで中継をやっていたようだが、
朝見たことはない。総集編をたまたま見ただけである。
しかも総集編の前編も後編も運良く見ることができた。

さて、最長片道切符とは何だろう。
私は鉄道マニアというほどではないが、鉄道の旅は好きである。
海外に行っても好んで鉄道の旅をするほどである。
過去には東京から帯広まで途中下車しながら旅行したこともある。
このときには経路を指定して切符を買った。
そんな私だから、最長片道切符という熟語を聞いただけで
その意味するところは理解した。

JRでは同じ駅を2度通過しなければ、自分の乗りたい経路で切符を買うことができる。
その切符の経路が100kmを超えていれば途中下車も自由なので、
単に乗る経路ではなく、バックさえしなければどこの駅で降りることも可能なのである。
そして有効期間も200kmに対して1日加算される。
ここで同じ駅を2度通過しないというところがポイントで、
(厳密には他にも色々なルールがあるのだがここでは省略)
このルールの範囲、そしてもちろん現在のJRの路線の範囲で
最も長い経路の切符を買って、その経路を旅しようというものである。
詳しくはこのページを見て欲しい。
最長片道切符
これによると「最長片道切符」というのは
NHKが考え出した企画ではなく、昔から存在していた企画であるということが解る。

ここまでは「最長片道切符」の説明で、前置きである。
この投稿の本題は「最長片道切符を解く」である。
日本全国に広がるJRの路線図を見て、さて上記の最長片道切符とは具体的に
「どこを起点とし、どのような経路を通って、どこの駅が終点となるのか」
ということである。
この「」の問題をどう解くのか。
番組の最初で、旅人が稚内から出発する前に切符を見せながら、
テロップではこの旅の経路(この問題の解)が示されていた。
このときに私は、旅そのもの同様にこの問題をいかに解いたかにも
関心を持ったのであった。

この問題は、トポロジー(位相幾何学)の問題で、
よくあるのは最短配達経路問題である。
最長経路などというのは、ひまな旅人が考えることで、
一般には最も効率の良い経路を考えるものである。
私は専門でないので正しいかどうかはわからないのだが、
最長片道切符問題と最短配達経路問題は、
もちろん具体的な解法は異なるだろうが、似ているところもあるだろうと感じた。

興味はあるが自分で解いてみようなどとは思わない。
この問題が簡単に解けるものではない、そのくらいは解っているつもりである。
一般的な最適問題の場合、力ずくで解くか何某かのアルゴリズムを開発するかである。
力ずくはコンピュータがいくつあっても足らないし、
アルゴリズムの開発は私の頭がいくつあっても足らない。

しかし世の中には物好きが居るものである。
理論立ててこの問題に取り組み、力ずくとアルゴリズムの2方向のアプローチから
1つの解を求めている人が居る。
東大大学院の葛西隆也さんを中心とするグループだ。
最長片道きっぷの経路を求める
JRの解釈や最長の定義などで、NHKの番組と経路が異なる部分もあるようだが、
この問題をNHKが独力で解いたとは到底思えない。
必ずこのグループの世話になっているはずだ。
昔から存在していた問題を、単にNHKが取り上げただけのようである。
そして問題としてではなく、企画として番組にしたと言える。

上記のサイトはパラパラと見たが、まだ詳しく読んではいない。
しかし目次だけ見ても苦労はうかがえた。
すべての数学の問題の解法に言えることだが、
自分には解けないし、解法の一語一句は理解できなくても、
その美しさは理解できる。
それはまるで芸術作品を見るが如くである。
時間をかけてゆっくり読んでみたいと思う。

| | コメント (0) | トラックバック (0)