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)]))

我还尝试了第二个版本（我添加了包含 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)))

在您链接的页面中，函数定义后十行，明确表示：

手动评估证实，随着函数的重复，它会一次又一次地用完全相同的参数调用自己。换句话说，评估永远不会停止。

因此，这正是您观察到的行为。

对于第二种情况：

以下产生#f 即使解决方案显然是可能的：

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

定义第一个函数后的四行，明确表示：

再看一下图 85。在这个简单的图中，没有从 C 到 D 的路线。

因此，函数必须正确返回#f，因为它没有从 C 到 D 的路线（请记住，弧是有方向的，实际上，在示例之前，它明确表示：“......每个节点都有一个（单向）连接到另一个节点”）。

最后，在您的最后两个示例中：

以下测试（列表是我的）在这里也会产生错误，即使解决方案显然是可能的：

(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 连接到 B、C 和 D 等），因此在这种情况下程序不起作用。

如果您考虑该功能，您可以立即看到原因neighbor：它找到连接到某个节点的第一个节点，而不考虑所有其他节点。因此，例如，从A唯一neighbor返回的 is B，它不是直接或间接连接到D，因此函数route-exists2?回复（正确地，根据规范）没有这样的路由。

于 2016-09-15T05:28:41.430 回答