A* Search Algorithm

Question

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.

Answer 1

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

Answer 2

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...