Introduction to a Search Algorithm*
In the realm of Artificial Intelligence, there exists a class of searching algorithms known as A* (A-star).
Achieving the search for the most optimum and shortest path between two nodes, a start node and a goal node, it is the most efficient search algorithm.
The A-star algorithm is the most winner of the A-uniform cost search as well as the greedy best first search winner.
A* Search is most popularly used in almost all pathfinding processes, robotics, in games, and in navigation systems.
The algorithm guarantees to give the most optimal path, as long as the heuristic is admissible.
Defining A Search Algorithm*
The A Search Algorithm* is a search algorithm classified as an informed search technique. An informed search can plan the most efficient path by using the actual cost from the start node and a heuristic (best guess) to the end goal. In this case, the most promising node is computed and cost of a node is evaluated by a function defined as the past cost plus the future estimated cost.
Cost function of A*
The evaluation function is:
f(n) = g(n) + h(n)
- g(n) → Actual cost from start node to current node
- h(n) → Heuristic (estimated cost from current node to goal)
- f(n) → Total estimated cost of the path through node n
g(n) refers to the cost incurred from the start node to the current selected node, and h(n) recalls the estimated cost (heuristic) from the current node to the end goal.
f(n) describes the total projected cost of traversing the path, inclusive of node n.
Operation of A Algorithm
Procedures in a Simplified Step
- Begin from the starting node.
- Add the node to the open list (list of nodes to explore).
- For each of the neighbor nodes, determine the value of f(n).
- From the neighbor nodes, choose the one with the lowest value of f(n).
- Move it to the closed list (already explored).
- Repeat until the goal node is reached.
- Trace back the path to get the optimal solution.
Example of A Search Algorithm
Problem Statement
| Node | g(n) | h(n) | f(n) |
|---|---|---|---|
| A | 0 | 6 | 6 |
| B | 1 | 4 | 5 |
| C | 3 | 2 | 5 |
| G | 5 | 0 | 5 |
Explanation
- From A, evaluate neighbors B and C.
- Choose node with smallest f(n).
- Continue expanding nodes based on minimum f(n).
- Finally, G is reached with the lowest total cost.
- The path found is the shortest and optimal.
Properties of A Algorithm
- Complete: Always finds a solution if one exists.
- Optimal: Finds the least-cost path.
- Admissible Heuristic: h(n) never overestimates.
- Efficient: Reduces unnecessary exploration.
Advantages of A Search Algorithm
- Guarantees optimal solution.
- Faster than uninformed search algorithms.
- Uses domain knowledge via heuristics.
- Suitable for real-time applications.
- Widely implemented and proven.
Limitations of A Search Algorithm
- High memory consumption.
- Performance depends heavily on heuristic quality.
- Not suitable for very large state spaces.
- Heuristic design can be complex.
Where A* Algorithms Can be Used
- Map Navigation and GPS Systems
- Pathfinding in Game Development
- Motion Planning in Robotics
- Routing in Networks
- Solving puzzles (15-puzzle, 8-puzzle, etc.)
A* Algorithms and Common Questions
What does A mean in A?
- A* denotes A-star, where star indicates optimal.
What makes A* better than Dijkstra’s?
A is faster because it is guided by heuristics. Dijkstra’s has no guidance so it is slower.
Is A* an informed search algorithm?
- Yes. A is an informed search algorithm because it uses heuristics.
What happens to A* when the heuristic is wrong?
- If the heuristic is an overestimate, A* can lose to be optimal.
Can A* be used in real-time applications?*
Yes. It is commonly used in applications like gaming and navigation that require real-time responses.
