The algorithm we studied in the previous lecture was a backtracking algorithm to search for a goal in a given graph. There are some other graph search algorithms which are more flexible.
• Depth First Search
• Breadth-First Search
• Best First Search (will be discussed later)
Depth First Search:
In addition, to specify the search direction, a search algorithm must determine the order in which states are examined in the tree or the graph. There are two possibilities for the order in which states can be traversed
• Depth First Search
• Breadth-First Search
In a 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. e.g.
The depth-first search states in the above figure as
A, B, E, K, S, L, T, F, M, C, G, N, H, O, P, U, D, I, Q, J, R
The backtracking algorithm in the last lecture was also traversing space in a depth-first manner.
Also Read: Memory Management in Operating Systems
Breadth-first search 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.
The graph in figure 1, can be traversed according to breadth-first search as follow:
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U
To implement a breadth-first search, we will use two lists, open and closed, to keep track of the progress through the state space. The open list contains all 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 search. The closed list keeps a record of all nodes that have been examined.
The open is maintained as a queue, or first-in-first-out (FIFO) data structures. States are added to the right of the list and removed from the left. These biases search toward the states that have been an open the longest, causing the search to be breadth-first.
“While” loop is no longer satisfied (open = ) then it has search the entire graph without finding the desired goal; the search has failed.
The breadth-first search considers every node at each level of the graph before going deeper into 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.
Duplicate states can be discarded.
The breadth-first search does not maintain a list of states on the current path to a goal as the backtracking algorithm did on the list SL. If the path is required for the solution, it can be returned by the algorithm. It can be done by storing ancestor information along with the state as (state, parent).
e.g. at fourth iteration above open and close list can be stored as
open=[(D, A),(E, B),(F, B),(G, C),(H, C)] close=[(C, A),(B, A),(A, nill)]
When a gal is found, the algorithm may construct the solution path by tracking back along with the parent from the goal to the start state.
By simply changing the input and output procedure as Last-in-first-out, this algorithm will traverse the graph or tree in depth-first order. Or in other words, if we use stack instead of the queue this algorithm will work as depth-first search
Also Read: Best Open Source Password Manager Bitwarden
Unlike breadth-first search, a depth-first search is guaranteed to find the shortest path to a state the first time that state is encountered. Later in the search, a different path may be found in any state. If path length matters in a problem solver, when the algorithm encounters a duplicate state, the algorithm should save the version reached along the shortest path, This could be done by storing each state as a triple: (state, parent, length-of-path).
Breadth-first vs Depth-first Search:
The choice of depth-first search and breadth-first search depends on the specific problem being solved. Significant features include:
- Importance of finding the shortest path
- of branches
- Available Time and space resource
- The average length of the path
- How many solutions are required: one or duplicate.
- If we need the shortest path
- Not preferable if bad branching factor or too many branches
- If each state has an average of B children, the number of states on a given level is B times the number of states on the previous level. This gives states on level n.
- Quickly get deep into the search
- If it is known the solution path will be long, the depth-first search will not waste time searching a large number of “shallow” states in the graph.
- On the other hand, depth-first search gets lost in deep in a graph if the depth is higher.
- Suitable when there are too many branches because it focuses only at one branch at the time
- If the graph has on average of B children per state, this requires total space using B*n state to go on n levels deep into space.
Progressive deepening actually emulates BFS using DFS. The idea is to simply apply DFS to a specific level. If you find the goal, exit, otherwise repeat DFS to the next lower level. Go on doing this until you either reach the goal node or the full height of the tree is explored.
For example, apply a DFS to level 2 in the tree, if it reaches the goal state, exit, otherwise increase the level of DFS and apply it again until you reach level 4. You can increase the level of DFS by any factor. An example will further clarify your understanding.
Where ‘I’ is the goal node. We will apply DFS to level 2 in the tree. According to that the traversing order will be [S,A,C,D,B,E,F]. After exploring to level 2, the progressive deepening procedure will find out that the goal state has still not been reached. Hence, it will increment the level by a factor of, say 2, and will now perform a DFS in the tree to depth 4.
Now the traversing order will be [S, A,C,G,H,K,L,D,B,E,I]. As soon as the procedure finds the goal state it will quit. Notice that it guarantees to find the solution at a minimum depth like BFS. Imagine that there are a number of solutions below level 4 in the tree. The procedure would only travel a small portion of the search space and without large memory requirements, will find out the solution.