Yuriko.Net 個別記事

おうちで LOP

最長片道きっぷを線形計画法で解いた葛西さんが、ふつうの PC で計算できるツール LOP toolkitを公開しているようです。GNU のフリーウェアと葛西さん作成の Perl スクリプトを組み合わせるようです。それなら Mac でも動くのではと思って試してみました。

Mac OS X なら、Perl は入っているし、Postscript ファイルは標準アプリ「プレビュー」で開けるので Ghostscript は不要。GLPK という線形計画法ソルバーは Darwinports のパッケージで入れるのが楽でしょう。Darwinports が入っていれば、ターミナルで sudo port install glpk とタイプすれだけで楽勝。

次は LOP toolkit をいじります。とりあえずサンプルデータを動かすことにして、それをコピーしておきます。

$ cp sample/edgeshon.csv edges.csv
$ cp sample/lophonsh.txt map.txt

それから、計算に必要な路線図データと制約式を作ります。

$ perl edge2cs.pl edges.csv > css.csv
$ perl makedata.pl Lee > east_Lee.mod

あとは起動スクリプトを動かそうと思いましたが、これは DOS バッチファイルなので使えません。シェルスクリプトとして移植します。以下のコードを auto.sh という名前で保存します。

#! /bin/sh
while [ $? -lt 100 ];
do
      glpsol -m $1.mod -o res.txt
      perl coloring.pl $3 res.txt | perl txt2sw.pl | perl sw2ps.pl > res.ps
      perl loopchk.pl $1 $2
done

これに実行権限を追加 (chmod +x auto.sh) して、いよいよ起動です。

$ ./auto.sh east_Lee Lee map.txt 

あとはダーっと表示が流れて進んでいきます。しかし、2時間たっても計算が終了しません。独立ループを含んだ結果なら出ているんですが、それを除去して再計算するループを3回繰り返した4回目の計算が時間かかっています。

途中経過でいいや、とおもって res.ps をプレビューで開いてみると文字化け……。どうやら、PS ファイルの文字列は Shift_JIS なのに、それを Unicode マッピングのフォントで代替表示しているようです。仕方ないので、Perl で Osaka フォントを指定するように修正します。

$ perl -lpe 's/Ryumin-Light-RKSJ-H/Osaka/g' -i res.ps

これで文字化けはなくなりましたが、駅名の表示がなんか変てこなような……。