最大の問題は「ソルバーが手元にない」ということでした。「最長経路を求めたい」という理由だけで一個人が買うのは難しいでしょう。性能面ではやはり、商用のソルバーに太刀打ちできません。具体的には、解ける問題の大きさ(規模)の上限が小さいのです。求めることは、さらに問題を分割しない限りは不可能のようでした。ところが、本編の発表から約5年、事情は大きく変わりました。Kit)が登場しました。いちおう簡易なソルバー(glpsol.exe)が付属してきます。しのぐ高性能ぶりを発揮します。フリーのソフトウェアだけでJR全線を対象とした最長経路を求めることが可能です。用いて、自分のPCで最長経路を求めています。LOP」という夢の(?)時代がやってきたのです。900MHz・メモリ768MB)で、特に高性能というわけではありません。多くの場合には現実的な時間内に解答を得られます。環境」を整えてみましょう。必要になるものは以下のとおりです。計算結果を路線図上に描画したりするための道具もあったほうが便利です。ページで入手できます。sources」をダウンロードしてきてセットアップしてください。ファイルを展開するだけでOKです。その他のOSの人は自力でがんばってください。環境を前提としたものなので、以下でさらにがんばる必要があります。2005年3月現在、最新のバージョンは4.8です。できるだけ新しいバージョンを利用するといいでしょう。ダウンロードしてください。圧縮してありますので、適当なフォルダに解凍してください。この時点であきらめてください。用法については後述します。無保証ですし、サポートも全くありません。「動かないんですけど」といった問い合わせは勘弁してください。スクリプトの中身を見てみるか、といったレベルのユーザを想定しています。インストールしてください。バージョンは4以降なら何でもかまいません。変換するスクリプトはちょっと怪しげです。最新版を入れておけば無難でしょう。画面表示する環境が必要です。Ghostscript(+GSView)ということになるでしょう。ここでは詳しくは述べません。ページ(三重大の奥村先生による)を紹介しておきます。インストールしてください。関連づけられ、計算結果を即座に地図に変換して見ることができます。toolkit」の使いかたを紹介します。以下の2つの要素から成っています。それぞれの関係をまとめておきます。矢印は入出力の関係を示します。付属するものであって、筆者が制作したものではありません。あとは自動的に事が進むということが分かります。一から作らなくてもだいじょうぶです。路線データについては、JR運賃計算システム「MARS」のデータを変換して作ることもできます。必要な地域のデータだけを抜き出して使うことになります。手作業で対応をとることになります。準備すれば、あとは以下のようにコマンド3個で終わりです。最適解を求めようとしています。それぞれのタイプの最適解が得られます。計算経過を地図に描き込みながら、ループ除去が済むまで計算を繰り返します。孤立ループが完全になくなると「res.txt」に計算結果が残ります。計算の過程をトレースすることができます。開き、自動更新をオンにしておくと、解き直しの過程を視覚的に追うことができます。出力の見かたについて説明しておきます。必要と思われるところだけを説明します。定義した変数などの情報がすさまじい勢いで流れていき、それから計算が始まります。開始直後は以下のような表示になっているはずです。「変数の値が整数である」という制約を全部無視して解いた場合の最適解が見つかったということです。(=整数制約)を全部取り除くことを「線形緩和」と呼びます。線形緩和した問題のほうが圧倒的に易しいのです。計算した結果、この変数の値が0.5とか0.221とかになってしまうと困ります。したがって、最長経路を得るにはもとの整数計画問題をがんばって解くしかありません。この「線形緩和した場合の最適解」にも意味がないわけではありません。本来解くべき整数計画問題の最適値の上界を示しているからです。「フィルターが云々...」という部分をよく読み直してください)。整数制約が加わる分だけ、整数計画問題のほうが制約が多いことになります。常に「(整数計画問題の最適値)≦(それを線形緩和した問題の最適値)」ということがいえるわけです。この制約式における最長経路の長さがここで出てきた値(上記の例では32372.66667)を超えることはない」ということになります。いうことをまずチェックするといいでしょう。解いたら最長距離(この時点では「暫定最長距離」)が33000だったとします。計算は(真の最長経路になる見込みがないので)やめていいわけです。計算時間の見込みは?線形緩和した問題を解き終わると、いよいよ本来の整数計画問題を解き始めます。すると、以下のように途中経過が出力されます。したのでは?と心配しないために)およそ5秒おきに出力されます。4049)たとえば2行目に注目してみます。number」で、累計の計算量だと考えればいいでしょう。増分は解く問題によりますが、おおよそ時間に比例して増えていきます。「現段階では最適値が28098以上32372以下ということが分かっている」という意味です。「逆に、3237.2kmを超える経路は絶対に作れない」ということが判明しています。その間の長さの経路は「実際に作れるかどうか分からない状態」です。先に出てきた線形緩和問題の最適値(32372.66667)を上回っていないことに注意してください。計算の途中で「このタイプには望みがない」と判断することができます。割合で表示したものです(計算方法は「32372÷28098−1」)。「分からない範囲」は計算を進めていくと小さくなり、最終的には0になります。(considered)」です。「これまでに解き終わった子問題の数」といった意味です。必要ならその子問題をさらに分割し...ということを行っています)。後者が「決裁済の箱に入れた書類の数」といった感覚的な理解でいいと思います。そのうち減少に転じて、最終的には0になります。いうのを判断する目安になります。後者は「決裁済の数」なので単純に増えていくだけです。計算結果そしてお待ちかね、計算結果です。`res.txt'...この場合、得られた最適値は29042ということになります。計算時間、使ったメモリ量などは見てのとおりです。結果は「res.txt」に書き込まれたということなので、この中身を見てみます。=線形計画の意)が並んで書かれています。最長経路の長さは前者です。重要なのは枝の使用状況なので、「e001」などという変数名を探しましょう。1ここでは「Activity」の欄に注目します。112番の枝は通りません。...、402番は通る、999番は通らない、ということが分かります。「色つき地図」を作るスクリプトはこの部分から計算結果を得ています。簡易包装にご協力ください。