来自HTDP的路径或路由功能不起作用

Question

下面的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

Answer 1

对于第一种情况：

下面这个页面本身的示例创建了无限循环： (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是B，它不是直接或间接连接到D，因此函数route-exists2? (根据规范正确地回答)没有这样的路由。