parvvaresh / astar-algorithm

The A* algorithm combines the actual cost (g), which represents the distance traveled, with a heuristic cost (h) that estimates the remaining distance to the goal. It intelligently selects the most promising nodes to explore, leading to efficient pathfinding in search spaces.

A* Algorithm

This repository contains the implementation of the A* algorithm, an informed search algorithm for finding paths in a search space.

Algorithm Description

The A* algorithm intelligently navigates in the search space by combining the actual cost (g), which represents the distance traveled so far, and the heuristic cost (h), which provides an estimate of the distance from the current node to the goal.

The algorithm follows the following steps:

1. Initialization: Initialize the Open List and Closed List.
2. Adding the initial node: Add the initial node to the Open List with a cost of 0.
3. Pathfinding: Repeat the pathfinding steps until the Open List becomes empty:
   • Select a node with the minimum total cost (f) from the Open List as the current node and remove it from the Open List.
   • Generate neighboring nodes and designate the current node as their parent.
   • For each neighboring node:
     • If the neighboring node is the goal, return the obtained path as the solution.
     • Calculate the actual cost (g) and the heuristic cost (h) for the neighboring node.
     • Calculate the total cost (f) by adding the g and h costs.
     • Update the neighboring node's cost and parent if necessary.
     • Add the neighboring node to the Open List if it is not already present.
   • Add the current node to the Closed List.
4. If the Open List becomes empty and the goal has not been reached, terminate the algorithm as there is no path to the goal.
5. Otherwise, return the path by traversing back from the goal node to the initial node using the parent pointers.

Usage

1. Clone the repository: git clone https://github.com/parvvaresh/A--ALG/blob/main/a*.py
2. Compile and run the code using your preferred compiler.
3. Provide the necessary inputs, such as the start and goal nodes, and any additional parameters required.
4. The algorithm will output the path from the start to the goal, or indicate if no path exists.

Feel free to modify the code and experiment with different heuristics or search spaces to suit your specific requirements.

License

This project is licensed under the MIT License.