How does this specific version of A-star algorithm work?

Question

I was having a course in AI when I came across this problem in A* algorithm:

The heuristics are as follows:

          N : h(N)

---

         'A': 9,
         'B': 10,
         'C': 13,
         'D': 9,
         'E': 17,
         'F': 4,
         'G': 0,
         'H': 9,
         'I': 11,
         'J': 2,
         'K': 5,
         'L': 14,
         'M': 4,
         'N': 6,
         'O': 11,
         'P': 4,
         'Q': 4,
         'R': 6,
         'S': 12

The start node is 'S' and goal node is 'G'. The internode costs are specified in the image in red. The official answer is the path 'SCDFJG' with cost = 26. The order of node inspection is given as : S,I,C,D,F,H,K,J.

As per my understanding, at each step we choose and expand a node according to the value of the heuristic f = g + h, where g is the cost of movement from node 'S' to the given node along the path to reach there. For the cases of equal g value, the tie breaker is supposed to be alphabetical order of nodes in the original problem.

FAILED Attempts

S -> {C,H,I,K}
argmin(f{SC,SH,SI,SK}) = SI
I -> {N,O,L,E}
argmin(f{SIN,SIO,SIL,SIE}) = SIN
.
.
.
path = SINRQG
cost = 36

Following the above procedure, I tried for weighted A* (weight W = 3) in which f = g + 3*h, and I got:

path = SKHFJG
cost = 48

In this case the official answer is the path SINRQG! Now, in the original problem (w = 1), when I apply Dijkstra's algorithm with f as the deciding heuristic in place of g only, the cost is 26 and the order of inspection is S,I,N,K,H,C,D,F,J,G. So, how do I use A* manually? After some work I could get the code version of the solution from the course:

from collections import deque

class Graph:
    

    def __init__(self, adjacency_list):
        self.adjacency_list = adjacency_list

    def get_neighbors(self, v):
        return self.adjacency_list[v]

    # heuristic function with equal values for all nodes, H[n]
.....
def a_star_algorithm(self, start_node, stop_node):
        open_list = set([start_node])
        closed_list = set([])
        g = {}
        g[start_node] = 0
        parents = {}
        parents[start_node] = start_node
        W = 3 #weight

        while len(open_list) > 0:
            n = None

            # Printing open and closed lists
            print(f"Open List: {open_list}")
            print(f"Closed List: {closed_list}")

            for v in open_list:
                if n is None or (g[v] + W*self.h(v)[0], v) < (g[n] + W*self.h(n)[0], n):
                    n = v;

            if n is None:
                print('Path does not exist!')
                return None

            if n == stop_node:
                reconst_path = []
                while parents[n] != n:
                    reconst_path.append(n)
                    n = parents[n]
                reconst_path.append(start_node)
                reconst_path.reverse()
                print('Path found:', reconst_path)
                return reconst_path

            for (m, weight) in self.get_neighbors(n):
                if m not in open_list and m not in closed_list:
                    open_list.add(m)
                    parents[m] = n
                    g[m] = g[n] + weight
                    print(f"Inspecting node {m}")
                    print(g[m]+W*self.h(m)[0])

                else:
                    if g[m] > g[n] + weight:
                        g[m] = g[n] + weight
                        parents[m] = n
                        if m in closed_list:
                            closed_list.remove(m)
                            open_list.add(m)

            open_list.remove(n)
            closed_list.add(n)

        print('Path does not exist!')
        return None

# Test your modified A* algorithm
adjacency_list = {
.......

However, I find this too clumsy to understand and implement by hand, though it gives the correct answer.

Answer 1

The A* star algorithm never discards paths it has expanded. Any of those paths -- short or long -- will still compete with newer paths by their f-values.

You have apparently not done this in your written analysis:

S -> {C,H,I,K}
argmin(f{SC,SH,SI,SK}) = SI
I -> {N,O,L,E}
argmin(f{SIN,SIO,SIL,SIE}) = SIN
.
.
.
path = SINRQG
cost = 36

Yes, S expands to C,H,I,K, with these values for g, h and f:

node	g	h	f=g+h
SI	6	11	17
SC	6	13	19
SK	16	5	21
SH	16	9	25

And you are right that now node I expands to SIN,SIO,SIL,SIE, but you shouldn't discard SC,SK and SH: they still stay in the "competition"! So we get this:

node	g	h	f=g+h
SC	6	13	19
SK	16	5	21
SIN	16	6	22
SH	16	9	25
SIO	30	11	41
SIL	30	14	44
SIE	30	17	47

The next node to expand is thus not N (via SIN), but C (via SC), which is in line with the expected node inspection order (S,I,C,...).

If you continue like this, never discarding paths, except the one that is replaced by its extensions, then you'll get the expected results.