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))
.
精彩评论