Basic AI Concepts: A* Search Algorithm
Introduction
Artificial intelligence in its core strives to solve problems of enormous combinatorial complexity. Over the years, these problems were boiled down to search problems.
A path search problem is a computational problem where you have to find a path from point A to point B. In our case, we’ll be mapping search problems to appropriate graphs, where the nodes represent all the possible states we can end up in and the edges representing all the possible paths that we have at our disposal.
So the next logical question would be:
How do we convert a problem into a search problem?
What is A*?
Let’s say that you have to get through an enormous maze. This maze is so big that it would take hours to find the goal manually. Additionally, once you finish the maze “by foot”, you’re supposed to finish another one.
To make things significantly easier and less time consuming, we’ll boil the maze down to a search problem, and come up with a solution that can be applied to any additional maze that we may encounter – as long as it follows the same rules/structure.
Any time we want to