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

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

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

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

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

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