A* Search Algorithm
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.
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 = 8
Expand 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 = 16
Expand 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