A simple and easy-to-understand guide for newcomers to software engineering.
This is part 2 of my Search Algorithms summary with an easy-to-understand approach.
You can find part 1 here.
So far, we have talked about the main concepts necessary to understand the examples and also about Breadth-First Search and Depth-First Search Algorithms. We used a simple example of a guard inside a prison going after a fugitive. We also connected Breadth-First and Depth-First Searches to the Data Structures Stack and Queue. In the end, we categorized these two algorithms as Uninformed Search algorithms.
Today, we are going to continue our prison example and learn about Informed Search Algorithms, the ones that use problem-specific knowledge to find solutions more efficiently.
Don’t feel intimidated by all I wrote above; you can always return to part 1 of this topic and read all the explanations and examples. You can do it!
Informed Search Algorithms
An algorithm is a sequence of steps to solve a specific problem. In the prison example, our algorithms didn’t use any information regarding the environment (the prison itself). They followed their pattern and, on decision points to decide which path to follow (action), it was a random decision.
Informed search algorithms make choices about the path based on a specific strategy that tries to predict the shorter way to reach the task goal (solution).
Greedy Best-First Search
In our example, the guard’s goal is to reach the fugitive who is hiding in the prison. The guard is in point A, and the man is hiding in point B. There are many paths in the prison, and not all take the guard to the solution (point B). Which path should the guard take?
Instead of following paths randomly based on trial and error, Greedy Best First uses a function called “heuristic” to estimate, in every decision point (right or left path?), how close we are to the hiding man (our task solution).
In this image above, we can see our initial state, the environment (the representation of the prison), the paths (the darker areas), the goal (point B), the guard (point A), and two points of decision (actions), C and D.
In C and D, decision points, we want to estimate how far we are from B, and this doesn’t consider the walls (blue squares); it is a generic estimation. All we can get to know is that D is six steps from point B, and D is closer to point C. This distance is called the Manhattan distance.
The function applied to our environment (prison and the paths) shows how far the guard is from the goal with every step he takes. The numbers are the Manhattan distance added to every node in the maze.
From 16 to 12, he follows the only path available. On number 12, he needs to decide: left or right? At this point, the Greedy Best Search is advantageous compared to Depth-First Search and Breadth-First Search because it shows that if he turns right, he will be 11 steps from the goal, while if he turns left, he will be 13 steps from the goal.
The name greedy comes because the decision is made locally on that exact position. It doesn’t worry if the current best result will bring the overall optimal result or not.
Following the rules of this algorithm, which is to take the path with the smallest distance to the goal, he will turn right.
This implies that all the upper-left-fork paths will not be explored, and the cost to reach our goal will be decreased (the guard will run through fewer corridors), making the algorithms more optimal compared to the two aforementioned (Depth-First and Breadth-First Searches), which are uninformed.
The function applied to the path does not guarantee the distance the guard will take to reach the goal; it is an estimate.
Notice that, in the last point of decision in the maze, the agent is in a node with a Manhattan distance of 5. The function indicates that if he goes up, he will be closer (4) to the prisoner, while if he goes down, he will be at position 6 (in theory, he would be farther away than following the path above). But following the upper path will lead to a wall, and he will have to come back and follow the other path that goes down, right, and up to reach point B.
This clearly demonstrates that the information provided by the Manhattan distance, acquired through the Heuristic function, is really not exact. Even so, the cost of this algorithm is usually better, I repeat, than the other two options we explored before.
Great, we are evolving toward more complex algorithms and more optimal solutions!
The A* Search Algorithms (read: A Star)
It is a search algorithm to find the shortest path between an initial and a final point. It looks perfect for our case!
The logic behind it evolves from the Greedy Algorithm. It also calculates the estimated cost to reach the goal with a Heuristic function that provides the Manhattan distance. On top of that, it calculates the cost to reach the goal, how many steps the guard will take to achieve it. Both are summed up to help the guard make the best decision on every decision point (action).
On the image above, we can see a maze with the Manhattan distance added and, on the yellow bath, the distance is also added to the cost to reach the node, the number of steps. From A, the guard gives 1 step to the next node and the estimated distance is 16 nodes to reach the hidden man. The same logic applies to all the nodes, or squares, in the image.
Examining the image, pay special attention to the number six, the next potential node. It’s calculated as 15 completed steps plus an estimated 6 steps to reach the goal, totaling 21 steps. Going back to the initial decision point, the number 13, which initially appeared less favorable, would be computed as 6 steps taken plus an estimated 13 steps to the goal with the A* approach, totaling 19 steps. Therefore, using the A* method, we can infer that taking a left turn at the initial decision point is a much better choice.
A* algorithm considers the steps given and the distance to the goal, increasing our capacity to analyze the cost of reaching the solution. Hence, we have a much more optimal receipt for the hidden man position on point B. One downside is that we are using more memory to calculate and keep the info regarding every node.
We are evolving on a good pace to understand the basics of the most used search algorithms.
In the next and last part, we will explore the MinMax Algorithm and study a basic game implemented with Python using Search Artificial intelligence algorithms.
See you there!
The Maze images and structure follow the excellent CS50 Artificial Intelligence with Python course, with more content and examples from other sources, where beneficial.
About me: I am a Software Engineering student in Berlin/Germany. I have experience in web development, and I am deep-diving into AI/Data/ML and the Math behind it. I am also a Lawyer in Brazil, and I have worked in the area for more than 15 years. My goal with my articles is to create a summary of what I am studying and to make the content more accessible and easy to understand for me and for whoever might benefit from it. The texts might evolve with time with new content added and corrections might be made. Thanks!