Uninformed Search Techniques- Depth First Search, Breadth First Search, Depth Limit Search, and Search Strategy Comparison

Uninformed search is often known as blind search as well. This search is also one of the search techniques which have no additional information about the states beyond provided in the problem definition. All they can do is generate a successor and distinguish a goal state from a non-goal state. The search technique typically visits all the nodes of a tree in a pre-defined order looking for its goal. In depth-first search, the search is performed first by dividing downwards into a tree as quickly as possible. It does this by generating a child node from the most recently expanded node and generating that child’s children and so on. It keeps on performing this task until a goal is found. If the goal is not found the program backtracks to most recently expanded node and generates another of its children when a leaf node is found. This process continues until a goal is found. This strategy can be implemented by tree search with a stack. The advantages of DFS are: Space complexity is very modest that is O (b.d) where b is the branching factor and d is the depth of solution and it is easy to implement recursively. The drawback of DFS is that it can make a wrong choice and get stuck while going down a very long (even infinite) path when a different choice would lead to the solution near the root of the search tree. It is not complete (goal is not sure to achieve). The breadth first search technique is performed by exploring all nodes at a given level before proceeding to the next level. This means all the immediate children of a node are expanded before any of the grandchildren are considered. The nodes that are visited first will be expanded first following the FIFO rule (First in First out). The advantage of BFS is that it is complete which means the goal is fixed to achieve. The problem of an unbounded tree can be alleviated by supplying depth for search with a pre-determined depth limit (L). That is node at level L is treated as if they have no successor. This approach is called depth limited search. This algorithm solves the infinite path problem. Unfortunately it also introduces an additional source of incompleteness if we choose the value of L such that L is less that is d (L < d). This algorithm can be terminated with the two kinds of failure and they are standard failure and cut-off failure.

Summary

Uninformed search is often known as blind search as well. This search is also one of the search techniques which have no additional information about the states beyond provided in the problem definition. All they can do is generate a successor and distinguish a goal state from a non-goal state. The search technique typically visits all the nodes of a tree in a pre-defined order looking for its goal. In depth-first search, the search is performed first by dividing downwards into a tree as quickly as possible. It does this by generating a child node from the most recently expanded node and generating that child’s children and so on. It keeps on performing this task until a goal is found. If the goal is not found the program backtracks to most recently expanded node and generates another of its children when a leaf node is found. This process continues until a goal is found. This strategy can be implemented by tree search with a stack. The advantages of DFS are: Space complexity is very modest that is O (b.d) where b is the branching factor and d is the depth of solution and it is easy to implement recursively. The drawback of DFS is that it can make a wrong choice and get stuck while going down a very long (even infinite) path when a different choice would lead to the solution near the root of the search tree. It is not complete (goal is not sure to achieve). The breadth first search technique is performed by exploring all nodes at a given level before proceeding to the next level. This means all the immediate children of a node are expanded before any of the grandchildren are considered. The nodes that are visited first will be expanded first following the FIFO rule (First in First out). The advantage of BFS is that it is complete which means the goal is fixed to achieve. The problem of an unbounded tree can be alleviated by supplying depth for search with a pre-determined depth limit (L). That is node at level L is treated as if they have no successor. This approach is called depth limited search. This algorithm solves the infinite path problem. Unfortunately it also introduces an additional source of incompleteness if we choose the value of L such that L is less that is d (L < d). This algorithm can be terminated with the two kinds of failure and they are standard failure and cut-off failure.

Things to Remember

  • Uninformed search is often known as blind search as well. This search is also one of the search techniques which have no additional information about the states beyond provided in the problem definition.
  • The search technique typically visits all the nodes of a tree in a pre-defined order looking for its goal.
  • In depth first search, search is performed first by dividing downwards into a tree as quickly as possible.
  • It does this by generating a child node from the most recently expanded node and generating that child’s children and so on.
  • It keeps on performing this task until a goal is found.  If the goal is not found the program backtracks to most recently expanded node and generates another of its children when a leaf node is found. This process continues until a goal is found.
  • This strategy can be implemented by tree search with a stack.
  • The advantages of DFS are: Space complexity is very modest that is O (b.d) where b is the branching factor and d is the depth of solution and it is easy to implement recursively.
  • The drawback of DFS is that it can make a wrong choice and get stuck while going down a very long (even infinite) path when a different choice would lead to the solution near the root of the search tree.
  • It is not complete (goal is not sure to achieve).
  • The breadth first search technique is performed by exploring all nodes at a given level before proceeding to the next level.
  • The nodes that are visited first will be expanded first following the FIFO rule (First in First out).
  • The advantage of BFS is that it is complete which means the goal is fixed to achieve.
  • Depth limited search solves the infinite path problem. Unfortunately it also introduces an additional source of incompleteness if we choose the value of L such that L is less that is d (L < d).
  • This algorithm can be terminated with the two kinds of failure and they are standard failure and cut-off failure.

MCQs

No MCQs found.

Subjective Questions

No subjective questions found.

Videos

No videos found.

Uninformed Search Techniques- Depth First Search, Breadth First Search, Depth Limit Search, and Search Strategy Comparison

Uninformed Search Techniques- Depth First Search, Breadth First Search, Depth Limit Search, and Search Strategy Comparison

Blind Search / Uninformed Search:

Uninformed search is often known as blind search as well. This search is also one of the search techniques which have no additional information about the states beyond provided in the problem definition. All they can do is generate a successor and distinguish a goal state from a non-goal state. The search technique typically visits all the nodes of a tree in a pre-defined order looking for its goal. No cleverness is used to decide where to look next. The types of uninformed search techniques are discussed below:

Depth First Search (DFS):

In a depth-first search, the search is performed first by dividing downwards into a tree as quickly as possible. It does this by generating a child node from the most recently expanded node and generating that child’s children and so on. It keeps on performing this task until a goal is found. If the goal is not found the program backtracks to most recently expanded the node and generates another of its children when a leaf node is found. This process continues until a goal is found. This strategy can be implemented by tree search with a stack.
Algorithm:

  1. Push the starting node in the stack.
  2. If the stack is empty return FAILURE and stop.
  3. If the first element on the stack is the goal node then return SUCCESS otherwise.
  4. Remove and expand the first element and place the children at the front of the stack.
  5. Return to step 2.

Advantages:

  • Space complexity is very modest that is O (b.d) where b is the branching factor and d is the depth of solution.
  • It is easy to implement recursively.

Drawbacks:

  • The drawback of DFS is that it can make a wrong choice and get stuck while going down a very long (even infinite) path when a different choice would lead to the solution near the root of the search tree.
  • It is not complete (goal is not sure to achieve).
  • In the worst case, this algorithm will generate O (bm) where m is the depth maximum.

Breadth First Search (BFS):

The breadth-first search technique is performed by exploring all nodes at a given level before proceeding to the next level. This means all the immediate children of a node are expanded before any of the grandchildren are considered. The nodes that are visited first will be expanded first following the FIFO rule (First in First out). That is all the nodes of level L are expanded before expanding any node of level L+1. This algorithm can be implemented by tree using the queue.

Algorithm:

  1. Place the starting node on the queue.
  2. If the queue is empty then return FAILURE and stop.
  3. If the first element on the queue is goal node then return SUCCESS and stop.
  4. Otherwise, remove and expand the first element from the queue and place all the children at the end of the queue.
  5. Return step 2.

Advantage: The advantage of BFS is that it is complete which means the goal is fixed to achieve.

Disadvantages:

  • Exponential time complexity that is O (bd) where d is the depth of the solution.
  • Exponential space complexity that is O (bd).

Depth-Limited Search:

The problem of an unbounded tree can be alleviated by supplying depth for search with a pre-determined depth limit (L). That is the node at level L is treated as if they have no successor. This approach is called depth limited search. This algorithm solves the infinite path problem. Unfortunately, it also introduces an additional source of incompleteness if we choose the value of L such that L is less that is d (L < d). This algorithm can be terminated with the two kinds of failure and they are:

  • Standard failure: In this type of failure there is no goal of the problem definition.
  • Cut-off failure: In this type of failure the goal is beyond the pre-determined level.

Depth First Search (DFS)

Breadth First Search (BFS)

Depth-Limited Search (DLS)

It is a search technique which is tracked down from roots to its child and again generating child’s children until the goal is achieved and backtracking.

It is a search technique where each node at each level is explored before proceeding to the next level.

It is a search technique following the technique similar to DFS.

It is implemented using stack.

It is implemented using queue.

It is implemented using stack.

Space complexity is O (b.d).

Space complexity is O (bd).

Space complexity is O (b.l).

References:

  1. Elaine Rich, Kevin Knight 1991, "Artificial Intelligence".
  2. Nilsson, Nils J. Principles of Artificial Intelligence, Narosa Publishing House New Delhi, 1998.
  3. Norvig, Peter & Russel, Stuart Artificial Intelligence: A modern Approach, Prentice Hall, NJ, 1995
  4. Patterson, Dan W. Introduction to Artificial Intelligence and Expert Systems, Prentice Hall of India Private Limited New Delhi, 1998.

Lesson

Search Techniques

Subject

Computer Engineering

Grade

Engineering

Recent Notes

No recent notes.

Related Notes

No related notes.