3

OnLisp の P.303 に幅優先探索の疑似コードがありますので、以下に示します。以下のグラフでは、最初にノード 1 を処理し、次にノード 2、3、および 4 をキューに入れ、繰り返し自分自身を再度呼び出します。次に、キューの先頭にあるノード 4 に進みます。これにより、ノード 7 と 8 がキューの先頭に配置されます。

最後に、それが通過したパスは、深さ優先検索である 1->4->7-11->12->8->3->2->5->9->10->6 になります。私はここで間違っていますか？

ここに画像の説明を入力

(define (path node1 node2)
  (bf-path node2 (list (list node1))))

(define (bf-path dest queue)
  (if (null? queue)
      '@
      (let* ((path (car queue))
             (node (car path)))
        (if (eq? node dest)
            (cdr (reverse path))
            (bf-path dest
                    (append (cdr queue)
                    (map (lambda (n)
                           (cons n path))
                         (neighbors node))))))))
4

1 に答える 1

1

幅優先検索は、トラバースする要素に対して先入れ先出しキューを利用します。

最初のノードを見て、(1)その子(2, 3, 4)を取得し、その順序でリストに入力する必要があります。次に、リストの最初の要素を見て、その子を取得し、(5, 6)参照するもののリストの最後に追加します(3, 4, 5, 6)。

最初の要素だけでこれを繰り返します。

3 -> (4, 5, 6)
4 -> (5, 6, 7, 8)
5 -> (6, 7, 8, 9, 10)
6 -> (7, 8 , 9, 10)
7 -> (8, 9, 10, 11, 12)
8 -> (9, 10, 11, 12)
9 -> (10, 11, 12)
10 -> (11, 12)
11 -> (12)
12 -> ()

先入れ後出し (あなたが行っているように、最後に追加された要素をループする) を行うことで、深さ優先検索を作成します。

于 2014-08-16T13:38:24.967 に答える