开发者

Backtracking infinite loop

This is Exercise 28.1.2 from HtDP. I've successfully implemented the neighbors function and all test cases pass.

(define Graph (list
               (list 'A (list 'B 'E))
               (list 'B (list 'E 'F))
               (list 'C (list 'D))
               (list 'D empty)
               (list 'E (list 'C 'F))
               (list 'F (list 'D 'G))
               (list 'G empty)))

(define (first-line n alist)
  (cond
    [(symbol=? (first alist) n) alist]
    [else empty]))

;; returns empty if node is not in graph
(define (neighbors n g)
  (cond
    [(empty? g) empty]
    [(cons? (first g)) 
     (cond
       [(symbol=? (first (first g)) n) (first-line n (first g))]
       [else (neighbors n (rest g))])]))

; test cases
(equal? (neighbors 'A Graph) (list 'A (list 'B 'E)))
(equal? (neighbors 'B Graph) (list 'B (list 'E 'F)))
(equal? (neighbors 'C Graph) (list 'C (list 'D)))
(equal? (neighbors 'D Graph) (list 'D empty))
(equal? (neighbors 'E Graph) (list 'E (list 'C 'F)))
(equal? (neighbors 'F Graph) (list 'F (list 'D 'G)))
(equal? (neighbors 'G Graph) (list 'G empty))
(equal? (neighbors 'H Graph) empty)

The problem comes when I copy-paste the code from Figure 77 of the text. It is supposed to determine whether a destination node is reachable from an origin node. However it appears that the code goes into an infinite loop except for the most trivial case where the origin and destination nodes are the same.

;; find-route : node node graph  ->  (listof node) or false
;; to create a path from origination to dest开发者_如何学Pythonination in G
;; if there is no path, the function produces false
(define (find-route origination destination G)
  (cond
    [(symbol=? origination destination) (list destination)]
    [else (local ((define possible-route 
            (find-route/list (neighbors origination G) destination G)))
        (cond
          [(boolean? possible-route) false]
          [else (cons origination possible-route)]))]))

;; find-route/list : (listof node) node graph  ->  (listof node) or false
;; to create a path from some node on lo-Os to D
;; if there is no path, the function produces false
(define (find-route/list lo-Os D G)
  (cond
    [(empty? lo-Os) false]
    [else (local ((define possible-route (find-route (first lo-Os) D G)))
        (cond
          [(boolean? possible-route) (find-route/list (rest lo-Os) D G)]
          [else possible-route]))]))

Does the problem lie in my code? Thank you.


OK the problem indeed lies in my own code. I was supposed to return a list, not a list containing the node and its neighboring nodes. i.e. (neighbor 'A Graph) is supposed to produce (list 'B 'E), and not (list 'A (list 'B 'E)).

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜