2011-03-01 13 views
1

私はスキームで深さの最初の検索を実装しようとしていますが、部分的にしか機能しません。 これは私のコードです:プロシージャにスキームで深さの最初の検索を実装する際の問題

(depth-first-search complete-graph (caar complete-graph) (cdar complete-graph) (list (caar complete-graph)) 'd) 

フルを返すshoud:

(define (depth-first-search graph node neighbour path dest) 
    (cond ((null? neighbour) #f) 
     ((equal? node dest) path) 
     ((member (car neighbour) path) (depth-first-search graph node (cdr neighbour) path dest)) 
     ((memq (car neighbour) (car graph)) (depth-first-search (cdr graph) (car neighbour) (memq (car neighbour) (car graph)) (append path (list (car neighbour))) dest)) 
     (else depth-first-search (cdr graph) path dest))) 

そして、これは私のグラフ、データ構造である:これは私がプロシージャを呼び出す方法です

(define complete-graph 
    '((a b c d e) 
    (b a c) 
    (c a b f) 
    (d a e h) 
    (e a d) 
    (f c g i) 
    (g f h i j) 
    (h d g j) 
    (i f g j) 
    (j g h i))) 

始点ノードから終点(dest)(ination)までの経路がリストとして示されていますが、始点ノードと終点ノードでは動作しているようです。 'a'と 'c'で始まる場合、正しいリスト '(a b c)が返されますが、' a 'と' d 'を試してみると、#fが返されます。だから、おそらくアルゴリズムのバックトラッキングに何か問題があります。しかし、私はあまりにも長いコードを見てきましたが、実際には問題を見つけることはできません。

+0

'else'節で' depth-first-search'を呼び出す前に括弧がありません。 –

+1

'(追加パス(リスト(カーネイバー)))'は悪いことです。 – knivil

答えて

0

深さ優先検索と同じようにグラフを変更する必要はありません。

(define (depth-first-search graph node dest path) 
    (let dfs ((node node) (path path)) 
    (let ((recur (lambda (node) (dfs node (cons node path))))) 
     ; Write code here 
     ; Recursive calls should use recur, not dfs or depth-first-search 
     ...))) 

(結果としてパスまたは#fを返す):あなたは純粋に機能的に物事を行いたい場合は、あなたのような機能を見てみましょう。 ormap(RacketまたはSRFI-1)を使用すると、ノードのすべての隣接ノードを反復処理し、#fでない最初の値を返すことができます。

1

ノード 'a have children'(b c d e)、ノード 'b has children'(a c)、ノード...まずノードをその子に展開する関数が必要です。

(define (expand graph node) 
    (let ((c (assq node graph))) 
    (if c (cdr c) '()))) 

2番目:訪問したすべてのノードを覚えておく必要があります。一般的に帽子はパスとは異なります(この例では問題ではないかもしれません)。第3に、訪問したいすべてのノード(ノード展開プロセスの結果)を覚えておく必要があります。したがってヘルパー関数を定義する

(define (dfs* graph visited border path dest) 

訪問するノードがない場合、道路は存在しません。

(cond ((null? border) #f) 

ボーダーの最初の要素は、私たちの目的地に等しい場合、我々は

 ((eq? (car border) dest) (cons (car border) path)) 

は、すべての訪問のノードを確認できます満足しています。ボーダーの最初のノードが前に訪れた場合、

 ((memq (car border) visited) 
     (dfs* graph visited (cdr border) path dest)) 

は、それ以外の場合はボーダーの最初のノードを展開ノード展開せずに続行

 (else (dfs* graph 
        (cons (car border) visited) 
        (append (expand graph (car border)) (cdr border)) 
        (cons (car border) path) 
        dest)))) 

呼び出すことを訪問し、境界線とパスの開始値を持つヘルパー関数:

呼吸最初の検索について
(define (dfs graph src dst) 
    (dfs* graph '() (list src) '() dst) 

:境界の終わりに拡張ノードを追加

編集: a)訪問先とパスが同じ場合、それらのいずれかを削除できます。 b)パスは逆順で返されます。 c)手順は正しくありません。パスにはすべての訪問先ノードが含まれています。しかし、dfs *の結果の後処理がその仕事をします。

関連する問題