Uninformed search strategies are methods for exploring a state space when no domain-specific estimate of the remaining distance to the goal is available. They use information supplied by the problem formulation, such as the initial state, successor function, goal test, and sometimes path cost. Breadth-First Search explores nodes in increasing depth order. Depth-First Search follows one branch as deeply as possible before backtracking. Uniform-Cost Search expands the node with the lowest accumulated path cost. Other uninformed strategies include Depth-Limited Search and Iterative Deepening Search. These algorithms differ in their completeness, optimality, time complexity, and memory requirements. Breadth-First Search is optimal when all actions have equal cost, while Uniform-Cost Search can find an optimal solution when step costs are nonnegative and the relevant minimum-cost solution is reachable. Depth-First Search generally uses less memory but can become trapped in deep or infinite branches without appropriate safeguards. Selecting a strategy depends on the structure of the problem and available computational resources.
Uninformed Search Strategies
Uninformed search strategies explore a problem's state space without using additional heuristic knowledge about how close a state is to the goal.
Uninformed Search: Selection of nodes uses problem information without a heuristic estimate h(n).
Explanation
Variables
| Symbol | Meaning |
|---|---|
n | A node or state being considered by the search algorithm. |
g(n) | The accumulated path cost from the initial state to node n, when path cost is used. |
d | The depth of a node in the search tree. |
b | The branching factor, or average number of successors per node. |
h(n) | A heuristic estimate of remaining cost; uninformed strategies do not use this estimate. |
Example or application
Imagine searching for a particular name in an unsorted list when no information about its position is available. A basic search must inspect items according to a chosen strategy rather than using an estimate of where the name is likely to appear.
Text
Uninformed search is also called blind search because the algorithm does not receive an estimate of the distance to the goal. It relies on the problem definition, available actions, and path costs when applicable.
Key Points
Uninformed search does not use heuristic estimates.
It relies on the formal problem definition.
Breadth-First Search explores by depth.
Depth-First Search explores deeply before backtracking.
Uniform-Cost Search considers accumulated path cost.
Completeness and optimality depend on the algorithm and problem assumptions.
Applications
Small puzzle-solving problems
Graph traversal
Basic route exploration
State-space exploration
Problems without useful heuristic information
Learning Outcomes
Define uninformed or blind search.
Compare major uninformed search strategies.
Explain the difference between completeness and optimality.
Practice Questions
Why is uninformed search called blind search?
How does Breadth-First Search differ from Depth-First Search?
Which uninformed strategy selects nodes using accumulated path cost?
Related Concepts
Breadth-First Search
Depth-First Search
Uniform-Cost Search
Informed Search and Heuristics
Common Mistakes
Assuming uninformed search means random search.
Confusing path cost with heuristic cost.
Assuming all uninformed strategies are optimal.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Russell, S. and Norvig, P. Artificial Intelligence: A Modern Approach, uninformed search chapter.
- Nilsson, N. J. Principles of Artificial Intelligence, search methods.
Suggest a correction or source · More in Artificial Intelligence & Machine Learning