Table of contents
Say you want to go to a specific place. What do you do first? For most of us, go to Google Maps and get a near-accurate distance and ETA from your location to your destination. But how do they do it? How do they always get the shortest and best path sorted out for you every single time?
Three words:
Graph-Searching-Algorithms
Graph searching algorithms are a type of algorithm used to explore graphs and find paths or other information within the graph. Graph searching algorithms are typically used to find paths between two points in a graph, or to find other information within the graph, such as connected components or cycles.
Some common examples are: A-Star, breadth-first search algorithm and depth-first search algorithm.
Let’s take a deeper dive into the A-star Algorithm in this post.
Let’s go back to google maps. Consider multiple paths from your to your destination as paths in a graph from a point S to F. You can choose any one and usually google chooses the shortest path for you. To do that, they use this algorithm.
The A* algorithm is a search algorithm that is used to find the shortest path from a starting point to a goal in a weighted graph. The algorithm uses a combination of the actual distance from the starting point to the goal and the distance travelled from the starting point to the current location to explore the graph and find the optimal path. This algorithm, no matter what, will always provide the most shortest and efficient path, provided you give it some extra data or heuristics.
Let’s discuss that. The data it does require: the traffic, the distance, road conditions etc; These are called heuristics. A heuristic is a technique or strategy that helps to solve a problem or find a solution. In the context of artificial intelligence and search algorithms, a heuristic is a function that estimates the cost of reaching the goal from a given state.
This estimate is based on the distance to the goal, the number of moves made so far, and any other information that may be relevant to the problem at hand. They’re used to guide search algorithms and help them find the best solution to a problem in a reasonable amount of time.
A* algorithm works based on heuristic methods, and this helps achieve optimality. Its heuristic function is admissible if it can effectively estimate the real distance between a node ‘n’ and the end node. It never overestimates; if it ever does, it will be denoted by ‘d’, which also denotes the accuracy of the solution.
Here are some examples of heuristics that might be used in the context of artificial intelligence and search algorithms:
In a game of chess, a heuristic might be used to evaluate the potential value of a given move by considering factors such as the relative strength of the pieces on the board, the number of possible moves for each piece, and the likelihood of capturing an opponent's piece.
In a navigation problem, a heuristic might be used to estimate the distance between two points on a map, or to predict the time it would take to travel from one point to another based on factors such as traffic conditions, road conditions, and the speed limit.
In a puzzle game, a heuristic might be used to evaluate the likelihood of solving a particular puzzle by considering factors such as the number of moves required to reach the solution, the number of different possible solutions, and the complexity of the puzzle.
In a machine learning problem, a heuristic might be used to evaluate the quality of a given model by considering factors such as the accuracy of the model on a training dataset, the complexity of the model, and the amount of computational resources required to train and use the model.
How does A-star work?
You have a graph G with starting point/node S and final goal F. Within graph G you have vertices V and these vertices having edges E. You have a heuristics function H(n), where n represents every node in the graph. For travelling from a node A to B you would have pathcost P(B). In other words, at each step, the algorithm selects the node that has the lowest cost + heuristic value and explores the neighbouring nodes. The cost of a node is the sum of the cost of the previous node and the edge weight between the previous node and the current node.
You start at S, look at the possible edges you can go to and choose edge E such that the sum of P(E)+H(E) is minimum. So you do this for each and every neighbouring node and choose the optimal path until you reach the goal node F.
Why A-Star?
A* is a popular choice for pathfinding because it is both complete and optimal, meaning that it is guaranteed to find a solution if one exists and that the solution it finds is guaranteed to be the best possible solution. A* achieves this by combining the strengths of two other search algorithms: depth-first search and breadth-first search. Depth-first search is fast but can get stuck in infinite loops, while a breadth-first search is guaranteed to find a solution but can be very slow. A* balances these two approaches by using a heuristic function to guide the search and prioritise the most promising paths. This allows A* to find a solution quickly while still ensuring that the solution is optimal.
Complexities
The time complexity of the A* algorithm varies depending on the implementation and the quality of the heuristic function used. In the worst case, when the heuristic function is not admissible (i.e. it underestimates the true cost to reach the goal), the time complexity of A* can be exponential. However, in the best case, when the heuristic function is both admissible and consistent (i.e. it never overestimates the true cost to reach the goal), the time complexity of A* is guaranteed to be no worse than O(b^d), where b is the branching factor (i.e. the average number of successor states from each state) and d is the depth of the shallowest goal state. In practice, A* is often used with a heuristic function that is admissible but not necessarily consistent, in which case the time complexity can be anywhere between O(b^d) and O(b^(d+1)).
The space complexity of the A* algorithm is the amount of memory required to store the data and variables used in the algorithm. This can vary depending on the specific implementation and the size of the input data, but in general, the A* algorithm has a space complexity of O(b^d), where b is the branching factor of the search tree (the average number of possible actions that can be taken at each step) and d is the depth of the shallowest goal (the minimum number of steps required to reach a goal state from the starting state). This means that the space complexity of A* increases exponentially with the branching factor and the depth of the shallowest goal.
Applications
The A* algorithm has a wide range of applications in fields such as artificial intelligence, robotics, and computer science. Some common examples of applications of the A* algorithm include:
Navigation and route planning: The A* algorithm is commonly used in applications that require finding the shortest or most efficient path between two points in a given space, such as in self-driving cars or in route planning applications for delivery trucks.
Video games: The A* algorithm is often used in video games to help characters navigate their environments and find the shortest path to their destination.
Natural language processing: The A* algorithm can be used in natural language processing systems to find the most likely sequence of words in a sentence or to identify the most efficient way to parse a sentence.
Robotics: The A* algorithm is commonly used in robotics to help robots navigate their environments and find the shortest path to their destination.
Graph theory: The A* algorithm is used in graph theory to find the shortest path between two nodes in a graph.