Engineering : Overview of A* algorithm

The A* algorithm is a widely used search algorithm that efficiently finds the shortest path from a starting state to a goal state in a graph or a grid. It combines elements of both Dijkstra’s algorithm and greedy best-first search. The A* algorithm employs a heuristic function to estimate the cost from the current state to the goal, along with a priority queue to guide the search process. Here is the A* algorithm:

1. Initialize an empty priority queue.
2. Create a start node with the initial state and add it to the priority queue.
3. Initialize a hash table or set to keep track of visited states.
4. Create a hash table to store the g-values (actual cost) for each state.
5. Create a hash table to store the parent of each state.
6. Initialize the g-value of the start node as 0.
7. While the priority queue is not empty:
   • Pop the node with the lowest f-value (f = g + h, where g is the cost so far, and h is the heuristic estimate) from the priority queue.
   • If the node represents the goal state, terminate and return the path.
   • Otherwise, mark the node as visited.
   • Generate the successors of the current node.
   • For each successor:
     • Calculate the tentative g-value by adding the cost from the current node to the successor.
     • If the successor has not been visited or the new g-value is lower than the previous g-value:
       • Update the g-value of the successor.
       • Calculate the f-value of the successor.
       • Set the parent of the successor to the current node.
       • If the successor is not in the priority queue, add it to the priority queue.

Proof of Admissibility: To prove that the A* algorithm is admissible, we need to show that it always finds the optimal solution, i.e., the shortest path, if one exists. The admissibility property guarantees that A* will not overestimate the cost from the current state to the goal.

Let’s assume there is a suboptimal path from the start state to the goal state. Let’s say A* explores a node on this suboptimal path, and there exists a shorter path to reach the same node. Since the heuristic function is admissible, it never overestimates the actual cost from the current state to the goal. Therefore, the estimated cost of the suboptimal path from the current node to the goal will always be greater than or equal to the actual cost.

Now, when A* explores the node on the suboptimal path, it will calculate the f-value for this node, which is the sum of the g-value (actual cost so far) and the h-value (heuristic estimate). However, since the heuristic estimate is admissible, it will always underestimate the actual remaining cost from the current node to the goal.

Since the f-value is the sum of the g-value and the heuristic estimate, which never overestimates the actual cost, the f-value for the suboptimal path will always be greater than or equal to the f-value of the optimal path. As A* prioritizes nodes with lower f-values, it will explore nodes on the optimal path before exploring nodes on any suboptimal path.

Hence, A* will always find the shortest path from the start state to the goal state if one exists, making it an admissible algorithm.