I have the following game board below, and we're using A* search to find the optimal path from the agent to the key. There are 8 directions. Up, down, left, right have a cost of 1, and diagonal directions have cost 3. We will be using a priority queue with function $f(v) = g(v) + h(v)$ where $g(v)$ is the backwards cost from the goal through the given edges and up to the vertex v while $h(v)$ is the optimal least cost distance from v to the goal node.
So I calculated the f(s) for the different states, assuming no prior edges specified:
And then I started the search and these are the steps I took: expand C: (CD,3), (CE,3), (CF,3), (CA,5), (CB,5)
expand CD: (CDF,3),(CE,3), (CF,3), (CA,5), (CB,5), (CDB,5)
expand CDF: (CDFH,3), (CE,3), (CF,3), (CA,5), (CB,5), (CDB,5), (CDFG,6)
expand CDFH: (CE,3), (CF,3), (CA,5), (CB,5), (CDB,5), (CDFG,6)
So I only expanded, C,D,F,H. I got the correct answer for the optimal path, but not the correct answer for nodes expanded, which is supposed to be C, D, E, F, G, H. What am I doing wrong?