→超軽量簡易版はこちら

2007/07/11

ようやく仕事ひと段落してLOP toolkitを改造して最長O型きっぷ探索中ですよ

新しいカテゴリをつくりました。

もう先月からドハマりまくってたお仕事、8日遅れで(涙)ようやくひと段落つきまして、今日はLOP toolkitをO型きっぷ算出用に改造してさきほどからJR各会社の最長O型きっぷを計算しておりますです。

改造はパーフェクトではなく、目視作業が必要で(というのはいわゆる「ループ除去」をするわけですが最適解自体もループになるわけで(笑)、最終的に独立ループ(というか複数ループ)がなくなった解が必ず最適解というわけではないので、途中経過の最大解をすべて記録しておいてそれを比較する部分は人力(not 党派名)のままにしてあります)、また計算自体もループの場合はLee型とかよかはるかに手間も時間もかかるみたいですが、それでも、3島および東海は速攻、またそれなりに難関だったJR西日本でも20分とたたずに正解が出まして、ただいまもっと難関なJR東日本を計算中であります。

まぁしかし、これ、やっぱり本州はそのままじゃ時間かかりすぎるような感じです…
それでもほっとけばよいわけですから、まぁラクです。
今宵は、JR東日本を算出したら、本州の計算をはじめてから寝ちゃいます。Zzz...

P.S. 東海のO型きっぷって、一見、東海道-中央西-太多-高山の1つしかないように見えますけど、冷静に考えると4種類あるんですよね。つーかSWAさんのPostScript路線図見れば4箇所すぐに気づきますが(^^;;)。

追記:開始から12時間近く経過しましたが、JR東の計算がまだじぇーんじぇん終わりません(汗)。
かなり早い段階から、長野-豊野間・小出-越後湯沢間・安積永盛-郡山間・いわき-水戸間の4箇所を通らず、その南北で分断された2つのループができ、東京近郊区間を含む南側のループの微細な最適化が延々と走っているだけです。。。
というわけで、これは計算を分割する必要がありますね。近藤英明さんの計算では定番の3枝地帯分割ですが、現時点の経過におけるGPLKのクセからして、上記4枝で場合わけをしてみましょうかね。

P.S. O型は、分割するとLee型になるため、計算速度が劇的に向上するはずです。ただしその場合、分割した各区間内でのO型最長を計算して、分割した結果がそれらすべてを上回ることを示さなければ「厳密解」とはいえません。実は近藤さんの解の解説ページにはその検証が出ていないわけですが。(もしや単に枝を取り除いた各区間の総キロ数が全体より小さいので証明不要なのかな?(結果を信頼してるので私は検証してみたりしません^^;;))

この記事へのトラックバック

トラックバックはありません。

この記事へのトラックバックURL

http://feelfine.blog.izumichan.com/trackback/tb.php?id=14621

この記事へのコメント

コメントはありません。

Post Your Comment


*は入力必須です。E-Mailは公開されません。