スキームで幅優先ツリートラバーサルを実装する方法を理解しようとして、私は髪を引っ張っています。私は Java と C++ でそれを行いました。コードがあれば投稿しますが、正確にどのように開始すればよいかわかりません。
以下のツリー定義を考えると、再帰を使用して幅優先検索を実装する方法は?
(define tree1 '( A ( B (C () ()) (D () ()) ) (E (F () ()) (G () ())) ))
他の言語でこれを行ったときは、dfs にスタックを使用し、bfs にキューを使用したに違いありません。深さ優先検索を行う場合、基本的にスタックを使用して次に探索するノードを決定し、再帰によって関数呼び出しスタックが提供されるため、2 つのミラーが互いにどのようにミラーリングされるかを簡単に概念化できます。幅優先検索では、キューを再帰的に走査するにはどうすればよいかという問題が生じます。
反復的に実行できることはすべて、再帰的に実行できることを思い出してください。「while x < 10: x += 1」と書くところに、代わりに次のように書くことができます。
(define (my-loop x)
(if (< x 10)
(my-loop (+ x 1))
... ;; your base case
))
そして突然、反復を再帰的に行っています。偉大な。
このキューがあります。私たちは一方の端に物を置き、もう一方の端から物を外します。上記のループでループ制御変数 x を渡したように、キューを明示的に渡す必要があります。再帰の次のレベルになる次の「反復」では、いくつかの新しい子をキューに入れたいと思うでしょう。その次の再帰は、キューのもう一方の端から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)))))]))
完全にテストされておらず、ほぼ確実にバグがあります(測度論的な意味ではありません:))
グラフの独自の表現と「到達可能-から」が必要です。
リストは優れたキューの実装ではありません。
次のようなことができます。深さ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のパラメータ/方言に基づいて、またアイテムがツリーにあるかどうかをテストする以上のことをしたい場合は、おそらくわずかに異なりますが、それを行う方法のアイデアに役立つかもしれません。