AI Search Algorithms: A Deep Dive into the Most Popular Ones
Going through four of the most-used search algorithms in AI
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:
![Pol Marin](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="20" height="20"><rect fill-opacity="0"/></svg>){kind=small}
