Perform the A* algorithm on the graph below. You are travelling from S to G. Each node is labelled by a capital letter and the value of a heuristic function. Each edge is labelled by the cost to traverse that edge. If two nodes have the same f value, traverse the node first whose h value is smaller than that of the other node.

1) Show each step of running the A* algorithm with g, h, and f values. [4 marks]

2) Find the shortest path from node S to node G (show the shortest path on the graph).[1 mar

A, h=5 E, h=2 C, h=4.5 4 4 3 2 S, h=8 2 1 GE 4 3 B, h=5 D, h=4 F, h=1 1 2. 3 4 5 6 7 8 9 10 11 12 13 14 let the openlist equal empty list of nodes let the closedlist equal empty list of nodes put the startNode on the openlist (leave it's f at zero) while the openlist is not empty let the currentNode equal the node with the least f value remove the currentNode from the openlist add the currentNode to the closedList if currentNode is the goal You've found the end! let the children of the currentNode equal the adjacent nodes for each child in the children if child is in the closedlist continue to beginning of for loop child.g = currentNode.g + distance between child and current child.h = distance from child to end child. f = child.g + child.h if child.position is in the openlist's nodes positions if the child.g is higher than the openlist node's g continue to beginning of for loop add the child to the openlist 15 16 17 18 19 20