Section 3.3 Uninformed Search

Now that we understand trees, graphs, and state spaces, we can finally explore how AI systems actually search through these structures to find solutions. In this section, we’ll look at uninformed search—sometimes called blind search—which is the most basic approach to searching through a state space.

An uninformed search strategy uses only the information that comes with the problem itself: where you start, what moves you can make, and how to recognize when you’ve reached the goal. The algorithm has no additional guidance about which paths are more promising or how close a state might be to the goal.

Think of it like exploring a maze with no map, no compass, and no sense of direction. You can only move step by step and explore systematically, but you have no "intuition" about which direction to head. You might try every path until you eventually find the exit—or get hopelessly lost.

Because they lack guidance, uninformed search methods are generally slower than informed methods and take more time to find solutions. However, they are guaranteed to find a solution (if one exists) and, in some cases, guaranteed to find the best one. This makes them valuable tools when:

No helpful "rule of thumb" is available to guide the search
The state space is small enough to explore completely
You need a guaranteed best answer in a known problem domain

Think of It This Way....

Uninformed search is like trying to find a book in a huge library without using the catalog. You have to walk down every aisle, check every shelf, and examine every book until you happen to find the one you’re looking for. It will work eventually, but it’s not very efficient!

Subsection 3.3.1 Breadth-First Search (BFS)

Breadth-first search (BFS) is one of the simplest search strategies. It explores all nodes at the current level before moving to the next level. In other words, BFS examines the shallowest (closest to the start) unexamined node first.

How it works:

Imagine you’re at the entrance of a maze. BFS is like exploring every path one step at a time: you take one step down every possible corridor, then two steps down every possible corridor, then three steps, and so on. You never go deeper down any single path until you’ve checked everything at your current distance from the start.

The algorithm works like this:

Start with the initial node and place it in a queue (think of a line at a store—first in, first out)
Remove the first node from the queue
If this node is the goal, you’re done!
Otherwise, expand the queue by generating all its children and add them to the back of the queue
Repeat until the queue is empty or the goal is found

Properties of BFS:

Table 3.3.1. Properties of Breadth-First Search

Property	What It Means
Complete	Yes—it will always find a solution if one exists
Optimal	Yes—but only if all moves have the same cost
Time	Can be very slow—it may need to explore many nodes
Space	Can use a lot of memory—it stores many nodes at once

Best for: Problems where the shortest path is the goal, the number of possible moves from each state is small, memory is not a concern, and all moves cost the same.

Weakness: BFS can use a huge amount of memory. For a problem where each state has 10 possible moves, BFS might need to store billions of states in memory before finding a solution!

Example: Finding the shortest route in a city where all roads take the same amount of time.

Subsection 3.3.2 Depth-First Search (DFS)

Depth-first search (DFS) takes the opposite approach. DFS explores as far as possible along each branch before turning back. It expands the deepest (farthest from the start) unexpanded node first.

How it works:

Imagine you’re exploring a maze by walking down one corridor as far as it goes. When you hit a dead end, you turn back to the last fork and try the next corridor. You keep doing this until you find the exit.

The algorithm works like this:

Start with the initial node and place it on a stack (think of a stack of plates—last in, first out)
Remove the top node from the stack
If this node is the goal, you’re done!
Otherwise, expand the node by generating all its children and push them onto the stack
Repeat until the stack is empty or the goal is found

Properties of DFS:

Table 3.3.2. Properties of Depth-First Search

Property	What It Means
Complete	No—it can get stuck going in circles forever
Optimal	No—it may find a long, winding path instead of a short one
Time	Can be very slow—it may explore very deep paths
Space	Very efficient—it only stores the current path

Best for: Problems where the solution is deep in the tree, memory is limited, or you need to explore all possible solutions.

Weakness: DFS can get stuck in infinite loops if the state space has cycles. It also might find a solution that is not the best one.

Example: Solving a puzzle where the goal is far from the start, and you want to explore all possibilities without using too much memory.

Subsection 3.3.3 Depth-Limited Search (DLS)

Depth-limited search (DLS) is a version of DFS that avoids the infinite-loop problem by setting a maximum depth limit. The algorithm stops exploring any branch once it reaches this limit.

How it works:

It works exactly like DFS, but with a rule: "Don’t go deeper than depth L." If you reach depth L without finding the goal, simply stop exploring that branch and turn back.

Properties of DLS:

Table 3.3.3. Properties of Depth-Limited Search

Property	What It Means
Complete	No—if your limit is too shallow, you’ll miss the solution
Optimal	Only if the solution is within the depth limit
Time	Depends on your chosen limit
Space	Very efficient—it only stores the current path and the limit value

Best for: Problems where you know how deep the solution is, or you want to avoid infinite loops.

Weakness: If you set the limit too low, you might not find the solution. If you set it too high, the search becomes as slow as regular DFS.

Subsection 3.3.4 Comparing Uninformed Search Strategies

Table 3.3.4. Comparison of all uninformed search strategies

Algorithm	Complete?	Finds Best?	Memory Use	Best For
BFS	Yes	Yes*	High	Shortest path, all moves equal
DFS	No	No	Low	Deep solutions, memory-limited
DLS	No	No	Low	Known depth limit

*Finds the best solution only when all moves have the same cost

Subsection 3.3.5 When to Use Uninformed Search

Uninformed search is the right tool when:

You have no helpful hints — If you can’t define a "rule of thumb" to guide the search, uninformed search may be your only option.
The problem is small — For small state spaces (like Tic-Tac-Toe), the extra work of designing a clever strategy isn’t worth it.
You need guaranteed results — Uninformed search provides mathematical guarantees that informed methods might not offer.

You’re building a foundation — Understanding uninformed search is a prerequisite for understanding informed search, just as learning basic arithmetic comes before algebra.

Choosing Your Uninformed Search Strategy.

Think of it like searching for a lost item in a building: If you want to check every room on each floor before moving up, use BFS. If you want to search the same room on every floor (101, 201, 301) before moving to the next, use DFS.

You have attempted of activities on this page.

Prev Top Next