Menu
I would like to have something clarified with regards to the following A* Search example:
The sections highlighted with the red ellipses are the areas that I do not understand; it appears that {S,B} f=2+6=8 has been taken/moved/copied from Expand S (above) and used in Expand A. It also appears that {S,A,X} f=(1+4)+5=10 has been taken/moved/copied from Expand A and used in Expand B.
Could somebody kindly explain why this happens? I am able to read the graph perfectly well and do not have any trouble interpreting it - it is merely the fact that I do not know why the aforementioned paths/routes have been duplicated elsewhere.
Thank you.
615
A search algorithm is the step-by-step procedure used to locate specific data among a collection of data. It is considered a fundamental procedure in computing. In computer science, when searching for data, the difference between a fast application and a slower one often lies in the use of the proper search algorithm.
The A* Algorithm Like Dijkstra, A* works by making a lowest-cost path tree from the start node to the target node. What makes A* different and better for many searches is that for each node, A* uses a function f ( n ) f(n) f(n) that gives an estimate of the total cost of a path using that node.
What A* Search Algorithm does is that at each step it picks the node according to a value-'f' which is a parameter equal to the sum of two other parameters – 'g' and 'h'. At each step it picks the node/cell having the lowest 'f', and process that node/cell.
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 travelled, shortest time, etc.).
This is taking the current best item, removing it, and replacing it with the expansion (inserting the new items into appropriate positions in the list). Think of it like this:
Expand S:
{S,A} f = 1+5 = 6{S,B} f = 2+6 = 8Expand A:
{S,A} f = 1+5 = 6{S,B} f = 2+6 = 8{S,A,X} f = (1+4)+5 = 10{S,A,Y} f = (1+7)+8 = 16Expand B:
{S,B} f = 2+6 = 8{S,A,X} f = (1+4)+5 = 10{S,B,C} f = (2+7)+4 = 13{S,A,Y} f = (1+7)+8 = 16{S,B,D} f = (2+1)+15 = 18
101
The paths are not duplicated, they simply remain as paths that the algorithm hasn't explored yet. A* works by maintaining an open set, it is the collection of nodes the algorithm knows already how to reach (and by what cost), but it hasn't tried expanding them yet.
At each iteration the algorithm chooses a node to expand from the open set (the one with the lowest f function - the f function is the sum of the cost the algorithm already knows it takes to get to the node (g) and the the algorithm's estimate of how much it will cost to get from the node to the goal (h, the heuristic).
http://en.wikipedia.org/wiki/A*_search_algorithm
look at the pseudo-code there, as you can see the open set is used. So bottom line - it's not that the algorithm works by duplicating\copying\moving paths or nodes from one iteration to another - it simply does its work on the same collection of nodes (of course nodes do get added and removed from the collection).
Hope this helps...
36
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
