AI Search Algorithms - A Deep Dive Into The Most Popular Ones

It’s as if we don’t have enough humans on Earth, that we’ve been trying for years to create machines that behave like us. We create mathematical models or agents that act rationally, so we don’t have to rely on other human beings’ decisions.

Search algorithms were the most used for a long time, but with the rise of machine and deep learning, they’ve kind of taken a seat back. However, I think all data scientists should know about them because they are an amazing toolset that will prove useful in many situations.

They can be applied in many situations, but the most representative ones are games: tic tac toe, maze, even chess… And we’ll use these to explain the algorithms we’ll be visiting today.

We’ll be introducing four of the most famous ones and we’ll be expanding a little bit on them, using some practical and visual examples.

As always, refer to the Resources section at the bottom of this article for more info and code.

But before that, we need to introduce some definitions to understand some key terms.

Terminology

Agent: it’s the human, model, or algorithm that interacts with its environment.
State: a particular environment or set of elements that represent the problem at a given moment.
State space: the set of all possible reachable states.
Goal state: the final state, where certain conditions are met.
Action: a function or decision the agent must make in a given state to move to the next one.

We could define more terms but these are the basic-most ones, enough for today’s topic.

Representation

AI Search Algorithms are usually explained using graphs and we won’t change the status quo today.

Here’s a sample graph:

Sample graph we'll use to explain the concepts - image by the author — Sample graph we’ll use to explain the concepts – image by the author

In a graph, each node is a state. And we always have the initial state (A in this case, in green) and the goal state (which I’ve decided it’ll be E, in red). It’s through the actions we defined in the previous section that our agent can move from one state to the next and repeat that successively until we reach the goal state.

All the nodes, from A to F, define the state space.

What differs then is the algorithm we use to get from A to E. And that’s what we’ll start exploring next.

Depth First Search

The Depth First Search (DFS)[1] algorithm is one of the uninformed search algorithms, in which the only information we have is the one provided in the problem definition.

In other words, in an uninformed search algorithm, we know where we want to go – we want to reach the goal state E – but we don’t know how close or far we are from it.

The Depth First Search in particular keeps on moving forward until it reaches a leaf node. At each bifurcation it might encounter, it randomly selects one direction and keeps on moving forward.

If the leaf node we reach is the goal state, then we’re done. But if it’s not, then it goes up again to the last bifurcation and keeps on moving forward. This process is repeated recursively until we get to the goal state.

Let’s see it now:

The first action applied - image by the author — The first action applied – image by the author

From the initial state A, we can only move towards B. So, after the action takes place, our agent will be in that second state. Then comes the bifurcation, and we need to choose. As DFS is an uninformed type of algorithm, it chooses randomly because we know nothing about which one is best. Let’s suppose it chose F instead of C.

DFS second decision - image by the author — DFS second decision – image by the author

As the algorithm is trained to go in-depth until it explores other branches, it will have to again decide between going to D and E. If it chose E, we’d be done. But we’re unlucky this time and it randomly goes to D.

Possible DFS implementation - image by the author — Possible DFS implementation – image by the author

At this point, the algorithm has visited A, B, F, and D. Being at D, there’s only one direction possible and it takes us to E. There, we’re done.

This algorithm is simple yet effective in multiple cases. It follows the last-in first-out strategy and that’s why it could be implemented using a stack.

In our example, the optimal solution gets us from A to E in 3 steps, but it’s not guaranteed. In fact, the example we followed took us 4 actions.

Breadth-First Search

Breadth First Search or BFS[2] is another type of uninformed search algorithm and we could say it’s the opposite of DFS: instead of going deep branch by branch, it doesn’t reach the next depth level until all nodes from the previous level have been explored.

While we used a stack in DFS, here we use a queue: it follows the first-in-first-out strategy.

Again, let’s traverse the graph to see it visually. It goes from A to B as we saw previously, we have no alternative here. Then we arrive at the bifurcation at B and, as it’s an uninformed algorithm, we simply choose randomly between C and F. We’ll basically be exploring both, it’s just a matter of which one we explore first.

Second step of BFS: we've explored A, B, C and F— image by the author — Second step of BFS: we’ve explored A, B, C and F— image by the author

We’ve explored level 1 (node A), level 2 (node B), and level 3 (nodes C and F). We now move on to level 4, where we explore the final leaves – E and D.

Again, whether we explore E before D or vice versa is a completely arbitrary decision:

If C went first in the B bifurcation, then we would reach E right after that.
But if F went first, then a random decision would be made as to whether we explore D or E first.

BFS has some potential, as well as DFS, but both have their flaws. One will be best in some cases but will result inefficient in others. These are simple algorithms and, while still useful, we deserve more.

Greedy Best-First Search

This is the first informed search algorithm we’ll be visiting today. In this kind of algorithm, we do have information about the goal state, and our duty is to use that information to choose wisely before each step. We define the term heuristic as this piece of information that tells us how close or far we are from the goal.

The Greedy Best-First Search (GBFS)[3] algorithm is simple: we simply move toward the nodes that take us closer to the goal node, and the heuristic h(x) is the one measuring the closeness.

In the typical maze game, the closeness could be expressed by the number of pixels/tiles away we are from it, both in the vertical and horizontal direction.

Let’s suppose an example, in which we want to go from A to B, and we’ve already played up until we reach a tricky decision point. If we were using BFS or DFS, the selection would have been random. But we’re using informed algorithms now.

Check the following maze, in which there’s a number in each tile defining how many tiles away we are from the goal. In other words, the heuristic defines the number of steps we need to go from the actual tile to the goal, supposing a maze without walls in which we can only move horizontally or vertically:

Sample maze with closeness heuristic values - image by the author — Sample maze with closeness heuristic values – image by the author

If we used GBFS, the closeness heuristic we’re using suggests that we go up because if we go up the number of steps needed to reach B is decreased from 2 to 1, but if we go down it increases from 2 to 3. In other words, if we go up we get closer to the goal and we move further if we decide to go down.

This isn’t perfect, because we’re only taking into account how close we are to B, but not the actual walls we have between us and the goal state. That’s something we just cannot control with GBFS.

For consistency purposes, let me go back to the graph representation we’ve been using on and on, only that this time it will be a whole new graph. We still want to get from A to E but, as we already know, we now have information in each node about how close we are to the end state.

We’re going to use the letter h to provide an imaginary value to the heuristic.

Sample graph with heuristics - image by the author — Sample graph with heuristics – image by the author

The proposed example works the same way the maze does: every action required to move from state to state gets us either one unit closer to the goal, one unit further, or makes us remain the same. The most optimal path is clear: From A to C to E. It’s a matter of moving toward the node with a smaller h(x) if there’s a bifurcation.

But it could have been different. Imagine that the heuristic didn’t differ by one unit at max from node to node, but it depended on several environmental factors. If it was that way, the optimal path would not have changed in our example, because it’s a really simple one, but it would be a totally different story in a more complex graph.

Greedy Best-First Search is a powerful algorithm but it isn’t perfect. While it considers how close we are to the goal, it doesn’t take into account the actual costs of having gone that far.

Believe it or not, the cost of getting to a state or node is as important as the cost of the greedy search.

Get ready for the next algorithm.

A* Search

The *A search algorithm**[4] is a variation of the GBFS algorithm but now, as stated, we take into account the costs of getting to each node. In other words, traversing via different edges might not have the same cost.

We’ll define:

Forward cost – h(x). It’s the same heuristic used in GBFS: the distance between the current state and the goal state.
Backward cost – g(x). It’s the cost of going from the initial state to the current state. It’s a cumulative cost, in the sense that it sums all the previous costs.

The goal of A* Search then is to find a path where the sum of both costs is the least. In mathematical terms, the overall cost of the node x is given by f(x) = g(x) + h(x).

To illustrate this, I’ll be using the initial graph we’ve already used. We still want to get from A to E and the costs are shown now:

New graph to perform the A* Search in - image by the author — New graph to perform the A* Search in – image by the author

Take a moment to think about which could be the optimal path here. The numbers around the nodes are the forward costs and the numbers close to the lines are the backward costs.

Let’s try to decipher it now, going step by step:

We have no other option than going from A to B. The cost of reaching B is f(B) = 2 + 2 = 4.
From B, we can either go to C or F. Here we pause and check which one’s lower. We see that f(C) = 7 + 1 = 8 and f(F) = 3+1 = 4. Then, we determine F to be the best solution.
From F, we again have two options: we can go to E and reach the goal state or go towards D. Most would choose E because we wouldn’t need to do extra steps, but we’re smart and we’ll let the math do the work: f(D) = 6+1 = 7 and f(E) = 13+0 = 13. D is therefore a better option than E. However, remember that we still have an open path at B, where we could go towards C. But the cost of going from B to C is 8, still above 7, so we’ll still keep on moving in the F->D direction.
From D we can only go to E (or move backward to F, which doesn’t make sense). The cost is f(E) = 7+0 = 7. As it is still lower than f(C), we’re done here.

So the optimal path is finally A->B->F->D->E.

Optimal path using A* Search— image by the author

Conclusion

Put this knowledge into practice.

We haven’t used any code here because I believe trying to build it on your own is the best way to understand how these algorithms work. However, in the resources section below you’ll have a link to a GitHub repo[5] I’ve created where I’ve coded three of these four algorithms we’ve seen today.

My implementations are simple and not the most efficient. My goal in providing the code was to let you play with it and improve it your way by making an iterative function recursive, by creating more complex classes…

Go ahead and try to implement your own maze implementation using DFS, BFS, GBFS, or A* Search. Don’t just copy my code, use it as a template (you might find some surprises there).

Be creative and resourceful, and don’t stop here. Try other algorithms we haven’t covered here like minimax or uniform cost search. Google is your friend.

Today I’ve covered the basics of these four algorithms showing how they work with visual examples and following a set of steps. I used simple examples but the process is the same on larger graphs.

The key here is, as data scientists, to understand them, know how to use them, and, most importantly, identify situations in which they could be useful for us.

Search algorithms are just a part of AI and they’re still key even though they’ve been around for a while.

Go ahead and try them out!

Thanks for reading the post! 

I really hope you enjoyed it and found it insightful.

Follow me and subscribe to my mail list for more 
content like this one, it helps a lot!

@polmarin

If you’d like to support me further, consider subscribing to Medium’s Membership through the link you find below: it won’t cost you any extra penny but will help me through this process.