Search fundamentals

The ability to plan before acting is a hallmark of intelligence. Before going on a trip to a different country, before starting a new project, before writing functions in code, we plan. Planning happens at different levels of detail to strive for the best possible outcome when carrying out the tasks involved to accomplish goals.

Plans rarely work out perfectly in the way that we envision at the start. We live in a world where things are constantly changing, so it is impossible to account for all the variables and unknowns along the way. Regardless of the plan we started with, we almost always deviate. We need to (again) make a new plan from our current point going forward as unexpected events occur. As a result, the final plan that is carried out is usually quite different from the original one.

Searching is a way to guide planning by creating steps in a plan. When we plan a trip, for example, we search for routes to take, evaluate the stops along the way and what they offer, and search for accommodations and activities that we like and can afford. Depending on the results of these searches, the plan changes.

One scenario where search algorithms are useful is finding the shortest path to the goal in a maze. Suppose that we’re in a square maze that is 10 blocks by 10 blocks. There’s a goal that we want to reach and barriers that we cannot step into or over. The objective is to find a path to the goal while avoiding barriers with as few steps as possible by moving north, south, east, or west. In this example, the “player” cannot move diagonally.

Uninformed search is also known as unguided search, blind search, or brute-force search. Uninformed search algorithms have no additional information about the domain of the problem apart from the representation of the problem, which is usually a tree.

Breadth-first search

Breadth-first search is an algorithm used to traverse or generate a tree. This algorithm starts at a specific node, usually the root, and explores every node at that depth before exploring the next depth of nodes. Think of BFS like dropping a stone into a calm pond. The ripples expand uniformly in all directions, touching everything 1 meter away, then everything 2 meters away, and so on. The algorithm mimics this expanding ring, visiting all neighbors at the current depth before moving outward. This guarantees finding the shortest path in unweighted graphs (graphs where all edges have the same cost).

Depth-first search

Depth-first search is another algorithm used to traverse a tree or generate nodes and paths in a tree. Think of DFS like a maze explorer who commits to a single path, walking as far as possible until hitting a dead end. Only then do they backtrack to the last intersection to try a different turn. Unlike the cautious, expanding nature of BFS, DFS is aggressive and dives deep immediately.

Play with a search simulation

The simulation below illustrates the difference between BFS and DFS. The agent attempts to find the goal in the maze using both algorithms. You can tap Reset to start a new simulation with a random maze. Play with choosing different goals in the maze to see how the algorithms perform by tapping on the maze grid.