0

http://htdp.org/2003-09-26/Book/curriculum-ZH-38.html#node_chap_30の次のコードが機能していないようです (デバッグ用に println ステートメントを追加しました)。

(define (neighbor a-node sg)
  (println "in neighbor fn")
  (cond
    [(empty? sg) (error "neighbor: impossible")]
    [else (cond
        [(symbol=? (first (first sg)) a-node)
         (second (first sg))]
        [else (neighbor a-node (rest sg))])]))

(define (route-exists? orig dest sg)
  (println "in route-exits? fn")
  (cond
    [(symbol=? orig dest) true]
    [else (route-exists? (neighbor orig sg) dest sg)]))

私は2番目のバージョンも試しました（contains fnを追加しました）：

(define (contains item sl)
  (ormap (lambda (x) (equal? item x)) sl)  )

(define (route-exists2? orig dest sg)
  (local ((define (re-accu? orig dest sg accu-seen)
            (cond
              [(symbol=? orig dest) true]
              [(contains orig accu-seen) false]
              [else (re-accu? (neighbor orig sg) dest sg (cons orig accu-seen))]))) 
    (re-accu? orig dest sg empty)))

そのページ自体の次の例では、無限ループが作成されます。

(route-exists? 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)))

解決策が明らかに可能であるにもかかわらず、以下は #f を生成します。

(route-exists2? 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)))

次のテスト（リストは私のものです）は、解決策が明らかに可能であっても、ここでもエラーを生成します。

(route-exists?
 'A 'C
 '('('A 'B) '('B 'C) '('A 'C) '('A 'D) '('B 'E) '('E 'F) '('B 'F) '('F 'G) ) 
 )

(route-exists2?
 'A 'C
 '('('A 'B) '('B 'C) '('A 'C) '('A 'D) '('B 'E) '('E 'F) '('B 'F) '('F 'G) ) 
 )

問題はどこにあり、どのように解決できますか?

編集：

新しい関数を選択して余分な引用符を削除した後でも、以下は機能しません (A と D の間に直接のパスがあっても):

(route-exists2?
 'A 'D
 '((A B) (B C) (A C) (A D) (B E) (E F) (B F) (F G) ) )

エラーを出力します：

neighbor: impossible
4

1 に答える 1

3

最初のケース:

そのページ自体の次の例では、無限ループが作成されます。

(route-exists? 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)))

リンクしたページでは、関数の定義の 10 行後に、次のように明確に記述されています。

手動評価では、関数が再帰するときに、まったく同じ引数で何度も自分自身を呼び出すことが確認されます。つまり評価が止まらない。

したがって、それはまさにあなたが観察した動作です。

2 番目のケースの場合:

解決策は明らかに可能ですが、以下は #f を生成します。

(route-exists2? 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)))

最初の関数の定義の 4 行後、次のように明確に述べられています。

図 85 をもう一度見てください。この単純なグラフには、C から D へのルートはありません。

そのため、C から D へのルートがないため、関数は正しく返さなければなりません#f(実際、例の前に弧が方向付けられていることを思い出してください。「...各ノードには正確に 1 つのノードがあります（一方向）別のノードへの接続」）。

最後に、最後の 2 つの例では:

次のテスト（リストは私のものです）は、解決策が明らかに可能であるにもかかわらず、ここでもエラーを生成します：

(route-exists? 'A 'C '('('A 'B) '('B 'C) '('A 'C) '('A 'D) '('B 'E) '('E 'F) '('B 'F) '('F 'G) ) )

(route-exists2? 'A 'C '('('A 'B) '('B 'C) '('A 'C) '('A 'D) '('B 'E) '('E 'F) '('B 'F) '('F 'G) ) )

引用しすぎているため、必要なものとは異なるデータを関数に与えています。

'Xの略語であることを忘れないでください(quote X)。これは、最後のパラメーターが次と等しいため、正しいグラフではないことを意味します。

((quote (quote A) (quote B)) (quote (quote B) (quote C)) ...)

そしてしない

((A B) (B C) ...)

追加した

これが最後の質問に対する答えです。

新しい関数を選択して余分な引用符を削除した後でも、以下は機能しません (A と D の間に直接のパスがあっても):

(route-exists2? 'A 'D '((A B) (B C) (A C) (A D) (B E) (E F) (B F) (F G) ) )

エラーを出力します：

neighbor: impossible

リンクしたページの「A Problem with Generative Recursion」セクションの最初の段落で、次のように明確に述べられています。

ここでは、各ノードが別のノードへの接続を 1 つ (一方向) だけ持つ単純なグラフの問題の少し単純なバージョンを調べます。

グラフにはノードからの接続が複数あるため (たとえば、A が B、C、および D に接続されているなど)、この場合、プログラムは機能しません。

その理由は、関数を考えればすぐにわかります。他のすべてのノードを考慮せずに、特定のノードに接続された最初のneighborノードを見つけます。したがって、たとえば、 からは のみが返され、これは に直接または間接的に接続されていないため、関数は (仕様によると正しく) そのようなルートは存在しないと応答します。AneighborBDroute-exists2?

于 2016-09-15T05:28:41.430 に答える