AI Foundations: Search

Imagine you're in a new city, looking for the best coffee shop. Do you explore every street methodically? Follow your instincts toward the busy areas? Or pull up Google Maps and trust its suggested route? The way you solve this everyday problem reveals something fascinating about how computers think.

From Google Maps finding your fastest route to Netflix recommending your next favorite show, a powerful family of algorithms drives these everyday AI experiences. These algorithms—from the methodical Breadth-First Search to the clever A*—don't just help us navigate cities; they're the foundation for how computers solve complex problems.

In this guide, we'll explore these search algorithms through a lens you already understand: finding your way around a city. Along the way, you'll discover why some approaches work better than others, and how these same principles power everything from social media recommendations to robot navigation.

How Computers See Cities: An Introduction to Graphs

Before we look at different ways to navigate a city, let’s peek into how a computer “sees” a city’s layout. To a computer, a city isn’t a collection of buildings, streets, and landmarks - it’s what computer scientists call a graph.

Imagine standing at an intersection. From there, you can see several different roads leading to other intersections. To a computer, each intersection is a node (or vertex), and each road is an edge connecting these nodes. This concept of nodes and edges isn’t only useful for city maps. It’s how computers understand your social media friend network (people are the nodes and friendships the edges), possible moves in a chess game (board positions are the nodes and possible moves are the edges), or even how Google organizes facts (where “Taylor Swift” might be a node connected by a “wrote the song” edge to “Shake it Off”).

When you ask Google Maps for directions, it’s really asking: “in this huge graph of intersections and roads, what’s the best path from point A to point B?” Different search algorithms answer this question in different ways, each with its own strengths and weaknesses.

DFS (Depth First Search)

Imagine that you’re a tourist with way too much time and a deep, dark (and super quirky, fun, and maybe a little weird) desire to explore every hidden alley in the city. You might decide to explore by always taking the first turn you see and going on as far as you can until you hit a dead end, then backtrack and try another path. Here’s how DFS might work if you’re trying to find a coffee shop in a new city:

1. You start at an intersection.
2. Take the first road you see.
3. At each new intersection, immediately turn down any road you haven’t yet explored.
4. When you hit a dead end or only see streets you’ve already taken, backtrack to the last intersection and try a new street.
5. Then you backtrack to the last intersection and try a different road.

If this sounds like an inefficient way to find a coffee shop, it’s because it absolutely is! That said, DFS is perfect in other situations:

• Mapping every possible route in a maze
• Finding all the pages linked to a website
• Exploring every possible move sequence in a chess game
• Detecting cycles (loops) in a network

As is hopefully clear, DFS might send you wandering to the farthest corner of the city before checking the coffee shop on the next block over. For finding the shortest path, we need a new plan…

Breadth First Search

Alright, you’ve decided that maybe exploring a single route until it dead-ends isn’t the right approach for you. Instead, you’re more careful - you like to check everything nearby before venturing further out from home base. In our coffee shop search example, BFS would work like this:

1. Start at your current intersection
2. Check each single street directly connected to our current intersection (level 1)
3. Check every street connected to those streets (level 2)
4. Expand outward, level by level, until you find a coffee shop.

This methodical (slow) approach ensures you'll find the closest coffee shop first. Unlike DFS, which might send you all over town, BFS will never find a coffee shop that’s ten blocks away before finding one that’s two blocks away.

BFS is great when you want to find:

• your closest LinkedIn connections (1st, then 2nd, then 3rd)
• The shortest number of moves to win a puzzle
• The minimum number of steps between two people in a social network (like the Six Degrees of Kevin Bacon. -question: is this reference too old?)

However, BFS still has limitations. For instance, BFS treats all roads as though they take the same amount of time to travel down, which isn't realistic in city navigation. Some roads might be highways while others are slow residential streets. For this sort of additional complexity, we need something more sophisticated…

Uniform Cost Search (Dijkstra’s Algorithm)

Remember how, in the last section you read like 3 seconds ago, BFS assumed all streets take the same travel time? Well, in the real world we care about actual travel time, not just minimizing the number of turns we take or the number of streets we walk down. This is where Dijkstra’s Algorithm comes in.

If we consider a network of roads, we wouldn’t want to find the path with the fewest number of roads - rather we may want to find the path with the shortest total distance or expected travel time. Imagine (once again) that you are looking for that coffee shop. This time, though, you know how long each street takes to drive down. Instead of counting intersections, you keep running tally of total travel time, then at each intersection, you ask yourself: “What’s the fastest route I’ve found so far, and which next turn is the shortest.”

Here’s how it works:

1. Start at the intersection
2. Always explore the total path that’s currently looking the fastest. So, at the first intersection, we turn down the road that looks the shortest, but when we get to that road, we compare the paths from that road with the paths from the starting intersection and explore the fastest one.
3. When we find a new way to reach an intersection, compare it with any previous ways you found to get there.
4. Keep track of the fastest known route to each intersection.
5. Repeat 2-4 until you find coffee.

Use cases include:

• Navigation and route planning
• Network routing (OSPF uses Dijkstra’s Algorithm to calculate the best path through the network)
• Robotics pathfinding
• Game AI pathfinding

While UCS guarantees we'll find the optimal path, it still has a significant limitation: it explores in all directions equally, even when some directions are clearly less promising. Imagine searching for a coffee shop that you know is north of you, but UCS spends time exploring southern routes just to be thorough. This is where we need an algorithm that can combine UCS's thoroughness with some common sense about direction.

A*

A* (pronounced “A-star”) is like knowing both how long each street takes to drive down (like in UCS), plus having a compass and a rough idea of the distance to the destination. It combines UCS’s knowledge of actual road times with an educated guess about which direction the closest coffee shop is in.

Let's return to our coffee shop search one final time, now armed with both the precise path-cost awareness of UCS and the intuitive directional sense that humans naturally use.

1. We’re at an intersection.
2. We ask ourselves (like in UCS) “What is the best path to the current intersection that we’ve found so far?” and note that it’s taken about 10 minutes.
3. Next, we note that the coffee shop is about half a mile to the north.
4. Driving half a mile usually takes about 5 minutes, and there’s a road that heads north. Let’s estimate that the total trip should take about 15 minutes and take the road that goes north.

The A* algorithm combines the known cost so far with an estimated cost (called the “heuristic”), allowing the algorithm to prioritize and explore the most promising routes.

This is very useful in navigation when we know both our coordinates on a 2d plane and the coordinates to the goal on a 2d plane. In a case such as this, we can use the Euclidean Distance (think Pythagorean Theorem, or the straight-line distance between 2 points) as the heuristic. The best thing about this is that if our guess always underestimates travel time, we’re guaranteed to find the best path, but we’ll find it faster than with UCS.

Important considerations for the Heuristic:

• Admissibility: A heuristic is admissible if it never overestimates the actual cost to reach the goal.
• Consistency: A consistent heuristic satisfies the triangle inequality. So, if point B is on the way to point C from point A, our estimate for A to C shouldn’t be more than from A to B plus B to C.

It's not absolutely, one-hundred-percent

Use cases for A*

• Path-finding in games
• Map navigation (e.g. finding the optimal route considering factors like distance, traffic, road types, speed limits, etc.)
• Path-finding in robotics to plan efficient paths through a warehouse

Finally, Coffee

After much searching, we’ve found the coffee. A* is the culmination of this journey through search algorithms. We briefly touched on DFS, and threw it out because no one needs to explore THAT much just to find a cup of coffee. We then stepped through the methodical, but complete exploration of BFS and added awareness of path cost with UCS. A* combines all of the lessons we learned earlier with the simple human intuition of “head in the general direction of coffee”, creating something that’s very powerful and very efficient.

I hope you’ll consider subscribing, and join me in the next articles where we continue our exploration of knowledge graphs.