1 Explain what is a breadth-first search. 2 Implement the informal algorithm ( p
ID: 3801772 • Letter: 1
Question
1 Explain what is a breadth-first search.
2 Implement the informal algorithm ( pseudo code) of breadth first search. Provide the description of what the code does.
3 Implement the breadth first search algorithm in Lisp. Enter your function definition into a text file. Then load it into LISP.
4 Explain what is the depth first search, and what is the difference between breadth-first, and depth-first search.
5 Implement the informal algorithm ( pseudo code) of depth-first search. Provide the description of what the code does.
6 Implement the depth-first search algorithm in Lisp. Enter your function definition into a text file. Then load it into LISP.
I need the answer for Q# 3,5,6
Explanation / Answer
3. LISP Program
(defun run-breadth (start goal)
(declare (special *open*)
(special *closed*)
(special *goal*))
(setq *open* (list start))
(setq *closed* nil)
(setq *goal* goal)
(breadth-first))
(defun breadth-first ()
(declare (special *open*)
(special *closed*)
(special *goal*)
(special *moves*))
(cond ((null *open*) nil)
(t (let ((state (car *open*)))
(cond ((equal state *goal*) 'success)
(t (setq *closed* (cons state *closed*))
(setq *open*
(append (cdr *open*)
(generate-descendants state *moves*)))
(breadth-first)))))))
;;; Generates all the descendants of a given state.
(defun generate-descendants (state moves)
(declare (special *open*)
(special *closed*))
(cond ((null moves) nil)
(t (let ((child (funcall (car moves) state))
(rest (generate-descendants state (cdr moves))))
(cond ((null child) rest)
((member child rest :test #'equal) rest)
((member child *open* :test #'equal) rest)
((member child *closed* :test #'equal) rest)
(t (cons child rest)))))))
5.
Depth-first search is to travel as deep as possible from neighbour to neighbour before backtracking.
What determines how deep is possible is to follow edges, and not visit any vertex twice.
To do this properly we need to keep track of which vertices have already been visited,
plus how we got to (the path to...) where we currently are,
so that we can backtrack. We could keep track of which nodes were visited in a boolean array,
and a stack to push nodes onto that we mean to visit Here's some pseudocode:
DFS(G,v) ( v is the vertex where the search starts )
Stack S := {}; ( start with an empty stack )
for each vertex u, set visited[u] := false;
push S, v;
while (S is not empty) do
u := pop S;
if (not visited[u]) then
visited[u] := true;
for each unvisited neighbour w of u
push S, w;
end if
end while
END DFS()
It would probably be useful to keep track of the edges we used to visit the vertices, since these edges
would span the vertices visited. One way to do this is with another array predecessor[u] which indicates
which vertex u was reached from. When we are processing the neighbours of, say, vertex u,
for each neighbour (say v) of u that we push onto the stack, we set predecessor[v] to u.
Eventually we end up with a tree: an acyclic, connected graph of all the vertices that can be reached
from our starting point.
What happens if our original graph G isn't connected? Then DFS(G,v) won't visit any vertices
that aren't connected to its starting point. In that case we need an outer loop that iterates
over unvisited vertices, and then calls DFS(G,V).
The end result is a forest (a collection of trees) representing the connected components of G.
6. LISP Program
(defun depth-first-search (start goal been-list moves)
(cond ((equal start goal)
(reverse (cons start been-list)))
(t (try-moves start goal been-list moves moves))))
; Try-moves scans down the list of moves in moves-to-try,
; attempting to generate a child state. If it produces
; this state, it calls depth-first-search to complete the search.
(defun try-moves (start goal been-list moves-to-try moves)
(cond ((null moves-to-try) nil)
((member start been-list :test #'equal) nil)
(t (let ((child (funcall (car moves-to-try) start)))
(if child
(or (depth-first-search (funcall (car moves-to-try) start)
goal
(cons start been-list)
moves)
(try-moves start goal been-list (cdr moves-to-try) moves))
(try-moves start goal been-list (cdr moves-to-try) moves))))))
; run-depth-first calls depth-first-search, initializing the been-list to ().
(defun run-depth (start goal moves)
(depth-first-search start goal () moves))
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.