← 図 A1
各回ごとの計算時間、それまでに追加した「ループ禁止制約式」の累計本数、
真の解との差をグラフにしました。
このページでは、新しい最長経路を計算する過程、 すなわち計算時間や再計算回数など実際の計算作業について紹介します。
前のページで紹介した新たな最長経路は、東北地方で新展開を見せたものの、
その他の地域は従来とまったく同じものでした。
東北新幹線の八戸開業による変化は比較的小規模で、
予想の範囲内だったといえるでしょう。
が、LOP 界の第一人者 :-) がこのような報告をするからには、
裏で地道に最長経路の計算を行って、
「新たな最長経路はこれだ！」という数学的な保証を得ています。
実際、筆者はこの記事を書くためにひさしぶりに母校を訪れ、
共同研究者とともに計算機に向かいました。
このページでは、実際の計算作業がどのような過程をたどったかを紹介します。
なお、今回、北海道、四国、九州については新たな計算が不要でした。 というのは、これら三島では路線図が何ら変わっていないからで、 本編で計算した「本州と出入りできる中で最長のもの」をそのまま使えます。
最長経路を求めるにあたっては、本編で解説したように、タイプ Lee について「再計算」が何度も発生します （他のタイプは最長になり得ないことがすぐに判明するので、 解き直すまでもなく捨てることができます）。 整数計画問題を解いて、得られた解がループを含んだ「使えない解」だった場合、 その解に含まれるループを明示的に禁止する制約式を追加してふたたび整数計画問題を解く…という作業を、 ループがなくなるまで繰り返す必要があるのでした。
今回、新たな路線図のもとでの最長経路を求めるにあたっては、
11回の再計算が必要でした。
つまり12回目の計算で最長経路が求まったことになります。
実は、11回目の計算でループのない解を得ることはできたのです。
しかしその経路は「運賃計算の特例」を考慮すると、
実際に発売可能な乗車券の運賃計算経路としては不適切なものでした。
そこで、特例に対応する制約式３本を加えてもう一度再計算（詳細は
[付録1-4]
で述べます）、12回目で「実際に発売可能な乗車券の運賃計算経路」が得られました。
もちろん、12回目の経路にもループは含まれていません。
解き始めてから、
出てきた解を見てループ禁止のために追加した制約式の本数は合計で34本でした。
初回の再計算時には実に10本の制約式を追加しましたが、
以後、追加する制約式はだんだん少なくなって、
１本しか追加しない回もありました。
追加する制約式の本数が「出てきた解に含まれるループの数」と同じであることに注目すると、
この傾向は「１回目の再計算で全国の『雑魚ループ』をまとめて禁止したら、
以後はそこそこ有力なループしか出てこなくなった」と理解することができます。
計算時間は回により異なりましたが、短いと１秒以下、長くても13秒以下でした。
前回よりもかなり速いマシンを使用したため（Athron
950MHz、メモリ640ＭＢ）、ほとんどストレスを感じることなく計算できました。
ちなみに、最初に出てきた経路の長さは（不要なループを含めて）12332.8kmでした。
真の最長経路が11614.9kmですから、だいたい700kmほど長かったわけです。
１回目の再計算で経路の長さは一気に500km以上も短くなりましたが、
その後はしばらく膠着状態が続きました。
計算を繰り返しても距離がなかなか減らなかったのは、
新幹線と在来線を別々の路線として扱うことのある区間において、
同じ重みの枝を素直に２本入れたのが一因だと思われます。
これらの区間でも、タイプ Lee
の最長経路を探す場合に限定すれば新幹線と在来線のどちらか一方しか使えないことがあるため、
後述するような「特例に対応する制約式」をあらかじめ入れておけば、
計算の回数はぐんと減ったかもしれません。
最後に、計算作業のようすをグラフにまとめてみました（図 A1）。 計算機に向かって「あー」とか「うー」とか言っている筆者と共同研究者の姿を想像してもらえれば幸いです。:-)
← 図 A1
各回ごとの計算時間、それまでに追加した「ループ禁止制約式」の累計本数、
真の解との差をグラフにしました。