いけがみを召喚するには、出現予定を参考にしてください。三週間前までにメールをくだされば、日程を追加するなどしてスケジュールに組み込むことができるかもしれません。勉強会や個人的な会合、中途採用面接などに応じます。日記に書かないことはこちら。
以上の議論を興味深く読みました。まず、「木(tree)」とは連結かつサイクルを持たないグラフを指しますので、「木の循環」というのはちょっと違和感が。でも、些細なことです。さて。
データ構造を循環リストにした場合(ただし線形とは限らないので、循環リストとは呼ばないのかもしれない)、問題は非常に単純になります。つまり、最初に決めた始点=終点の間に「全体」よりも「小さなループ」があるかどうか、という問題になります。
(直感を働かせるためにも、ここにグラフの絵が必要である、すなわち、「ループ部分」がある場合とない場合)描くのはめどいので「文字」で見ることにしよう。残念ながら字面は有向グラフではないが、実は有向でも無向でも、アルゴリズムの計算量は循環リストを考える限り変わらないのである(その紹介は後で)。
線形とは限らない循環リストとは、たとえば「P」である。左上に始点=終点を取ったとしよう。「O」とは違い、途中で枝分かれが生じている(実際、何本でも枝をとってよいと仮定する)が、全体よりも小さなループはない。別の例として、「Φ」を見てみよう。これは、もし始点=終点を中心の円のどこかにとったとして、全体よりも小さなループが真ん中に二つ存在しているのを見て取ることができる。
もし、あなたが「最大流問題(maximum flow problem)」について少しでも知っていれば、一般的な循環リストにおいて、内部ループの有無を調べる問題には、重みが特殊な(重みがすべて1)最大流問題におけるMengerの補題(Menger, K[1927], "Zur allgemeinen Kurventheorie.", Fundamenta Mathematicae, vol. 10, pp. 96--115, 1927)を適用できることに気がつくかもしれない。幸いなことに、ドイツ語を読むことができなくても、この問題は「組合せ最適化(Combinatorial Optimization)」という分野で広く知られており、どの初歩的な教科書でも大抵は説明が行われている。これは、僕にとっては、興味深い応用例に思われる。
「Φ」のように、全体よりも小さなループが2つ以上あったとして、それらを全て列挙する問題は「有向(無向)辺素パス問題(Directed/Undirected Edge-Disjoint Paths Problem)」という名前が付けられている。この問題についてはいくつもの解析がなされており(良いサーベイとしてVygen, J. "NP-completeness of some edge-disjoint paths problems", Discrete Applied Mathematics, Vol. 61, pp.83--90, 1995や、後述のKorte-Vegenの教科書第19.3章がある)、問題のクラスはグラフのサイズ(辺と頂点)に対して多項式時間NP-困難である。(ここにどうでもいい記述があったのを削除)有向か無向かは関係ない、と以前に触れたが、実際、無向グラフについては Menger の補題の系となり、Whitney[1932](Whitney, H. "Congruent graphs and the connectivity of graphs", American Journal of Mathematics, vol. 54, pp.150--168, 1932)が述べている。しかし、具体例を分類してみると有向と無向の違いは大きいのだが、もうこれ以上深追いはしない。（いろいろな粗がでてきた）
ここで立ち止まると、ループの有無を調べるだけなら、全てのループを列挙する必要はない。さらに賢い方法が考えられるだろう。と思うのが普通だよね。実際、ここまでは釣りなんだ。すまない。
と、長ったらしく小難しいコラムを書いた後で、嫌らしくも「より簡単な」方法について述べる。ループ部分があるかどうかは、素人考えでは走査すれば良いように思われるが、実際、うまい走査法 O(m + n) があるのである(m, n はそれぞれ辺の個数と頂点の個数とする)。それは、やはりデータ構造を工夫するところに鍵がある。
一般に、有向グラフは「隣接リスト(adjacency list)」という保持のしかたがある。隣接リストを記憶するための総 bit 数は O(n log(m) + m log(n)) である。線形リストでは、m = n - 1であることに注意しよう。
走査法には、いつものように幅優先か深さ優先かのどちらかが考えられる。どちらが優れているかは、グラフの形(正確には隣接行列が疎か密か)によるトレードオフがある。が、どちらにしても、線形時間で走査は終わる。線形リストなら、隣接行列は疎であると考えられるため、深さ優先でよろしい。ループを見つけたら走査を打ち切ることができる。
全走査アルゴリズム(巧みな2回の深さ優先探索)を変形すると、「有向グラフの強連結成分を求めるアルゴリズム」ならびに「有向グラフのトポロジカル順序の有無を求めるアルゴリズム」になる。んで、トポロジカル順序があるかどうかは閉路があるかどうかに対応する。こいつらの計算量は、みんな O(m + n) である。
以上のことは、教科書 Korte-Vegen の和訳本 (Bernhard Korte and Jens Vygen, "Combinatorial Optimization - Theory and Algorithm 『組合せ最適化 理論とアルゴリズム』浅野 孝夫, 平田 富夫, 小野 孝男, 浅野 泰仁(訳), 2005")から学習した。もちろん、間違いがあったとしたら、いけがみに非があるのでご自身で確認していただきたい。
個人的には、「並行」アルゴリズムになるのかどうかが気になる。最近のマシンはコアが複数あるのがあたりまえだし、あまりにも巨大な線形リストをグリッドでなんとかしたいときもあるかもしれないし(先行研究はあるみたいだね。Jun Ma, Kazuo Iwama, Tadao Takaoka, and Qian-Ping Gus,"Efficient Parallel and Distributed Topological Sort Algorithms", pas,pp.378, 2nd AIZU International Symposium on Parallel Algorithms / Architecture Synthesis (pAs '97), 1997とか)。
(追伸:2008-12-01) 有向(無向)辺素パス問題(Directed/Undirected Edge-Disjoint Paths Problem)は、NP-困難である、というのはよく知られた事実だったのに昨日は間違えて書いてしまった。The マチ☆ガエタ！ええと、しかしグラフに特殊な事情があると、多項式時間アルゴリズムがあったりする。この辺はとてもこみいっているので Korte-Vegen をやはり推奨する次第である。辺素好きフリークにとっては、多項式時間アルゴリズムがあるグラフのサブクラスを決定する問題は大好物であり、まだ知られていない宝島があればいいのになあと思われている。が、この航海は危険である。
Shiroさん: TAOCPの4巻でカバーされるんだろうか。このへんは。
Korte-Vegen の教科書によれば、topological sorting は TAOCP(Knuth, D.E. "The Art of Computer Programming; Vol.1; Fundamental Algorithms, Addison-Wesley, Reading 1968 (3rd ed. 1997) に言及されているとのことです。僕も持っているけど、今風の書き方でないので押し入れの中に眠っています。
で、もう一度きむらさんの引用しているFloyd's cycle finding algorithmを見てみると、線形リストの場合はさらに強いことが言えるみたいだ。これは知りませんでした。時間計算量、空間計算量は同じだけれど、Brent's algorithm は「うさぎと亀」よりも(平均的に)速いらしい。さらに、空間計算量を犠牲にすれば、さらなる高速化も可能だとのこと。
いつものことながら Wikipedia 先生は偉いなあ。就職面接では、質問に対して 'search "keyword site:en.wikipedia.org"' と答えるのが best solution なのではないだろうか(ウソ)。
RSS feed を再開しました。RSS の思想を尊重するために全文配信はしません、あしからず。