Texas State CS 5346 - Depth-First and Breadth-First Search

Unformatted text preview:

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Depth-First and Breadth-First SearchIn addition to specifying a search direction (data-driven or goal-driven), a search algorithm must determine the order in which states are examined in the tree or the graph. This section considers two possibilities for the order in which the nodes of the graph are considered: depth-first and breadth-first search.Consider the graph represented in Figure 3.15. States are labeled (A, B, C .... ) so that they can be referred to in the discussion that follows. In depth-first search, when a state is examined all of its children and their descendants are examined before any of its siblings. Depth-first search goes deeper into the search space whenever this is possible. Only when no further descendants of a state can be found are its siblings considered. Depth-first search examines the states in the graph of Figure 3.15 in the order A, B, E, K, S, L, T, F, M, C, G, N, H, 0, P, U, D, I, Q, J, R. The backtrack algorithm of Section 3.2.2 implemented depth-first search.Breadth-first search, in contrast, explores the space in a level-by-level fashion. Only when there are no more states to be explored at a given level does the algorithm move on to the next level. A breadth-first search of the graph of Figure 3.15 considers the states in the order A, B, C, D, E, F, G, H, I, J, K, L, M, N, 0, P, Q, R, S, T, U.We implement breadth-first search using lists, open and closed, to keep track of progress through the state space. open, like NSL in backtrack, lists states that have been generated but whose children have not been examined. The order in which states are removed from open determines the order of the search. closed records states already examined. closed is the union of the DE and SL lists of the backtrack algorithm.function breadth_first_search;begin open := [Start]; % initialize closed := [ ]; while open ≠ [ ] do % states remain begin remove leftmost state from open, call it X; if X is a goal then return SUCCESS % goal foundelse begin generate children of X; put X on closed; discard children of X if already on open or closed; % loop check put remaining children on right end of open % queueend end return FAIL % no states leftend.Child states are generated by inference rules, legal moves of a game, or other state transition operators. Each iteration produces all children of the state X and adds them to open. Note that open is maintained as a queue, or first-in-first-out (FIFO) data structure. States are added to the right of the list and removed from the left. This biases search toward the states that have been on open the longest, causing the search to be breadth-first. Child states that have already been discovered (already appear on either open or closed) are discarded. If the algorithm terminates because the condition of the "while" loop is no longer satisfied (open = [ ]) then it has searched the entire graph without finding the desired goal: the search has failed.A trace of breadth_first_search on the graph of Figure 3.15 follows. Each successivenumber, 2,3,4, ... , represents an iteration of the "while" loop. U is the goal state.1. open = [A]; closed = []2. open = [B,C,D]; closed = [A]3. open = [C,Q,E,F]; closed = [B,A]4. open = [D,E,F,G,H]; closed = [C,B,A]5. open = [E.F,G,H,I,J]; closed = [D,C,B,A]6. Open = [F,G,H,I,J,K,L]: closed = [E,D.C,B,A]7. open = [G,H,I,J,K,L,M] (as L is already on open); closed = [F,E,D,C,B,A]8. open = [H,I,J,K,L,M,N]: closed = [G,F,E,D,C,B,A]9. and so on until either U is found or open = [ ]Figure 3.16 illustrates the graph of Figure 3.15 after six iterations of breadth-first-search. The states on open and closed are highlighted. States not shaded have not been discovered by the algorithm. Note that open records the states on the "frontier" of the search at any stage and that closed records states already visited.Because breadth-first-search considers every node at each level of the graph before going deeper into the space, all states are first reached along the shortest path from the start state. Breadth-first-search is therefore guaranteed to find the shortest path from the start state to the goal. Furthermore, because all states are first found along the shortest path, any states encountered a second time are found along a path of equal or greater length. Because there is no chance that duplicate states were found along a better path, the algorithm simply discards any duplicate states.It is often useful to keep other information on open and closed besides the names of the states. For example, note that breadth_first_search does not maintain a list of states on the current path to a goal as backtrack did on the list SL; all visited states are kept on closed. If the path is required for a solution, it can be returned by the algorithm. This can be done by storing ancestor information along with each state. A state may be saved along with a record of its parent state, i.e., as a (state, parent) pair. If this is done in the search of Figure 3.15, the contents of open and closed at the fourth iteration would be:open = [(D,A), (E.B), (F,B), (G,C), (H,C)]; closed = [(C,A), (B,A), (A,nil)]The path (A, B, F) that led from A to F could easily be constructed from this information. When a goal is found, the algorithm may construct the solution path by tracing back along parents from the goal to the start state. Note that state A has a parent of nil, indicating that it is a start state; this stops reconstruction of the path. Because breadth-first-search finds each state along the shortest path and retains the first version of each state, this is the shortest path from a start to a goal.Figure 3.17 shows the states removed from open and examined in a breadth-first-search of the graph of the 8-puzzle. As before, arcs correspond to moves of the blank up, to the right, down, and to the left. The number next to each state indicates the order in which it was removed from open. States left on open when the algorithm halted are not shown.Next, we create a depth-first search algorithm, a simplification of the backtrack algorithm already presented in Section 3.2.3. In this algorithm, the descendant states are added and removed from the left end of open: open is maintained as a stack, or last-in-first-out (LIFO), structure. The organization of open as a stack directs search toward the most


View Full Document

Texas State CS 5346 - Depth-First and Breadth-First Search

Download Depth-First and Breadth-First Search
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Depth-First and Breadth-First Search and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Depth-First and Breadth-First Search 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?