Last updated: Thu, 26 Mar 2015 13:23:36 -0400
Here are some slides about searching via generative recursion.
Note: These slides are from a previous semester. We provide them because learning is often aided by looking at different presentations of the same material. However, previous iterations of the course had a different structure and different style requirements. Read these slides for their ideas only. When there are discrepancies, follow the rules of our current course.
Understand the concept of backtracking and when and how to write backtracking functions.
Understand how accumulators are also useful in generative recursive functions.
(require rackunit) (require racket/set) ; A Node is a Symbol ; Represents a vertex in a graph. ; A Path is a ListOf<Node> ; Represents a sequence of connected Nodes. ; A Graph is a ListOf<(cons Node ListOf<Nodes>)> ; A list of adjacency lists representing a directed graph. ; WHERE: (map first G) has no duplicates and represents the nodes in G ; and the rest of each adj list are the neighbors of the first node. (define SAMPLE-G '((A B E) (B E F) (C D) (D) (E C F) (F D G) (G))) ; get-nodes : Graph -> ListOf<Node> ; Returns the nodes in g. (define (get-nodes g) (map first g)) ; neighbors : Node Graph -> ListOf<Node> ; Returns a list of all nodes v such that G has edge u-v. (define (neighbors u G) (rest (assq u G))) ; find-path : Node Node Graph -> Maybe<Path> ; Finds a path from orig to dest in G, or #f if no such path exists. ; Strategy: ??? ; Termination argument: ??? (define (find-path orig dest G) (cond [(symbol=? orig dest) (list dest)] [else (local ((define next (neighbors orig G)) (define path/#f (find-path/list next dest G))) (if (false? path/#f) #f (cons orig path/#f)))])) ; find-path/list : ListOf<Node> Node Graph -> Maybe<Path> ; Finds a path from some node in origs to dest in G. ; Returns #f is there is no path from any node in origs to dest. ; Strategy: data decomposition on origs : ListOf<Node> (define (find-path/list origs dest G) (cond [(empty? origs) #f] [else (local ((define path/#f (find-path (first origs) dest G))) (if (false? path/#f) (find-path/list (rest origs) dest G) path/#f))])) (check-equal? (find-path 'C 'D SAMPLE-G) '(C D)) (check set-member? '((E F D) (E C D)) (find-path 'E 'D SAMPLE-G)) (check-false (find-path 'C 'G SAMPLE-G))
- Implement the following list-processing function:
Revise find-path to use find instead of find-path/list.
- Revise find-path such that the following test case does not loop forever:
(define CYCLIC-G '((A B E) (B E F) (C B) (D) (E C F) (F D G) (G))) (check set-member? '((B F D) (B E F D) (B E C D)) (find-path 'B 'D CYCLIC-G))Be sure to state a proper invariant if you use an accumulator. Also, update the termination argument such that it explains why the function always terminates.