A* Search Algorithm in C, C++, Java, Python

Kumar-laxmi commented 1 year ago

Feature = A* Search Algorithm

The A* (A-star) search algorithm addresses the problem of finding the shortest path from a starting node to a goal node in a graph or a weighted grid. It considers both the cost to reach a particular node (the "g-score") and an estimate of the remaining cost to reach the goal node (the "h-score"). The algorithm aims to find the optimal path that minimizes the total cost, which is the sum of the g-score and h-score, from the start node to the goal node.

The A* search algorithm combines the advantages of Dijkstra's algorithm (uniform-cost search) and Greedy Best-First Search.

Approach:

Initialize an open set of nodes to be explored, starting with the initial node.
Assign a g-score value of 0 to the start node and an initial h-score estimate to the goal node (typically calculated using heuristics like Euclidean distance or Manhattan distance).
While the open set is not empty:
- Select the node with the lowest f-score (g-score + h-score) from the open set. This node becomes the current node.
- If the current node is the goal node, the algorithm terminates, and the optimal path is reconstructed by backtracking through the parent pointers.
- Generate the neighbors of the current node and calculate their g-scores and h-scores.
- For each neighbor: If it has not been visited or its new g-score is lower than the previously recorded g-score, update its g-score, h-score, and parent pointer. Add the neighbor to the open set if it is not already present.
If the open set becomes empty before reaching the goal node, then there is no path from the start to the goal, and the algorithm terminates.

Additional context