1

スキームで幅優先ツリートラバーサルを実装する方法を理解しようとして、私は髪を引っ張っています。私は Java と C++ でそれを行いました。コードがあれば投稿しますが、正確にどのように開始すればよいかわかりません。

以下のツリー定義を考えると、再帰を使用して幅優先検索を実装する方法は?

(define tree1 '( A ( B (C () ()) (D () ()) ) (E (F () ()) (G () ())) )) 
4

3 に答える 3

3

他の言語でこれを行ったときは、dfs にスタックを使用し、bfs にキューを使用したに違いありません。深さ優先検索を行う場合、基本的にスタックを使用して次に探索するノードを決定し、再帰によって関数呼び出しスタックが提供されるため、2 つのミラーが互いにどのようにミラーリングされるかを簡単に概念化できます。幅優先検索では、キューを再帰的に走査するにはどうすればよいかという問題が生じます。

反復的に実行できることはすべて、再帰的に実行できることを思い出してください。「while x < 10: x += 1」と書くところに、代わりに次のように書くことができます。

(define (my-loop x)
  (if (< x 10)
      (my-loop (+ x 1))
      ... ;; your base case
      ))

そして突然、反復を再帰的に行っています。偉大な。

このキューがあります。私たちは一方の端に物を置き、もう一方の端から物を外します。上記のループでループ制御変数 x を渡したように、キューを明示的に渡す必要があります。再帰の次のレベルになる次の「反復」では、いくつかの新しい子をキューに入れたいと思うでしょう。その次の再帰は、キューのもう一方の端から1つの子を取り出すか、停止します(戻ります) これ以上子がいない場合。

現在、コール スタックはツリー内の位置を反映していないため、再帰の方が優れている、またはより直感的である理由を理解するのは困難ですが、常に可能です。

お役に立てば幸いです、
グレム

于 2010-05-03T12:11:50.770 に答える
2
  1. これは宿題ですか?もしそうなら、読むのをやめてください:)。

BFSアルゴリズム:キューが空の場合は、あきらめます。それ以外の場合は、キューを最初の要素と残りの要素に分け、最初の要素が目的の要素であるかどうかを確認します。そうでない場合は、残りの要素と新しく到達可能なすべての要素を含むキューで繰り返します。

もちろん、Schemeで同じ文を「言う」ことができます。

#lang scheme

(define (bfs pred queue)
  (match queue
    [empty #f]
    [(cons elt queue-rest) 
     (or (pred elt)
         (bfs pred (append queue-rest (remove* queue-rest (reachable-from elt)))))]))
  1. 完全にテストされておらず、ほぼ確実にバグがあります(測度論的な意味ではありません:))

  2. グラフの独自の表現と「到達可能-から」が必要です。

  3. リストは優れたキューの実装ではありません。

于 2010-05-05T00:58:37.537 に答える
0

次のようなことができます。深さnに移動し、要素を行と連結する再帰ヘルパー関数があります...出力は、深さnのツリーのすべての要素を含むリストになります。

(defun findAtN (tree n)
(cond ((equal tree nil) nil)
      ((equal (n 0)     (car tree))
      (t                (append (findAtN (cadr tree) (- n 1))
                                (findAtN (caddr tree) (- n 1))))))

次に、深さを増やす2番目の関数で、各レベルで特定のノードを検索します。

(defun ContainsElt (tree Elt n)
(cond ((equal (findAtN tree n) nil)   nil)
      ((member Elt (findAtN tree n))  true)
      (t                              (ContainsElt tree Elt (+ n 1)))))

これはテストされておらず、Lispのパラメータ/方言に基づいて、またアイテムがツリーにあるかどうかをテストする以上のことをしたい場合は、おそらくわずかに異なりますが、それを行う方法のアイデアに役立つかもしれません。

于 2010-05-03T18:07:16.187 に答える