Practice With Searches #1
Putprop, Depth First, and Breadth First
1. Draw the graph for these putprops:
(putprop 'A '(B D) 'adjacent)
(putprop 'B '(A C E) 'adjacent)
(putprop 'C '(A E) 'adjacent)
(putprop 'D '(A) 'adjacent)
(putprop 'E '(D C) 'adjacent)
2. Depth First, trace a search from A to C
#1 expand A, put the new lists on a stack (in a lists of lists)
#2 ((B A) nodes are put on in reverse order
(D A))
#3 Pop first path off stack and extend node B, put back on stack:
((A B A)
(C B A)
(E B A)
(D A)) ;;from the first stack
#4 Pop first path off stack and extend node A. This results in
an infinite cycle.
3. Depth First, trace a search from E to B
#1 expand E, put the new lists on a stack
#2 ((D E) nodes are put on in reverse order
(C E))
#3 Pop first path off stack and extend node D, put back on stack:
((A D E)
(C E))
#4 Pop first path off stack and extend node A.
((B A D E)
(D A D E)
(C E))
#5 Pop path off stack, B is the goal node.
4. Breadth First, trace a search from A to C
#1 expand A, put new path lists on the queue
front ((B A) (D A)) rear (nodes are put on in reverse order)
#2 dequeue first path from the front of the queue. Expand node B,
put the new paths on the rear of the queue:
front ((D A) (A B A) (C B A) (E B A)) rear
#3 dequeue a path from the front of the queue, expand node D,
put the new paths on the rear of the queue:
front ((A B A) (C B A) (E B A) (A D A)) rear
#4 dequeue a path from the front of the queue, expand node A,
put the new paths on the rear of the queue:
front ((C B A) (E B A) (A D A) (B A B A) (D A B A)) rear
The path is found (C B A) path is in reverse
5. Breadth First, trace a search from E to B
#1 expand E, put new path lists on the queue
front ((D E) (C E)) rear (nodes are put on in reverse order)
#2 dequeue first path from the front of the queue. Expand node D,
put the new paths on the rear of the queue:
front ((C E) (A D E)) rear
#3 dequeue a path from the front of the queue, expand node C,
put the new paths on the rear of the queue:
front ((A D E) (A C E) (E C E)) rear
#4 dequeue a path from the front of the queue, expand node A.
front ((A C E) (E C E) (B A D E) (D A D E)) rear
#5 dequeue path from the fron of the queue, expand node A.
front ((E C E) (B A D E) (D A D E) (B A C E) (D A C E)) rear
#6 One more level 3 path, (E C E), expand node E.
front ((B A D E) (D A D E) (B A C E) (D A C E) (D E C E) (C E C E)) rear
#7 Dequeue (B A D E) and B is the goal node.
6. Depth first with "remove". Path from A to C
#1 expand A, put the new lists on a stack
(B A) nodes are put on in reverse order
(D A)
#3 Pop first path off stack and extend node B, put back on stack:
(A B A) remove the cycle, don't put this path on the stack
(C B A)
(E B A)
(D A) ;;from the first stack
#4 Pop first path off stack and extend node C.
(C B A)
(E B A)
(E B A)
(D A)
C is the goal node.