The A-star (A*) algorithm is a popular pathfinding and graph traversal algorithm often used in computer science, particularly in applications like AI for games, robotics, and geographic information systems (GIS). Here's a concise overview:
Key Characteristics-
- Heuristic-based: A* uses heuristics to guide its search, aiming to improve efficiency by estimating the cost to reach the goal.
- Optimal: If the heuristic is admissible (never overestimates the true cost), A* is guaranteed to find the shortest path.
- Complete: A* will always find a path if one exists.
Algorithm Steps
- Initialization: Place the starting node on the open list (nodes to be evaluated) and initialize the closed list (nodes already evaluated) as empty.
- Main Loop: Select Node: Choose the node with the lowest f-cost (f = g + h), where g is the cost from the start node and h is the heuristic estimate to the goal. Goal Check: If the selected node is the goal, reconstruct the path from start to goal. Expand Node: Move the selected node to the closed list and examine its neighbors. Neighbor Processing: For each neighbor, calculate its g, h, and f costs. If the neighbor is already on the closed list with a lower g-cost, ignore it. If the neighbor is not on the open list or has a higher g-cost, update its costs and set its parent to the current node.
- Repeat until the goal is reached or the open list is empty (no path found). ### Pros and Cons**Pros**:- Efficient and effective for many pathfinding problems.- Can be adapted with different heuristics for various types of environments. **Cons**:- Can be memory-intensive for large maps or graphs.- Performance heavily depends on the choice of heuristic. In summary, the A* algorithm is a powerful tool for pathfinding and graph traversal, balancing optimality and performance with the help of heuristics.
3 parameters used are -
G cost - cost
