-
Notifications
You must be signed in to change notification settings - Fork 0
Implementation of A* algorithm on C++ with reading a map from a file
License
bayram-dev/AStar-Algorithm
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
AStar-Algorithm Implementation of A* algorithm on C++ with reading a map from a file ============ A * is an informed search algorithm, or a best-first search, meaning that it is formulated in terms of weighted graphs: starting from a specific starting node of a graph, it aims to find a path to the given goal node having the smallest cost (least distance traveled, shortest time, etc.). It does this by maintaining a tree of paths originating at the start node and extending those paths one edge at a time until its termination criterion is satisfied. At each iteration of its main loop, A * needs to determine which of its paths to extend. It does so based on the cost of the path and an estimate of the cost required to extend the path all the way to the goal. Specifically, A * selects the path that minimizes f (n) = g (n) + h (n) where n is the next node on the path, g (n) is the cost of the path from the start node to n, and h (n) is a heuristic function that estimates the cost of the cheapest path from n to the goal. A * terminates when the path it chooses to extend is a path from start to goal or if there are no paths eligible to be extended. The heuristic function is problem-specific. If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A * is guaranteed to return a least-cost path from start to goal.
About
Implementation of A* algorithm on C++ with reading a map from a file