2008/11/29

ループ検出

リンクつきリストにループ部分があるかどうかを確かめる - ときどきの雑記帳

最後の "Best solution" にあげられてる「うさぎと亀」は あらゆるLisp/Scheme処理系で使われていると思う。list?は 循環リストについても停止しないとならないため。 (CLのlistpは最初のペアしか見ないのでちょっと違うが、 lengthなどは循環リストを検出しないとだめ)。

難しいのはcar方向にも循環する場合、つまり木の場合で、 これはvisitした全ノードを何らかの方法で区別する (マークをつける、 ハッシュテーブルに記録する、みつけたものから移動してゆく、など) しかないと思うのだけれど、もっと効率の良い方法はあるのだろうか。

循環がある場合も停止する必要はあるけれど、必ずしもタイトに循環を検出しなくても良い、 という用途はあって、その場合は適当なところまで循環を気にせずに処理を進めて 怪しくなったら循環検出モードに切り替える、という手はある。 Adams&Dybvigのr6rs equal?実装とか。

(追記2008/11/30 01:47:30 PST): 木の循環検知、こんな感じだとどうでしょうか？

木の場合も結局、「何とか優先」で順番に辿るわけなんで、うさぎを作っちゃうという考え方です。

なるほど。考え方としてははたと膝を打った。ただ全ノード記録に比べて良いかどうかは疑問。

空間計算量については、全てのノードについて非末尾再帰が入るからO(D) (D=非循環部分の木の深さ)。 ランダムな木だとだいたいO(D) = O(logN) とみなせるかなあ。 で、リストに対する亀とうさぎ (空間計算量O(1)) にはかなわないけど、 全ノードを記録する (空間計算量O(N) (N=ノード数)) に比べればかなり良い。

ところが、このアルゴリズムは全ノードについて探索が2分岐するから 時間計算量はO(2^N)になる。全ノードを記録する場合はO(N)。 Nの上限がわりと小さい値であって、空間計算量をケチりたい場合くらいにしか使えなさそう。 (訂正：O(2^N)にはならない。上記リンク先の追記参照。)

(追記2008/11/30 02:58:44 PST): miuraさんの解にヒントを得た。 時間計算量が爆発するのはうさぎが増えまくるからで、 あくまで一匹を追いかけるようにすればよい。つまり木の全ノードの列挙を シリアライズしてその列について亀とうさぎを適用すればいいわけだ。 ちょっとsamefringe problemに似てる。遅延ストリームを使ってみるが、 samefringeと同じように、コルーチンとか継続渡しでも書けるはず。

(use util.stream)

(define (acyclic-tree? t)
  (define (traverse tree)
    (stream-delay
     (if (pair? tree)
       (stream-append (stream tree) (traverse (car tree)) (traverse (cdr tree)))
       (stream tree))))

  (let1 str (traverse t)
    (or (stream-null? str)
        (let loop ((tortoise str)
                   (hare     (stream-cdr str)))
          (cond [(stream-null? hare) #t]
                [(stream-null? (stream-cdr hare)) #t]
                [(eq? (stream-car tortoise) (stream-car hare)) #f]
                [else (loop (stream-cdr tortoise)
                            (stream-cddr hare))])))))

どうかな?

あ、だめだ。

gosh> (acyclic-tree? '((a . #1=(c . d)) #1#))
#f

そうか、部分共有があるとeq?なノードに出会ってしまうんだ。 だから元の木構造の情報を失ってしまうと間違える。 ということは各ノードへの元の木構造のパスをストリームの各要素とする? むー、結局余分な空間を食いそうだが…

やっぱだめだ。パスの等価性判定のところで循環を考慮した比較が必要になるので 堂々めぐりだ。

まてよ、全ノードマークっていうのも勘違いしてたかも。全トラバースしてハッシュテーブルに 登録してゆく方法だと上のように部分共有があるケースを循環と間違える。 マークするのは各パス内だけ (現在いるノードからルートまでが見える状態) にしとかないと。 そうすると、ハッシュテーブルは使いづらい。リストを使うとして時間O(N・D)、 空間O(D)か?

Tags: Programming, Gauche