Skip to main content

鉄道ファンのためのグラフ理論: マルコフ行列の中の著者達番外編


この話は マルコフ行列の中の著者達の番外編である．鉄道ファンとグラフ理論の関係は何かという話である． (English version)

同僚の Dietger がグラフの全ての edge をたどる問題を知っているかと聞くので，Hamiltonian path のことかと答えると，Hamiltonian path は全ての nodeを一度通るもので，そうではなく全ての edge を通るものだということだった．

私はVertex と Edge の Dual を考えれば良いではないかと言ったのだが，Triangle mesh ではVertex と Face は Dual になるが，Edge はそうではない．(図1, 2, 3)考えてみると，点は辺を介して接続され，面も辺を介して接続されている．では辺は何を介して接続されているのだろうか．面か点である．面と点の接続関係は辺によるものなので，辺はある意味この面・点とは異なる．だから面と点を入れかえることはまだできるが，辺は何かと入れかえられないと考えた．

Figure 1: Duality of face and vertex: faces to a dual grah.
Figure 2: Duality of face and vertex: a dual graph to faces.

Figure 3: Edge's duality?

これはどんな問題を考えているのかと尋ねたところ，彼の友人は鉄道の線路の管理をしているということであった．つまり線路を定期的に全て検査しなくてはならない．効率良く線路を全てまわるのはどうすれば良いのかという問題をグラフの問題として考えたものである．結局，これは中国人の郵便配達問題と呼ばれていることがわかった．中国人の数学者(Mei Ko Kuan)がこの問題に関して研究していたことにちなむらしい．これは Euler path 問題，つまり一筆書き問題とかかわりが深い．

私は昔，PTT (Programming tools and techniques) という集まりでこれに類する話を聞いたことがある．この会はソフトウェア関係の会であるが，鉄道好きの人も多数いらした．葛西さんという方が，この会で発表したのは，最長の片道切符はどんなものかというものであった．これは JR (Japan Railway) で買うことができる最長の切符である．http://www.swa.gr.jp/lop/index.html

referred from http://www.swa.gr.jp/lop/lop_res.html
彼の計算では線形計画法と総当たり法の二つで求めた解が一致している．ただし，総当たり法ではグラフの簡略化や分割など様々なテクニックが利用されている．

葛西氏は日本語ではあるが，アルゴリズムに関しても詳しく説明されている．2000年当時，彼の使った線形計画法のソフトウェアは商用の高価なものであったが，2005 年には計算機の性能の向上，そして，GLPK (GNU Linear Programming Kit) の登場によって家庭でもこのような計算が可能になっているそうである．その方法も示されている．

驚くことに1960年頃から手計算で片道切符の旅に取り組んでいる方がいらして，その方の経路はほとんどこの計算結果と同じというのも驚いた．人間の脳がすごいのか，この人が特殊なのか，とにかくすごいことである．

ところで，世界には鉄道ファンは多数いるはずである．ドイツにも鉄道ファンのテレビがあると聞く．そういう番組では，きっとこのような試みがあるであろう．多分．しかし，日本は地理的条件からグラフの分割というものが可能である．(グラフ的には島を結ぶ辺が極端に少ないので，葛西氏はこれを利用して計算量を減らしている．)ドイツの鉄道の最長片道切符，あるいはヨーロッパの最長片道切符はどういうものか，ご存知の方は御一報下さい．

Labels:

Comments

Post a Comment

Popular posts from this blog

共有メモリによるプロセス間通信

Unix の共有メモリを使ったプロセス間通信について調べて実験をしてみた．対象は1つのホスト上での複数のプロセスである．ネット上でいくつか例題はないかと探したが，どうも良い例となるコードが見当たらなかった．結局はある解説記事と，Stack Overflow の議論と，man page を見て作ってみたものになったので，例をここに置くのも有用かと考え，この記事を書く．(もしかしたら探し方が悪くて良いコード例をみつけられなかっただけかもしれない．) mmap を使うかどうかという話がいくつもでていたが，POSIX の方向としては，shmem_open と mmap を使うという方向があるということだったので，それを信じてその形での実装を試してみた． 基本的なコードの流れは次のようになる． 共有メモリ領域を1つのプロセスが shm_open() を使って作成する．その際に，プロセス間で共通の文字列を識別子(``identifier'')とする．(Linux ではこれが /dev/shm/identifier のように見える．) 共有メモリ領域を mmap() でメモリにマップする．共有メモリポインター (shared_ptr)が得られる． shared_ptr を使って複数のプロセスで通信をする． 利用終了後は munmap() をつかってマップを消す． 共有メモリオブジェクトを shm_unlink() によって消す． 以下に示すプログラムは，server と client の2つのプロセスが共有メモリを使って通信をするものである．ここで，server プロセス数と client プロセス数は共に 1 を仮定する．server と client は自分の領域にしか値を書き込まないことで，ロックを避けている．互いに相手の値を読み，それよりも1大きい数を一定の期間ごとに自分の領域に書くという例題である．シンプルではあるが，共有メモリで通信をする基本としては十分なものだと思う．ソースコード(shmem_test.cpp)を以下に付加する．ソースコードのコメントにコンパイル方法とどのように利用するかを書いておく． /*   Shared memory inter process communication minimal exa...
Post a Comment
Read more

複数の線を持つ線グラフを Jenkins の plot plugin で描く方法

私は毎夜のソフトウェアテストを自動化するために Jenkins というツールを使っています．今回は， valgrind  を使ってメモリーリークのテストを自動化することにし ました．その際，エラーの数の結果をグラフとして表そうと思って， Plot plugin  を使うことにしました． Plot plugin の例図からは，複数のデータラインを描くことができるのは明らかなのですが，どうやったらいいのかは参照のページや，例としてあった Perl script，plugin 中の help からは私にはよくわからなかったのです． ここで重要な考えは，それぞれのデータラインにはそれぞれの出力ファイルが必要ということでした．私はこれを誤解していました． 例として，ビルドの時に次の property データファイルを出力します．それぞれのファイルが1つのデータラインを表します． valgrind_trunk_result.definitely.property valgrind_trunk_result.indirectly.property valgrind_trunk_result.possibly.property それぞれのデータの中身は1行のデータ点です．たとえば， valgrind_trunk_result.definitely.property ファイルの中身は次のような1行 です． YVALUE=0 このファイルを ${WORKSPACE} ディレクトリ以下に出力します．ここで，" WORKSPACE " は jenkins が提供する環境変数です． 図1が私の plot plugin の設定を示しています．これは jenkins の config 画面です．3つの data series があって，それぞれにデータファイルがあります． Figure 1: Plot plugin configuration in Jenkins 図2が結果です．複数の線が描かれているのがわかります．(実際には 3 本の線がありますが，最初の線と2番目の線が同じデータなので，重ねって見えません．) Fugure 2: Plot data with multiple data lines
Post a Comment
Read more

ソニーのカメラ (α 5000) の 30 分のビデオ録画時間の制限を外す方法

私は Sony の Alpha 5000 を気にいって使っています。しかし一つだけ問題がありました。それはビデオの録画時間の制限が 30 分というものです。 今日，ちょっと気になって探したらこの制限を解除できることがわかりました。以下のビデオがその紹介です。 https://youtu.be/7cstA_PuRIg このビデオの作者によれば，ほとんどのソニーのカメラのビデオの制限はなくせるそうです。ただし私が試したのは，Alpha 5000 のみです。 手順 カメラ側 スイッチ On Menu -- Setup --- USB connection を MTP にする スイッチ Off and On USB ケーブルでカメラをコンピュータに接続する (以下接続したままにする) コンピュータ側でソフトのダウンロードとインストール (私は Windows 10 で試しました) 次の URL に行く https://sony-pmca.appspot.com/apps ただし，Internet Explorer か Safari のみサポートということでした。Chrome では上手くいきませんでした。私が試したのは Windows 10，Internet Explore 11 です。 注意事項: このサイトは Sony のサイトですが，ここにあるソフトウェアは Sony のものとは限らないので保証はありません。御自分でリスクを判断してご利用下さい。当方も何も責任を負えません。 上記の URL から，OpenMemories のページに移動する。 このページにある PMCADownloader plugin (PMCADownloader.msi) をダウンロードする PMCADownloader をインストールする 私はいちどここでページを閉じてもう一度 https://sony-pmca.appspot.com/apps を開き，OpenMemories のページに移動しました ここで log に Loading plugin Plugin loaded と表示されます。PMCADownloader の Install がされていない時には，``Plugin loaded'...
Post a Comment
Read more