Shortest path A* f(n) = g(n) + h(n)
When you use A*, it chooses the best node which is the closest to the goal right? ( using f(n) = g(n) + h(n)) ( using Manhattan distance for h(n) )
But what if there are walls between the start and goal. I can't explain it in words but I'll show a picture.
(source: uploadir.com)
If A* chooses the node that is closest to the goal, why is the path not the one encircled in red? But the one encircled in green. I really don't understand A* especially when there are impassable cells/tiles/nodes/etc. (walls). Also, you can see this picture I made like in this video http://www.youtube.com/watch?v=DINCL5cd_w0 (Path Finding Algorithms (A*, Dijkstra, Bi-Directional BFS)) at 1:20
A* also considers the length of the current path as well as the distance to the goal. All possible paths are expanded, but with a priority on those which are:
- Closest to the goal
- Shortest
The path cost, f(n) is equal to the cost at the previous step, g(n), plus a factor based on distance to the goal, h(n). So for every extra grid space the path goes through, the cost of the path increases. This will effectively create a balance between short paths, and paths which move directly to the goal.
So by the time your example paths have joined up again, it is the purple path which is shortest, and so that will be the path which is expanded first, and will eventually reach the goal first.
There is a Udacity course: Programming a Robotic Car which has a good section on the A* (and similar) algorithms.
- Mathematical explanation of Leetcode question: Container With Most Water
- How to check a point is inside an ellipsoid with orientation?
- algorithm to trace border in 2D array
- Red Black Tree Black Height Increase after Insertion
- Coin Change II : To take a value or not to
- Logic to implement to get maximum points
- Generate all strings under length N in C
- Algorithm to extract overlapping range
- Merging two sorted linked lists
- Median of two sorted-arrays algorithm for O(log(m+n))
- Calculating new longitude, latitude from old + n meters
- Calculation of Average Queue Length in a Simple Queueing Model
- what is the most efficient way to gather all points at a certain height?
- Does a recursive segment tree require more space than an iterative one?
- Tarjan Algorithms for SCC
- Is there a balanced BST with each node maintain the subtree size?
- Sort on a string that may contain a number
- Optimally counting number of nodes in a complete binary tree
- Fraction to Recurring Decimal
- Quicksort with Python
- What is the optimal algorithm for the game 2048?
- Asteroid Mining - Dynamic Programming problem
- Optimize performance for dense ranking algo
- Looking for a sort algorithm with as few as possible compare operations
- How to remove a line by its number from file without rewriting file python
- The output gives the same result
- Radix sort slower than expected compared to standard sort
- How to find minimum pairing cost? (Any Language)
- Algorithm to minimize the number of printing plates when printing sheets of stickers
- Travel from city 1 to city n, visiting at least 3 odd cities