Graphillionと最長片道切符

一部で話題になってた「組み合わせ爆発のお姉さん」の動画、気付いたら新作が出ていた。

元動画はこちら。やたら壮大なスケールで、組み合わせ爆発の怖さがわかる。

『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！ - YouTube

そしてこっちが新作、というかフォローみたいな動画。

Graphillion: 数え上げおねえさんを救え / Don't count naively - YouTube

25万年、ひたすら数え上げしていたお姉さんはいったいどうやって救われるのかと思って動画を見てみたら、特に新ストーリーとかではなく、ゆっくりボイスでグラフを扱うスクリプトの紹介をされていた・・・なんだ・・・

と思ったが、このGraphillion、Pythonのモジュールで、複雑なグラフも簡単な記述で扱えちゃうスグレモノらしい。この動画では電力ネットワークの例題が上げられているが、ほかにも東京近郊区間大回りの計算なんかもサクッとできてしまうようだ。この大回り計算は、その名もekillionとしてweb上に公開されていて、だれでも簡単に大回りの経路を列挙して眺めて楽しむことが出来る。

このekillionで遊びながら、これを「最長片道切符」の経路の算出に応用したら結構簡単に経路が出せるのではないかとかふと思った。

最長片道切符のルートの計算については、葛西隆也氏が整数計画法という数学的手法を用いて計算したり(
最長片道きっぷの経路を求める
)、近藤英明氏が整数計画法をExcelのソルバーに落としこむ(ＥＸＣＥＬによる最長片道ルート探索)など、既にいくつかの例がある。
葛西氏は商用のソルバーによる計算を行っていたが、フリーのソルバーGLPKを使用する方法もサイト上で紹介されている。私もこれで経路を計算したことがあるが、当時所有のPCでは計算に非常に長い時間がかかり、ツール内部の理解も十分には出来なかった。整数計画法で問題を解くには、片道切符の発券条件を線形の「制約式」に置き換える必要があるが、その制約式の作り方がトリッキーで、自分で組み立てるのは困難であった。

Graphillionを使用すると、制約式を作る作業無しに最長片道切符の経路の探索ができ、問題の変更も比較的簡便にできるようなので、少し遊んでみると楽しそうだ。