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

Question

http://htdp.org/2003-09-26/Book/curriculum-Z-H-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)]))

我也试过第二个版本（我加了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

Answer 1

第一种情况：

Following example from that page itself creates infinite loop:

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

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

The hand-evaluation confirms that as the function recurs, it calls itself with the exact same arguments again and again. In other words, the evaluation never stops.

所以，这正是您观察到的行为。

第二种情况：

Following produces #f even though solution is clearly possible:

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

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

Take another look at figure 85. In this simple graph there is no route from C to D.

因此，函数必须 return 正确 #f，因为没有从 C 到 D 的路径（记住弧是有向的，其实在例子之前，已经明确的说：“...每个节点与另一个节点恰好有一个（单向）连接”）。

最后，在你的最后两个例子中：

Following tests (lists are mine) produce errors here also even though solution is clearly possible:

(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) ...)

已添加

这是最后一个问题的答案：

Even after choosing the new function and remove excess quotes, following does not work (even though there is a direct path between A and D):

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

It outputs an error:

neighbor: impossible

在您链接的页面中，第 “A Problem with Generative Recursion" 部分的第一段中明确表示：

Here we study the slightly simpler version of the problem of simple graphs where each node has exactly one (one-directional) connection to another node.

由于您的图从一个节点有多个连接（例如 A 连接到 B、C 和 D 等），在这种情况下程序会不工作。

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

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

Path or route function from HTDP not working

scheme

racket

htdp