99081567 - Nicholas Hardman – Search and Control in AI – Assignment 2 - 1 -
Depth First vs Breadth First Searches in Lisp
Source code:
(defun binary-tree (x)
"The Data Set, the actual tree"
(list (* 2 x) (+ 1 (* 2 x))))
(defun finite-binary-tree(n)
"This Function was given in class
It Limits the tree to the value passed n"
#'(lambda(x)
(remove-if #'(lambda (child) (> child n))
(binary-tree x))))
(defun tree-search (states goal-p successors combiner)
"Search algorythem dependant on parameters"
(print states)
(cond ((null states) fail)
((funcall goal-p (car states)) (car states))
(t (tree-search
(funcall combiner
(funcall successors (car states))
(cdr states))
goal-p successors combiner))))
(defun depth-first-search (start goal-p successors)
"newest nodes expanded until goal is reached and
reverts when cutoff is hit - 128"
(tree-search (list start) goal-p successors #'append))
(defun breadth-first-search (start goal-p successors)
"Oldest node searched first and expanded nodes are added to the end of the
search list. Finding node 4 will take 4 turns and finding 66 will take 66"
(tree-search (list start) goal-p successors #'swapsuccessors))
(defun swapsuccessors(x y)
"moves the child nodes to the end of the list"
(append y x))
(defun is (value)
#'(lambda (x) (eql x value)))
Search Values
To demonstrate the pro’s and con’s of each search I will demonstrate searching for 66 with the depth first and 5 with the depth first. This gives an obvious better technique for each number.
The Depth first Search
Check if the queue is empty
If it is empty
The search has failed
End search
If it is not empty
Check if the next item in the queue (states) is the goal,
If it is the goal
The search is successful.
End Search
If it is not the goal
You remove it from the queue
Add its children if they are less than 128 to the front of the queue.
Loop back to start until the search is complete.
How the depth first search finds the number 66
The Breadth first Search
Check if the queue is empty
If it is empty
The search has failed
End search
If it is not empty
Check if the next item in the queue (states) is the goal,
If it is the goal
The search is successful.
End Search
If it is not the goal
You remove it from the queue
Add its children if they are less than 128 to the back of the queue.
Loop back to start until the search is complete.
Conclusion
Both strategies take the same route searching for the solution. That’s because they are blind searches. The DFS checks 11 nodes to find node 66. The BFS would take 66. The BFS checks 5 nodes to find 5 where as the DFS checks 35.
The DFS can only be used on a finite tree because if the tree infinite it will pass the goal and search the very left branch of the tree until the stack overflows. The DFS only records the current path so it tends to require less memory.
The BFS may use more memory but guarantees to find the shortest path.
Neither searches are very effective. The best search depends on the data.
Trace data for examples given in the assignment
(depth-first-search 1 (is 190)(finite-binary-tree 16384))
(1)
(2 3)
(4 5 3)
.... data removed to save paper
error: argument stack overflow
> (depth-first-search 1 (is 7987)(finite-binary-tree 16384))
(1)
(2 3)
(4 5 3)
.... data removed to save paper
error: argument stack overflow
> (depth-first-search 1 (is 14397)(finite-binary-tree 16384))
(1)
(2 3)
(4 5 3)
.... data removed to save paper
error: argument stack overflow
> (depth-first-search 1 (is 2048)(finite-binary-tree 16384))
(1)
(2 3)
(4 5 3)
(8 9 5 3)
(16 17 9 5 3)
(32 33 17 9 5 3)
(64 65 33 17 9 5 3)
(128 129 65 33 17 9 5 3)
(256 257 129 65 33 17 9 5 3)
(512 513 257 129 65 33 17 9 5 3)
(1024 1025 513 257 129 65 33 17 9 5 3)
(2048 2049 1025 513 257 129 65 33 17 9 5 3)
2048
> (breadth-first-search 1 (is 190)(finite-binary-tree 16384))
(1)
(2 3)
(3 4 5)
(4 5 6 7)
.... data removed to save paper
error: argument stack overflow
> (breadth-first-search 1 (is 7987)(finite-binary-tree 16384))
(1)
(2 3)
(3 4 5)
(4 5 6 7)
.... data removed to save paper
error: argument stack overflow
> (breadth-first-search 1 (is 14397)(finite-binary-tree 16384))
(1)
(2 3)
(3 4 5)
.... data removed to save paper
error: argument stack overflow
> (breadth-first-search 1 (is 2048)(finite-binary-tree 16384))
(1)
(2 3)
(3 4 5)
.... data removed to save paper
error: argument stack overflow
> (breadth-first-search 1 (is 35)(finite-binary-tree 128))
(1)
(2 3)
(3 4 5)
(4 5 6 7)
(5 6 7 8 9)
(6 7 8 9 10 11)
.... data removed to save paper
(34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67)
(35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69)
35
> (breadth-first-search 1 (is 46)(finite-binary-tree 128))
(1)
(2 3)
(3 4 5)
(4 5 6 7)
.... data removed to save paper
(46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91)
46
> (depth-first-search 1 (is 32)(finite-binary-tree 128))
(1)
(2 3)
(4 5 3)
(8 9 5 3)
(16 17 9 5 3)
(32 33 17 9 5 3)
32
> (depth-first-search 1 (is 86)(finite-binary-tree 128))
(1)
(2 3)
(78 79 5 3)
(79 5 3)
(5 3)
(10 11 3)
(20 21 11 3)
(40 41 21 11 3)
(80 81 41 21 11 3)
(81 41 21 11 3)
(41 21 11 3)
(82 83 21 11 3)
(83 21 11 3)
(21 11 3)
(42 43 11 3)
(84 85 43 11 3)
(85 43 11 3)
(43 11 3)
(86 87 11 3)
86